Equivalence Relations

Date: 05/06/2003 at 17:32:13
From: Kerri
Subject: Equivalence Relations

I have a question about Equivalence relations.

Determine with proof which of the three equivalence relation 
properties hold for the following relation. 

(a) Let R be the relation on the set A={1,2,3,4} defined by
    R = {(1,1),(1,2),(1,3),(1,4),(2,1),(2,2),(3,1),(3,3),(4,1)}

(b) Let R be the relation on the natural numbers defined by nRm if 
    and only if n divides into m with zero remainder.

How would you prove the equivalence relation with ordered pairs such 
as in (a)?

Thanks. 
Kerri

Date: 05/06/2003 at 23:57:16
From: Doctor Samus
Subject: Re: Equivalence Relations

Hi Kerri,

To start, we should list the three different properties of an 
equivalence relation R on a set A:

     I)  Reflexivity:  xRx for all x in A
    II)  Symmetry:     If xRy then yRx for x and y in A
   III)  Transitivity: If xRy and yRz then xRz for x, y and z in A

To determine which properties hold, we must look at the elements in 
the relation and see which properties they satisfy.

Let's look at a) and see which properties hold:

     I)  Doesn't hold, since 4 is in A, but (4,4) is not in R
    II)  Holds, since for every (x,y) in R, (y,x) is also in R
   III)  Doesn't hold, since (2,1) and (1,3) are in R, but (2,3)
         is not

So for (a), only property II (symmetry) holds.

To do b, simply investigate the same three properties for the relation 
in the problem.

Note that to show a property doesn't hold, we need only find a single 
example showing that the property doesn't hold. To show that a 
property does hold, we have to show that it's true for all elements in 
the relation to which the property applies.

I hope this helps. Please feel free to write back if you neeed more 
help.

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

Date: 05/07/2003 at 00:16:26
From: Kerri
Subject: Thank you (Equivalence Relations)

Thank you Doctor Samus, so much! I had no idea how to work this and 
now I understand it completely. (b) wasn't a problem after your 
explanation of (a). 

Thanks again! 
Kerri