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.

I hope this helps. Please write back if you'd like to talk about this 
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/