Symmetric, Transitive, and Reflexive Relations

Date: 11/10/98 at 11:30:27
From: Mike
Subject: Discrete math

Suppose R is a symmetric and transitive relation on A. Suppose that 
for each a in A there is b in A such that (a,b) and is in R.
Show: R is an equivalence relation.

Suppose R is a reflexive and transitive relation on A. Define a new                  
relation, T = { (a,b) | both (a,b) and (b,a) are in R}.
Show: T is an equivalance relation. 

Suppose R is a reflexive relation on A. Show: R is an equivalence 
relation <==> [ (a,b) and (a,c) in R ==> (b,c) in R]
                                                     
Let Z = {positive integers}.  Define A = ZxZ. Define a relation, R,
on A by: R = { ((a,b), (c,d)) | a*d = b*c}.
Prove that R is an equivalence relation on A.

Date: 11/16/98 at 19:39:59
From: Doctor Teeple
Subject: Re: Discrete math

Hi Mike,

Before we get to these proofs, let's review the ideas of relations and 
equivalence relations. That way, we'll have definitions to refer to 
when we try the proofs. 

Suppose we have a set A and a relation R on A. Then R is just a set of 
ordered pairs that are made up from the elements of A. 

For example, 
    if A = {1, 2, 3}, we can define a relation 
       R = {(1,2), (2,3), (3,1), (3,2)}. 

Note that this is only one relation we could define on A. There are 
plenty of other ones.

To show that a relation R is an equivalence relation, we need to prove 
that it has three properties. We need to show that it is reflexive, 
symmetric, and transitive. It helps to have the exact definitions 
written down, so go ahead and do that now.

Here's what I have:

   reflexive:  For every element a in A, (a,a) is in R.
   symmetric:  If an ordered pair (a,b) in R, (b,a) is in R.
   transitive: If ordered pairs (a,b) and (b,c) in R, (a,c) in is R.

All three of these must hold to have an equivalence relation. We can 
check the relation we defined above to see whether it is an equivalence 
relation. 

First check reflexivity. Recall R = {(1,2), (2,3), (3,1), (3,2)}. 
For R to be reflexive it must contain (1,1), (2,2), and (3,3). 
Since R doesn't even contain (1,1), it is not reflexive. Here is an 
equivalence relation R2 on A: 

   R2 = {(1,1), (1,3), (2,2), (3,1), (3,3)}. 

Do a quick mental check to see that all three properties hold.

Okay, now we're ready to start the proofs. Sorry for the detour, but it 
helps to have the definitions in front of you.

For the first one, we are already given that R is a symmetric and 
transitive relation on A. So we only need to check that R is reflexive, 
which means that for each a in A, (a,a) is in R. Look at the next line 
given in the problem: "Suppose that for each a in A there is b in A 
such that (a,b) and is in R." This is very similar to the definition 
for reflexivity. We know that for each a in A, (a,b) is in R. But we 
need to show that (a,a) is in R. We also have some other information we 
can use. Remember that we know R is symmetric and transitive. Use the 
definition of symmetric and the fact we know that (a,b) is in R. 

In the next step we reason that because R is symmetric, and we know 
that for each a in A, (a,b) is in R, we know that for each a in A, 
(b,a) is in R, but that doesn't get us the fact that (a,a) is in R. 
However, we also know that R is transitive. Try finishing the proof 
using the facts that R is transitive and for each a in A, (a,b) and 
(b,a) are in R. 

Once you have finished the first proof, the second two are very 
similar. For both you need to show just one more of the three 
properties required. Look at the definitions of the property in 
question and then look at what you're given about the relation that you 
need to prove is an equivalence relation. 

The last proof is a little tricky because the elements of A that you 
make your ordered pairs from are actually themselves ordered pairs, so 
we may want to alter the definitions above to make it easier to see 
what we need to prove. Try rewriting them with ordered pairs. For 
instance, instead of using "a" to represent an arbitrary element of A, 
we could call (a,b) an arbitrary element of A. 

Please write back if you need clarification of any of this or if you 
need more help in figuring out the rest of the proofs. 

If the definitions are giving you trouble, do lots of examples. That 
will help you get a better feel for relations and equivalence 
relations. And keep referring back to the definitions. They'll help in 
the proofs. Good luck!

- Doctor Teeple, The Math Forum
  http://mathforum.org/dr.math/   

Date: 10/08/2002 at 21:24:05
From: Chris
Subject: Possible error

The answer given by Dr. Math implied that it was possible to prove 
that ~ was an equivalence relation.

I'm not completely sure, but I think that I have seen this problem 
before in a textbook. The textbook gave the proof and asked why it was 
false. It then stated: If ~ is symmetric and transitive, then we can 
not conclude that ~ is reflexive.

Here is the argument:
Call this argument: PROOF1

We know that a~b => b~a
We know that a~b and b~c => a~c
Suppose a~b
Then b~a by symmetry.
So a~b and b~a.
Then a~a by transitivity.
Thus, ~ is an equivalence relation.

Here is an counterexample:

Suppose a>a and a>a.
Then a~a.
But a cannot be greater than a.
This is a contradiction.
So, a is not related to a.
Thus, ~ is not reflexive.
It is easy to show that ~ is symmetric and transitive.

So...this counterexample shows that symmetry and transitivity do not 
imply reflexivity.

I think that the problem with PROOF1 is that it relies on a~b. "If 
a~b, then a~a"  We can write this as "a~b only if a~a"

Looking at a truth table...

If P, then Q

P Q   P=>Q
-----------
F F    T
F T    T
T F    F <-- We can ignore this line since P=>Q was proven true.
T T    T

It is easy to see that P is true only if Q is true.
But notice that Q can be true or false.

F F => T
F T => T

For ~ to be an equivalence relation, Q must be true.
PROOF1 does not guarantee that Q is true.
It merely says that Q is true when a~b.

I hope I did not make a mistake in my logic,
Chris

Date: 10/09/2002 at 01:46:27
From: Doctor Mike
Subject: Re: Possible error

Hi Chris,
  
You are right that symmetry and transitivity are not enough to prove 
reflexivity. But that isn't what Dr. Math was claiming to be able to 
do. There was an extra assumption that each item "a" is related to 
something. That extra assumption, in addition to symmetry and 
transitivity, allows proof of reflexivity.
   
Your example's definition says that a is related to b means a<b and 
also b>a. This can never happen, so you have described what could be 
called the "empty relation."  Nothing is related to anything else. It 
is symmetric because whenever a is related to b (which NEVER happens) 
then b is related to a. Similar to the transitivity property; it also 
is in the "if ... then" form, so when the if part is not true, the 
whole expression is true.  
   
Perhaps you have seen made up sentences like this. "If X is a real 
number and X squared is negative, then I'm a monkey's uncle." This is 
a true sentence even though I'm not a monkey's uncle, because the 
first part is false. You referred to truth tables so you are probably 
familiar with these ideas.

I hope this helps this helps you see what Dr. Math was getting at.

- Doctor Mike, The Math Forum
  http://mathforum.org/dr.math/