📂집합론

동치류

정의 ¹

집합 $X$ 상에서 동치관계 $R$ 이 정의되어있다고 하자. $x \in X$ 에 대해 $x / R := \left\{ y \in X : y R x \right\}$ 를 $x$ 의 동치류라고 한다. 주어진 $X$ 의 모든 동치류를 모은 집합을 $X / R := \left\{ x / R : x \in X \right\}$ 과 같이 나타낸다.

설명

표현이 조금 더러워 보이지만 예시를 생각해보면 전혀 어려운 개념이 아니다.자연수집합 $\mathbb{N}$ 상에서 $3$ 으로 나눈 나머지가 같으면 동치라하고 $x,y \in \mathbb{Z}$ 가 동치면 $x \equiv y \pmod{3}$ 과 같이 나타내도록 하자. $5,7$ 은 $3$ 으로 나눈 나머지가 각각 $2,1$ 이므로 동치가 아니지만 $11,17$ 은 $3$ 으로 나눈 나머지가 $2$ 가 되므로 $11 \equiv 17 \pmod{3}$ 과 같이 쓸 수 있는것이다. $$1 \equiv 4 \equiv 7 \equiv 10 \equiv \cdots \pmod{3} \\ 2 \equiv 5 \equiv 8 \equiv 11 \equiv \cdots \pmod{3} \\ 3 \equiv 6 \equiv 9 \equiv 12 \equiv \cdots \pmod{3}$$ 위의 계산에서 알 수 있듯 $1$ 의 동치류는 $( 1 / \equiv) = \left\{ 1, 4, 7, 10, \cdots \right\}$ 이고, $2$ 의 동치류는 $(2 / \equiv) = \left\{ 2, 5, 8, 11, \cdots \right\}$ 이고, $3$ 의 동치류는 $(3 / \equiv) = \left\{ 3, 6, 9, 12, \cdots \right\}$ 임을 알 수 있다. $3$ 보다 큰 수부터는 위 세가지 동치류가 반복되며, 따라서 $$(\mathbb{N} / \equiv) = \left\{ 1 / \equiv , 2 / \equiv , 3 / \equiv \right\}$$ 위의 예시에서 확인할 수 있듯, 동치류는 다음과 같이 상식적인 성질들을 가진다.

기초 성질

• [1] $x / R \ne \emptyset$
• [2] $x / R \cap y / R \ne \emptyset \iff xRy$
• [3] $x/R = y/R \iff x R y$
• [4] $x / R \cap y / R \ne \emptyset \iff x/R = y/R$

증명

[1]

$R$ 은 $X$ 상의 동치관계이므로 반사성에 의해 모든 $x \in X$ 에 대해 $x R x$ 이고, $x \in x / R$ 이어야한다.

■

전략 [2][3]: $x,y$ 와 별개의 $z$ 를 하나 잡아서 동치관계의 대칭성과 추이성을 이용해 식들을 연결한다.

[2]

$x/R$ 과 $y/R$ 은 공집합이 아니고 $X$ 위의 동치관계이므로 $x/R \cap y/R \ne \emptyset$ 이고, 이는 어떤 $z$ 에 대해 $$\begin{align*} & z \in x / R \land z \in y / R \\ \iff & z R x \land z R y \\ \iff & x R z \land z R y \\ \iff & x R y \end{align*}$$ 인 것과 동치다.

■

[3]

$( \implies )$ $x/R = y/R$ 이면 $x/R \cap y/R \ne \emptyset$ 이므로 [2]에 의해 $x R y$

---

$( \impliedby )$ $x R y$ 이면 모든 $z \in x / R$ 에 대해 $z R x$ 다. $x R y$ 이므로 $R$ 의 추이성에 의해 $z R y$ 이고, $z \in y / R$ 이다. 정리하면 $$z \in x / R \implies z \in y / R$$ 집합의 포함관계 꼴로 바꿔보면 $$x / R \subset y / R$$ 마찬가지의 방법으로 $y / R \subset x / R$ 을 얻을 수 있으므로 $$x / R = y / R$$

■

[4]

삼단논법에 따라 [2]와 [3]에서 $$x / R \cap y / R \ne \emptyset \iff xRy \iff x/R = y/R$$

■