Expert: Sherry Wallin - 6/23/2010

Question
if A={a,b,c}
then the relation on A X A
R={(a,a),(b,b),(c,c)}

is equvalance relation.

sherry please explain it"

Answer
Hi Pratap~
    In order to be an equivalence relation three properties have to be satisfied:
reflexive, symmetric, and transitive. Reflexive basically means do you get the same thing with A x A and A x A?  Now about symmetry, you need to verify that if A R A (shorthand for A is related to A} then show that A R A. Again since you are using A with itself it is automatically symmetric. For transitive you need to show if A R A and A R A then A R A. Usually transitivity is stated given A R B and B R C, then is A R C? And if this is true then the relation is transitive. The key difference between reflexive, and symmetric and tansitive is that in symmetric and transitive you assume that the first part of the relation is true and then see if the conclusion follows. Let me think of another example that is not an equivalence relation and one that is.

Ok suppose the relation is "less than" and we want to see if A R A: it doesn't matter what is in A because every element of A will not be less than itself so it can't be reflexive but if it make you more comfortable let's give A some elements like the integers. So let A be the set of integers and choose any integer and see if it is less than itself. Clearly any integer is not less than itself so A R A is NOT reflexive. Let's see if it is symmetric: choose any two integers who satisfy the relation, let's say -1 and 2 and it is true that -1 < 2, to be symmetric 2 must be less than -1 so this relation is not symmetric either. How about transitivity? Let -1 be from set A and 2 be from set B, and 3 be from set C, then if -1 < 2 and 2 < 3, is it true that -1 < 3? Yes it is, so this particular relation is only transitive thus the relation is not an equivalence relation.

'equals' is an equivalence relation because x = x and x = x, so 'equals' is reflexive and
if x = y, then y = x, so 'equals' is symmetric, and if x = y and if y = z, then 'equals' is always true so x = z. Carefully note the use of 'if' for symmetric and transitive. These are assumptions. Remember the truth tables for a conditional?

p    q     p->q
_________________
T    T       T
T    F       F
F    T       T
F    F       T

There are only two instances where the assumption (p) is true and the conditional is false only when q is false. This means that if you satisfy the conditional (meaning it is true, and that means that both p and q have to be true) then you check for symmetric by seeing if q -> p also, and if it does, then the relations is symmetric. For transitive, if p -> q and if q -> r, then see whether p -> r and if p -> r then the relation is transitive.

Hopefully this has helped you in understanding equivalence relations.

Math Prof