동치관계

나머지가 같은 수끼리 한 묶음으로 나눠 봅니다. 세 가지 약속을 전부 검사해 동치인지 확인합니다.

동치관계는 '같은 편'이라는 뜻의 관계입니다. 누구나 자기 자신과 같은 편입니다. 같은 편인지는 양쪽이 똑같이 느껴야 합니다. 편이 이어지면 끝까지 같은 편입니다. 이 셋이 성립하면 전체가 겹치지 않는 묶음으로 갈립니다.

예를 들면, 🧑 친구 12명을 4명씩 세 모둠으로 나누는 것과 같습니다. 누구도 두 모둠에 겹쳐 들어가지 않습니다. 모둠 안에서는 전원이 같은 편입니다. 나머지가 같은 수들의 묶음이 딱 이 모습입니다.

a∼b  ⟺  n∣(a−b)a \sim b \iff n \mid (a - b)
[r]={r,r+n,r+2n}[r] = \{r, r + n, r + 2n\}
z∈[x]∩[y]  ⟹  [x]=[y]z \in [x] \cap [y] \implies [x] = [y]

예제

정수의 집합 Z\mathbb{Z} 위에서 합동식 a∼b  ⟺  n∣(a−b)a \sim b \iff n \mid (a - b)로 정의된 관계가 동치관계임을 완전히 증명하세요 — 반사·대칭·추이 세 조건을 각각 나눗셈의 산술로 끌어내리세요.

a∼b    ⟺    a≡b(modn)a \sim b \;\iff\; a \equiv b \pmod n
n∣(a−b),  n∣(b−c)  ⇒  n∣(a−c)=(a−b)+(b−c)n \mid (a-b),\; n \mid (b-c) \;\Rightarrow\; n \mid (a-c) = (a-b) + (b-c)
n=4n = 4: UU는 00부터 1111까지의 1212개 수, 동치류는 [0]={0,4,8}[0] = \{0, 4, 8\}, [1]={1,5,9}[1] = \{1, 5, 9\}, [2]={2,6,10}[2] = \{2, 6, 10\}, [3]={3,7,11}[3] = \{3, 7, 11\}. 예: 7∼37 \sim 3 (7−3=47 - 3 = 4), 7∼47 \sim 4는 거짓 (7−4=37 - 4 = 3은 44로 나누어지지 않음).
증명 보기

  1. 반사(reflexive): 모든 정수 aa에 대해 a−a=0a - a = 0이고 n∣0n \mid 0이므로 a∼aa \sim a. 씬의 수치로는 n=4n = 4일 때 UU의 1212개 원소가 모두 자기자신과 관련됩니다.

  2. 대칭(symmetric): a∼ba \sim b라 하세요. 그러면 n∣(a−b)n \mid (a - b)라서 a−b=nka - b = nk인 정수 kk가 존재하고, 이로부터 b−a=−nk=n(−k)b - a = -nk = n(-k)이므로 n∣(b−a)n \mid (b - a), 즉 b∼ab \sim a.

    씬에서는 UU의 모든 122=14412^2 = 144개 순서쌍에 대해 확인됩니다.

  3. 추이(transitive): a∼ba \sim b이고 b∼cb \sim c라 하세요. a−b=nka - b = nk, b−c=nmb - c = nm인 정수 k,mk, m이 존재하고, 두 식을 더하면 a−c=(a−b)+(b−c)=nk+nm=n(k+m)a - c = (a - b) + (b - c) = nk + nm = n(k + m)이므로 n∣(a−c)n \mid (a - c), 즉 a∼ca \sim c.

    씬에서는 123=172812^3 = 1728개 삼중항이 모두 확인됩니다. 세 조건이 성립하므로 합동식은 동치관계입니다.

분할 정리(partition theorem)를 완전히 증명하세요: 집합 SS 위의 동치관계 ∼\sim에 대해 (i) 모든 xx는 그 동치류 [x][x]에 속하고, (ii) [x][x]와 [y][y]가 원소를 하나라도 공유하면 [x]=[y][x] = [y]입니다.

이로부터 서로 다른 동치류는 겹치지 않고 동치류 전체가 SS를 덮음을 도출하세요.

[x]={y∈S:y∼x}[x] = \{y \in S : y \sim x\}
z∈[x]∩[y]  ⇒  [x]=[y]z \in [x] \cap [y] \;\Rightarrow\; [x] = [y]
n=4n = 4: 네 동치류 [0]={0,4,8}[0] = \{0, 4, 8\}, [1]={1,5,9}[1] = \{1, 5, 9\}, [2]={2,6,10}[2] = \{2, 6, 10\}, [3]={3,7,11}[3] = \{3, 7, 11\}은 서로 겹치지 않고 합집합이 UU 전체입니다 — 분할 정리의 유한 구체예.
증명 보기

  1. (i) 반사성(reflexivity)에 의해 x∼xx \sim x이므로 x∈[x]x \in [x]입니다. 따라서 어떤 동치류도 비어 있지 않고, 모든 원소가 최소 하나의 동치류에 들어갑니다 — 동치류들의 합집합이 SS 전체입니다.

  2. (ii)의 준비: 원소 z∈[x]∩[y]z \in [x] \cap [y]가 존재한다고 하세요. 정의에 의해 z∼xz \sim x이고 z∼yz \sim y입니다.

    대칭성에 의해 z∼xz \sim x에서 x∼zx \sim z를 얻고, 여기에 z∼yz \sim y와 추이성을 적용하면 x∼yx \sim y를 얻습니다.

  3. 이제 [x]⊆[y][x] \subseteq [y]를 보입니다. w∈[x]w \in [x]라 하면 w∼xw \sim x이고, 위의 준비에서 얻은 x∼yx \sim y와 w∼xw \sim x를 추이성으로 바로 이으면 w∼yw \sim y, 즉 w∈[y]w \in [y]입니다.

    역할을 바꾸면 [y]⊆[x][y] \subseteq [x]도 얻어지므로 [x]=[y][x] = [y]입니다.

  4. 결론: 두 동치류가 조금이라도 겹치면 둘은 같습니다. 따라서 서로 다른 동치류는 서로소이고, (i)에 의해 그 합집합은 SS입니다 — 동치관계는 집합을 동치류들로 분할(partition)합니다.

    n=4n = 4인 씬에서는 네 동치류가 UU의 1212개 원소를 33개씩 정확히 나눠 가집니다.

