Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Properties of Relation

Date: 05/28/2003 at 16:07:37
From: Idiot
Subject: Properties of Relation

What are reflexive, symmetric, anti-symmetric, and transitive 
relations?

I do have some understanding about the definition of these relations.
But I have this feeling I need to clarify few things.

Reflexive Relation

From the definition we know a relation is reflexive if every element 
of it is related with itself. For example, R={(1,1),(2,2), (3,3)}. But
if we have a relation like R={} (the null set), how are we going to
define reflexivity?

Antisymmetric Relation

We know if in a relation a pair (1,2) is present and a pair (2,1) is 
never present, then we call it antisymmetric. If, say, we have a
relation such as R={(1,1),(2,2)}, is it antisymmetric? Is
R={(1,1),(1,2)} antisymmetric?

Symmetric Relation

From the definition, we know that if (1,2) and (2,1) are both present,
then it is symmetric. So if we have something like R={(1,1)}, is that
symmetric? And is there any relation which is symmetric and
antisymmetric both?

Transitive Relation

Again the definition says if (a,b) and (b,c) is present then (a,c) 
has to be present to make the relation transitive. Let's say we have a
relation R={(1,2)}. The defintion says if (a,b) and (b,c) are both
present, but here we can only safely say (a,b) is present. So is R
still a transitive relation?

I hope I didn't take too much of your time. Thank you in advance.



Date: 05/29/2003 at 06:39:26
From: Doctor Jacques
Subject: Re: Properties of Relation

Hi,

I think we should first clarify a few issues about mathematical 
logic, and, in particular, the meaning of statements related to the 
empty set.

When we say "If P then Q", or "P -> Q" this simply means that P is 
false or Q is true (or both). This has some consequences that may 
appear surprising (until you get used to them). For example:

  "If 6 is prime, then 11 is negative"

is a true statement, because the "If" part is false.

A statement like P -> Q does not mean that there is any "logical 
relationship" between P and Q.

Consider now what happens when we make statements about elements of a 
set. Let us say we have a statement:

 "For all x in S, P(x)"

where P(x) is some statement about x. This is equivalent to saying:

  x is in S -> P(x)

What does this mean if S happens to be the empty set? In that case, 
the left part ("x is in S") is false, and therefore the complete 
statement is true, (whatever P(x) may mean). We can say that any 
property is true when applied to the elements of the empty set. For 
example, in a universe without birds, both statements:

 "All birds are green"
 "All birds are red"

are true, and this does not create a contradiction.

Another way to see this is the following example. Assume that you have 
to inspect bags that may contain red and blue balls, and you want a 
procedure to decide whether or not all the balls in a given bag are 
red. This means that, given a bag B, you want to decide whether or not 
it is true that:

  "For all x in B, x is red"

The procedure would be executed as follows:

(1) if there are no more balls in the bag, exit and return TRUE (i.e.
    declare that the statement is true)

(2) pick a ball from the bag

(3) if the ball is not red, exit and return FALSE

(4) otherwise, go back to step (1)

Note that you must execute step (1) at the beginning, because step (2) 
is illegal if there are no more balls.

Now, you can see that, if a particular bag is empty, the procedure 
will immediately terminate at step (1), and declare the statement 
true. This shows that this interpretation is consistent.

On the other hand (we will not use that here), a statement like:

  "There exists x in S such that P(x)"

means

  "(There exists x in S) AND (P(x))"

and, if S happens to be the empty set, this statement is false 
(whatever P(x) may mean), because the first part of the AND statement 
is false.

To sumarize:

* "If P then Q", or "P -> Q" means "P is false or Q is true" (and
  nothing else).

* The statement "For all x in S, P(x)" is always true when S is the
  empty set.

* The statement "There exists x in S such that P(x)" is always false
  if S is the empty set.

The latter two statements do not depend on the definition of P(x).

Let us now go back to your questions.

First, note that a relation may be pictured as a table. For example, 
in a set A = {a,b,c}, we can describe a particular relation as:

   | a | b | c |
 --+---+---+---+
 a | * |   | * |
 --+---+---+---+
 b | * |   |   |
 --+---+---+---+
 c |   |   | * |
 --+---+---+---+

This is the relation {(a,a), (a,c), (b,a), (c,c)}

Reflexivity
-----------

A relation R on a set A is reflexive if:

  "For all x in A, (x,x) belongs to R"

which is equivalent to:

  "x is in A -> (x,x) is in R"

or

  "(x is not in A) OR ((x,x) is in R)"

By what we said above, we can immediately see that, if A is the empty 
set, _any_ relation is reflexive. (There is nothing to check, since 
the bag is empty).

