Associated Topics || Dr. Math Home || Search Dr. Math

### 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
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.
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/
```
Associated Topics:
High School Discrete Mathematics

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
Math Forum Home || Math Library || Quick Reference || Math Forum Search