실수 집합 R\mathbb{R} 위에서 x∼y  ⟺  x−y∈Qx \sim y \iff x - y \in \mathbb{Q}로 관계를 정의합니다. (a) 이 관계가 동치관계임을 증명하고, (b) 동치류의 모양을 규명하세요([x]=x+Q[x] = x + \mathbb{Q}), (c) 이 분할에서 각 동치류마다 대표원소 하나를 골라 모은 집합이 비탈리 집합(Vitali set)의 구성과 정확히 같음을 설명하세요.

x∼y  ⟺  x−y∈Qx \sim y \iff x - y \in \mathbb{Q}
[x]=x+Q={x+q:q∈Q}[x] = x + \mathbb{Q} = \{x + q : q \in \mathbb{Q}\}
n=2n = 2: 유한 원형 — 두 동치류 [0]={0,2,4}[0] = \{0, 2, 4\}와 [1]={1,3,5}[1] = \{1, 3, 5\}가 U={0,…,5}U = \{0, \dots, 5\}를 분할합니다. 나머지 대신 “같은 유리수 차이”를 쓰는 것이 이 문제의 관계입니다.
증명 보기

  1. (a) 반사: x−x=0∈Qx - x = 0 \in \mathbb{Q}이므로 x∼xx \sim x. 대칭: x−y∈Qx - y \in \mathbb{Q}이면 y−x=−(x−y)∈Qy - x = -(x - y) \in \mathbb{Q}이므로 y∼xy \sim x (유리수는 부호를 바꿔도 유리수).

    추이: x−y∈Qx - y \in \mathbb{Q}이고 y−z∈Qy - z \in \mathbb{Q}이면 x−z=(x−y)+(y−z)∈Qx - z = (x - y) + (y - z) \in \mathbb{Q}이므로 x∼zx \sim z (유리수의 합은 유리수). 앞선 문제 1의 합동식 증명과 정확히 같은 골격이며, “나눗셈”이 “Q\mathbb{Q}의 원소”로 대체됐을 뿐입니다.

  2. (b) [x]={y∈R:y−x∈Q}[x] = \{y \in \mathbb{R} : y - x \in \mathbb{Q}\}이고 y=x+(y−x)y = x + (y - x)라 두면 이 집합은 정확히 x+Q={x+q:q∈Q}x + \mathbb{Q} = \{x + q : q \in \mathbb{Q}\} — 유리수 집합을 xx만큼 통째로 평행이동한 복사본입니다. 유리수 차이만큼 떨어진 실수들은 서로 동일시되고, 분할 정리(문제 2)에 의해 이 이동된 복사본들이 R\mathbb{R}을 겹침 없이 덮습니다.

  3. (c) 각 동치류 x+Qx + \mathbb{Q}에서 대표원소 딱 하나를 골라 모은 집합이 비탈리 집합입니다. 그런데 동치류가 비가산히 많고 어느 하나도 “자연스러운” 대표원소가 없기 때문에, 이 선택은 선택 공리(the axiom of choice)를 필요로 합니다 — 규칙으로는 고를 수 없고, 공리가 존재만을 보장합니다. 적분 단원의 비탈리(vitali) 씬에서는 바로 이 집합이 르베그 가측(measure)이 아님을 보입니다.

    대표원소는 [0,1][0,1] 안에서 고릅니다 (모든 동치류 x+Qx + \mathbb{Q}는 [0,1][0,1]와 만남) — 따라서 V⊆[0,1]V \subseteq [0,1]입니다. q∈Q∩[−1,1]q \in \mathbb{Q} \cap [-1,1]인 이동 V+qV + q들은 서로소입니다: (V+q1)∩(V+q2)≠∅(V + q_1) \cap (V + q_2) \ne \emptyset이면 두 대표원소의 차가 q2−q1∈Qq_2 - q_1 \in \mathbb{Q}라 같은 동치류에 속해 둘이 같아야 하고, 따라서 q1=q2q_1 = q_2입니다. 모든 이동은 평행이동 불변성에 의해 VV와 측도가 같고, 합집합은 [0,1][0,1]를 덮으며 (각 x∈[0,1]x \in [0,1]는 그 대표원소와 ∣q∣≤1|q| \le 1인 유리수 qq만큼 차이 남), [−1,2][-1, 2] 안에 들어갑니다.

    VV가 가측이고 m(V)=0m(V) = 0이면 가산합집합의 측도가 00이라 [0,1][0,1]를 덮는다는 데 모순이고, m(V)>0m(V) > 0이면 [−1,2][-1, 2] 안의 합집합 측도가 무한대가 되어 모순입니다. 따라서 VV는 가측이 아닙니다.

1. 증명의 기초