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

### Equivalence Relations

```
Date: 12/10/2001 at 16:01:15
From: Joelle
Subject: Equivalence relations

Let  X = {1, 2, 3, 4, 5} , Y =  {3, 4}. Define a relation R on the
power set of X by

A R B if A U Y = B U Y.

a) Prove that R is an equivalence relation.

b) What is the equivalence class of {1, 2}?

c) How many equivalence classes are there?
```

```
Date: 12/11/2001 at 09:03:15
From: Doctor Paul
Subject: Re: Equivalence relations

>a) Prove that R is an equivalence relation.

Certainly this relation is reflexive:

A ~ A means A u Y = A u Y and this is clearly true.

To show ~ is symmetric, we need to show A ~ B -> B ~ A

A ~ B means A u Y = B u Y.  This implies B u Y = A u Y and this is
equivalent to B ~ A.  So ~ is symmetric.

Finally, show ~ is transitive:  A ~ B and B ~ C -> A ~ C

Well, A~B means A u Y = B u Y
and   B~C means B u Y = C u Y

Thus we have A u Y = B u Y = C u Y

so A ~ C

Thus ~ is an equivalence relation.

>b) What is the equivalence class of {1, 2}?

Two elements of the power set of X are going to be related if and only
if they are in the same equivalence class - that's what an equivalence
relation does - it partitions the elements of a set into classes where
two elements are in the same equivalence class if and only if they are
related by the given equivalence relation.

So what elements are going to be in the same class as {1,2}?  Those
that are related to it by ~

So we want to pick an element A of the power set of X such that

A u {3,4} = {1,2} u {3,4} = {1,2,3,4}

So we have the following restrictions on the set A:

It must contain both 1 and 2.
It might or might not contain either 3 or 4.
It cannot contain 5.

It looks as if your possibilities are:

{1,2}
{1,2,3}
{1,2,4}
{1,2,3,4}

>c) How many equivalence classes are there?

I'll leave this for you. The idea is similar to part (b) - just pick
an element of the power set of X and compute the elements that are in
the same equivalence class. Recall that equivalence classes are
distinct (their intersections are always empty) so you'll never use
any of the four that we found above in any other class. Finally,
recall that since X has 5 elements, P(X) will have 2^5 = 32 elements.
It shouldn't take you too long to come up the classes to which the
other 28 elements belong.

some more (especially if there is something you don't understand).

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

```
Date: 12/11/2001 at 10:11:24
From: Joelle
Subject: Equivalence relation

Resp. Dr. Paul,

Thank you for the solution. What I did not understand is ... to
calculate the total number of equivalence classes, do I need to
consider each of the 28 members separately, as you did for one member,
or is there a general method? Is it possible to calculate the number
of equivalence classes for a set with n elements?
```

```
Date: 12/11/2001 at 10:36:32
From: Doctor Paul
Subject: Re: Equivalence relation

It is in general not possible to calculate the number of equivalence
classes for a set with n elements because the number of equivalence
classes will always depend on the associated equivalence relation
(whenever we speak of equivalence classes, there had better be an
assumed equivalence relation somewhere in the background). We had:

A ~ B if A u Y = B u Y

What if I came up with some other way of defining the relation ~ that
retained the property of ~ being an equivalence relation?  Consider:

A ~ B if A = B

Here, ~ is clearly an equivalence relation (verify this if it's not
inherently obvious) and the equivalence classes are going to be the
32 elements of P(X). Certainly two distinct elements of P(X) won't be
in the same equivalence class under this new definition of the
relation ~ because this can only happen when the elements are related
(i.e., they are equal) and we are assuming from the outset that these
two elements are distinct. Thus we have 32 distinct, one element
equivalence classes.

> do I need to consider each of the 28 members separately

Yes. Pick one (we picked {1,2} earlier) and then see what other
elements are in the same equivalence class. This will eliminate some
of your other possibilities (we eliminated three other choices). You
won't need to pick the element {1,2,3} because we know that the
intersection of two distinct equivalence classes is empty. For
example, if you try to find what elements are in the same equivalence
class as {1,2,3}, you'll just end up with {1,2}, {1,2,4}, and
{1,2,3,4} again.

So you won't have to actually compute this 28 different times - each
time you pick one, it should eliminate several of the remaining
possibilities. After you've compute the class associated with a
particular element, just pick an element that doesn't belong to any of
the classes that have already been determined.

- Doctor Paul, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
College Logic
High School Logic
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