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

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