@John
Thanks for the pointer. It really helped out a lot. Indeed I was trying to say \$$x \sim_P y \Leftrightarrow S_x = S_y\$$ but didn't know quite how to do it nor how much needed to be said in order to prove it!

@Jared Thanks for showing every step so that even the bottom rung can follow. :)

I have never actually written out a full proof so to practice and also collect all the answers, I took Jared's answers to Puzzle 28,29,31 and tried to rewrite it in my own words. It's quite difficult talking like a mathematician LOL.

###**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.

So we have to check if \$$\sim_P\$$ satisfies **Reflexivity**, **Transitivity**, and **Symmetry** :

**Reflexivity**
For all \$$x \in X\$$, \$$x \sim_P x\$$ is true if and only if \$$x,x \in S\$$ for some \$$S \in P\$$ which is trivially true by definition of an element of a set.

**Transitivity**
For all \$$x,y,z \in X\$$, \$$x \sim_P y\$$ and \$$y \sim_P z\$$ imply \$$x \sim_P z\$$ with \$$x,y \in S_1, y,z \in S_2, x,z \in S_3\$$ by definition is true if and only if \$$S_1 = S_2 = S_3\$$. This is true since \$$S_1 \cap S_2 = y \neq \varnothing\$$ and therefore not disjoint and by property 2 of a partition, \$$S_1 = S_2\$$. This then implies \$$x,y,z,\in S_1\$$ and since \$$x,z \in S_3\$$, \$$S_1 = S_2 = S_3\$$.

**Symmetry**
For all \$$x,y, \in X\$$, \$$x \sim_P y\$$ implies \$$y \sim_P x\$$ with \$$x,y \in S_1, y,x \in S_2\$$ is true if and only if \$$S_1 = S_2\$$. This is true since \$$S_1 \cap S_2 = x,y \neq \varnothing\$$ and therefore not disjoint and by property 2 of a partition, \$$S_1 = S_2\$$.

### **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\$$.

So this time we have to prove that the set above satisfies the definition of a partition.

**1. Each set \$$s \in P\$$ is nonempty**
For all \$$S_x \in P\$$, \$$S_x \neq \varnothing\$$ is true if and only if there exists at least one equivalence relation for every \$$x \in X\$$. This is true because **Reflexivity** states that for all \$$x \in X\$$, \$$x \sim x\$$.

**2. If \$$S_x \neq S_y\$$, then \$$S_x \cap S_y = \varnothing\$$.**
To prove this, we can just prove if \$$S \neq T\$$ then \$$S \cap T \neq \varnothing\$$ is false.

So if \$$S_x \cap S_y \neq \varnothing\$$, then there must exist a \$$z\$$ in both partitions:
\$$S_x = \\{z \in X : z \sim x\\} \in \\{x,y\\}\$$
\$$S_y = \\{z \in X : z \sim y\\} \in \\{y,z\\}\$$

But through **Symmetry** we get \$$S_z=S_x\$$ and \$$S_z=S_y\$$. Therefore \$$S_x=S_y\$$ and we have a contradiction.

**3. The union of all the sets \$$S \in P\$$ is X.**
\$$X= \bigcup_{S \in P}S\$$ if there exists \$$S\$$ for all \$$x \in X\$$ . This is true since \$$x \sim x\$$ for all \$$x\$$ and therefore there exists an \$$S_x\$$ for all \$$x\$$.

### **Puzzle 31** : Show that the previous two puzzles give a one-to-one correspondence between partitions of \$$X\$$ and equivalence relations on \$$X\$$.

Edited:
So to prove an one-to-one correspondence between equivalence relations and partitions we have to prove the following :

1. For any \$$x,y \in X\$$ where \$$x \sim y\$$, there exists an equivalence relation \$$x \sim_{P_\sim} y\$$.
2. For any \$$x,y \in S\$$ where \$$S \in P\$$ and \$$P\$$ is a partition on \$$X\$$, there exists a \$$P_{\sim_P}\$$ where \$$S_x \in P_{\sim_P}\$$ and \$$x,y \in S_x\$$.

given \$$S_x\$$ and \$$\sim_P\$$ which are defined in Puzzle 28 and 29.

1. If \$$x,y \in X\$$ and \$$x \sim y\$$, then define the set \$$S_y = \\{ x \in X : x \sim y \\}\$$. By **Symmetry** we also have \$$y \sim x \Rightarrow S_x = \\{ y \in X : y \sim x \\}\$$. This means \$$S_x = S_y\$$ and \$$x,y \in S_x\$$. Since \$$S_x \in P_\sim\$$ as shown by Puzzle 29, there exists an equivalence relation \$$\sim_{P_\sim}\$$ such that \$$x \sim_{P_\sim} y\$$ as shown by Puzzle 28.

2. If \$$x,y \in S\$$ and \$$S \in P\$$ and \$$P\$$ is a partition on \$$X\$$, then \$$x \sim_P y\$$ is an equivalence relation shown by Puzzle 28. Then there exists a partition \$$P_{\sim_P}\$$ on \$$X\$$ whose parts are sets of the form \$$S_y = \\{x \in X : x \sim_P y \\}\$$ as shown in Puzzle 29. By **Symmetry**, we also get \$$S_x = \\{y \in X : y \sim_P x \\}\$$ and therefore \$$S_x = S_y\$$ and \$$x,y \in S_x\$$.