A community for students.

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

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.

  • This Question is Closed
  1. zzr0ck3r
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  6. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    Right, "equivalence classes" form a partition of the set \(S\)

  8. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  11. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  14. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    @zzr0ck3r knows more about the notation than anybody else here

  15. zzr0ck3r
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    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
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

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

  17. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  18. Not the answer you are looking for?
    Search for more explanations.

    • Attachments:

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy

Your question is ready. Sign up for free to start getting answers.

spraguer (Moderator)
5 → View Detailed Profile

is replying to Can someone tell me what button the professor is hitting...

23

  • Teamwork 19 Teammate
  • Problem Solving 19 Hero
  • You have blocked this person.
  • ✔ You're a fan Checking fan status...

Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.