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\\)).

- _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\\)).