Partition
Definition 1. Let $X$ be a nonempty set. A partition $\mathcal{P}$ of $X$ is a set of nonempty subsets $X$ such that
(a) If $A, B \in \mathcal{P}$ and $A \neq B$, then $A \cap B = \emptyset$
(b) $\cup_{C \in \mathcal{P}} C = X$.
직관적으로 말하면, partiton은 집합 $X$를 겹치는 부분 없이 잘라놓은 집합이라고 할 수 있다.
Equivalence Class, Quotient Set
Definition 2. Let $R$ be an equivalence relation on a nonempty set $X$. For each $x \in X$, we define $$x / R = \{ y \in X \, | \, yRx \}$$ which is called the equivalence class determined by the element $x$.
The set of all such equivalence classes on $X$ is called the quotient set, denoted by $X / R$. That is, $X / R = \{x / R \, | \, x \in X\}$.
Theorem 1
Theorem 1. Let $R$ be an equivalence relation on a nonempty set $X$. Then
(a) $\forall x \in X, \emptyset \neq x / R \subseteq X$.
(b) $x / R \cap y / R \neq \emptyset \iff xRy$.
(c) $xRy \iff x / R = y / R$
위 정리로부터 equivalence class, 즉 동치류들을 모아 놓은 집합인 quotient set $X / R$은 사실상 partition임을 알 수 있다. 다시 말해 임의의 동치 관계 $R$이 주어지면 $R$에 대하여 partition을 항상 구성해 낼 수 있다는 것이다.
Theorem 2
Theorem 2. Let $R$ be an equivalence relation on a nonempty set $X$. Then $X / R$ is a partition of $X$.
그렇다면 역으로, 어떤 partition이 주어진다면 항상 equivalence relation을 잡아낼 수 있을까? 이때 항상 그렇다는 사실이 보장되어 있으며, 예컨대 다음과 같이 relation을 정의해보자.
Definition 3. Let $\mathcal{P}$ be a partition of a nonempty set $X$. We define a relation $X / \mathcal{P}$ on $X$ by $x (X / \mathcal{P}) y \iff \exists A \in \mathcal{P}$ such that $x, y \in A$.
이렇게 정의한 relation $X / \mathcal{P}$는 equivalence relation이며, 이 사실을 다음과 같이 요약할 수 있다.
Theorem 3. Let $\mathcal{P}$ be a partition of a nonempty set $X$. Then the relation $X / \mathcal{P}$ is an equivalence relation on $X$, and the equivalence classes induced by $X / \mathcal{P}$ are precisely the sets in $\mathcal{P}$. Symbolically, $$X / (X / \mathcal{P}) = \mathcal{P}.$$