Mg Problem 21

PRELIMINARY
Given a partition {Xα}α∈I of X, show that the relation R⊆X×X defined by ((a,b)∈R⇔∃α∈I such that both a,b∈Xα) is an equivalence relation on X whose equivalence classes are precisely the sets Xα of the partition.

Roadmap:
Prove reflexivity, symmetry, and transitivity (equivalence relationship)

Reflexivity: If $a \in X_\alpha$, then $a,a \in X_\alpha$, so $(a,a) \in R$.

Prove the precisely sets $X_\alpha$ part? This is very weird.

FINAL:

Given a partition {Xα}α∈I of X, show that the relation R⊆X×X defined by ((a,b)∈R⇔∃α∈I such that both a,b∈Xα) is an equivalence relation on X whose equivalence classes are precisely the sets Xα of the partition.

To prove that this is an equivalence relation, we must show that it satisfies reflexivity, symmetry, and transitivity. Reflexivity is simple. If $a \in X_\alpha$, then both $a$ and $a$ are in $X_\alpha$, so $(a,a)\in R$. Symmetry is also simple. We must show that $(c,d)\in R \leftrightarrow (d,c) \in R$. For $(c,d)\in R$ to hold, $c,d \in X_\alpha$ must hold. The equivalent requirement $d,c \in X_\alpha$ therefore must hold, so $(d,c) \in R$ must hold. The reverse statement is proven similarly. Thus the biconditional is proven. Finally, we must show transitivity by showing that [[(a,b),(b,c)\in R \rightarrow (a,c)\in R$]]. For the left side to hold, it must be the case that$a,b,c \in X_\alpha$. This clearly implies that$a,c \in X_\alpha$, so [[(a,b),(b,c)\in R \rightarrow (a,c)\in R$]].

Next, we must show that the equivalence classes are precisely the parts of the partition. Since every element of X is contained exactly one part of the partition, every element will be in a representative of exactly one equivalence class by the relation's definition. Additionally, since the equivalence classes are defined by membership in a particular part of the partition, there are no elements of an equivalence class that are not in some part of the partition. Therefore, the equivalence classes are precisely the parts of the partition.
$QED$

Comments - Andrew Furash
Nice work on the first part, but the second part could be slightly more formal. You have the right ideas though.

page revision: 3, last edited: 20 Mar 2018 17:21
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License