Find all equivalence classes. Questions about functions

[Caldus]

Questions about functions:

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.

 

[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.

 

[Caldus]

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

 

[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.

 

[HallsofIvy]

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

 

[Caldus]

The first one now reads:

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.

 

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

 

[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.

 

[Caldus]

Thank you. That helped a lot.

My quotient set ends up being:

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

Is this right?

 

[master_coda]

Originally posted by Caldus
Thank you. That helped a lot.

My quotient set ends up being:

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

Is this right?

Yes.