37주차 · 강의 — 예제 · 연습 · 해설#
예제 — 동치류의 증명을 함께 만들기#
완성된 증명을 먼저 보이지 않는다. 설계부터 한 줄씩 만든다. 각 단계에서 확인 상자의 빈칸을 연필로 먼저 채운 뒤 답을 연다.
예제 2.1 — 핵심 정리의 증명#
명제. \(R\)이 \(A\) 위의 동치관계이면, 임의의 \(x, y \in A\)에 대해 \(x\,R\,y \iff [x] = [y]\)이다.
설계 — 쓰기 전에 정하는 것. 명제가 \(\iff\) 꼴이므로 두 방향을 각각 증명한다 (25주차 서식). 방향마다 출발점과 도착점을 정의로 번역해 둔다.
방향 |
출발점 (가정) |
도착점 (만들 것) |
|---|---|---|
(\(\Rightarrow\)) |
\(x\,R\,y\) |
\([x] = [y]\) — 집합 상등 |
(\(\Leftarrow\)) |
\([x] = [y]\) — 집합 상등 |
\(x\,R\,y\) — 관계 문장 하나 |
확인 11. (\(\Rightarrow\))의 도착점 \([x] = [y]\)를 정의 27.1(상등의 판정 기준)로
번역하면 무엇을 보여야 하는가. 그리고 각 포함을 보이는 첫 문장은 어떤 꼴인가.
답
\([x] \subseteq [y]\)와 \([y] \subseteq [x]\) 둘 다 보여야 한다. 각 포함의 첫 문장은
원소 추적의 서식대로 “\(z \in [x]\)라 하자”이고, 이 문장은 정의 37.2에 의해 곧바로
“\(x\,R\,z\)이다”로 번역된다. 집합 차원의 목표가 원소 차원의 작업으로 내려온다.
확인 12. (\(\Leftarrow\))의 출발점은 집합의 상등뿐이다. 여기서 관계 문장 하나를
뽑아내려면, 먼저 어느 집합에 어떤 원소가 속한다는 사실부터 확보해야 하는가.
답
\(x \in [x]\)를 먼저 확보한다(확인 5 — 반사성). 가정 \([x] = [y]\)를 쓰면 \(x \in [y]\)가
되고, 이것은 정의 37.2에 의해 \(y\,R\,x\)이다. 목표는 \(x\,R\,y\)이므로 방향이 뒤집혀
있다 — 마지막에 대칭성이 한 번 필요하다. 반사성이 문을 열고 대칭성이 방향을 맞춘다.
1단계 — (\(\Rightarrow\))의 첫 포함. \(x\,R\,y\)를 가정하고 \([x] \subseteq [y]\)를 보인다.
확인 13. 다음을 완성해 보자.
“\(z \in [x]\)라 하자. 정의 37.2에 의해 \(\underline{\quad}\)이다.
가정 \(x\,R\,y\)에 \(\underline{\quad}\)성을 적용하면 \(y\,R\,x\)이고,
\(\underline{\quad}\)성(\(y\,R\,x\)와 \(x\,R\,z\))에 의해 \(y\,R\,z\)이다.
따라서 정의 37.2에 의해 \(z \in [y]\)이다.”
답
\(x\,R\,z\) / 대칭성 / 추이성.
손에 있는 것은 \(x\,R\,y\)와 \(x\,R\,z\)인데 둘 다 \(x\)가 앞자리에 있어 그대로는 이어지지
않는다. 대칭성으로 하나를 뒤집어 \(y\,R\,x\)로 만들면 \(y \to x \to z\)의 사슬이 되고,
추이성이 지름길 \(y\,R\,z\)를 준다. 그리고 \(y\,R\,z\)가 바로 \([y]\)의 소속 조건이다.
2단계 — (\(\Rightarrow\))의 둘째 포함. 같은 가정에서 \([y] \subseteq [x]\)를 보인다.
확인 14. 다음을 완성해 보자.
“\(z \in [y]\)라 하자. 정의 37.2에 의해 \(\underline{\quad}\)이다.
가정 \(x\,R\,y\)와 함께 \(\underline{\quad}\)성을 쓰면 \(x\,R\,z\)이므로 \(z \in [x]\)이다.”
이 방향에도 대칭성이 필요한가.
답
\(y\,R\,z\) / 추이성. 대칭성은 필요하지 않다 — 가정 \(x\,R\,y\)와 \(y\,R\,z\)가 이미
\(x \to y \to z\)의 사슬을 이루므로 추이성 한 번으로 끝난다.
두 포함이 겉보기에는 대칭적이지만 소비하는 부품이 다르다. 어느 줄에서 무엇을 썼는지
표시해 두는 습관이 문제 13의 진단을 가능하게 한다.
3단계 — (\(\Leftarrow\)). 이번에는 \([x] = [y]\)를 가정하고 \(x\,R\,y\)를 만든다.
확인 15. 다음을 완성해 보자.
“\([x] = [y]\)라 가정하자. \(\underline{\quad}\)성에 의해 \(x\,R\,x\)이므로
정의 37.2에 의해 \(x \in [x]\)이다. 가정에 의해 \(x \in \underline{\quad}\)이고,
정의 37.2에 의해 \(\underline{\quad}\)이다. \(\underline{\quad}\)성에 의해 \(x\,R\,y\)이다.”
답
반사성 / \([y]\) / \(y\,R\,x\) / 대칭성.
\([y]\)의 소속 조건은 “앞자리가 \(y\)”이므로 \(x \in [y]\)에서 나오는 것은 \(y\,R\,x\)다.
목표 \(x\,R\,y\)와 순서가 반대이므로 대칭성으로 마무리한다. 순서를 확인하지 않고
\(x\,R\,y\)를 곧바로 적는 경우가 많은데, 그러면 정의 37.2를 반대로 읽은 것이 된다.
완성본. 방금 만든 세 덩어리를 이어 붙이면 아래 왼쪽 열이 된다. 손으로 베껴 쓰면서 각 줄 옆의 “왜?”에 스스로 답해 본다.
증명의 한 줄 |
왜 이 줄을 쓰는가? |
|---|---|
(\(\Rightarrow\)) \(x\,R\,y\)라 가정하자. 먼저 \([x] \subseteq [y]\)를 보인다. \(z \in [x]\)라 하자. 정의 37.2에 의해 \(x\,R\,z\)이다. |
\(\iff\)이므로 방향을 나눈다. 집합 상등의 목표를 정의 27.1로 포함 둘로 쪼개고, 소속을 관계 문장으로 번역한다(근거 ①). |
대칭성에 의해 \(y\,R\,x\)이고, 추이성(\(y\,R\,x\), \(x\,R\,z\))에 의해 \(y\,R\,z\)이다. 따라서 \(z \in [y]\)이고, \([x] \subseteq [y]\)이다. |
두 관계 문장의 \(x\)가 모두 앞자리라 이어지지 않는다 — 대칭성이 방향을 맞추고 추이성이 잇는다. |
다음으로 \([y] \subseteq [x]\)를 보인다. \(z \in [y]\)라 하자. 그러면 \(y\,R\,z\)이고, 가정 \(x\,R\,y\)와의 추이성에 의해 \(x\,R\,z\)이다. 따라서 \(z \in [x]\)이다. |
이 방향은 사슬이 이미 \(x \to y \to z\)로 맞아 있어 추이성 한 번으로 닫힌다. |
양방향 포함이 성립하므로 \([x] = [y]\)이다. |
정의 27.1을 인용하며 집합 상등을 선언한다(근거 ④). |
(\(\Leftarrow\)) \([x] = [y]\)라 가정하자. 반사성에 의해 \(x\,R\,x\)이므로 \(x \in [x] = [y]\)이다. |
가정이 집합 상등뿐이므로, 반사성으로 원소 하나를 확보해 가정을 쓸 자리를 만든다. |
\(x \in [y]\)이므로 정의 37.2에 의해 \(y\,R\,x\)이고, 대칭성에 의해 \(x\,R\,y\)이다. 두 방향이 모두 증명되었으므로 \(x\,R\,y \iff [x] = [y]\)이다. \(\blacksquare\) |
\([y]\)의 소속 조건은 앞자리가 \(y\)다 — 순서를 대칭성으로 맞추고 \(\iff\)의 종합을 선언한다. |
세 성질이 전부 쓰였는지 확인. 반사성은 (\(\Leftarrow\))의 첫 줄, 대칭성은 (\(\Rightarrow\))의 첫 포함과 (\(\Leftarrow\))의 마지막 줄, 추이성은 (\(\Rightarrow\))의 두 포함에서 쓰였다. 셋 중 하나라도 없으면 그 줄이 그대로 비고 정리가 무너진다 — 문제 13이 그 확인이다.
확인 16. 이 증명의 \(R\)에 \(\equiv \pmod 3\)을, \(x\)에 \(1\)을, \(y\)에 \(4\)를 넣어 읽어
보자. (\(\Rightarrow\))의 첫 포함은 어떤 계산이 되는가.
답
“\(1 \equiv 4 \pmod 3\)이라 하자. \(z \in [1]\)이라 하자. 즉 \(1 \equiv z\)이다.
대칭성에 의해 \(4 \equiv 1\)이고, 추이성에 의해 \(4 \equiv z\)이다. 따라서 \(z \in [4]\)이다.”
\(z = 7\)을 넣으면 \(1 \equiv 7\), \(4 \equiv 1\), \(4 \equiv 7\)로 모든 줄이 성립한다.
증명의 어느 줄도 \(R\)이 합동이라는 사실을 쓰지 않았다 — 쓴 것은 세 성질이라는
자격뿐이므로, 같은 여섯 줄이 “같은 홀짝”에도 “원점에서 같은 거리”에도 그대로 작동한다.
예제 2.2 — 따름정리: 같거나 서로소#
명제. \(R\)이 \(A\) 위의 동치관계일 때, \([x] \cap [y] \neq \emptyset\)이면 \([x] = [y]\)이다.
이번에는 설계만 함께 하고, 본문은 완성본으로 본다.
확인 17. 번역표를 채워 보자.
가정: \([x] \cap [y] \neq \emptyset\) \(\to\) 공통 원소 \(z\)가 \(\underline{\quad}\)하고,
정의 37.2에 의해 \(\underline{\quad}\)이고 \(\underline{\quad}\)이다.
목표: \([x] = [y]\) \(\to\) 예제 2.1을 인용하면 \(\underline{\quad}\) 하나만 만들면 된다.
답
존재 / \(x\,R\,z\) / \(y\,R\,z\) / \(x\,R\,y\).
“공집합이 아니다”는 원소의 존재 주장이므로, 증명의 첫 동작은 그 원소에 이름을
붙이는 것이다(”\(z \in [x] \cap [y]\)라 하자”). 목표 쪽은 양방향 포함으로 직접 갈
필요가 없다 — 핵심 정리가 이미 \(x\,R\,y\)에서 \([x] = [y]\)로 가는 길을 뚫어 두었다.
확인 18. 손에 있는 것은 \(x\,R\,z\)와 \(y\,R\,z\)이고 목표는 \(x\,R\,y\)다.
두 문장을 그대로 이을 수 없는 이유와, 무엇을 먼저 해야 하는지 적어 보자.
답
두 문장 모두 \(z\)가 뒷자리에 있어 \(x \to z\)와 \(y \to z\)가 같은 방향으로 들어온다.
추이성은 \(x \to z \to y\) 꼴의 사슬을 요구하므로, 대칭성으로 \(y\,R\,z\)를 \(z\,R\,y\)로
뒤집어야 사슬이 이어진다. 예제 2.1의 확인 13과 같은 상황이고, 처방도 같다.
증명의 한 줄 |
왜 이 줄을 쓰는가? |
|---|---|
\([x] \cap [y] \neq \emptyset\)이라 가정하자. 그러면 \(z \in [x] \cap [y]\)인 \(z\)가 존재한다. |
“공집합이 아니다”는 존재 주장이다 — 원소에 이름을 붙이는 것이 첫 동작이다. |
교집합의 정의에 의해 \(z \in [x]\)이고 \(z \in [y]\)이므로, 정의 37.2에 의해 \(x\,R\,z\)이고 \(y\,R\,z\)이다. |
집합 차원의 정보를 관계 문장 둘로 번역한다(근거 ①). |
대칭성에 의해 \(z\,R\,y\)이고, 추이성(\(x\,R\,z\), \(z\,R\,y\))에 의해 \(x\,R\,y\)이다. |
두 문장의 \(z\)가 모두 뒷자리라 이어지지 않는다 — 대칭성으로 뒤집어 사슬을 만든다. |
핵심 정리(예제 2.1)에 의해 \([x] = [y]\)이다. \(\blacksquare\) |
원소 차원의 결과를 집합 차원으로 옮긴다(근거 ④). 양방향 포함을 다시 쓸 필요가 없다. |
이 결과가 하는 일. 두 동치류가 원소를 하나라도 공유하면 통째로 같은 집합이 된다 — 일부만 걸치는 상태가 불가능하다. 정의 37.3의 조건 ②가 여기서 나오고, 확인 5에서 얻은 \(x \in [x]\)가 ①과 ③을 준다. 세 조건이 모두 채워지므로 분할 정리가 성립한다 (그 문장을 세우는 일이 문제 8이다).
예제 2.3 — 유리수의 정체#
\(A = \mathbb{Z} \times (\mathbb{Z} - \{0\})\) 위에 관계를 정의한다.
기호 \(\sim\)는 “물결”로 읽고, \((a,b) \sim (c,d)\)는 “\((a,b)\)와 \((c,d)\)는 동치이다”로 읽는다. \(R\) 대신 \(\sim\)을 쓰는 것은 관계가 “같음의 기준”일 때의 관례이며, 뜻은 정의 37.1의 \(R\)과 다르지 않다.
이 관계가 \(A\) 위의 동치관계임은 문제 16에서 증명한다. 여기서는 동치관계임을 인정하고 동치류 하나를 계산한다. 이번에는 설계부터 스스로 해 보자.
명제. \([(1,2)] = \{(k, 2k) : k \in \mathbb{Z},\ k \neq 0\}\)이다.
확인 19. 번역표를 채워 보자.
목표: 집합 상등 \(\to\) 정의 27.1에 의해 \(\underline{\quad}\)과 \(\underline{\quad}\)을 각각 보인다.
소속 조건: \((c,d) \in [(1,2)]\) \(\to\) 정의 37.2에 의해 \(\underline{\quad}\) \(\to\) 관계의 정의에
의해 \(\underline{\quad}\).
답
\([(1,2)] \subseteq \{(k,2k) : k \in \mathbb{Z},\ k \neq 0\}\)과 그 반대 포함 /
\((1,2) \sim (c,d)\) / \(1 \cdot d = 2 \cdot c\), 곧 \(d = 2c\).
소속 조건이 \(d = 2c\)라는 등식 하나로 내려오므로, 남은 일은 그 등식을 만족하는
순서쌍의 생김새를 적는 것뿐이다. 무대의 조건 \(d \neq 0\)을 잊지 않는다.
증명. (\(\subseteq\)) \((c,d) \in [(1,2)]\)라 하자. 정의 37.2에 의해 \((1,2) \sim (c,d)\)이고, 관계의 정의에 의해 \(1 \cdot d = 2 \cdot c\), 곧 \(d = 2c\)이다. \((c,d) \in A\)이므로 \(d \neq 0\)이고, \(d = 2c\)에서 \(c \neq 0\)이다. 따라서 \((c,d) = (c, 2c)\)이고 \(c\)는 0이 아닌 정수이므로 오른쪽 집합에 속한다.
(\(\supseteq\)) \(k\)를 0이 아닌 정수라 하자. \(2k \neq 0\)이므로 \((k, 2k) \in A\)이다. \(1 \cdot 2k = 2 \cdot k\)이므로 \((1,2) \sim (k, 2k)\)이고, 정의 37.2에 의해 \((k,2k) \in [(1,2)]\)이다.
양방향 포함이 성립하므로 두 집합은 같다. \(\blacksquare\)
목록으로 적으면
이다. 각 순서쌍을 분수로 읽으면 \(\frac{-2}{-4},\ \frac{-1}{-2},\ \frac12,\ \frac24,\ \frac36\) — 초등학교의 “약분해도 같은 분수”가 정확히 이 동치관계이고, 유리수 \(\frac12\)의 정체는 순서쌍 하나가 아니라 동치류 하나다. 3주차에서 “\(\frac{a}{b}\) 꼴의 수”라고만 적었던 \(\mathbb{Q}\)는, 집합론의 언어로는 이 동치류들을 원소로 삼는 집합이다.
확인 20. \([(2,4)]\)는 \([(1,2)]\)와 같은 방인가. 목록을 비교하지 말고 핵심 정리로
판정해 보자.
답
같다. \(1 \cdot 4 = 2 \cdot 2\)이므로 \((1,2) \sim (2,4)\)이고, 핵심 정리에 의해
\([(1,2)] = [(2,4)]\)이다. 방 하나에 이름이 무한히 많으므로, 실제로 적을 때는
기약분수에 해당하는 대표원 하나를 골라 쓰는 관례를 따른다. 이 대표원 선택이
48주차에서 유리수를 셀 때 실제로 일한다.
관찰 — 같은 뼈대#
세 예제는 소재가 다르지만 절차가 같다. 대응표의 빈칸을 채워 보자.
확인 21. 각 단계에 해당하는 문장을 예제에서 찾아 아래 표의 빈칸 (1)(2)(3)을 채워 보자.
단계 |
예제 2.1 (\(\Rightarrow\)) |
예제 2.2 |
예제 2.3 |
|---|---|---|---|
① 방의 상등을 어떻게 다루는가 |
양방향 포함(정의 27.1)으로 쪼갠다 |
핵심 정리를 인용해 \(x\,R\,y\) 하나로 바꾼다 |
\(\underline{\quad(1)\quad}\) |
② 소속을 관계 문장으로 번역 |
\(z \in [x]\) \(\leftrightarrow\) \(x\,R\,z\) |
\(z \in [x] \cap [y]\) \(\leftrightarrow\) \(x\,R\,z\)이고 \(y\,R\,z\) |
\(\underline{\quad(2)\quad}\) |
③ 목표 문장을 만드는 도구 |
대칭성과 추이성 |
\(\underline{\quad(3)\quad}\) |
관계의 정의(\(ad = bc\))로 직접 계산 |
답
(1) 양방향 포함(정의 27.1)으로 쪼갠다.
(2) \((c,d) \in [(1,2)]\) \(\leftrightarrow\) \((1,2) \sim (c,d)\) \(\leftrightarrow\) \(d = 2c\).
(3) 대칭성과 추이성.
세 예제 모두 ① 집합 차원의 목표를 원소 차원으로 내리고 ② 소속을 관계 문장으로
번역한 뒤 ③ 세 성질(또는 관계의 정의)로 목표 문장을 만든다.
방금 확인한 절차에 이름을 붙인다.
백지 암기 대상
동치류 다루기의 3단계 틀
① 방의 상등 \([x] = [y]\)는 집합 상등이므로 양방향 포함으로 내려간다 — 또는 핵심 정리로 관계 문장 하나로 바꾼다 \(\to\) ② 소속 \(z \in [x]\)를 정의 37.2로 관계 문장 \(x\,R\,z\)로 번역한다 \(\to\) ③ 대칭성으로 방향을 맞추고 추이성으로 사슬을 이어 목표 문장을 만든다.
이 틀은 다음 주에 \(\mathbb{Z}_n\)의 연산이 잘 정의되는지 검사할 때 그대로 다시 쓴다.
빈칸 사다리 — 지지대를 하나씩 빼며#
필사에서 자립으로 넘어가는 다리다. 훈련이 진행될수록 빈칸이 커진다. 베끼지 말고 빈칸만 스스로 채운다. 답은 해설(§6)에 있다 — 다 채운 뒤에 대조한다.
훈련 1 ●○○ — 수식 빈칸#
\(\mathbb{Z}\) 위의 관계 “같은 홀짝”(\(x\,R\,y \iff x \equiv y \pmod 2\))에 대해 다음을 채운다. 이 관계는 세 칸이 모두 ✓이므로(§1.2의 표) 동치류를 말할 자격이 있다.
(1) \([0] = \{\underline{\quad(1)\quad}\}\) — 말로 하면 \(\underline{\quad(2)\quad}\) 전체.
(2) \([1] = \{\underline{\quad(3)\quad}\}\) — 말로 하면 \(\underline{\quad(4)\quad}\) 전체.
(3) 대표원을 \(0\) 또는 \(1\)로 바꿔 적으면 \([4] = [\underline{\quad(5)\quad}]\)이고 \([-3] = [\underline{\quad(6)\quad}]\)이다. 각각 핵심 정리의 어느 조건을 확인해 얻는가.
(4) 서로 다른 동치류는 \(\underline{\quad(7)\quad}\)개이고, 이들이 \(\mathbb{Z}\)의 \(\underline{\quad(8)\quad}\)을 이룬다.
훈련 2 ●●○ — 수식과 근거를 함께#
이번에는 근거 문장도 빈칸이다.
명제. \(R\)과 \(S\)가 모두 \(A\) 위의 동치관계이면 \(R \cap S\)도 \(A\) 위의 동치관계이다.
증명. (반사) 임의의 \(x \in A\)에 대해, \(R\)이 반사적이므로 \((x,x) \in R\)이고 \(S\)가 반사적이므로 \(\underline{\quad(1)\quad}\)이다. 교집합의 정의에 의해 \((x,x) \in \underline{\quad(2)\quad}\)이다 ✓.
(대칭) \((x,y) \in R \cap S\)라 \(\underline{\quad(3)\quad}\)하자. 그러면 \((x,y) \in R\)이고 \((x,y) \in S\)이다. \(R\)과 \(S\) 각각의 \(\underline{\quad(4)\quad}\)에 의해 \((y,x) \in R\)이고 \((y,x) \in S\)이므로 \((y,x) \in R \cap S\)이다 ✓.
(추이) \((x,y) \in R \cap S\)이고 \((y,z) \in R \cap S\)라 하자. \(R\) 안에서 \(\underline{\quad(5)\quad}\)에 의해 \((x,z) \in R\)이고, \(S\) 안에서도 같은 근거로 \((x,z) \in S\)이다. 따라서 \(\underline{\quad(6)\quad}\)이다 ✓.
세 성질이 모두 성립하므로 \(R \cap S\)는 \(\underline{\quad(7)\quad}\)이다. \(\blacksquare\)
(36주차 문제 16의 “mod 2이면서 동시에 mod 3”인 관계가 이 명제의 특수한 경우다.)
훈련 3 ●●● — 뼈대만 남기고#
이번에는 3단계 틀의 각 칸을 통째로 채운다.
명제. \(R\)이 \(A\) 위의 동치관계이고 \([x] \neq [y]\)이면 \([x] \cap [y] = \emptyset\)이다.
증명의 뼈대.
① 증명 방식의 선택과 그 이유: \(\underline{\quad(1)\quad}\)
② 뒤집은 명제의 가정에서 얻는 관계 문장들: \(\underline{\quad(2)\quad}\)
③ 목표 도달과 마무리: \(\underline{\quad(3)\quad}\)
(결론이 “\(\emptyset\)이다”라는 부정형이므로 직접 가면 다루기 어렵다. 어느 서식으로 바꾸면 손에 원소가 하나 생기는지 생각해 본다. 이 훈련이 문제 8의 조건 ② 부분의 예행연습이다.)
연습문제 (20문항)#
해설을 보기 전에 문제당 최소 10분 스스로 시도한다. 막히면 곧바로 풀이를 읽지 말고, 해설의 ‘접근’까지만 읽고 다시 시도한다 \(\to\) 그래도 안 되면 풀이를 읽는다. 동치류가 나오는 증명 문제는 반드시 §2의 3단계 틀부터 적고 시작한다.
이번 주의 채점 기준
답이 아니라 근거가 점수다. “\([4] = [0]\)이다(맞음)”는 0점이고,
“\(4 \equiv 0 \pmod 2\)이므로 핵심 정리에 의해 \([4] = [0]\)이다”가 만점이다.
특히 동치류를 다루는 문제에서는 어느 줄이 반사성, 어느 줄이 대칭성, 어느 줄이
추이성인지 표시한다 — 문제 8과 문제 13이 그 표시를 직접 묻는다.
난이도와 무관하게, 힌트 상자는 5분 이상 막힌 뒤에만 연다.
기본 ●○○#
1. [백지] 동치관계\(\cdot\)동치류\(\cdot\)분할의 정의를 쓰시오.
힌트
세 정의 모두 조각의 개수가 정해져 있다 — 동치관계는 성질 세 개, 동치류는
조건제시법 한 줄, 분할은 조건 ①②③이다. 분할의 ①(비공)을 빠뜨리는 경우가 많으므로
확인 8을 떠올린다.
2. \(\mathbb{Z}\) 위의 \(\equiv \pmod 4\)에 대해 서로 다른 동치류를 모두 나열하시오 (각각 원소 4개씩 예시).
힌트
대표원 후보는 4로 나눈 나머지다. 나머지가 몇 가지인지 세면 동치류의 개수가 나온다.
\([5]\)나 \([-1]\)은 새 동치류인지, 이미 적은 방의 다른 이름인지 핵심 정리로 판정한다.
3. 빈칸 훈련(홀짝)을 백지에서 완성하시오.
힌트
훈련 1의 답을 외워 옮기지 말고, \([0]\)의 소속 조건 “\(0 \equiv z \pmod 2\)”부터 다시
세운다. 조건을 세우면 목록은 따라 나온다.
4. \(A = \{1, 2, 3, 4, 5, 6\}\) 위의 관계 “\(x \equiv y \pmod 3\)”의 동치류를 모두 구하고, 분할의 세 조건을 확인하시오.
힌트
무대가 \(\mathbb{Z}\)가 아니라 유한집합 \(A\)다 — 동치류도 \(A\) 안에서만 모은다.
세 조건 확인은 말로 넘기지 말고 ① 각 조각이 비지 않았음 ② 쌍마다 교집합이 공집합
③ 합집합이 \(A\)임을 각각 계산으로 적는다.
5. 다음은 \(A = \{a, b, c, d\}\)의 분할인가? 아니라면 어느 조건 위반인지 지적하시오. (a) \(\{a, b\}, \{c\}, \{d\}\) (b) \(\{a, b\}, \{b, c\}, \{d\}\) (c) \(\{a\}, \{c, d\}\) (d) \(\{a, b\}, \emptyset, \{c, d\}\)
힌트
정의 37.3의 세 조건을 검사 항목으로 삼아 항목마다 통과\(\cdot\)탈락을 적는다.
탈락한 항목은 위반의 증거(공유하는 원소, 빠진 원소, 빈 조각)를 지목해야 완결된다.
6. 예제 2.1(핵심 정리)을 백지에 재현하시오.
힌트
뼈대는 네 덩어리다 — (\(\Rightarrow\))의 두 포함, 상등 선언, (\(\Leftarrow\)).
각 덩어리를 쓴 뒤 옆에 반사\(\cdot\)대칭\(\cdot\)추이 중 무엇을 썼는지 적어 두면 빠뜨린 부품이 보인다.
표준 ●●○#
7. 예제 2.2(같거나 서로소)를 백지에 재현하시오.
힌트
첫 문장은 “공집합이 아니다”를 원소의 존재로 바꾸는 문장이다. 마지막 문장은
양방향 포함이 아니라 핵심 정리의 인용이다.
8. 동치류 전체가 분할의 세 조건(비공\(\cdot\)서로소\(\cdot\)덮음)을 만족함을 — 각 조건이 어느 성질/정리에서 오는지 명시하며 — 증명하시오.
힌트
세 조건을 각각 한 문단으로 쓴다. ①과 ③의 재료는 같다(\(x \in [x]\))지만 결론이
다르므로 따로 적는다. ②는 “서로 다른 두 동치류”에 대한 주장이므로 대우로 가는
것이 짧다 — 훈련 3에서 만든 뼈대를 그대로 쓴다.
9. \(\mathbb{R}\) 위의 관계 \(x R y \iff x - y \in \mathbb{Z}\) (36주차 훈련 1)에 대해: (a) \(\left[\frac12\right]\)의 원소를 5개 나열하시오. (b) \([0]\)의 정체는? (c) \(\left[\frac12\right] = \left[\frac32\right]\)인 이유를 핵심 정리로 설명하시오.
힌트
소속 조건을 먼저 적는다: \(z \in \left[\frac12\right] \iff \frac12 - z \in \mathbb{Z}\).
이 조건을 만족하는 \(z\)는 \(\frac12\)에서 정수만큼 떨어진 실수다.
10. \(\mathbb{R}\) 위의 관계 \(x R y \iff |x| = |y|\)에 대해: (a) 동치관계임을 확인하시오 (등식 기반 — 한 줄씩). (b) \([3]\), \([0]\)을 구하시오. (c) 동치류들의 일반형을 묘사하시오.
힌트
관계의 조건이 등식이므로 세 성질이 전부 등호의 성질에서 상속된다. 각 성질마다
어떤 등식 조작을 했는지 한 줄씩 적는다. (c)에서는 \(x = 0\)인 경우를 따로 본다.
11. (분할 \(\to\) 동치관계) 집합 \(A\)의 분할이 주어졌을 때, “\(x\)와 \(y\)가 같은 조각에 속한다”로 정의한 관계가 동치관계임을 증명하시오. (반사에서 조건 ③, 추이에서 조건 ②가 소비된다 — 어디서인지 명시할 것)
힌트
추이가 관문이다. \(x, y\)가 조각 \(P\)에, \(y, z\)가 조각 \(Q\)에 있다고 하면 \(y\)가 두 조각에
동시에 들어간다 — 그러면 \(P \cap Q \neq \emptyset\)이고, 조건 ②를 대우로 읽으면
\(P\)와 \(Q\)에 대해 무엇을 말할 수 있는가.
12. \(A = \{1, 2, \dots, 10\}\) 위의 \(\equiv \pmod 4\): 동치류를 모두 나열하고 각각의 크기를 구하시오. (크기가 균등하지 않음을 관찰)
13. (성질 하나가 빠지면) \(\mathbb{Z}\) 위의 \(\le\)에 대해 “\([x] = \{z : x \le z\}\)”를 동치류처럼 정의해 보자. (a) \([1]\)과 \([2]\)를 구하시오. (b) \([1] \cap [2] \neq \emptyset\)인데 \([1] \neq [2]\)임을 확인하시오. (c) 예제 2.2의 증명이 \(\le\)에서 정확히 어느 줄에서 무너지는지 지적하시오.
힌트
(c)는 “\(\le\)는 동치관계가 아니다”로 끝내면 절반이다. 예제 2.2의 네 줄을 하나씩
손가락으로 짚으며 \(\le\)를 대입해 보고, 처음으로 참이 아니게 되는 줄을 특정한다.
\(\le\)가 가진 성질(반사\(\cdot\)추이)로는 통과되는 줄이 어디까지인지도 함께 적는다.
14. 36주차 문제 19(원점에서 같은 거리)의 동치류가 평면의 분할을 이룸을 확인하고, 동치류 전체의 모임이 무엇과 1:1 대응되는지 답하시오 (힌트: 반지름).
힌트
앞부분은 새 증명이 아니다 — 36주차 문제 19에서 동치관계임이 이미 판정되었으므로
문제 8의 일반론을 인용하면 끝난다. 뒷부분은 동치류 하나를 결정하는 수가 무엇인지
묻는 것이다. 원점 자신이 만드는 조각도 빠뜨리지 않는다.
도전 ●●●#
15. \(\mathbb{Z}\) 위의 관계 \(x R y \iff x^2 \equiv y^2 \pmod 3\)을 생각하자. (a) 동치관계임을 증명하시오 (합동의 성질 + 등식 상속). (b) 동치류가 몇 개인지 구하시오 (힌트: 17주차 문제 8 — \(n^2\)의 mod 3 나머지는 0 또는 1뿐).
힌트
(a)는 \(f(x)\)를 “\(x^2\)을 3으로 나눈 나머지”로 두면 \(x\,R\,y \iff f(x) = f(y)\)가 되어
문제 10과 같은 꼴이 된다. (b)는 \(f\)가 취할 수 있는 값의 개수가 곧 방의 개수라는
관찰이다 — 값 하나마다 방 하나가 대응하고, 그 값이 실제로 나타나는지 예를 들어
확인해야 개수가 확정된다.
이 문제가 빌려 쓰는 사실 — 영인수 성질 (문제 16용)
정수 \(x, y\)에 대해 \(xy = 0\)이면 \(x = 0\) 또는 \(y = 0\)이다. 25주차 문제 13에 딸린
상자에서 영인수 성질이라는 이름으로 다룬 사실이고, 이번 주에는 근거 ④로 인용해
쓴다. 문제 16의 추이성 증명에서 \(d(af - be) = 0\)과 \(d \neq 0\)으로부터 \(af = be\)를
끌어내는 자리가 그 인용 지점이다.
16. (유리수의 탄생) 예제 2.3의 관계 \((a,b) \sim (c,d) \iff ad = bc\)가 \(\mathbb{Z} \times (\mathbb{Z} - \{0\})\) 위의 동치관계임을 증명하시오. (추이성 힌트: \(ad = bc\), \(cf = de\)에서 \(adf = bcf = bde\) — \(d \neq 0\)으로 소거. “0이 아닌 정수의 소거”는 정당한가?)
힌트
반사와 대칭은 곱셈의 교환법칙과 등식 뒤집기로 각각 한 줄이다. 추이에서는
손에 있는 두 등식에 공통으로 등장하는 문자가 무엇인지 본다 — 그 문자를 소거해야
\(a, b, e, f\)만 남는다. 소거는 나눗셈이 아니라 위 상자의 영인수 성질로 정당화한다.
17. 두 동치관계 \(R, S\)가 같은 분할을 만들면 \(R = S\)임을 증명하시오. (힌트: \(x R y \iff\) “\(x, y\)가 같은 \(R\)-조각” — 핵심 정리)
힌트
관계는 순서쌍의 집합이므로(정의 36.1) \(R = S\)의 목표는 “모든 \(x, y\)에 대해
\(x\,R\,y \iff x\,S\,y\)”다. 왼쪽 끝에서 오른쪽 끝까지 \(\iff\)의 사슬을 만든다 —
핵심 정리가 관계를 동치류의 상등으로 바꾸고, 가정이 동치류를 조각으로 바꾼다.
이 문제가 되살리는 구분 — 반례와 가정 위반 (29주차 정의 29.2, 문제 18용)
정리가 “\(P\)이면 \(Q\)이다” 꼴일 때, \(Q\)가 거짓인 사례를 찾았다고 곧바로 반례가 되는
것은 아니다. 반례가 되려면 \(P\)도 함께 참이어야 한다. \(P\)가 거짓인 사례는 정리의
적용 대상 밖이므로, 그 사례에서 무슨 일이 일어나든 정리와 충돌하지 않는다.
이 두 검증(가정 만족\(\cdot\)결론 위배)의 서식이 정의 29.2이고, 30주차 확인 1\(\cdot\)2가 그것을
판별 동선에 넣었다. 문제 13과 문제 18은 같은 구분을 각각 \(\le\)와 \(R\)에서 확인한다.
18. (진단) 학생이 \(A = \{1,2,3,4\}\) 위의 관계 \(R = \{(1,1),(2,2),(3,3),(4,4),(1,2),(2,1),(2,3),(3,2)\}\)의 동치류를 “\([1] = \{1,2\}\), \([2] = \{1,2,3\}\), \([3] = \{2,3\}\)”으로 계산하고 동치류가 겹친다고 물었다. 무엇이 잘못인지 — 관계 자체의 결함을 — 진단하고, 겹침이 핵심 정리와 모순되지 않는 이유를 설명하시오.
힌트
계산 자체는 틀리지 않았다. 그러므로 결함은 계산 앞, 정의 37.2를 쓸 자격에 있다.
세 성질을 하나씩 검사해 실패하는 항목과 그 반례 사슬을 특정한다.
19. \(|A| = 3\)인 집합 \(A = \{a, b, c\}\)의 분할을 모두 나열하시오 (5개). 따라서 \(A\) 위의 동치관계는 정확히 몇 개인가? (동치관계 \(\longleftrightarrow\) 분할의 1:1 대응 사용)
힌트
빠뜨림 없이 세려면 기준이 필요하다. 조각의 크기 배분으로 경우를 나눈다 —
\(3\) / \(2+1\) / \(1+1+1\)의 세 가지뿐이고, 가운데 배분에서만 어느 두 원소를 묶는지의
선택이 남는다. 뒷부분은 문제 11과 문제 17이 함께 만드는 1:1 대응을 인용한다.
20. (서술) (a) “동치관계와 분할은 같은 정보의 두 얼굴”을 양방향 대응(동치류 만들기 / 같은-조각 관계 만들기)으로 두 문장 이내 설명하시오. (b) 20주차 문제 20에서 “같음의 조건을 느슨하게 바꾼 세계마다 새로운 산술이 생긴다”고 했다 — 다음 주(\(\mathbb{Z}_n\))에 무엇이 만들어질지, 동치류의 언어로 예고를 써 보시오.
백지 재현 — 복습 프로토콜#
권장 일정 — 1~3일차: §0~§4 학습과 연습문제 / 4일차: 1차 재현 / 5일차: 완전 백지 재현. 재현은 두 번으로 나눈다. 한 번에 완전 백지로 가지 않는다.
1차 시도 (4일차) — 틀 카드 허용. 동치류 다루기의 3단계 틀(§2 관찰)과 근거 목록(§1.8)만 펴 놓고, 예제 2.1(핵심 정리)을 처음부터 끝까지 적는다. 정의와 본문은 보지 않는다.
2차 시도 (5일차) — 완전 백지. 아무것도 보지 않고 수행한다.
동치관계\(\cdot\)동치류\(\cdot\)분할의 정의를 조각 그대로 정확히 썼다 (분할의 ①까지).
예제 2.1(핵심 정리)을 두 방향 모두 처음부터 끝까지 재현했다.
재현한 증명의 각 줄 옆에 반사\(\cdot\)대칭\(\cdot\)추이 중 무엇을 썼는지 표시했고, 셋이 모두 등장했다.
예제 2.2(같거나 서로소)를 재현했고, 마지막 줄이 핵심 정리의 인용임을 확인했다.
분할 정리의 세 조건이 각각 어느 사실에서 오는지 말했다.
분할에서 동치관계를 만드는 역방향(문제 11)을 설명했다.
유리수가 순서쌍들의 동치류라는 것을 \(\frac12\)의 예로 설명했다.
막힌 지점별 처방. 막힌 지점이 무엇을 다시 볼지 알려 준다.
막힌 지점 |
처방 |
|---|---|
정의가 정확히 기억나지 않는다 |
§1.3과 §1.6의 해부 표 — 조각의 역할과 함께 다시 외운다 |
\([x] = [y]\)를 어디서부터 손대야 할지 모르겠다 |
§2 관찰의 3단계 틀 ① — 집합 상등은 양방향 포함으로 내려간다 |
\(z \in [x]\) 다음 줄이 나오지 않는다 |
예제 2.1의 1단계 — 소속을 정의 37.2로 관계 문장으로 번역한다 |
관계 문장이 두 개 있는데 이어지지 않는다 |
확인 13과 확인 18 — 자리(앞\(\cdot\)뒤)를 보고 대칭성으로 방향을 맞춘다 |
세 성질 중 무엇을 쓸지 매번 헷갈린다 |
§1.3의 해부 표 — 반사는 자기 방 넣기, 대칭은 방향 맞추기, 추이는 잇기 |
분할의 세 조건이 잘 안 떠오른다 |
확인 7의 표 — 빠짐\(\cdot\)겹침\(\cdot\)빈 조각의 세 사유로 복원한다 |
겹치는 “동치류”를 보고 정리를 의심하게 된다 |
문제 18 앞 상자 — 가정 위반과 반례의 구분 |
하나라도 실패하면 그 항목만 다시 필사하고 다음날 재시도한다.
해설#
각 해설은 접근(문제 앞에서 무엇을 생각하는가)과 풀이로 나뉜다. 막혔을 때는 접근까지만 읽고 연필을 다시 잡는다.
빈칸 사다리 — 훈련 1#
(1) \(\dots, -4, -2, 0, 2, 4, \dots\) (2) 짝수 (3) \(\dots, -3, -1, 1, 3, 5, \dots\) (4) 홀수 (5) \(0\) (6) \(1\) (7) \(2\) (8) 분할
※ (5)(6)의 근거를 적는 것이 이 훈련의 핵심이다. \([4] = [0]\)은 “\(4 \equiv 0 \pmod 2\)이므로 핵심 정리에 의해”이고, \([-3] = [1]\)은 “\(-3 \equiv 1 \pmod 2\)(\(-3 - 1 = -4\)가 2의 배수)이므로 핵심 정리에 의해”다. 목록을 눈으로 비교해 같다고 적으면 무한집합에서는 검사가 끝나지 않는다 — 핵심 정리가 그 검사를 유한하게 만든다. (8)에서 두 방이 \(\mathbb{Z}\)를 덮고 겹치지 않는다는 것은 분할 정리의 특수한 경우다.
빈칸 사다리 — 훈련 2#
(1) \((x,x) \in S\) (2) \(R \cap S\) (3) 가정 (4) 대칭성 (5) 추이성 (6) \((x,z) \in R \cap S\) (7) 동치관계
※ 세 성질이 모두 “\(R\)에서 한 번, \(S\)에서 한 번, 그다음 교집합의 정의로 합치기”라는 같은 절차로 처리된다. 교집합의 정의(정의 5.1)가 세 번 모두 마지막 줄에서 일한다. 합집합에 대해서는 같은 논증이 통하지 않는다 — 추이 단계에서 \((x,y)\)가 \(R\)에만, \((y,z)\)가 \(S\)에만 속하는 경우를 이을 방법이 없기 때문이고, 실제로 반례가 존재한다.
빈칸 사다리 — 훈련 3#
(1) 대우로 증명한다. 결론이 “\([x] \cap [y] = \emptyset\)”이라는 부정형이라 직접 다루기 어려운 반면, 대우의 가정 “\([x] \cap [y] \neq \emptyset\)”은 원소 하나를 손에 쥐여 주므로 계산을 시작할 수 있다. 즉 “\([x] \cap [y] \neq \emptyset\)이면 \([x] = [y]\)”를 증명한다.
(2) \(z \in [x] \cap [y]\)라 하자. 교집합의 정의에 의해 \(z \in [x]\)이고 \(z \in [y]\)이므로, 정의 37.2에 의해 \(x\,R\,z\)이고 \(y\,R\,z\)이다.
(3) 대칭성에 의해 \(z\,R\,y\)이고, 추이성(\(x\,R\,z\), \(z\,R\,y\))에 의해 \(x\,R\,y\)이다. 핵심 정리에 의해 \([x] = [y]\)이다. 대우가 증명되었으므로 원명제도 성립한다. \(\blacksquare\)
※ 이 명제가 예제 2.2의 대우 판본이고, 문제 8의 조건 ②가 요구하는 것이 바로 이 꼴이다 (“서로 다른 두 동치류는 서로소”). 부정형 결론을 만나면 대우를 먼저 검토하는 것이 19주차에서 세우고 30주차의 판별 동선에서 다시 확인한 습관이다.
문제 1#
접근. 세 정의를 순서대로 적되, 각 정의가 몇 조각으로 되어 있는지 세면서 적는다. 동치관계는 성질 셋, 동치류는 조건제시법 한 줄, 분할은 조건 셋이다. 조각 수를 세는 것이 빠뜨림을 막는 가장 단순한 장치다.
풀이. (동치관계, 정의 37.1) 집합 \(A\) 위의 관계 \(R\)이 반사적이고 대칭적이고 추이적일 때 \(R\)을 \(A\) 위의 동치관계라 한다. — 세 성질을 함께 적으면 다음과 같다. 반사적: 모든 \(x \in A\)에 대해 \(x\,R\,x\). 대칭적: 모든 \(x, y \in A\)에 대해 \(x\,R\,y\)이면 \(y\,R\,x\). 추이적: 모든 \(x, y, z \in A\)에 대해 \(x\,R\,y\)이고 \(y\,R\,z\)이면 \(x\,R\,z\).
(동치류, 정의 37.2) \(A\) 위의 동치관계 \(R\)과 \(x \in A\)에 대해 \([x] = \{z \in A : x\,R\,z\}\)이며, \(x\)를 이 동치류의 대표원이라 한다.
(분할, 정의 37.3) 집합 \(A\)의 분할이란 \(A\)의 부분집합들의 모임으로서 ① 각 조각이 공집합이 아니고 ② 서로 다른 두 조각이 서로소이며 ③ 조각들의 합집합이 \(A\)인 것이다.
복기. 동치류의 정의에 “동치관계 \(R\)과”라는 전제가 들어 있다는 것과, 분할의 ①이 있다는 것 — 이 두 조각이 가장 자주 빠진다. 앞의 것이 빠지면 문제 18의 혼란이 생기고, 뒤의 것이 빠지면 문제 19의 개수가 두 배로 부풀어 동치관계와의 1:1 대응이 깨진다.
문제 2#
접근. 대표원 후보는 4로 나눈 나머지 \(0, 1, 2, 3\)이다. 나머지가 같은 정수끼리 한 방에 모이므로 방의 개수는 나머지의 가짓수와 같다. 새로 적은 방이 이미 있는 방과 같은지는 핵심 정리로 판정한다.
풀이. 소속 조건은 \(z \in [r] \iff r \equiv z \pmod 4 \iff 4 \mid (z - r)\)이다. 따라서
서로 다른 동치류는 이 4개다. 다른 이름은 새 방이 아니다 — 예컨대 \([5]\)는 \(5 \equiv 1 \pmod 4\)이므로 핵심 정리에 의해 \([5] = [1]\)이고, \([-1]\)은 \(-1 \equiv 3 \pmod 4\)이므로 \([-1] = [3]\)이다. 임의의 정수 \(n\)은 4로 나눈 나머지가 \(0, 1, 2, 3\) 중 하나이므로 네 방 중 하나에 반드시 속하고, 나머지는 하나뿐이므로 두 방에 동시에 속하지 않는다.
검산. 네 방의 합집합이 \(\mathbb{Z}\)이고 쌍마다 교집합이 공집합이다 — 분할 정리가 예측한 그대로다.
문제 3#
접근. 훈련 1의 답을 외워 옮기지 않는다. \([0]\)의 소속 조건을 정의 37.2로 다시 세우면 목록이 저절로 나온다.
풀이. 소속 조건은 \(z \in [0] \iff 0 \equiv z \pmod 2 \iff 2 \mid z\)이므로 \([0] = \{\dots, -4, -2, 0, 2, 4, \dots\}\) — 짝수 전체다. 마찬가지로 \(z \in [1] \iff 2 \mid (z - 1)\)이므로 \([1] = \{\dots, -3, -1, 1, 3, 5, \dots\}\) — 홀수 전체다. \(4 \equiv 0 \pmod 2\)이므로 핵심 정리에 의해 \([4] = [0]\)이고, \(-3 \equiv 1 \pmod 2\) (\(-3 - 1 = -4 = 2 \times (-2)\))이므로 \([-3] = [1]\)이다. 임의의 정수는 짝수이거나 홀수이므로 서로 다른 동치류는 2개이고, 두 방이 겹침 없이 \(\mathbb{Z}\)를 덮으므로 \(\mathbb{Z}\)의 분할을 이룬다.
복기. “\([4] = [0]\)”의 근거는 목록 비교가 아니라 \(4 \equiv 0\)이라는 관계 문장 하나다. 무한집합에서 방의 상등을 판정하는 유일한 실용적 방법이 핵심 정리다.
문제 4#
접근. 무대가 유한집합 \(A = \{1, \dots, 6\}\)이므로 동치류도 \(A\) 안에서만 모은다. \(\mathbb{Z}\)에서와 달리 각 방의 원소가 유한 개이고, 나머지가 0인 방의 대표원으로 \(A\) 안에서는 \(3\)을 쓰게 된다.
풀이. 3으로 나눈 나머지로 묶으면
이다(\([4] = [1]\), \([5] = [2]\), \([6] = [3]\)이므로 새 방은 없다). 분할의 세 조건을 확인한다. ① 세 조각 모두 원소를 2개씩 가지므로 공집합이 아니다. ② \(\{1,4\} \cap \{2,5\} = \emptyset\), \(\{1,4\} \cap \{3,6\} = \emptyset\), \(\{2,5\} \cap \{3,6\} = \emptyset\)으로 쌍마다 서로소다. ③ \(\{1,4\} \cup \{2,5\} \cup \{3,6\} = \{1,2,3,4,5,6\} = A\)이다. 세 조건이 모두 성립하므로 분할이다.
검산. 조각 크기의 합이 \(2 + 2 + 2 = 6 = |A|\)다 — 분할이면 크기의 합이 전체 크기와 같아야 하므로(14주차 덧셈 원리) 빠짐이나 겹침이 없음을 수로 재확인한 것이다.
문제 5#
접근. 정의 37.3의 세 조건을 검사 항목으로 삼는다. 탈락시킬 때는 위반의 증거 — 공유하는 원소, 빠진 원소, 빈 조각 — 를 지목해야 답이 완결된다.
풀이. (a) 분할이다. ① \(\{a,b\}, \{c\}, \{d\}\) 모두 비지 않았다. ② 쌍마다 교집합이 공집합이다. ③ 합집합이 \(\{a,b,c,d\} = A\)다. (b) 분할이 아니다 — 조건 ② 위반. \(\{a,b\} \cap \{b,c\} = \{b\} \neq \emptyset\)인데 두 조각이 서로 다르다. 원소 \(b\)가 두 조각에 동시에 속한다. (c) 분할이 아니다 — 조건 ③ 위반. 합집합이 \(\{a, c, d\}\)로 \(b\)가 어느 조각에도 속하지 않는다. (d) 분할이 아니다 — 조건 ① 위반. 둘째 조각이 공집합이다. (②와 ③은 통과한다 — 공집합은 어느 집합과도 서로소이고, 합집합에 아무것도 더하지 않는다.)
복기. (d)가 ②③을 통과한다는 점이 조건 ①의 존재 이유를 보여 준다. ①이 없으면 같은 나눔에 공집합을 붙인 목록이 별개의 분할로 한 번 더 세어지고, 문제 19의 개수가 두 배로 부풀어 동치관계와의 1:1 대응이 깨진다.
문제 6#
접근. 뼈대는 네 덩어리다 — (\(\Rightarrow\))의 두 포함, 상등 선언, (\(\Leftarrow\)). 쓰고 나서 각 줄 옆에 반사\(\cdot\)대칭\(\cdot\)추이 중 무엇을 썼는지 적어 셋이 모두 나왔는지 본다.
풀이. \(R\)이 \(A\) 위의 동치관계이고 \(x, y \in A\)라 하자.
(\(\Rightarrow\)) \(x\,R\,y\)라 가정한다. 먼저 \([x] \subseteq [y]\)를 보인다. \(z \in [x]\)라 하자. 정의 37.2에 의해 \(x\,R\,z\)이다. 대칭성에 의해 \(y\,R\,x\)이고, 추이성(\(y\,R\,x\)와 \(x\,R\,z\))에 의해 \(y\,R\,z\)이다. 따라서 정의 37.2에 의해 \(z \in [y]\)이고, \([x] \subseteq [y]\)이다. 다음으로 \([y] \subseteq [x]\)를 보인다. \(z \in [y]\)라 하자. 정의 37.2에 의해 \(y\,R\,z\)이고, 가정 \(x\,R\,y\)와의 추이성에 의해 \(x\,R\,z\)이므로 \(z \in [x]\)이다. 양방향 포함이 성립하므로(정의 27.1) \([x] = [y]\)이다.
(\(\Leftarrow\)) \([x] = [y]\)라 가정한다. 반사성에 의해 \(x\,R\,x\)이므로 정의 37.2에 의해 \(x \in [x]\)이고, 가정에 의해 \(x \in [y]\)이다. 정의 37.2에 의해 \(y\,R\,x\)이고, 대칭성에 의해 \(x\,R\,y\)이다.
두 방향이 모두 증명되었으므로 \(x\,R\,y \iff [x] = [y]\)이다. \(\blacksquare\)
복기. 소비처는 반사 1회((\(\Leftarrow\)) 첫 줄), 대칭 2회((\(\Rightarrow\)) 첫 포함과 (\(\Leftarrow\)) 마지막), 추이 2회((\(\Rightarrow\))의 두 포함)다. 재현 후 이 표시가 비는 칸이 있으면 그 성질을 쓰는 줄을 빠뜨린 것이다.
문제 7#
접근. 첫 문장은 “공집합이 아니다”를 원소의 존재로 바꾸는 문장이고, 마지막 문장은 양방향 포함이 아니라 핵심 정리의 인용이다. 이 두 끝을 먼저 적어 두면 가운데는 두 줄이다.
풀이. \(R\)이 \(A\) 위의 동치관계이고 \([x] \cap [y] \neq \emptyset\)이라 가정한다. 공집합이 아니므로 \(z \in [x] \cap [y]\)인 원소 \(z\)가 존재한다. 교집합의 정의에 의해 \(z \in [x]\)이고 \(z \in [y]\)이므로, 정의 37.2에 의해 \(x\,R\,z\)이고 \(y\,R\,z\)이다. 두 문장 모두 \(z\)가 뒷자리에 있으므로 그대로는 이어지지 않는다 — 대칭성에 의해 \(y\,R\,z\)를 \(z\,R\,y\)로 뒤집는다. 이제 \(x\,R\,z\)와 \(z\,R\,y\)가 사슬을 이루므로 추이성에 의해 \(x\,R\,y\)이다. 핵심 정리(예제 2.1)에 의해 \([x] = [y]\)이다. \(\blacksquare\)
복기. 대칭성이 필요한 이유는 두 가정의 \(z\)가 같은 자리에 있기 때문이다. 관계 문장을 이을 때는 문자의 자리(앞\(\cdot\)뒤)를 먼저 본다 — 이 습관 하나가 문제 13에서 \(\le\)가 무너지는 줄을 정확히 짚게 해 준다.
문제 8#
접근. 세 조건을 각각 한 문단으로 쓴다. ①과 ③은 재료가 같지만(\(x \in [x]\)) 결론이 다르므로 따로 적는다. ②는 “서로 다른 두 동치류”에 대한 주장이므로 대우로 간다 — 훈련 3에서 만든 뼈대를 그대로 쓴다.
풀이. \(R\)을 \(A\) 위의 동치관계라 하고, \(\mathcal{P}\)를 서로 다른 동치류 전체의 모임이라 하자.
(① 비공) 임의의 동치류 \([x] \in \mathcal{P}\)를 잡자. 반사성에 의해 \(x\,R\,x\)이고, 정의 37.2에 의해 \(x \in [x]\)이다. 따라서 \([x] \neq \emptyset\)이다.
(② 서로소) 보일 것은 “\([x], [y] \in \mathcal{P}\)이고 \([x] \neq [y]\)이면 \([x] \cap [y] = \emptyset\)이다”이다. 대우를 보인다 — 대우는 “\([x] \cap [y] \neq \emptyset\)이면 \([x] = [y]\)이다”이고, 이것이 곧 따름정리(예제 2.2) 그 자체다. 대우가 성립하므로 원명제도 성립한다. 즉 서로 다른 두 동치류는 서로소다(훈련 3에서 만든 뼈대가 이 문단이다).
(③ 덮음) \(\bigcup_{[x] \in \mathcal{P}} [x] \subseteq A\)는 각 동치류가 \(A\)의 부분집합이므로 성립한다. 반대로 임의의 \(a \in A\)에 대해, 반사성에 의해 \(a \in [a]\)이고 \([a]\)는 동치류이므로 \(\mathcal{P}\)에 속한다. 따라서 \(a\)는 합집합에 속하고 \(A \subseteq \bigcup [x]\)이다. 양방향 포함으로 합집합은 \(A\)와 같다.
세 조건이 모두 성립하므로 \(\mathcal{P}\)는 \(A\)의 분할이다. \(\blacksquare\)
복기. 각 조건의 출처를 한 줄로 정리하면 ① 반사성, ② 따름정리(그 안에서 대칭\(\cdot\)추이), ③ 반사성이다. 세 성질 중 반사성만이 두 번 등장하는데, 반사성이 각 원소를 자기 방에 넣는 유일한 부품이기 때문이다. 반사성이 빠지면 방이 비고 무대에 구멍이 남는다.
문제 9#
접근. 소속 조건을 먼저 적는다. \(z \in \left[\frac12\right] \iff \frac12 - z \in \mathbb{Z}\)이므로, \(\frac12\)에서 정수만큼 떨어진 실수 전체가 이 방의 원소다.
풀이. (a) \(\frac12 - z\)가 정수가 되는 \(z\)를 고르면 된다. \(z = \frac12\)(\(\frac12 - z = 0\)), \(z = \frac32\)(\(=-1\)), \(z = -\frac12\)(\(=1\)), \(z = \frac52\)(\(=-2\)), \(z = -\frac32\)(\(=2\))이므로
이고, 일반형은 \(\left[\frac12\right] = \left\{\frac12 + n : n \in \mathbb{Z}\right\}\)이다.
(b) \(z \in [0] \iff 0 - z \in \mathbb{Z} \iff z \in \mathbb{Z}\)이므로 \([0] = \mathbb{Z}\) — 정수 전체가 하나의 방이다.
(c) 관계 문장의 앞자리가 \(\frac12\)이므로 확인할 값은 \(\frac12 - \frac32\)다. \(\frac12 - \frac32 = -1 \in \mathbb{Z}\)이므로 \(\frac12\,R\,\frac32\)이다. 핵심 정리에 의해 \(\left[\frac12\right] = \left[\frac32\right]\)이다. 원소 두 개의 관계 하나를 확인한 것만으로 무한집합 두 개의 상등이 확정된다.
복기. 각 동치류는 “소수 부분이 같은 실수 전체”이고, 대표원을 구간 \([0,1)\)에서 하나씩 고를 수 있다. 20주차의 시계가 12시간마다 같은 눈금을 가리키는 것의 실수 판본이다.
문제 10#
접근. 관계의 조건이 등식 \(|x| = |y|\)이므로, 세 성질이 전부 등호의 성질에서 상속된다. 성질마다 어떤 등식 조작을 했는지 한 줄씩 적는다. (c)에서는 \(x = 0\)인 경우를 따로 본다.
풀이. (a) (반사) 임의의 \(x \in \mathbb{R}\)에 대해 \(|x| = |x|\)이므로 \(x\,R\,x\)이다 — 등호의 반사성. (대칭) \(x\,R\,y\)라 하면 \(|x| = |y|\)이고, 등식의 양변을 바꾸면 \(|y| = |x|\)이므로 \(y\,R\,x\)이다. (추이) \(x\,R\,y\)이고 \(y\,R\,z\)라 하면 \(|x| = |y|\)이고 \(|y| = |z|\)이므로, 등식을 이으면 \(|x| = |z|\)이고 \(x\,R\,z\)이다. 세 성질이 모두 성립하므로 동치관계다.
(b) \(z \in [3] \iff |3| = |z| \iff |z| = 3 \iff z = 3\) 또는 \(z = -3\)이므로 \([3] = \{3, -3\}\)이다. \(z \in [0] \iff |z| = 0 \iff z = 0\)이므로 \([0] = \{0\}\)이다.
(c) \(x \neq 0\)이면 \(|z| = |x|\)의 해가 \(z = x\)와 \(z = -x\)의 두 개이므로 \([x] = \{x, -x\}\)로 원소가 2개다. \(x = 0\)이면 \([0] = \{0\}\)으로 원소가 1개다. 따라서 수직선은 “원점 대칭인 두 점의 쌍들”과 “원점 하나”로 분할된다.
복기. 관계의 조건이 “어떤 값이 같다”는 꼴이면 세 성질은 항상 등호에서 상속된다 — 따로 증명할 것이 없다시피 하다. 문제 15가 같은 구조의 다른 사례이고, 그때는 값이 “\(x^2\)의 mod 3 나머지”로 바뀔 뿐이다. 크기가 다른 동치류가 한 분할 안에 공존한다는 점은 문제 12에서도 관찰된다 — 분할은 균등 분배를 요구하지 않는다.
문제 11#
접근. 세 성질을 각각 분할의 조건에서 끌어온다. 반사는 ③(모든 원소가 어느 조각엔가 속함), 대칭은 “같은 조각”이라는 표현 자체의 좌우 무관함, 추이는 ②(서로 다른 조각은 서로소)의 대우다. 추이가 관문이므로 여기에 시간을 쓴다.
풀이. \(\mathcal{P}\)를 \(A\)의 분할이라 하고, 관계 \(R\)을 “\(x\,R\,y \iff\) 어떤 조각 \(P \in \mathcal{P}\)가 있어 \(x \in P\)이고 \(y \in P\)”로 정의한다.
(반사) 임의의 \(x \in A\)를 잡자. 분할의 조건 ③에 의해 조각들의 합집합이 \(A\)이므로 \(x\)가 속하는 조각 \(P \in \mathcal{P}\)가 존재한다. 이 \(P\)에 대해 \(x \in P\)이고 \(x \in P\)이므로 정의에 의해 \(x\,R\,x\)이다.
(대칭) \(x\,R\,y\)라 하자. 정의에 의해 어떤 조각 \(P\)가 있어 \(x \in P\)이고 \(y \in P\)이다. 같은 \(P\)에 대해 \(y \in P\)이고 \(x \in P\)이므로 \(y\,R\,x\)이다. (정의의 조건이 \(x\)와 \(y\)의 순서에 무관하므로 새로 할 일이 없다.)
(추이) \(x\,R\,y\)이고 \(y\,R\,z\)라 하자. 정의에 의해 조각 \(P\)가 있어 \(x, y \in P\)이고, 조각 \(Q\)가 있어 \(y, z \in Q\)이다. 그러면 \(y \in P \cap Q\)이므로 \(P \cap Q \neq \emptyset\)이다. 분할의 조건 ②는 “서로 다른 두 조각은 서로소”이므로, 그 대우에 의해 서로소가 아닌 두 조각은 같다 — 즉 \(P = Q\)이다. 따라서 \(x \in P\)이고 \(z \in Q = P\)이므로, 이 한 조각 \(P\)가 \(x\,R\,z\)의 증인이 된다.
세 성질이 모두 성립하므로 \(R\)은 \(A\) 위의 동치관계다. \(\blacksquare\)
복기. ③이 반사를, ②가 추이를 책임진다. 조건 ①(비공)은 이 증명에서 쓰이지 않는데, 빈 조각이 있어도 관계 자체는 동치관계로 남기 때문이다. ①이 일하는 곳은 관계가 아니라 분할을 세는 자리다(문제 19). 조건과 성질의 대응이 정확히 어긋나지 않는다는 점이, 동치관계와 분할이 같은 정보라는 주장의 절반이다.
문제 12#
접근. 4로 나눈 나머지로 묶되, 무대가 \(\{1, \dots, 10\}\)이므로 각 방의 원소를 그 안에서만 센다. 10이 4의 배수가 아니므로 방의 크기가 균등하지 않을 것을 미리 예상할 수 있다.
풀이. 나머지가 1인 수는 \(1, 5, 9\), 나머지가 2인 수는 \(2, 6, 10\), 나머지가 3인 수는 \(3, 7\), 나머지가 0인 수는 \(4, 8\)이다. 따라서
이고, 서로 다른 동치류는 4개이며 크기는 각각 \(3, 3, 2, 2\)다. 크기가 균등하지 않다 — 무대의 크기 10이 4로 나누어떨어지지 않기 때문이고, 나머지 \(1, 2\)에 해당하는 방만 원소를 하나씩 더 받는다.
검산. 크기의 합이 \(3 + 3 + 2 + 2 = 10 = |A|\)다. 분할이면 조각 크기의 합이 전체 크기와 같아야 하므로(14주차 덧셈 원리), 빠뜨린 원소나 중복이 없음을 수로 확인한 것이다.
복기. 분할은 “똑같이 나눈다”가 아니라 “빠짐없이 겹침 없이 나눈다”이다. 문제 10의 \([x] = \{x, -x\}\)와 \([0] = \{0\}\)도 같은 관찰이었다.
문제 13#
접근. \(\le\)는 반사적\(\cdot\)추이적이지만 대칭적이 아니다. 그러므로 예제 2.2의 증명에서 대칭성을 쓰는 줄이 유일한 고장 지점이다. (c)에서는 “동치관계가 아니다”로 끝내지 말고, 증명의 네 줄에 \(\le\)를 대입해 가며 처음 참이 아니게 되는 줄을 특정한다.
풀이. (a) \([1] = \{z \in \mathbb{Z} : 1 \le z\} = \{1, 2, 3, 4, \dots\}\)이고 \([2] = \{z \in \mathbb{Z} : 2 \le z\} = \{2, 3, 4, 5, \dots\}\)이다.
(b) \(2 \in [1]\)이고 \(2 \in [2]\)이므로 \([1] \cap [2] \neq \emptyset\)이다(실제로 교집합은 \(\{2,3,4,\dots\}\)로 무한집합이다). 그런데 \(1 \in [1]\)이고 \(1 \notin [2]\)(\(2 \le 1\)이 거짓)이므로 \([1] \neq [2]\)이다. 따라서 “같거나 서로소”가 성립하지 않는다.
(c) 예제 2.2의 증명을 \(\le\)에 대입해 한 줄씩 따라간다. 첫 줄 “\(z \in [x] \cap [y]\)인 \(z\)가 존재한다”는 참이다(\(z = 2\)). 둘째 줄 “\(x \le z\)이고 \(y \le z\)이다”도 참이다 (\(1 \le 2\), \(2 \le 2\)). 셋째 줄 “대칭성에 의해 \(z\,R\,y\)이다”에서 무너진다 — \(\le\)에는 대칭성이 없으므로 \(2 \le 2\)에서 얻을 것이 없고, 일반적으로 \(z \le y\)를 보장할 수 없다(\(x = 1\), \(y = 2\), \(z = 5\)이면 \(5 \le 2\)는 거짓이다). 사슬 \(x \le z \le y\)가 만들어지지 않으므로 넷째 줄의 추이성도 발동하지 못한다.
복기. 정의 37.1의 세 성질은 검사 항목이 아니라 정리의 부품이다. 부품 하나를 빼면 그 부품을 쓰던 줄이 그대로 비고, 그 줄이 없으면 결론이 나오지 않는다. 여기서 얻은 겹침은 따름정리의 반례가 아니다 — \(\le\)는 동치관계가 아니므로 따름정리의 가정을 만족하지 않고, 적용 대상 밖이다(문제 18 앞 상자의 구분).
문제 14#
접근. 앞부분은 새 증명이 아니다. 36주차 문제 19에서 이 관계가 반사\(\cdot\)대칭\(\cdot\)추이임이 이미 판정되었으므로, 문제 8의 일반론을 인용하면 분할임이 따라온다. 뒷부분은 동치류 하나를 결정하는 수가 무엇인지 묻는 것이다.
풀이. 평면의 점 집합을 \(\Pi\)라 하고 \(P\,R\,Q \iff |OP| = |OQ|\)라 하자. 36주차 문제 19에 의해 \(R\)은 \(\Pi\) 위의 동치관계다(조건이 등식이므로 세 성질이 등호에서 상속된다). 따라서 분할 정리(문제 8)에 의해 서로 다른 동치류 전체는 \(\Pi\)의 분할을 이룬다.
동치류의 정체는 \([P] = \{Q \in \Pi : |OQ| = |OP|\}\)이므로, \(|OP| = r > 0\)이면 \([P]\)는 원점 중심 반지름 \(r\)인 원이고, \(P\)가 원점이면 \([O] = \{O\}\)(반지름 0인 조각)이다. 평면은 원점 하나와 원점을 중심으로 하는 동심원들로 빠짐없이 겹침 없이 덮인다.
동치류 하나는 반지름 하나로 완전히 결정되고, 반지름이 다르면 동치류도 다르다. 따라서 동치류 전체의 모임은 가능한 거리 값들의 집합 \([0, \infty)\)와 1:1 대응한다 — 대응은 \([P] \leftrightarrow |OP|\)이다.
복기. “동치류들의 집합”을 하나의 새 집합으로 보고 그 집합이 무엇과 대응되는지 묻는 시선이 다음 주의 문법이다. 여기서는 동심원들의 모임이 반지름의 집합과 대응했고, 다음 주에는 mod \(n\)의 동치류들의 모임 \(\mathbb{Z}_n\)이 그 자체로 연산의 무대가 된다.
문제 15#
접근. (a) \(f(x)\)를 “\(x^2\)을 3으로 나눈 나머지”로 두면 \(x\,R\,y \iff f(x) = f(y)\)가 되어 문제 10과 같은 구조다 — 세 성질이 등호에서 상속된다. (b) 값이 몇 가지냐가 방이 몇 개냐를 결정한다. 17주차 문제 8이 값의 가짓수를 준다.
풀이. (a) \(f(x)\)를 \(x^2\)을 3으로 나눈 나머지라 하면, \(x^2 \equiv y^2 \pmod 3\)은 \(f(x) = f(y)\)와 같은 뜻이다. (반사) \(f(x) = f(x)\)이므로 \(x\,R\,x\)이다. (대칭) \(f(x) = f(y)\)이면 등식의 양변을 바꿔 \(f(y) = f(x)\)이므로 \(y\,R\,x\)이다. (추이) \(f(x) = f(y)\)이고 \(f(y) = f(z)\)이면 등식을 이어 \(f(x) = f(z)\)이므로 \(x\,R\,z\)이다. 세 성질이 성립하므로 동치관계다.
(b) 17주차 문제 8에 의해 임의의 정수 \(n\)에 대해 \(n^2\)을 3으로 나눈 나머지는 0 또는 1뿐이므로 \(f\)의 값은 두 가지다. 두 값이 실제로 모두 나타난다 — \(f(3) = 0\)이고 \(f(1) = 1\)이다. 따라서 방은 \([3]\)과 \([1]\)의 두 개다. 정체를 적으면, 17주차 문제 8의 경우 나누기에서 \(3 \mid n\)이면 \(n^2 \equiv 0\)이고 \(3 \nmid n\)이면 \(n^2 \equiv 1\)이었으므로
이며 동치류는 2개다.
검산. \(1\,R\,2\)인가. \(1^2 = 1 \equiv 1\)이고 \(2^2 = 4 \equiv 1 \pmod 3\)이므로 참이다 — \(1\)과 \(2\)가 같은 방에 있다. \(\equiv \pmod 3\) 자체에서는 \([1] \neq [2]\)였는데 여기서는 한 방이다. 관계가 바뀌면 분할도 바뀐다.
복기. “어떤 함숫값이 같다”는 꼴의 관계는 항상 동치관계이고, 동치류의 개수는 그 함수가 실제로 취하는 값의 개수와 같다. 문제 10(\(|x|\)), 문제 14(\(|OP|\)), 문제 15 (\(x^2 \bmod 3\))가 모두 이 하나의 틀이다. 44주차에서 이 틀이 함수의 언어로 다시 정리된다.
문제 16#
접근. 반사와 대칭은 곱셈의 교환법칙과 등식 뒤집기로 각각 한 줄이다. 추이가 본체다 — 가정 두 식에 공통으로 나오는 문자 \(d\)를 소거해야 \(a, b, e, f\)만 남는다. 소거는 나눗셈이 아니라 영인수 성질(문제 16 앞 상자)로 정당화한다. 무대의 조건 \(b, d, f \neq 0\)이 그 소거의 자격을 준다.
풀이. \(A = \mathbb{Z} \times (\mathbb{Z} - \{0\})\)이고 \((a,b) \sim (c,d) \iff ad = bc\)라 하자.
(반사) 임의의 \((a,b) \in A\)에 대해 곱셈의 교환법칙에 의해 \(ab = ba\)이므로 \((a,b) \sim (a,b)\)이다.
(대칭) \((a,b) \sim (c,d)\)라 하자. 즉 \(ad = bc\)이다. 목표는 \((c,d) \sim (a,b)\), 곧 \(cb = da\)이다. 교환법칙과 가정에 의해 \(cb = bc = ad = da\)이므로 성립한다.
(추이) \((a,b) \sim (c,d)\)이고 \((c,d) \sim (e,f)\)라 하자. 즉 \(ad = bc\)이고 \(cf = de\)이다. 첫 식의 양변에 \(f\)를 곱하면 \(adf = bcf\)이다. 여기에 \(cf = de\)를 대입하면 \(bcf = b(cf) = b(de) = bde\)이므로 \(adf = bde\)이다. 이항하면
이다. \((c,d) \in A\)이므로 \(d \neq 0\)이고, 영인수 성질에 의해 \(af - be = 0\), 곧 \(af = be\)이다. 따라서 \((a,b) \sim (e,f)\)이다.
세 성질이 모두 성립하므로 \(\sim\)은 \(A\) 위의 동치관계다. \(\blacksquare\)
검산. \((1,2) \sim (2,4)\)이고 \((2,4) \sim (3,6)\)인지 확인하면 \(1 \cdot 4 = 2 \cdot 2\), \(2 \cdot 6 = 4 \cdot 3\)으로 둘 다 참이고, 추이성이 예측하는 \((1,2) \sim (3,6)\)도 \(1 \cdot 6 = 2 \cdot 3\)으로 참이다.
복기. 소거를 “양변을 \(d\)로 나눈다”로 적으면 정수 세계를 벗어난다. 같은 일을 “이항 \(\to\) 인수분해 \(\to\) 영인수 성질”의 세 걸음으로 적으면 정수 안에서 끝난다 — 2주차에서 나눗셈 대신 곱셈 등식을 택한 이유가 여기서 다시 회수된다. 이 결과로 예제 2.3의 계산이 정당해지고, \(\mathbb{Q}\)가 이 동치류들의 집합으로 건설된다. 수 체계가 집합론 위에 서는 자리다.
문제 17#
접근. 관계는 순서쌍의 집합이므로(정의 36.1) 목표 \(R = S\)는 “모든 \(x, y \in A\)에 대해 \(x\,R\,y \iff x\,S\,y\)”와 같다. 핵심 정리가 관계를 동치류의 상등으로 바꾸고, 가정(같은 분할)이 동치류를 조각으로 바꾼다. \(\iff\)의 사슬을 왼쪽 끝에서 오른쪽 끝까지 잇는다.
풀이. \(R\)과 \(S\)가 \(A\) 위의 동치관계이고, 두 관계가 만드는 분할이 같다고 하자. 즉 \(\{[x]_R : x \in A\} = \{[x]_S : x \in A\} = \mathcal{P}\)이다. 먼저 각 \(x\)에 대해 \([x]_R = [x]_S\)임을 본다. \(x \in [x]_R\)이고(반사성), \([x]_R \in \mathcal{P}\)이며, 가정에 의해 \([x]_R\)은 \(S\)의 동치류이기도 하다 — 곧 어떤 \(w\)에 대해 \([x]_R = [w]_S\)이다. 그러면 \(x \in [w]_S\)이므로 \(w\,S\,x\)이고, 핵심 정리(\(S\)에 적용)에 의해 \([w]_S = [x]_S\)이다. 따라서 \([x]_R = [x]_S\)이다.
이제 임의의 \(x, y \in A\)에 대해
이다. 첫 \(\iff\)는 핵심 정리(\(R\)에 적용), 가운데 \(\iff\)는 방금 보인 \([x]_R = [x]_S\)와 \([y]_R = [y]_S\)의 대입, 마지막 \(\iff\)는 핵심 정리(\(S\)에 적용)다. 순서쌍의 소속 조건이 모든 \((x,y)\)에 대해 동치이므로 두 집합은 같다 — 즉 \(R = S\)이다. \(\blacksquare\)
복기. 문제 11이 “분할에서 동치관계를 만들 수 있다”를 주고, 문제 17이 “그 대응이 서로 다른 관계를 섞지 않는다”를 준다. 둘을 합치면 동치관계와 분할 사이의 대응이 1:1임이 확정되고, 문제 19에서 동치관계를 셀 때 분할을 세는 것으로 대신할 수 있는 근거가 된다.
문제 18#
접근. 학생의 계산 자체는 정의 37.2를 그대로 적용한 것이라 틀리지 않았다. 그러므로 결함은 계산보다 앞, 정의 37.2를 쓸 자격에 있다. 세 성질을 하나씩 검사한다.
풀이. 진단: \(R\)은 추이적이지 않다. \((1,2) \in R\)이고 \((2,3) \in R\)이므로 \(1\,R\,2\)이고 \(2\,R\,3\)인데, \((1,3) \notin R\)이므로 \(1\,R\,3\)이 아니다. 사슬은 있는데 지름길이 없다. (반사는 \((1,1),(2,2),(3,3),(4,4)\)가 모두 있으므로 성립하고, 대칭도 \((1,2)\)와 \((2,1)\), \((2,3)\)과 \((3,2)\)가 짝을 이루므로 성립한다. 실패하는 항목은 추이 하나다.)
따라서 \(R\)은 동치관계가 아니고, 정의 37.2의 전제(”\(A\) 위의 동치관계 \(R\)”)를 만족하지 않는다. 학생이 계산한 세 집합은 \(\{z : x\,R\,z\}\)라는 식의 값일 뿐 동치류가 아니다.
겹침이 핵심 정리와 모순되지 않는 이유: 핵심 정리와 따름정리는 모두 “\(R\)이 동치관계일 때”라는 가정 아래의 정리다. 이 \(R\)은 그 가정을 만족하지 않으므로 정리의 적용 대상이 아니고, 여기서 관찰된 겹침은 정리의 반례가 아니라 가정 위반의 증상이다. 반례가 되려면 가정(동치관계)이 참이면서 결론(같거나 서로소)이 거짓이어야 한다.
검산. 결함을 수리해 보면 진단이 확인된다. \((1,3)\)과 \((3,1)\)을 추가하면 \(R\)이 추이적이 되어 동치관계가 되고, 그때의 동치류는 \([1] = [2] = [3] = \{1,2,3\}\)과 \([4] = \{4\}\)로 겹침이 사라진다. 겹침의 원인이 정확히 추이성의 부재였음이 드러난다.
복기. 문제 13(\(\le\), 대칭 부재)과 이 문제(\(R\), 추이 부재)는 같은 유형이다 — 빠진 성질이 다르고 증상도 다르지만, 진단의 절차는 하나다. ① 세 성질을 검사해 실패 항목을 특정한다 ② 그 실패가 정리의 어느 줄을 비게 하는지 짚는다 ③ 관찰된 이상 현상을 반례가 아니라 가정 위반으로 분류한다.
문제 19#
접근. 빠뜨림 없이 세려면 기준이 필요하다. 조각 크기의 배분으로 경우를 나눈다 — \(|A| = 3\)이므로 배분은 \(3\) / \(2+1\) / \(1+1+1\)의 세 가지뿐이고, 가운데 배분에서만 어느 두 원소를 묶는지의 선택이 남는다.
풀이. (배분 \(3\)) 조각이 하나뿐이므로 \(\{a,b,c\}\) 하나다 — 1가지. (배분 \(2+1\)) 크기 2인 조각에 들어갈 두 원소를 고르면 나머지 하나가 자동으로 정해진다. 세 원소 중 둘을 고르는 방법이 3가지이므로 \(\{a,b\},\{c\}\) / \(\{a,c\},\{b\}\) / \(\{b,c\},\{a\}\) — 3가지. (배분 \(1+1+1\)) \(\{a\},\{b\},\{c\}\) 하나다 — 1가지.
따라서 분할은 \(1 + 3 + 1 = \) 5개다.
이 개수를 동치관계 쪽으로 옮기려면 대응이 1:1임을 확인해야 한다. 문제 8이 동치관계 \(R\)마다 분할 \(\Phi(R) = \{[x]_R : x \in A\}\)를 하나 주고, 문제 17이 이 사상 \(\Phi\)가 단사임을 준다(같은 분할을 만드는 두 동치관계는 같다). 전사성은 문제 11에서 만든 관계 \(R_{\mathcal{P}}\)의 동치류를 직접 계산하면 나온다 — 임의의 \(x \in A\)는 조건 ③에 의해 어떤 조각 \(P \in \mathcal{P}\)에 속하고, 조건 ②에 의해 그런 \(P\)는 유일하다. 따라서 \(x\)와 같은 조각에 속하는 원소 전체는 정확히 \(P\)이고, 곧 \([x]_{R_{\mathcal{P}}} = P\)이다. 조각마다 그 안의 원소를 대표원으로 잡으면 조각 전체가 동치류로 회수되므로 \(\Phi(R_{\mathcal{P}}) = \mathcal{P}\)다. 단사이고 전사이므로 \(\Phi\)는 1:1 대응이고, \(A\) 위의 동치관계도 정확히 5개다.
검산. 36주차 문제 2의 세는 방식대로 하면 \(|A| = 3\)일 때 \(A\) 위의 관계는 \(A \times A\)의 부분집합이므로, 4주차의 \(|\mathcal{P}(X)| = 2^{|X|}\)와 12주차 곱셈 원리에 의해 \(2^{3^2} = 2^9 = 512\)개다. 그중 동치관계는 5개뿐이다 — 세 성질이 얼마나 강한 제약인지가 수로 드러난다.
복기. 집합의 분할 개수를 벨 수(Bell number)라 하고 \(B_n\)으로 쓴다. 여기서 구한 것은 \(B_3 = 5\)이며, 크기 4에서는 \(B_4 = 15\)로 급격히 늘어난다. 세는 문제를 만나면 배분으로 경우를 나누는 것이 12~14주차에서 세운 기본 전략이고, 여기서도 그대로 작동했다.
문제 20#
접근. (a)는 문제 8(관계 \(\to\) 분할)과 문제 11(분할 \(\to\) 관계), 문제 17(왕복의 일치)을 한 문장으로 압축하는 서술이다. (b)는 “동치류들의 집합을 새 무대로 삼고 그 위에 연산을 얹는다”는 다음 주의 계획을 동치류의 언어로 적는 것이다.
풀이. (예시 답안)
(a) 동치관계가 주어지면 동치류를 모아 분할을 얻고(문제 8), 분할이 주어지면 “같은 조각에 속한다”는 관계로 동치관계를 얻는다(문제 11). 이 두 변환은 서로를 정확히 되돌리므로 — 문제 17이 한쪽(같은 분할을 주는 두 동치관계는 같다)을, 문제 19 풀이의 동치류 계산이 다른 쪽(\(R_{\mathcal{P}}\)의 동치류가 다시 \(\mathcal{P}\)의 조각들이다)을 보인다 — “같음의 기준”과 “그 기준으로 자른 결과”는 같은 정보를 다르게 적은 것이다.
(b) mod \(n\)의 동치류는 \([0], [1], \dots, [n-1]\)의 \(n\)개이고(문제 2가 \(n = 4\)의 경우다), 이들을 원소로 삼는 새 집합 \(\mathbb{Z}_n = \{[0], [1], \dots, [n-1]\}\) 위에 \([a] + [b] = [a+b]\), \([a][b] = [ab]\) 같은 연산을 정의하면, 원소가 수가 아니라 동치류인 새 산술이 생긴다 — 20주차의 시계 산술이 정식 무대를 얻는 것이다. 다만 방 하나에 이름이 여러 개이므로(\([1] = [5] = [-3]\), 문제 2의 mod 4), 연산의 결과가 어느 이름을 골랐느냐에 따라 달라지지 않는지를 먼저 확인해야 한다. 그 확인을 통과해야 위의 정의가 성립한다.
복기. (b)에서 지목한 물음 — 대표원을 바꿔도 결과가 같은가 — 이 다음 주의 주제인 “잘 정의됨”이다. 이번 주의 핵심 정리(\(x\,R\,y \iff [x] = [y]\))가 그 검사의 도구가 된다.
다음 주 예고: 동치류들의 집합 \(\mathbb{Z}_n = \{[0], [1], \dots, [n-1]\}\) 위에 덧셈과 곱셈을 얹는다. 원소가 수가 아니라 집합인 무대에서 연산을 정의하려면 대표원을 골라 계산해야 하는데, 방 하나에 이름이 여러 개이므로 “대표원을 바꿔도 결과가 같은가”라는 검문을 먼저 통과해야 한다. 이것이 잘 정의됨(well-defined) 이며, 이후의 모든 주차에서 집합 위에 무언가를 정의할 때마다 되풀이되는 절차다. 검문을 통과한 뒤에는 연산표를 그려 \(\mathbb{Z}_6\)에서 \([2][3] = [0]\)이 되는 현상 — 0이 아닌 두 원소의 곱이 0이 되는 현상 — 을 관찰하고, \(n\)이 소수일 때와 아닐 때 이 세계가 어떻게 달라지는지 비교한다.