1
$\begingroup$

I am reviewing the foundation course I took in year 1 and I found out that I still don't fully understand it.

I understand foundamental theorem of equivalence relations, i.e if there is an equivalence relation on a set S, then the set {Ex} of all equivalence classes with respect to the equivalence classes is a partition of set S.

Basically, we can show that (i) if x is related to y, then {Ex}={Can by using the symmetry and transitivity of equivalence relations. We can also show that (ii) if {Ex} and {Ey} have element other than the empty set in common, then {Ex}={Ey} by using the symmetry, the transitivity and (i). Hence, we can show that each of element x of set S belongs to one equivalence class. If two equivalence classes have the element x other than the empty set in common, they are the same. Therefore, each element x of set S belongs to one and only one equivalence class which means the set of all equivalence classes is a partition of set S.

The part that I don't understand is when I start with partition of a set S. We can define a relation on A set S that "x~y" means "x and y belong to a subset of set S". The reflexivity is trivial. The symmetry is also consistent since "x and y belong to a subset of set S" means exactly the same as "y and x...". The transitivity is also true here because partition decides x,y,z belong to one and the only subset of set S if x~y, y~z. Equivalence classes are subsets of set S and each element x of set S belongs to one and only one equivalence class which is also a unique subset of set S because of (ii).

I have skipped quite a few details in the proof of the theorem I know.

As for the second proof, I feel like this is the best I can do but I am not certain about the last part of proof I have written. Is there anything else that I can add into my proof to make it flawless?

Thank you so much!

Regards,

$\endgroup$
  • $\begingroup$ You say "x and y belong to a subset of set S". But what you need to say is "$x$ and $y$ belong to the same part of the given partition." Then the only difficult part is, as you say, transitivity. But that is no problem because the parts of a partition are disjoint. $\endgroup$ – ancientmathematician Aug 15 at 6:24
  • $\begingroup$ Thank you for your kind reply. I start off the second proof with defining a relation on set S and verify it as an equuvalence relation. Then, I tried to clarify that the equivalence classes are exactly the subsets of this partition by showing that the disjoint property of equivalence classes match the element x of set S belongs to one and only subset of a partition. I feel like the way I wrote down is not that convincing ( •̥́ ˍ •̀ू ). Thank you again. $\endgroup$ – Hi I am Max Aug 15 at 10:45
  • $\begingroup$ As you have written it you are allowing $x,y$ to be in any subset of $S$. You must insist that they lie in some part of the partition. $\endgroup$ – ancientmathematician Aug 15 at 12:52
0
$\begingroup$

You know that the equivalence relation induces a partition.

To go the other way around, assume a partition and define $a \equiv b$ if they belong to the same subset. This makes the subsets the classes of the relation. Then you need to prove that is an equivalence:

  • Reflexive: is obvious
  • Symmetric: ditto
  • Transitive: if $a$ and $b$ are in the same group, and $b$ and $c$ are in the same group, $a$ and $c$ are in the same group

So you can talk in terms of the relation or its classes, interchangeably.

$\endgroup$
  • $\begingroup$ Thank you for your answer! I still wonder how to clarify that the equivalence classes are exactly the sets of the partition. Thank you again. $\endgroup$ – Hi I am Max Aug 16 at 0:30

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.