#Puzzle 29
Show that if \$$\sim\$$ is an equivalence relation on a set \$$X\$$, we can define a partition \$$P_\sim\$$ on \$$X\$$ whose parts are precisely the sets of the form

$$S_x = \\{y \in X : \; y \sim x \\}$$

with \$$x \in X\$$. We call \$$S_x\$$ the **equivalence class** of \$$x\$$.
***
I'm going to start with something I'd realized and John states:
$$x \sim y \iff S_x = S_y$$
This follows from the definition of an **equivalence class** and that \$$\sim\$$ is symmetric and transitive.

Let \$$x,y \in X\$$ and \$$x \sim y\$$

Three immediate conclusions lead from this:

$$y \sim x\\\\ x \in S_y\\\\ y \in S_x$$

The first because \$$\sim\$$ is symmetric. The second two by the definition of **equivalence class**.

\$$\forall z \in S_y, z \sim y\$$. Given that \$$\sim\$$ is transitive and symmetric, this also means that \$$\forall z \in S_y, z \sim x\$$. Given the definition of \$$S_x\$$, \$$\forall z \in S_y, z \in S_x\$$. This implies that \$$S_y \subseteq S_x\$$. The same reasoning gives us \$$S_x \subseteq S_y\$$.

$$\therefore x \sim y \implies S_x = S_y$$

The reverse (that \$$S_x = S_y \implies x \sim y\$$) can be shown by similar reasoning but I'll stop here. I don't need it for the proofs below.
***
Now to the three parts of the definition of a partition:

- *Each part is non-empty*

\$$\forall x \in X: \exists S_x \in P_\sim\$$ by definition of \$$P_\sim\$$.

\$$\sim\$$ is reflexive so \$$x \sim x\$$.

By the definition of \$$S_x\$$ with \$$x \sim x\$$, \$$x \in S_x\$$ .

\$$\forall S_x \in P_\sim, S_x \neq \emptyset\$$.

- *Distinct parts are disjoint*

I'll attempt to do this as a proof by contradiction. (I'm rusty on constructing proofs of this sort so comments and corrections would be appreciated.)

Let \$$S_x, S_y \in P_\sim\$$ and \$$S_x \neq S_y\$$. Assume \$$S_x \cap S_y \neq \emptyset\$$.

Then \$$\exists z \in X \text{ s.t. } z \in S_x \wedge z \in S_y\$$.

\$$z \in S_y \implies z \sim y\$$ and \$$z \in S_x \implies z \sim x\$$.

These in turn give us (using the proposition at the start) that \$$S_z = S_y \wedge S_z = S_x\$$.

This leads to \$$S_x = S_y\$$, a contradiction. So our assumption must be false.

Given \$$S_x \neq S_y\$$ then \$$S_x \cap S_y = \emptyset\$$. So distinct parts are disjoint.

- *The union of all parts in \$$P\$$ is \$$X\$$*

\$$\forall x \in X, \exists S_x \in P_\sim s.t. x \in S_x\$$, from the definition of \$$P_\sim\$$.

Since \$$P_\sim\$$ is the set of all equivalence classes \$$S_x\$$, this means that the union of all parts in \$$P\$$ is the same as \$$\bigcup_{x \in X}S_x\$$.

Since each \$$x\$$ is in its respective \$$S_x\$$, \$$\bigcup_{x \in X}S_x = X\$$.