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

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