If now we have the empty relation R = {}:

* If A is empty, the relation is reflexive, as said before.

* If A is not empty, we can find an element x in A, and (x,x) is not
  in R. This means that "x is in A" is true, and "(x,x) is in R" is
  false, and the relation is not relfexive in this case.

To summarize, the empty relation is reflexive if and only if the 
related set is empty.

In the table representation, a relation is reflexive if it 
contains "*" on all the diagonal squares.

Antisymmetry
------------

A relation R on a set A is antisymmetric if:

  "For all x,y in A, ((x <> y) AND ((x,y) in R)) -> ((y,x) not in R)"

R is not antisymmetric if we can find x and y in A, with x <> y, such 
that (x,y) and (y,x) are both in R.

As the property is of the form:

  "For all x,y in A, (...)"

any relation is antisymmetric if A is the empty set.

The empty relation {} is antisymmetric, because "(x,y) in R" is 
always false.

Furthermore, if A contains only one element, the proposition "x <> y" 
is always false, and the relation is also always antisymmetric.

In the example:

  {(1,1), (2,2)}

the statement "x <> y AND (x,y in R)" is always false, so the 
relation is antisymmetric.

In the example:

 R = {(1,1), (1,2)}

the statement "x <> y AND (x,y in R)" is true only for (x,y) = (1,2), 
but, in that case, the statement "(y,x) not in R" is also true, so 
the relation is also antisymmetric.

In the table representation, a relation is antisymmetric if it does 
not contain two "*" in symmetrical off-diagonal squares.

Symmetry
--------

A relation R on a set A is symmetric if:

  "For all x,y in A, ((x,y) in R) -> ((y,x) in R)"

In the table representation, this means that the table is symmetrical 
with respect to the main diagonal.

Note that we do not use the condition x <> y here, since, if x = y, 
the condition will always be satisfied.

As before, as the statement is of the form "For all x,y in A, (...)", 
any relation on the empty set is symmetric.

The empty relation {} on any set is symmetric, because "(x,y) in R" 
is always false.

The relation {(1,1), (1,2)} is not symmetric, because it contains 
(1,2) but not (2,1).

The relation {(1,1)} is symmetric, since (x,y) in R is only true for 
x = y = 1, and, in that case, we also have (y,x) in R (it's the same 
pair). Note that this relation is also antisymmetric, because the 
proposition

  x <> y AND (x,y) in R

is always false, which means that

 ((x <> y) AND ((x,y) in R)) -> ((y,x) not in R)

is always true.

This shows that a relation can be symmetric and antisymmetric at the 
same time - this will be the case if there are no "*" in off-diagonal 
positions. This is independent of the fact that the relation is or is 
not reflexive.

Transitivity
------------

A relation R on a set A is transitive if:

  "For all x,y,z in A, ((x,y) in R) AND ((y,z) in R)) -> (x,z) in R"

Note that x,y,z need not be different.

Once again, any relation on the empty set is transitive, as is the 
empty relation on any set, for the same reasons as above.

In the relation {(1,2)}, we cannot find x,y,z such that R contains 
(x,y) and (y,z) but not (x,z), so the relation is transitive.

Consider now the relation:

  R = {(1,2),(2,1)}

In this case, if we let x = 1, y = 2, z = 1, we see that

  (x,y) = (1,2) is in R
  (y,z) = (2,1) is in R
  (x,z) = (1,1) is not in R

and this shows that the relation is not transitive.

General remarks
---------------

It is often easier to approach those questions using the opposite 
properties. It is like in a trial - you are presumed innocent unless 
proven guilty. In this case, you can assume that a relation is 
reflexive (or symmetric, ...) unless you can prove that it is not. If 
you cannot prove that it is not reflexive, then it is reflexive 
(well, this does not mean "if you are unable to find a proof," 
but "if a counterexample does not exist").

To show that a relation is:

* not reflexive, you must find an element x of A such that (x,x) is
  not in R

* not antisymmetric, you must find distinct elements x and y of A
  such that both (x,y) and (y,x) are in R

* not symmetric, you must find elements x and y of A such that R
  contains (x,y) but not (y,x)

* not transitive, you must find elements x,y,z of A (not necessarily
  distinct) such that R contains (x,y) and (y,z) but not (x,z)

In any case, if no such elements exist, the relation has the 
corresponding property.

Does this help?  Write back if you'd like to talk about this 
some more, or if you have any other questions.

- Doctor Jacques, The Math Forum
  http://mathforum.org/dr.math/ 
Associated Topics:
College Logic
High School Logic
High School Sets

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/