# 39주차 — 관계 종합 + 백지 시험 (8부 총정리) :::{admonition} 이 주의 길잡이 :class: keybox **핵심 문장**: 관계 $\to$ 동치 $\to$ 분할 $\to$ 몫 세계 — 이 사슬이 8부의 전부다. **이 주의 위치**: 50주 과정의 39주차. 36~38주차(관계의 성질, 동치관계, 동치류와 분할, $\mathbb{Z}_n$)를 한 장의 지도로 묶고, 백지 시험 20문항으로 8부를 닫는다. 다음 파트(함수)의 기초 공사가 끝났는지 검사하는 주이기도 하다 — 함수도 관계의 일종이기 때문이다. **원서 대응**: BoP(Book of Proof) 11장(11.1~11.4) 종합 — 병행자 참고용이고, 이 교재는 원서 없이 읽을 수 있다. ::: ## 이번 주 목표 1. 8부의 사슬(관계의 성질 $\to$ 동치관계 $\to$ 동치류$\cdot$분할 $\to$ $\mathbb{Z}_n$)을 한 장의 지도로 정리한다. 1. **백지 시험 20문항**으로 8부를 수료한다 (권장 150분). 1. 함수 파트(40주차~)로 가는 다리를 확인한다. 본문의 **확인** 상자는 연필로 먼저 답하는 자리다. 바로 아래의 **답** 상자는(웹에서는 접혀 있다) 스스로 답한 뒤에 열어 대조한다. ## 준비 운동 (38주차 복습) 1. 잘 정의됨 검증의 4행 구조(이름 두 벌 $\to$ 합동 번역 $\to$ (C4)/(C5) $\to$ 역번역)를 재현하시오. 1. $\mathbb{Z}_6$의 영인수 쌍을 하나 제시하고, $\mathbb{Z}_5$에 영인수가 없는 이유의 뿌리를 말하시오. 1. $\mathbb{Z}_7$에서 $[3]$의 곱셈 역원을 구하시오. :::{admonition} 답 :class: quotebox dropdown **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부 지도 :::{admonition} 백지 암기 대상 :class: keybox **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에서 스스로 적는다. :::{container} quotebox **확인 1.** 동치관계의 세 성질 가운데 반사성만 빠지면, 핵심 정리 "$x R y \iff [x] = [y]$"의 어느 방향이 무너지는가. ::: :::{admonition} 답 :class: quotebox dropdown ($\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$는 거짓이다. ::: :::{container} quotebox **확인 2.** 분할의 세 조건 ① 비공 ② 서로소 ③ 덮음은 동치류의 어떤 사실에서 각각 나오는가. ::: :::{admonition} 답 :class: quotebox dropdown ① 비공: 반사성에 의해 $x \in [x]$이므로 어느 동치류도 비어 있지 않다. ② 서로소: "같거나 서로소" 정리(37주차 예제 2.2)에 의해 두 동치류가 원소를 하나라도 공유하면 통째로 같아지므로, 서로 다른 동치류는 서로소다. ③ 덮음: 다시 $x \in [x]$이므로 모든 $x$가 어떤 동치류에 속한다. 세 조건 가운데 둘이 반사성 하나에서 나온다. 반사성을 사소한 조건으로 보기 어려운 이유다. ::: :::{container} quotebox **확인 3.** $\mathbb{Z}_n$에서 연산을 정의할 때마다 "잘 정의됨"을 물어야 하는 근본 이유를 한 문장으로 적어 보자. ::: :::{admonition} 답 :class: quotebox dropdown $\mathbb{Z}_n$의 원소는 방(동치류)인데 연산은 방이 아니라 방의 이름(대표원)으로 계산하고, 한 방의 이름은 여러 개이기 때문이다 — $\mathbb{Z}_6$에서 $[2] = [8]$이다. 어느 이름을 골라 계산해도 결과가 같은 방이라는 보장이 (C4)와 (C5)이고, 그 보장이 없는 규칙은 같은 입력에 두 출력을 주므로 정의가 되지 못한다(문제 19(b)). :::