📂Set Theory

Equivalence Relations and Set Partitions

Theorem ¹

A partition of a set $X$ with respect to an equivalence relation $R$ is $X / R$ of $X$.

Description

Though this theorem might seem trivial, it’s widely used across all areas of mathematics, including topology and abstract algebra. An equivalence relation, simply put, is viewing things as ’the same,’ and ironically, the concept of ’not being the same’ accompanies the establishment of an equivalence relation. The entire set is divided into several pieces under the law of equivalence relation, and it gets divided without ambiguous boundaries due to the strict criteria of the equivalence relation.

Proof

Strategy: By taking the contrapositive of the properties of equivalence classes, we show that equivalence classes do not overlap each other. An equivalence class is a subset of the entire set, but showing that the union of all equivalence classes is significantly larger than the entire set eventually proves that both sets are the same.

Definition of Partition: A $\mathscr{P}$ that satisfies the following conditions for all subsets $A,B,C$ of a set $X$ is called a partition of $X$.

• (i): $$A,B \subset \mathscr{P} \land A \ne B \implies A \cap B = \emptyset$$
• (ii): $$\bigcup_{C \in \mathscr{P} } C = X$$

Definition of Equivalence Class: Given an equivalence relation $R$ defined on a set $X$. For $x \in X$, $x / R := \left\{ y \in X : y R x \right\}$ is called the equivalence class of $x$. The set of all equivalence classes of $X$ is denoted as $X / R := \left\{ x / R : x \in X \right\}$.

According to the definition of $X / R$, $X / R \subset \mathscr{P} (X)$.

---

Part 1. $A,B \subset \mathscr{P} \land A \ne B \implies A \cap B = \emptyset$

Properties of Equivalence Class [4]: $$x / R \cap y / R \ne \emptyset \iff x/R = y/R $$

By the properties of equivalence class, $$ x / R \cap y / R \ne \emptyset \implies x/R = y/R $$ By contrapositive, $$ x/R \ne y/R \implies x / R \cap y / R = \emptyset $$

---

Part 2. $\displaystyle \bigcup_{C \in \mathscr{P} } C = X$

Since for all $x$, $x / R \subset X$, $$ \bigcup_{x \in X} x / R \subset X $$ And since for all $x$, $x \in x / R$, $$ X \subset \bigcup_{x \in X} x / R $$ Since the inclusion relationship of sets is established both ways, $$ X = \bigcup_{x \in X} x / R $$

■