#Puzzle 28

Show that if \$$P\$$ is a partition of a set \$$X\$$, and we define a relation \$$\sim_P\$$ on \$$X\$$ as follows:

$$x \sim_P y \textrm{ if and only if } x, y \in S \textrm{ for some } S \in P$$

then \$$\sim_P \$$ is an equivalence relation.

***

To be an equivalence relation we must satisfy the 3 parts of the definition:

##Reflexive
For all \$$x \in X\$$, there exists \$$S \in P\$$ s.t. \$$x \in S\$$. This follows from part 3 of the definition of partitions of a set. By the definition of \$$\sim_P\$$ then \$$x \sim_P x\$$.
##Transitive
Let \$$x,y,z \in X\$$ and assume \$$x \sim_P y \wedge y \sim_P z\$$.

\$$x \sim_P y\$$ implies \$$x,y \in S_1\$$.
\$$y \sim_P z\$$ implies \$$y,z \in S_2\$$.

Since every element of \$$P\$$ is pairwise disjoint, either \$$S_1 \cap S_2 = \emptyset\$$ or \$$S_1 = S_2\$$. The intersection is non-empty (contains at least \$$y\$$). So the second case must be true.

\$$x,z \in S_1 = S_2\$$ implies \$$x \sim_P z\$$ by the definition of \$$\sim_P\$$. Therefore, \$$\sim_P\$$ is transitive.
##Symmetric
Given \$$x\sim_P y\$$ for \$$x,y \in X\$$, there exists \$$S \subseteq X\$$ s.t. \$$S \in P\$$ and \$$x,y \in S\$$. \$$y \sim_P x\$$ follows from the definition of \$$\sim_P\$$.

Given that \$$\sim_P\$$ is reflixive, transitive, and symmetric then we can conclude that it is an equivalence relation.