Find all equivalence classes.

1. Feb 8, 2004

Caldus

Let A be a set and let f: A -> A be a function. For x,y belongs to A, define x ~ y if f(x) = f(y):

a. Prove that ~ is an equivalence relation on A.

This is my guess, but I am not sure whether I'm right:

Proving reflexiveness: If (x,y) belong to A, then f(x) = f(x), therefore, (x,y) ~ (x,y).

Proving symmetry: If (x,y) belong to A, then f(x) = f(y), therefore if (y,x) belong to A, then f(y) = f(x), so (x,y) ~ (y,x).

Proving transitivity: If (x,y) and (y,z) belong to A, then if f(x) = f(y) and f(y) = f(z), then f(x) = f(z). Therefore, (x,y) ~ (x,z).

Is this right?

b. Suppose A = {1, 2, 3, 4, 5, 6} and f = {(1,2), (2,1), (3,1), (4,5), (5,6), (6,1)}. Find all equivalence classes.

I have no idea where to start with this one. Could someone start this one out? I would really appreciate it.

2. Feb 8, 2004

master_coda

Reflexivness is just proving that x ~ x, for any x in A. There shouldn't be any "y" term in your proof.

The way to prove symmetry is to assume x ~ y and show that this implies y ~ x (for any x,y in A).

Similarly, for transitivity you must show that for any x,y,z in A if x ~ y and y ~ z then x ~ z.

In all three of your proofs you seem to be using "if (x,y) belong to A" as a synonym for "if x,y in A and x ~ y". This is incorrect.

The easiest way to solve the second question is just by brute force. Group the elements of {1,2,3,4,5,6} by what the result of f(x) is. In other words, split the numbers up into a set where f(x)=1, a set where f(x)=2, and so on. These are your equivalence classes.

3. Feb 8, 2004

Caldus

Wouldn't x,y be used in each one? Since a function is a cartesian product or whatever.

4. Feb 8, 2004

master_coda

Yes, elements of a function can be considered as ordered pairs. However the equivalence relation is on the set A, which his not made up of ordered pairs. So you have to examine elements of A, not elements of the function f.

5. Feb 8, 2004

HallsofIvy

Staff Emeritus
You start everyone with "If (x,y) belongs to A" which is incorrect.
A is the set containing x or y. If does not contain (x,y)!

6. Feb 8, 2004

Caldus

Reflexive: If x belongs to A, then f(x) = f(x). Therefore, x ~ x.
Symmetry: If x ~ y, then f(x) = f(y). So f(y) = f(x) and y ~ x.
Transitive: If x ~ y and y ~ z, then f(x) = f(y) and f(y) = f(z). Then f(x) = f(z). Therefore, x ~ z.

And I still don't know what to do for the second part.

7. Feb 8, 2004

Caldus

For the second part, could this be a possibility?:

Equivalence class of (1,2): {(x,y) | (x,y) belongs to (1,2)}
Equivalence class of (2,1): {(x,y) | (x,y) belongs to (2,1)}
(And so on...?)

8. Feb 8, 2004

master_coda

Given a set and an equivalence relation, in this case A and ~, you can partition A into sets called equivalence classes. These equivalence classes have the special property that:

If x ~ y if and only if x and y are in the same equivalance class.

In this case, two elements are equivalent if f(x) = f(y). Thus all the elements with f(x) = 1 are in the same equivalence class, and all the elements with f(x) not= 1 are in different equivalence classes. Similarly, all the elements with f(x) = 2 are in the same equivalence class, and all the elements with f(x) = 3 are in the same equivalence class, and so on.

Note that in this case, we are still working with elements of A, not elements of f. Thus the elements of the equivalence classes with be numbers, not ordered pairs.

9. Feb 8, 2004

Caldus

Thank you. That helped a lot.

My quotient set ends up being:

{{1}, {2,3,6}, {4}, {5}}

Is this right?

10. Feb 8, 2004

Yes.