0
$\begingroup$

If $X = \{1, 2, 3, 4\}$ and $\sim$ is an equivalence relation on $X$, then if $1 \sim 2$ and $2 \sim 3$ show that there are just two possibilities for the relation $\sim$ and describe both relations.

This was a bonus question assigned on our last test in proofs. We were studying sets and equivalence relations in particular. As it is a proofs class, there must be proof statements and such included. I wasn't able to even begin to figure this question out though.

$\endgroup$
  • 3
    $\begingroup$ Hint: an equivalence relation can be defined by specifying the equivalence classes. $\endgroup$ – Mark Bennet Mar 2 '14 at 20:28
0
$\begingroup$

Either everything is related to everything, or the only thing 4 is related to is itself.

$\endgroup$
  • $\begingroup$ I see.. so .. S={1,2,3} and S"={4} or S={1,2,3,4} but in a formal proof how would go about actually SHOWING this, I mean a partitioned diagram is one thing but a full proof is another don't you think? $\endgroup$ – user122661 Mar 4 '14 at 17:38
  • $\begingroup$ Certainly, what I gave was nothing close to a proof. What is given is that 1 ~ 2 and 2 ~ 3 so by transitivity 1 ~ 3 and by symmetry and reflexivity, you get that for every two elements of {1,2,3} the relationship holds. Now if any of these relates to 4, then again by transitivity, symmetry, and reflexivity, the relationship will hold between every two elements of {1,2,3,4} and this characterizes the relationship. On the other hand, if the relationship does not hold between 4 and any elements of {1,2,3}, then by reflexivity 4 ~ 4, and this characterizes this other possible relationship. $\endgroup$ – Addem Mar 4 '14 at 19:21
  • $\begingroup$ Of course, this also isn't a full-blown "from the axioms" proof either. But whatever is the level of proof you require, this blue-print should guide you through it. $\endgroup$ – Addem Mar 4 '14 at 19:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.