1. ## equivalence class

Find the equivalence class
from the set of {0,1,2,3}
for
{(0,0)(1,1),(2,2),(3,3))
and
{(0,0),(1,1)(1,2)(2,1)(2,2)(3,3)}

I said for the first one it is [a]={a,a} if 0<=a<=3. Not sure if thats right

I don't know what the second is..some help appreciated.

Thanks

2. Find the equivalence class
Do you need to find all classes or just one class?

I said for the first one it is [a]={a,a} if 0<=a<=3.
This is correct, but also recall that {a,a}={a} as sets.

I don't know what the second is..some help appreciated.
Draw a graph with vertices 0, 1, 2, 3 and an edge between each a, b such that (a, b) is in the relation. If you can travel from one vertex to another, they belong to the same equivalence class; otherwise they belong to different classes.

3. Originally Posted by emakarov
Do you need to find all classes or just one class?

This is correct, but also recall that {a,a}={a} as sets.

Draw a graph with vertices 0, 1, 2, 3 and an edge between each a, b such that (a, b) is in the relation. If you can travel from one vertex to another, they belong to the same equivalence class; otherwise they belong to different classes.
thanks!
let me answer your first question first..I need to find all the classes.

4. Ok, so i put 0 1 2 3 as vertices..I then drew lines between the ones that are in the relation. I'm guessing (0,0), (1,1) don't have lines then because you can't connect them to themselves? If so i only end up with a line from 1 to 2...does that mean only (1,2) and (2,1) are in the equivalence class?

5. Caveat: what I am offering is not a manual procedure set in stone; it's just a way to visualize the situation and find an answer.

I'm guessing (0,0), (1,1) don't have lines then because you can't connect them to themselves?
It makes sense to have a loop at every vertex. They correspond to (0,0), (1,1), (2,2) and (3,3).

If so i only end up with a line from 1 to 2
And a line from 2 to 1. In fact, we are talking not about lines but about arrows: one from 1 to 2 and one back.

does that mean only (1,2) and (2,1) are in the equivalence class?
(1,2) and (2,1) are not elements of the set. They are elements of the relation, whereas equivalence classes are subsets of the original set, not relation. This would mean that 1 and 2 are in one equivalence class. The other two classes are singletons (one-element sets) {0} and {3}.

In general, suppose you draw a diagram of a relation as described above. Then the relation is an equivalence relation if: (1) every vertex has a loop, (2) for every arrow from a to b there is an arrow back from b to a, and (3) if you can go from a to b in several steps, you can also do this in one step. These conditions are reflexivity, symmetry and transitivity of the relation expressed in terms of arrows and vertices. Given such diagram, an equivalence class consists of all vertices that are interconnected.

6. Originally Posted by emakarov
Caveat: what I am offering is not a manual procedure set in stone; it's just a way to visualize the situation and find an answer.

It makes sense to have a loop at every vertex. They correspond to (0,0), (1,1), (2,2) and (3,3).

And a line from 2 to 1. In fact, we are talking not about lines but about arrows: one from 1 to 2 and one back.

(1,2) and (2,1) are not elements of the set. They are elements of the relation, whereas equivalence classes are subsets of the original set, not relation. This would mean that 1 and 2 are in one equivalence class. The other two classes are singletons (one-element sets) {0} and {3}.

In general, suppose you draw a diagram of a relation as described above. Then the relation is an equivalence relation if: (1) every vertex has a loop, (2) for every arrow from a to b there is an arrow back from b to a, and (3) if you can go from a to b in several steps, you can also do this in one step. These conditions are reflexivity, symmetry and transitivity of the relation expressed in terms of arrows and vertices. Given such diagram, an equivalence class consists of all vertices that are interconnected.
Ok so in this case all those conditions are satisfied. so the equivalence classes would have [1,2]={(1,1),(2,2)(1,2),(2,1) and [0]={(0,0) and [3]={(3,3)} correct?

7. so the equivalence classes would have [1,2]={(1,1),(2,2)(1,2),(2,1) and [0]={(0,0) and [3]={(3,3)} correct?
Again, don't confuse the original set A = {0,1,2,3} with the relation R on A. Both A and R are sets, but elements of A are numbers, while elements of R are pairs of numbers. Speaking in programmer's terms, A and R have different types.

Equivalence classes are subsets of A, so they also consist of individual numbers, not pairs. So you have [0] = {0}, [1] = [2] = {1,2}, and [3] = {3}.

8. Originally Posted by bfpri
Ok so in this case all those conditions are satisfied. so the equivalence classes would have [1,2]={(1,1),(2,2)(1,2),(2,1) and [0]={(0,0) and [3]={(3,3)} correct?
No. A "relation" on set A is a set of ordered pairs from A. "Equivalence classes" are subsets of A.

For the first one, {(0,0)(1,1),(2,2),(3,3)) you should be able to see that 0 is equivalent to itself and nothing else: one equivalence class is {0}. Similarly, 1 is equivalent to itself and nothing else: another equivalence class is {1}. There are two more equivalence classes. What are they?

For the second, {(0,0),(1,1)(1,2)(2,1)(2,2)(3,3)}. 0 is equivalent to itself and nothing else: one equivalence class is {0}. 1 is equivalent to itself and is equivalent to 2 (which, of course, is equivalent to itself and 1): another equiivalence class is {1, 2}. There is one more equivalence class.

9. Ahhhh Alright I get it now. I was understanding the equivalence classes wrong. Thanks!