## anonymous one year ago Equivalence Relations Question Let S = {1, 2, 3}. Find all equivalence relations on S, and for each one, give the corresponding partition of S into equivalence classes. (You can describe each equivalence relation as a subset of $$S \times S$$. Ok, I am just completely lost on this one...I get that I will have 5 equivalence relations since there are 5 ways to partition a set of three numbers, but I have no idea how to go about "finding" these equivalence relations. Not looking for an answer, just looking for someone to give me a push and maybe check to see if I'm doing it right.

1. zzr0ck3r

First off, you must have that it is reflexive, so that every relations will contain $\{(1,1),(2,2),(3,3)\}$ as a subset. Also, note that this will pass all the rules of a relation, so it is one of them. Now what happens if we add $$(1,2)$$, well since it must be symmetric so we must add $$(2,1)$$, note that if we add these two that we still have transitive. So here is another ER.$\{(1,1),(2,2),(3,3),(1,2),(2,1)\}$ Similarly $\{(1,1),(2,2),(3,3),(1,3),(3,1)\}$ and $\{(1,1),(2,2),(3,3),(2,3),(3,2)\}$ But now take any one of these last three, say (\{(1,1),(2,2),(3,3),(2,3),(3,2)\}\) And throw in some point that is not in there, say $$(2,1)$$, wee then I got to throw in $$(1,2)$$, but now I have $$(1,2)$$ and $$(2,3)$$ so I got to throw in $$(1,3)$$, and if you play this game, you get the last one $\{(1,1),(2,2),(3,3),(1,2)(2,1)(2,3)(3,2)(1,3),(3,1)\}$

2. anonymous

Wow. I did not at all even think of looking at the problem from that angle. Two questions though, 1) when you have an equivalence relation, do you not need to have 2 variables related x~y by some clause? Like $$x \le y$$ or something? Like, can you just straight out call those equivalence relations? 2) Doesn't an equivalence relation have to partition a set into disjoint subsets?$\{(1,1),(2,2),(3,3),(1,2),(2,1)\}$How exactly is this ^ partitioned? I'm sorry if these are dumb questions, but I'm just very confused on this topic (this is from a Linear Algebra course).

3. anonymous

Someone help, please? I can definitely tell that those sets of points are indeed equivalence relations, but I don't quite get how the sets are disjoint partitions of $$S\times S$$?

4. anonymous

I guess a better question would be, when it says that "disjoint partitions" are formed, it doesn't mean that the ordered pairs of $$S \times S$$ are partitioned, but the elements of S are partitioned. So, as @zzr0ck3r posted above respectively, 1) $$\{\{1\}, \{2\}, \{3\}\}$$ 2) $$\{\{1,2\},\{3\}\}$$ 3) $$\{\{1, 3\},\{2\}\}$$ 4) $$\{\{2, 3\},\{1\}\}$$ 5) $$\{1, 2, 3\}$$ Is this the right reasoning?

5. ganeshie8

There are exactly $$9$$ elements in the cartesian product $$S\times S$$

6. anonymous

Right, which is what confused me since the ordered pairs of each equivalence relation are not disjoint partitions of all 9 ordered pairs. So, I'm now thinking that the cartesian product $$S\times S$$ is just a means of describing the equivalence relation, and the equivalence relation is simply partitioning the set itself. Is this correct?

7. ganeshie8

Right, "equivalence classes" form a partition of the set $$S$$

8. ganeshie8

for this equivalence relation $$\{(1,1),(2,2),(3,3),(1,2),(2,1)\}$$ the equivalence classes are $$[1] = \{1,2\}$$ and $$[3]=\{3\}$$ $$[1]$$ and $$[3]$$ do partition the set $$S$$

9. anonymous

Ok, that does make sense. So, to make sure, 1 more time, it's partitioning the set $$S$$, not $$S\times S$$. That was the part that was confusing me the most.

10. anonymous

And is what I posted above correct as far as the partitions for each equivalence relation? Just want to make sure.

11. ganeshie8

Yes, you earlier reply looks good to me : I guess a better question would be, when it says that "disjoint partitions" are formed, it doesn't mean that the ordered pairs of $$S \times S$$ are partitioned, but the elements of S are partitioned. So, as @zzr0ck3r posted above respectively, 1) $$\{\{1\}, \{2\}, \{3\}\}$$ 2) $$\{\{1,2\},\{3\}\}$$ 3) $$\{\{1, 3\},\{2\}\}$$ 4) $$\{\{2, 3\},\{1\}\}$$ 5) $$\{1, 2, 3\}$$ Is this the right reasoning?

12. anonymous

Ok, thanks! One last question, it is ok to denote equivalence relations as ordered pairs? When my professor taught equivalence relations to our class, he used the notation x~y and said that the variables were related if..."something". This is a binary relation, and it's not necessary to express the equivalence relation in this way, correct?

13. anonymous

I'm going to assume that's right for now (have to go to sleep). Thanks for all the help you guys!

14. ganeshie8

@zzr0ck3r knows more about the notation than anybody else here

15. zzr0ck3r

Sorry, the notation $$(a,b)$$means $$a\equiv b$$ or $$a$$ is equivalent to $$b$$. So transitivity would be this $$(a,b),(b,c)\in R \implies (a,c)\in R$$. Remember a relation is a set of ordered pairs.

16. zzr0ck3r

Yes, the partition thingy you guys are talking about is correct.

17. anonymous

Oh, ok. Thanks, I think I understand everything now! :)