Here is my slightly verbose solution to **puzzle 29**. I'm proving the three properties from the definition of "partition".

- _Each part is non-empty._ For any \$$x \in X\$$, the corresponding part \$$S_x\$$ has at least one element: \$$x \in S_x\$$ since \$$x \sim x\$$ (the equivalence relation is reflexive).
- _Distinct parts are disjoint._ For any \$$x, y \in X\$$, we show that the corresponding parts, \$$S_x\$$ and \$$S_y\$$, are either the same set, \$$S_x = S_y\$$, or they are disjoint sets, \$$S_x \cap S_y = \emptyset\$$:

1. Consider there exists a common element \$$z\$$, that is, \$$z \in S_x\$$ and \$$z \in S_y\$$. Then for any \$$x' \in S_x\$$, we have \$$x' \sim x\$$. We also know that \$$z \sim x\$$ (since \$$x \in S_x\$$) and by using the symmetry and transitivity of the equivalence relation, we get that \$$z \sim x'\$$. But \$$z \sim y\$$ (since \$$z \in S_y\$$), and using again the symmetry and transitivity properties, we get that \$$x' \sim y\$$, that is, \$$x' \in S_y\$$. Hence, \$$S_x = S_y\$$.
2. There is no common element; hence, the parts are disjoint.

- _The union of all the parts is the entire set._ Any \$$y \in X\$$ belongs to the union of all the parts, \$$\bigcup_{x \in X} S_x\$$, because \$$x \in S_x\$$ (as we have seen in the first bullet point) and we are iterating over all \$$x \in X\$$.

Edit: I think I should have started by showing that the partition, \$$\left\\{S_x\right\\}_\{x \in X\}\$$, is included in the power set \$$P(X)\$$, that is, \$$S_x \subseteq X\$$ (this can be seen from the definition of \$$S_x\$$).