39주차 — 관계 종합 + 백지 시험 (8부 총정리)#
이 주의 길잡이
핵심 문장: 관계 \(\to\) 동치 \(\to\) 분할 \(\to\) 몫 세계 — 이 사슬이 8부의 전부다.
이 주의 위치: 50주 과정의 39주차. 36~38주차(관계의 성질, 동치관계, 동치류와 분할, \(\mathbb{Z}_n\))를 한 장의 지도로 묶고, 백지 시험 20문항으로 8부를 닫는다. 다음 파트(함수)의 기초 공사가 끝났는지 검사하는 주이기도 하다 — 함수도 관계의 일종이기 때문이다.
원서 대응: BoP(Book of Proof) 11장(11.1~11.4) 종합 — 병행자 참고용이고, 이 교재는 원서 없이 읽을 수 있다.
이번 주 목표#
8부의 사슬(관계의 성질 \(\to\) 동치관계 \(\to\) 동치류\(\cdot\)분할 \(\to\) \(\mathbb{Z}_n\))을 한 장의 지도로 정리한다.
백지 시험 20문항으로 8부를 수료한다 (권장 150분).
함수 파트(40주차~)로 가는 다리를 확인한다.
본문의 확인 상자는 연필로 먼저 답하는 자리다. 바로 아래의 답 상자는(웹에서는 접혀 있다) 스스로 답한 뒤에 열어 대조한다.
준비 운동 (38주차 복습)#
잘 정의됨 검증의 4행 구조(이름 두 벌 \(\to\) 합동 번역 \(\to\) (C4)/(C5) \(\to\) 역번역)를 재현하시오.
\(\mathbb{Z}_6\)의 영인수 쌍을 하나 제시하고, \(\mathbb{Z}_5\)에 영인수가 없는 이유의 뿌리를 말하시오.
\(\mathbb{Z}_7\)에서 \([3]\)의 곱셈 역원을 구하시오.
답
1. ① \([a] = [a']\), \([b] = [b']\)라 하자(같은 방의 두 이름). ② 핵심 정리로 \(a \equiv a'\), \(b \equiv b' \pmod n\)(합동으로 번역). ③ (C4)에 의해 \(a + b \equiv a' + b' \pmod n\)(곱이면 (C5)). ④ 핵심 정리로 \([a + b] = [a' + b']\)(방의 언어로 역번역). 곧 대표원을 어느 것으로 골라도 결과가 같은 방이므로 연산이 잘 정의된다.
2. \([2][3] = [6] = [0]\)인데 \([2] \neq [0]\)이고 \([3] \neq [0]\)이다. \(\mathbb{Z}_5\)에 영인수가 없는 뿌리는 5가 소수라는 것이고, 그 사실이 작동하는 통로는 유클리드 보조정리(33주차 문제 16에서 증명 없이 인정한 채로 두기로 한 사실이다)다 — \(p \mid ab\)이면 \(p \mid a\) 또는 \(p \mid b\)이므로, \([a][b] = [0]\)에서 곧바로 \([a] = [0]\) 또는 \([b] = [0]\)이 따라 나온다.
3. \([5]\)다. \(3 \cdot 5 = 15 = 7 \cdot 2 + 1\)이므로 \([3][5] = [15] = [1]\)이다.
자주 나오는 세 가지 답 — 1번 문항#
방금 쓴 답은 대개 다음 세 유형 중 하나다. 셋 다 옳은 부분이 있고, 셋 다 이번 주에 메울 정확한 간격이 있다.
유형 1 — 가운데 두 행을 건너뛰기. ① 이름 두 벌과 ③ (C4)만 적고, ② 합동으로
번역하는 행과 ④ 방의 언어로 역번역하는 행을 빼서 세 행으로 줄이는 경우가 많다. (C4)가 이 증명의 핵심 도구라는 판단은 정확하다 — 보존을 실제로 주는 것은 (C4) 하나뿐이다. 빠진 것은 왕복이다. (C4)는 합동에 대한 정리이고 증명해야 할 것은 방의 등식이므로, ②로 내려가고 ④로 올라오는 두 행이 없으면 “대표원을 어느 것으로 골라도 같은 방”이라는 증명 대상 자체가 진술되지 않는다.
유형 2 — 임의의 \(a, b\)로 바로 계산하기. \([a] = [a']\)에서 출발하지 않고
\([a] + [b] = [a+b]\)를 그대로 계산해 보이는 경우가 많다. 계산은 한 줄도 틀리지 않는다. 다만 그것은 규칙을 한 번 적용한 것이지 규칙이 대표원 선택에 무관함을 보인 것이 아니다 — 증명할 명제는 “한 방에 이름이 두 개”라는 가정 위에 서 있고, 그 가정을 세우지 않으면 검사할 대상 자체가 생기지 않는다.
유형 3 — 백지. 첫 문장이 무엇이어야 하는지가 정해져 있지 않아 손이 나가지
않는다. 첫 문장은 언제나 “같은 방의 두 이름을 잡자”이고, 그 뒤 세 행은 번역 \(\to\) 보존 정리 \(\to\) 역번역으로 고정되어 있다. 38주차 예제 2.1의 네 행을 첫 문장부터 그대로 필사한 뒤 다시 백지로 재현하는 것이 최단 경로다.
개념 — 8부 지도#
백지 암기 대상
**8부의 사슬 **
관계 (\(R \subseteq A \times A\), 36주차)
\(\to\) 세 성질(반사\(\cdot\)대칭\(\cdot\)추이) 판정 = 성립이면 증명, 불성립이면 반증
\(\to\) 셋 다 성립 = 동치관계 (37주차) \(\to\) 동치류 \([x]\) \(\to\) 핵심 정리(\(x R y \iff [x] = [y]\)) \(\to\) 분할
\(\to\) 동치류들의 집합에 연산 얹기 = 몫 세계 (\(\mathbb{Z}_n\), 38주차) — 이때 통과해야 하는 검문이 잘 정의됨
화살표마다 정리가 하나씩 놓여 있다. 성질 판정의 서식은 36주차, 핵심 정리와 “같거나 서로소” 정리는 37주차, 잘 정의됨의 4행 서식은 38주차에서 세웠다. 이 사슬은 대학 수학에서 여러 번 다시 나타난다 — 벡터공간의 몫, 위상공간의 몫, 군의 몫이 모두 “동치관계 \(\to\) 분할 \(\to\) 몫 + 잘 정의됨 검문”이라는 같은 구조의 변주다.
함수로 가는 다리. 함수 \(f : A \to B\)도 순서쌍들의 집합이다. 정의 36.1은 무대를 \(A \times A\)로 잡았지만, 무대를 \(A \times B\)로 넓히면 두 집합 사이의 관계가 된다. 함수가 그 가운데 어떤 조건을 더 붙인 것인지는 문제 20에서 스스로 적는다.
확인 1. 동치관계의 세 성질 가운데 반사성만 빠지면, 핵심 정리 “\(x R y \iff [x] = [y]\)”의 어느 방향이 무너지는가.
답
(\(\Leftarrow\)) 방향이 무너진다. \([x] = [y]\)에서 \(x R y\)를 끌어내는 통로는 “\(x \in [x]\)이므로 \(x \in [y]\), 곧 \(y R x\)”인데, 그 첫 걸음 \(x \in [x]\)의 근거가 바로 반사성이다(37주차 예제 2.1).
반례: \(A = \{1, 2\}\), \(R = \emptyset\). 확인할 쌍이 하나도 없으므로 대칭과 추이는 성립하지만 반사는 성립하지 않는다. 정의 37.2는 동치관계에 대해서만 동치류를 정의하므로 엄밀히는 여기서 동치류가 정의되지 않는다 — 37주차 문제 13처럼 \([x] = \{z : x\,R\,z\}\)라는 식만 형식적으로 빌려 쓴다. 이때 \([1] = [2] = \emptyset\)이어서 \([1] = [2]\)인데도 \(1 R 2\)는 거짓이다.
확인 2. 분할의 세 조건 ① 비공 ② 서로소 ③ 덮음은 동치류의 어떤 사실에서 각각 나오는가.
답
① 비공: 반사성에 의해 \(x \in [x]\)이므로 어느 동치류도 비어 있지 않다.
② 서로소: “같거나 서로소” 정리(37주차 예제 2.2)에 의해 두 동치류가 원소를 하나라도 공유하면 통째로 같아지므로, 서로 다른 동치류는 서로소다.
③ 덮음: 다시 \(x \in [x]\)이므로 모든 \(x\)가 어떤 동치류에 속한다.
세 조건 가운데 둘이 반사성 하나에서 나온다. 반사성을 사소한 조건으로 보기 어려운 이유다.
확인 3. \(\mathbb{Z}_n\)에서 연산을 정의할 때마다 “잘 정의됨”을 물어야 하는 근본 이유를 한 문장으로 적어 보자.
답
\(\mathbb{Z}_n\)의 원소는 방(동치류)인데 연산은 방이 아니라 방의 이름(대표원)으로 계산하고, 한 방의 이름은 여러 개이기 때문이다 — \(\mathbb{Z}_6\)에서 \([2] = [8]\)이다. 어느 이름을 골라 계산해도 결과가 같은 방이라는 보장이 (C4)와 (C5)이고, 그 보장이 없는 규칙은 같은 입력에 두 출력을 주므로 정의가 되지 못한다(문제 19(b)).