The Math Forum

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

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)?


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 

- Doctor Samus, The Math Forum 

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! 
Associated Topics:
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- The Math Forum at NCTM. All rights reserved.