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

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