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

***

To be an equivalence relation we must satisfy the 3 parts of the definition:

##Reflexive

For all \\(x \in X\\), there exists \\(S \in P\\) s.t. \\(x \in S\\). This follows from part 3 of the definition of partitions of a set. By the definition of \\(\sim_P\\) then \\(x \sim_P x\\).

##Transitive

Let \\(x,y,z \in X\\) and assume \\(x \sim_P y \wedge y \sim_P z\\).

\\(x \sim_P y\\) implies \\(x,y \in S_1\\).

\\(y \sim_P z\\) implies \\(y,z \in S_2\\).

Since every element of \\(P\\) is pairwise disjoint, either \\(S_1 \cap S_2 = \emptyset\\) or \\(S_1 = S_2\\). The intersection is non-empty (contains at least \\(y\\)). So the second case must be true.

\\(x,z \in S_1 = S_2\\) implies \\(x \sim_P z\\) by the definition of \\(\sim_P\\). Therefore, \\(\sim_P\\) is transitive.

##Symmetric

Given \\(x\sim_P y\\) for \\(x,y \in X\\), there exists \\(S \subseteq X\\) s.t. \\(S \in P\\) and \\(x,y \in S\\). \\(y \sim_P x\\) follows from the definition of \\(\sim_P\\).

Given that \\(\sim_P\\) is reflixive, transitive, and symmetric then we can conclude that it is an equivalence relation.

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.

***

To be an equivalence relation we must satisfy the 3 parts of the definition:

##Reflexive

For all \\(x \in X\\), there exists \\(S \in P\\) s.t. \\(x \in S\\). This follows from part 3 of the definition of partitions of a set. By the definition of \\(\sim_P\\) then \\(x \sim_P x\\).

##Transitive

Let \\(x,y,z \in X\\) and assume \\(x \sim_P y \wedge y \sim_P z\\).

\\(x \sim_P y\\) implies \\(x,y \in S_1\\).

\\(y \sim_P z\\) implies \\(y,z \in S_2\\).

Since every element of \\(P\\) is pairwise disjoint, either \\(S_1 \cap S_2 = \emptyset\\) or \\(S_1 = S_2\\). The intersection is non-empty (contains at least \\(y\\)). So the second case must be true.

\\(x,z \in S_1 = S_2\\) implies \\(x \sim_P z\\) by the definition of \\(\sim_P\\). Therefore, \\(\sim_P\\) is transitive.

##Symmetric

Given \\(x\sim_P y\\) for \\(x,y \in X\\), there exists \\(S \subseteq X\\) s.t. \\(S \in P\\) and \\(x,y \in S\\). \\(y \sim_P x\\) follows from the definition of \\(\sim_P\\).

Given that \\(\sim_P\\) is reflixive, transitive, and symmetric then we can conclude that it is an equivalence relation.