# C11주차 · 강의 — 예제 · 연습 · 해설 ## 예제 — 판정부터 함께 만들기 완성된 답안을 먼저 보이지 않는다. 백지에서 설계부터 한 줄씩 만든다. 각 단계에서 확인 상자의 빈칸을 연필로 먼저 채운 뒤 답을 연다. ### 예제 2.1 — 동치관계 판정 **명제.** $\mathbb{Z}$ 위의 관계 "$a \mathrel{R} b \iff a - b$가 짝수"는 동치관계이다. **설계 — 쓰기 전에 정하는 두 가지.** 가정이 주는 것(출발점)과 만들어야 할 것(도착점)을 먼저 정의로 번역한다. 이번 명제는 가정이 관계의 정의 한 줄뿐이고 도착점이 세 개다. | | **말** | **수식 번역** | |---|---|---| | 가정 (주어진 것) | $a \mathrel{R} b$ | $a - b = 2k$인 정수 $k$가 존재한다 | | 목표 (만들 것) | $R$가 동치관계 | $\underline{\quad(?)\quad}$ | :::{container} quotebox **확인 10.** 목표 칸의 빈칸을 채워 보자. "동치관계임을 보인다"를 정의 11.3으로 번역하면 무엇을 몇 개 증명해야 하는가. ::: :::{admonition} 답 :class: quotebox dropdown **세 개의 독립한 $\forall$ 명제** — 반사, 대칭, 추이를 각각 증명해야 한다. 정의 11.3은 세 성질을 "그리고"로 묶었으므로 하나라도 빠지면 결론이 나오지 않는다. 곧 이 답안은 세 개의 작은 증명이 나란히 놓인 형태가 되고, 각각은 $\forall$ 명제이므로 선택법으로 임의의 정수를 잡아 시작한다. ::: **1단계 — 반사.** 임의의 $a$에 대해 $a \mathrel{R} a$를 보여야 하므로, $a - a$가 짝수임을 정의의 꼴로 제시한다. :::{container} quotebox **확인 11.** 첫 조각을 완성해 보자: "$a \in \mathbb{Z}$라 하자. $a - a = \underline{\quad} = 2 \cdot \underline{\quad}$이고 $\underline{\quad}$는 정수이므로 $a \mathrel{R} a$이다." ::: :::{admonition} 답 :class: quotebox dropdown $a - a = 0 = 2 \cdot 0$이고 $0$은 정수이므로 $a \mathrel{R} a$이다. "$0$은 짝수이다"라고만 적으면 절반이다 — 짝수의 정의가 요구하는 것은 $2 \times (\text{정수})$ 꼴을 실제로 제시하는 것이고, 그 정수가 $0$이다. ::: **2단계 — 대칭.** 가정 $a \mathrel{R} b$에서 정수를 받아 오고, 목표 $b \mathrel{R} a$의 꼴을 만들어 제시한다. :::{container} quotebox **확인 12.** 둘째 조각을 완성해 보자: "$a \mathrel{R} b$라 하자. 정의에 의해 $a - b = 2k$인 정수 $k$가 존재한다. 그러면 $b - a = \underline{\quad} = 2(\underline{\quad})$이고 $\underline{\quad}$는 정수이므로 $b \mathrel{R} a$이다." ::: :::{admonition} 답 :class: quotebox dropdown $b - a = -(a-b) = -2k = 2(-k)$이고 $-k$는 정수이므로 $b \mathrel{R} a$이다. 핵심은 $b - a$를 가정이 준 재료 $a - b$로 바꿔 적는 첫 등호다. 재료가 하나뿐일 때는 목표를 그 재료의 식으로 다시 쓰는 것이 유일한 출발이다. ::: **3단계 — 추이.** 가정이 둘이므로 정수도 둘 받아 오고, 목표 $a - c$를 두 재료의 합으로 만든다. :::{container} quotebox **확인 13.** 셋째 조각을 완성해 보자: "$a \mathrel{R} b$이고 $b \mathrel{R} c$라 하자. 정의에 의해 $a - b = 2k$, $b - c = 2l$인 정수 $k, l$이 존재한다. 그러면 $a - c = \underline{\quad} = 2(\underline{\quad})$이다." ::: :::{admonition} 답 :class: quotebox dropdown $a - c = (a-b) + (b-c) = 2k + 2l = 2(k+l)$이다. 가운데 항 $b$가 더해지고 빼지며 사라지는 것이 이 줄의 전부다. 목표에 없는 문자를 끼워 넣었다가 소거하는 이 조작은 합동$\cdot$부등식$\cdot$집합에서 되풀이해서 쓰이며, C6주차 예제 2.1의 선형결합도 같은 조작이었다. ::: **4단계 — 결론과 동치류.** 세 성질이 모두 성립했으므로 정의 11.3으로 결론을 선언하고, 정리 11.2가 주는 분할이 무엇인지 확인한다. :::{container} quotebox **확인 14.** 이 동치관계의 서로 다른 동치류는 몇 개이고 각각 무엇인가. 정리 11.1을 써서 $[0] = [2]$와 $[0] \neq [1]$을 판정해 보자. ::: :::{admonition} 답 :class: quotebox dropdown 두 개다 — $[0]$은 짝수 전체, $[1]$은 홀수 전체다. $0 - 2 = -2$는 짝수이므로 $0 \mathrel{R} 2$이고, 정리 11.1의 ①에서 ②로 가는 방향에 의해 $[0] = [2]$이다. $0 - 1 = -1$은 짝수가 아니므로 $0 \not\mathrel{R} 1$이고, 같은 정리의 대우에 의해 $[0] \neq [1]$이다. 정리 11.2에 의해 $\{[0], [1]\}$은 $\mathbb{Z}$의 분할이며, 이것이 C2주차 문제 11에서 세 조건으로 직접 확인했던 $\{E, O\}$와 같은 분할이다. ::: **완성본.** 방금 만든 조각들을 이어 붙이면 아래 왼쪽 열이 된다. 손으로 베껴 쓰면서 각 줄 옆의 "왜"에 스스로 답해 본다. | 증명의 한 줄 | 왜 이 줄을 쓰는가? | |---|---| | (반사) $a \in \mathbb{Z}$라 하자. $a - a = 0 = 2 \cdot 0$이고 $0 \in \mathbb{Z}$이므로 $a \mathrel{R} a$이다. | $\forall$ 명제이므로 선택법으로 임의의 정수를 잡는다. 짝수임은 $2 \times (\text{정수})$ 꼴을 제시해 보인다(근거 ①). | | (대칭) $a \mathrel{R} b$라 하자. 정의에 의해 $a - b = 2k$인 정수 $k$가 존재한다. | 가정 쪽의 "짝수"는 정수를 받아 오는 자리다. 문자 $k$는 이 줄에서 처음 소개된다(C1주차 §1.3의 기호 사용 10원칙). | | 그러면 $b - a = -(a-b) = -2k = 2(-k)$이고 $-k \in \mathbb{Z}$이므로 $b \mathrel{R} a$이다. | 목표 $b-a$를 가정이 준 재료 $a-b$로 다시 쓴다. 괄호 안이 정수임을 확인해야 정의가 만족된다(근거 ②). | | (추이) $a \mathrel{R} b$이고 $b \mathrel{R} c$라 하자. 정의에 의해 $a - b = 2k$, $b - c = 2l$인 정수 $k, l$이 존재한다. | 가정이 둘이므로 정수도 둘 받아 온다. 서로 다른 문자를 쓰지 않으면 두 차가 같다고 몰래 가정하는 것이 된다. | | 그러면 $a - c = (a-b) + (b-c) = 2k + 2l = 2(k+l)$이고 $k + l \in \mathbb{Z}$이므로 $a \mathrel{R} c$이다. | 목표에 없는 $b$를 끼워 넣었다가 소거한다. 두 재료를 하나의 목표로 합치는 표준 조작이다. | | 세 성질이 모두 성립하므로 $R$는 $\mathbb{Z}$ 위의 동치관계이다. $\blacksquare$ | 정의 11.3이 요구한 세 조각이 전부 갖춰졌음을 선언한다. | 이 관계는 $a \equiv b \pmod 2$와 같은 관계이므로, 위 세 조각은 1권 20주차의 (C1)(C2)(C3)을 $n = 2$에서 다시 적은 것이기도 하다. **1권에서 합동의 성질로만 불리던 세 줄이 여기서 동치관계의 정의를 만족하는 검사로 승격된다.** ### 예제 2.2 — 두 동치류는 같거나 서로소 **보조정리.** $R$이 $A$ 위의 동치관계이고 $[a] \cap [b] \neq \emptyset$이면 $[a] = [b]$이다. 이번에는 설계만 함께 하고, 본문은 완성본으로 본다. :::{container} quotebox **확인 15.** 번역표를 채워 보자. 가정: $[a] \cap [b] \neq \emptyset$ $\to$ $c \in [a]$이고 $c \in [b]$인 $\underline{\quad}$가 존재한다 $\to$ 동치류의 정의로 한 겹 더 풀면 $\underline{\quad}$이고 $\underline{\quad}$이다. 목표: $[a] = [b]$ $\to$ 집합의 상등이므로 $\underline{\quad}$와 $\underline{\quad}$를 각각 보인다. ::: :::{admonition} 답 :class: quotebox dropdown 가정: 그런 원소 $c$가 존재한다 $\to$ $c \mathrel{R} a$이고 $c \mathrel{R} b$이다. "공집합이 아니다"라는 부정형 진술을 원소의 존재로 바꾸는 이 한 걸음이 계산의 출발이다. C7주차 §1.6에서 존재를 다룬 방식 그대로, 그 원소에 이름 $c$를 준다. 목표: $[a] \subseteq [b]$와 $[b] \subseteq [a]$를 각각 보인다(1권 27주차의 상등 서식). 포함 하나를 보이는 일은 다시 $\forall$ 명제이므로 "$x \in [a]$라 하자"로 시작한다. ::: | 증명의 한 줄 | 왜 이 줄을 쓰는가? | |---|---| | $[a] \cap [b] \neq \emptyset$이라 하자. 그러면 $c \in [a] \cap [b]$인 원소 $c$가 존재한다. | 공집합이 아니라는 진술을 원소의 존재로 번역한다. 이 원소에 이름을 주지 않으면 다음 줄에서 가리킬 것이 없다. | | 교집합의 정의에 의해 $c \in [a]$이고 $c \in [b]$이며, 동치류의 정의에 의해 $c \mathrel{R} a$이고 $c \mathrel{R} b$이다. | 집합 표기를 관계로 한 겹 더 푼다(근거 ①). 계산이 가능한 형태는 관계 쪽이다. | | 대칭에 의해 $a \mathrel{R} c$이고, 추이($a \mathrel{R} c$와 $c \mathrel{R} b$)에 의해 $a \mathrel{R} b$이다. | 화살의 방향을 대칭으로 뒤집고 추이로 이어 붙인다. §1.3 확인 3이 지목한 그 두 줄이다. | | ($[a] \subseteq [b]$) $x \in [a]$라 하자. 그러면 $x \mathrel{R} a$이고, $a \mathrel{R} b$이므로 추이에 의해 $x \mathrel{R} b$, 곧 $x \in [b]$이다. | 포함을 보이는 표준 서식은 원소 추적이다(1권 27주차). 앞 줄에서 얻은 $a \mathrel{R} b$가 여기서 소비된다. | | ($[b] \subseteq [a]$) $x \in [b]$라 하자. 대칭에 의해 $b \mathrel{R} a$이므로, 추이에 의해 $x \mathrel{R} a$, 곧 $x \in [a]$이다. | 방향만 바꾼 같은 논증이다. 대칭이 없으면 $b \mathrel{R} a$를 얻지 못해 이 방향이 나오지 않는다. | | 양방향 포함이 성립하므로 $[a] = [b]$이다. $\blacksquare$ | 상등의 정의를 만족했음을 선언하며 마무리한다. | 이 보조정리가 정리 11.2의 조건 ②를 통째로 담당한다. 이 증명에 쓰인 것은 대칭과 추이 둘뿐이라는 점을 짚어 둔다 — 반사는 한 줄도 등장하지 않는다. 반사가 일하는 자리는 이 보조정리가 아니라 정리 11.2의 조건 ①과 ③이며, 거기서는 $a \in [a]$ 한 줄이 둘을 동시에 준다. 셋을 뭉뚱그려 "세 성질을 다 썼다"고 적으면 어느 성질이 어느 조건을 떠받치는지가 지워진다. ### 예제 2.3 — $\mathbb{Z}_5$ 덧셈의 well-defined **명제.** $\mathbb{Z}_5$에서 $[a] + [b] = [a+b]$는 well-defined이다. 이번에는 설계부터 스스로 해 보자. :::{container} quotebox **확인 16.** 번역표를 채워 보자. 가정 "$[a] = [a']$이고 $[b] = [b']$"을 정리 11.1과 합동의 정의로 풀면 무엇이 되는가. 목표 "$[a+b] = [a'+b']$"은 같은 번역을 거꾸로 하면 무엇을 보이는 일이 되는가. ::: :::{admonition} 답 :class: quotebox dropdown 가정: $5 \mid (a - a')$이고 $5 \mid (b - b')$이다. 정리 11.1의 ②에서 ①로 가는 방향으로 $a \equiv a'$와 $b \equiv b'$를 얻고, 합동의 정의(C6주차 정의 6.2)로 한 겹 더 풀면 나눗셈 진술이 된다. 목표: $5$가 $(a+b) - (a'+b')$을 나눔을 보이면 된다. 같은 두 번역을 거꾸로 밟아 올라가면 $[a+b] = [a'+b']$이 나온다. 이 표가 곧 well-defined 검사의 걸음 ①과 ②이며, 남은 계산이 걸음 ③이다. ::: **증명.** $[a] = [a']$, $[b] = [b']$이라 하자. 정리 11.1에 의해 $a \equiv a' \pmod 5$이고 $b \equiv b' \pmod 5$이므로, 합동의 정의에 의해 $a - a' = 5s$, $b - b' = 5t$인 정수 $s, t$가 존재한다. 그러면 $$ (a+b) - (a'+b') = (a - a') + (b - b') = 5s + 5t = 5(s+t) $$ 이고 $s + t$는 정수이므로 $5$가 $(a+b) - (a'+b')$을 나눈다. 곧 $a + b \equiv a' + b' \pmod 5$이고, 다시 정리 11.1에 의해 $[a+b] = [a'+b']$이다. 따라서 대표원을 어떻게 골라도 합의 동치류가 같으므로 덧셈은 well-defined이다. $\blacksquare$ 이번 증명은 표 없이 산문으로 적었다. 표는 연습 단계의 장치이고, 실전의 답안은 처음부터 끝까지 이런 산문이다. 계산으로 확인해 두면 $\mathbb{Z}_5$에서 $[3] + [4] = [7] = [2]$이고, $[3]$을 $[8]$로 바꿔도 $[8] + [4] = [12] = [2]$로 같다. 이 일치가 우연이 아님을 보장한 것이 위 증명이다. ### 관찰 — 세 예제의 같은 뼈대 예제 2.1, 2.2, 2.3은 소재가 다르지만 밟은 순서가 같다. 대응표의 빈칸을 채워 보자. | **걸음** | **예제 2.1** | **예제 2.2** | **예제 2.3** | |---|---|---|---| | ① 가정을 정의로 푼다 | $a - b = 2k$ | $c \in [a] \cap [b]$에서 $c \mathrel{R} a$, $c \mathrel{R} b$ | $\underline{\quad(1)\quad}$ | | ② 목표를 정의로 푼다 | 세 성질 각각의 $\forall$ 명제 | $\underline{\quad(2)\quad}$ | $5$가 $(a+b)-(a'+b')$을 나눔 | | ③ 재료로 목표 꼴을 만든다 | $a - c = 2(k+l)$ | 원소 추적 두 방향 | $(a+b)-(a'+b') = 5(s+t)$ | | ④ 정의로 되돌려 선언한다 | 동치관계이다 | $[a] = [b]$이다 | $\underline{\quad(3)\quad}$ | :::{container} quotebox **확인 17.** (1)(2)(3)을 채우고, 세 예제가 공통으로 밟은 순서를 한 문장으로 적어 보자. ::: :::{admonition} 답 :class: quotebox dropdown (1) $[a] = [a']$, $[b] = [b']$에서 $a - a' = 5s$, $b - b' = 5t$. (2) $[a] \subseteq [b]$와 $[b] \subseteq [a]$. (3) $[a+b] = [a'+b']$이므로 well-defined이다. 공통 순서: **가정과 목표를 각각 정의로 끝까지 풀어 계산 가능한 등식으로 바꾸고, 재료에서 목표 꼴을 만든 뒤 정의를 거꾸로 밟아 원래 언어로 되돌린다.** 이번 주에 새로 붙은 것은 푸는 겹이 하나 늘었다는 점뿐이다 — 동치류는 집합이므로 집합 표기를 관계로, 관계를 나눗셈 등식으로 두 번 풀어야 계산이 시작된다. ::: 방금 확인한 뼈대에 이름을 붙인다. :::{admonition} 백지 암기 대상 :class: keybox **동치관계 답안의 서식** ① **판정** — 세 성질을 각각 증명하거나 반례를 든다. 하나라도 빠지면 동치관계라고 부를 수 없다. ② **조각** — 동치류를 정의대로 적고, 서로 다른 동치류의 목록과 개수를 확정한다. ③ **왕복** — 정리 11.2로 분할을 얻거나 정리 11.3으로 동치관계를 얻는다. 어느 방향인지 답안에 밝힌다. ④ **연산** — 동치류 위에 연산을 얹었으면 well-defined 검사 세 걸음을 반드시 적는다. ::: ## 빈칸 사다리 — 지지대를 하나씩 빼며 예제의 필사에서 자립으로 넘어가는 다리다. 훈련이 진행될수록 빈칸이 커진다. 베끼지 말고 빈칸만 스스로 채운다. 답은 §6에 있다 — 다 채운 뒤에 대조한다. ### 훈련 1 ●○○ — 수식과 절차의 빈칸 **명제.** $\mathbb{Z}$ 위의 관계 "$a \mathrel{R} b \iff 3 \mid (a - b)$"는 동치관계이고, 그 동치류는 정확히 세 개다. **걸음 ① 판정.** - 반사: $a - a = 0 = 3 \cdot 0$이고 $0$은 정수이므로 $3 \mid (a-a)$이다 ✓. - 대칭: $3 \mid (a-b)$이면 $a - b = 3k$인 정수 $k$가 존재하고, $b - a = \underline{\quad(1)\quad} = 3(-k)$이므로 $3 \mid (b-a)$이다 ✓. - 추이: $3 \mid (a-b)$이고 $3 \mid (b-c)$이면 $a - b = 3k$, $b - c = 3l$이고, $a - c = (a-b) + (b-c) = \underline{\quad(2)\quad}$이므로 $3 \mid (a-c)$이다 ✓. - 세 성질이 모두 성립하므로 $R$는 $\underline{\quad(3)\quad}$이다. **걸음 ② 조각.** 동치류는 $[0] = \{\ldots, -3, 0, 3, 6, \ldots\}$, $[1] = \{\ldots, -2, 1, 4, \ldots\}$, $[2] = \{\ldots, -1, 2, 5, \ldots\}$이고, 서로 다른 동치류는 $\underline{\quad(4)\quad}$개다. **걸음 ③ 왕복.** 정리 $\underline{\quad(5)\quad}$에 의해 이 세 동치류의 모임은 $\mathbb{Z}$의 분할이다. ### 훈련 2 ●●○ — 수식과 근거를 함께 이번에는 구조 낱말과 근거 문장도 빈칸이다. **명제.** $\mathbb{Z}_4$에서 $[a] + [b] = [a+b]$는 well-defined이다. **걸음 ①.** $[a] = [a']$이고 $[b] = [b']$이라 하자. **걸음 ②.** 정리 $\underline{\quad(1)\quad}$에 의해 $a \equiv a' \pmod 4$이고 $b \equiv b' \pmod 4$이므로, $\underline{\quad(2)\quad}$의 정의에 의해 $a - a' = 4s$, $b - b' = 4t$인 정수 $s, t$가 존재한다. **걸음 ③.** 그러면 $$ (a+b) - (a'+b') = \underline{\quad(3)\quad} = 4s + 4t = 4(\underline{\quad(4)\quad}) $$ 이고, $\underline{\quad(5)\quad}$이므로 $s+t$는 정수이다. 따라서 $4$가 $(a+b)-(a'+b')$을 나누므로 $[a+b] = [a'+b']$이다. $\blacksquare$ **검산.** $[3] + [3] = [6] = [2]$이고, 왼쪽 대표원을 $7$로 바꾸면 $[7] + [3] = [10] = \underline{\quad(6)\quad}$으로 결과가 같다. ### 훈련 3 ●●● — 뼈대만 남기고 이번에는 무대가 정수가 아니다. 무대가 바뀌어도 서식이 그대로 작동하는지 확인한다. **명제.** $\mathbb{R}$ 위의 관계 "$x \mathrel{R} y \iff x - y \in \mathbb{Z}$"는 동치관계이고, 그 동치류들의 모임은 $\mathbb{R}$의 분할이다. **답안의 뼈대.** §2 관찰의 서식에서 걸음 ①②③의 각 칸을 통째로 채운다. - 걸음 ① 판정 (세 성질을 각각 증명): $\underline{\quad(1)\quad}$ - 걸음 ② 조각 ($[0]$과 $\left[\tfrac12\right]$을 구체적으로 적고, 일반형을 묘사): $\underline{\quad(2)\quad}$ - 걸음 ③ 왕복 (분할임을 어느 정리로 얻는지 밝히고 세 조건이 어디서 오는지 지목): $\underline{\quad(3)\quad}$ (이 훈련이 문제 2(d)와 문제 11의 예행연습이다.) ## 연습문제 (20문항) 해설을 보기 전에 문제당 최소 10분 스스로 시도한다. 막히면 곧바로 풀이를 읽지 말고, 해설의 '접근'까지만 읽고 다시 시도한다 $\to$ 그래도 안 되면 풀이를 읽는다. :::{admonition} 이번 주의 채점 기준 :class: quotebox 답이 아니라 **근거**가 점수다. 이번 주 답안에는 채점 항목이 넷이다. ① 관계 판정에서 세 성질을 **각각** 다뤘는가. 성립은 선택법으로 증명하고, 불성립은 반례를 C7주차 §1.4의 4단 서식으로 적는다. "동치관계이다"라는 낱말만 적으면 0점이다. ② 동치류를 물었으면 정의대로 $\{x : x \mathrel{R} a\}$를 적고, 서로 다른 동치류가 몇 개인지 확정했는가. 예시 원소 나열만으로는 개수가 확정되지 않는다. ③ 분할을 주장했으면 세 조건이 각각 어느 성질에서 오는지 밝혔는가. 정리 11.2를 인용해도 되지만 인용했음을 적어야 한다. ④ 동치류 위의 연산을 다뤘으면 well-defined 검사 세 걸음이 있는가. 대표원을 문자로 잡지 않은 검사는 사례 확인이다. 난이도와 무관하게, 힌트 상자는 5분 이상 막힌 뒤에만 연다. ::: ### 기본 ●○○ **1.** [백지] 세 성질 정의, 동치관계$\cdot$동치류 정의, 핵심 정리(동치관계$\leftrightarrow$분할), well-defined의 뜻을 쓰시오. :::{admonition} 힌트 :class: quotebox dropdown 정의 11.2$\cdot$11.3$\cdot$11.4와 정리 11.1$\cdot$11.2$\cdot$11.3, 그리고 S19주차 정의 19.3(well-defined의 뜻)과 그 아래의 검사 서식 세 걸음이 대상이다. 문장을 통째로 외우면 일부를 잊었을 때 복구할 길이 없다. §1.3의 해부 표에서 성질마다 "이것을 빼면 분할의 어느 조건이 무너지는가"를 함께 적어 두면 남은 조각에서 나머지를 재구성할 수 있다. ::: **2.** 다음 관계가 반사$\cdot$대칭$\cdot$추이 중 무엇을 만족하는지 판정하시오 (반례 포함). (a) $\mathbb{Z}$ 위 "$a \le b$" (b) $\mathbb{Z}$ 위 "$a \mid b$" (c) 사람들 위 "형제이다" (d) $\mathbb{R}$ 위 "$a - b \in \mathbb{Z}$" :::{admonition} 힌트 :class: quotebox dropdown 네 문항 모두 §1.2의 표에 이미 재료가 있다. (c)에서 추이를 검사할 때는 세 사람이 서로 달라야 한다는 조건이 없다는 점을 이용한다 — 셋째 사람으로 첫째 사람을 다시 쓰면 무엇이 나오는가. (d)는 훈련 3에서 뼈대를 세운 그 관계다. ::: **3.** 예제 2.1(짝수 차 동치관계)을 백지 재현하시오. :::{admonition} 힌트 :class: quotebox dropdown 세 조각의 순서가 아니라 각 조각의 **첫 문장**이 관건이다. 반사는 "$a$를 임의의 정수라 하자", 대칭과 추이는 "$a \mathrel{R} b$라 하자"로 시작한다. 시작 문장이 정해지면 나머지는 정의를 푸는 일뿐이다. ::: **4.** 빈칸 훈련을 백지에서 완성하시오. :::{admonition} 힌트 :class: quotebox dropdown 훈련 1은 예제 2.1에서 $2$를 $3$으로 바꾼 것이고, 훈련 2는 예제 2.3에서 $5$를 $4$로 바꾼 것이다. 바뀌지 않은 것이 무엇인지 확인하면서 적는다. ::: **5.** 예제 2.2(핵심 보조정리)를 백지 재현하시오. :::{admonition} 힌트 :class: quotebox dropdown 막히는 자리는 대개 셋째 줄이다. 공유 원소 $c$에서 얻는 것은 $c \mathrel{R} a$와 $c \mathrel{R} b$인데, 추이를 쓰려면 화살이 $a \to c \to b$로 이어져야 한다. 방향을 뒤집는 성질이 무엇인지 §1.3 확인 3에서 확인했다. ::: **6.** $\mathbb{Z}_4$에서 $[2] + [3]$, $[2] \cdot [3]$, $[3] + [3]$을 계산하시오. :::{admonition} 힌트 :class: quotebox dropdown 정의 11.5대로 대표원끼리 계산한 뒤 결과의 동치류를 $[0] \sim [3]$ 안으로 되돌린다. 되돌리는 근거는 정리 11.1이다 — 예를 들어 $6 - 2 = 4$이고 $4 \mid 4$이므로 $[6] = [2]$이다. ::: ### 표준 ●●○ **7.** $\mathbb{Z}$ 위 "$a \mathrel{R} b \iff a^2 = b^2$"가 동치관계임을 보이고 동치류를 구하시오 ($[a] = \{a, -a\}$). :::{admonition} 힌트 :class: quotebox dropdown 세 성질이 전부 등식의 성질에서 곧바로 나온다 — 등식이 반사적$\cdot$대칭적$\cdot$추이적이기 때문이다(근거 ③). 동치류를 구할 때는 $x^2 = a^2$을 $x^2 - a^2 = 0$으로 옮겨 인수분해한다. ::: **8.** 예제 2.2의 나머지 방향("$a \mathrel{R} b \Rightarrow [a] = [b]$")과 "$[a] = [b] \Rightarrow a \mathrel{R} b$"를 증명해, 세 조건 "$[a]=[b] \iff a \mathrel{R} b \iff [a] \cap [b] \neq \emptyset$"의 동치를 완성하시오. :::{admonition} 힌트 :class: quotebox dropdown 세 조건의 동치를 보이는 값싼 방법은 순환 고리 하나를 만드는 것이다: ① $\Rightarrow$ ② $\Rightarrow$ ③ $\Rightarrow$ ①. 예제 2.2가 ③ $\Rightarrow$ ②를 증명했고 그 논증의 앞부분(공유 원소에 대칭과 추이를 쓰는 두 줄)이 곧 ③ $\Rightarrow$ ①이므로, 그 두 줄을 그대로 옮겨 쓰면 된다. ②에서 ③으로 가는 화살에는 반사가 필요하다 — $a$가 어느 동치류에 들어 있는가. ::: **9.** $\mathbb{Z}_5$에서 $[a] \cdot [b] = [ab]$가 well-defined임을 증명하시오 (예제 2.3의 곱셈판 — 합동 곱셈 보존, C6주차 예제 2.2). :::{admonition} 힌트 :class: quotebox dropdown 덧셈에서는 $(a+b) - (a'+b')$이 곧바로 두 재료의 합이 되지만, 곱에서는 그렇지 않다. $ab - a'b'$에 $a'b$를 더했다가 빼면 두 덩어리로 갈라진다. 예제 2.1의 추이 증명에서 $b$를 끼워 넣었던 조작과 같은 수법이다. ::: **10.** 다음 제시된 증명을 평가하시오 (C5주차의 증명 평가 다섯 걸음). :::{container} quotebox **Result.** $\mathbb{R}$ 위 "$a \mathrel{R} b \iff \lvert a - b \rvert < 1$"은 동치관계이다. **증명.** 반사 $\lvert a-a \rvert = 0 < 1$ ✓. 대칭 $\lvert a-b \rvert = \lvert b-a \rvert$ ✓. 추이 성립. 따라서 동치관계. ::: :::{admonition} 힌트 :class: quotebox dropdown 증명 평가의 걸음 ①은 명제 자체의 진위다. 세 성질 중 두 개는 실제로 성립하므로, 의심할 곳은 남은 하나다. 추이는 $a$에서 $b$로, $b$에서 $c$로 각각 $1$ 미만씩 움직였을 때 $a$에서 $c$까지의 거리를 묻는다 — 두 번 움직이면 얼마까지 갈 수 있는가. ::: **11.** 분할 $\to$ 동치관계: $\mathbb{Z}$의 분할 $\{짝수, 홀수\}$에서 "같은 조각에 속함" 관계가 동치관계이고 그 동치류가 짝수$\cdot$홀수임을 확인하시오 (핵심 정리의 역방향). :::{admonition} 힌트 :class: quotebox dropdown 정리 11.3을 인용해도 되지만, 이 문제는 그 정리의 증명을 구체적인 분할에서 다시 밟아 보라는 것이다. §1.5 확인 6이 세 성질 각각에 어느 분할 조건이 쓰이는지 알려 준다. ::: **12.** $\mathbb{Z}_6$의 곱셈표에서 $[2] \cdot [3] = [0]$임을 계산하고, "0이 아닌 두 원소의 곱이 0"($\mathbb{Z}_6$의 영인자)이 됨을 관찰하시오 ($\mathbb{Z}_p$ $p$ 소수와의 차이 — C18주차 예고). :::{admonition} 새 낱말 — 영인자 (zero divisor) :class: quotebox 곱셈이 있는 무대에서 $x \neq [0]$, $y \neq [0]$인데 $xy = [0]$일 때 $x$와 $y$를 **영인자**라 한다. 정수 $\mathbb{Z}$에는 영인자가 없다 — 두 정수의 곱이 $0$이면 둘 중 하나가 $0$이기 때문이다. 영인자가 있는 무대에서는 "$xy = xz$이고 $x \neq 0$이면 $y = z$"라는 소거가 성립하지 않는다(1권 38주차 문제 11). ::: **13.** 동치류 개수: $\mathbb{Z}$ 위 "$a \equiv b \pmod n$"의 동치류가 정확히 $n$개임을 증명하시오 (나머지 $0, \ldots, n-1$이 서로 다른 동치류이고 전부를 덮음 — 나눗셈 정리). :::{admonition} 힌트 :class: quotebox dropdown "정확히 $n$개"는 두 가지 의무다 — 목록 $[0], \ldots, [n-1]$이 **전부를 덮는다**와 그 목록에 **중복이 없다**. 앞쪽은 나눗셈 정리의 존재(1권 33주차 예제 2.2), 뒤쪽은 두 나머지의 차의 크기를 재는 계산이다. $0 \le r, r' < n$이면 그 차의 절댓값은 얼마보다 작은가. ::: **14.** 다음이 동치관계가 **아님**을 보이시오 (어느 성질 실패). (a) $\mathbb{Z}$ 위 "$a \mathrel{R} b \iff a + b$가 짝수" (사실 동치관계인가? 반사 $a+a=2a$ 짝수 ✓ — 확인). (b) $\mathbb{R}$ 위 "$a \mathrel{R} b \iff ab > 0$" (반사 실패: $0 \cdot 0 = 0 \not> 0$). :::{admonition} 힌트 :class: quotebox dropdown 지시문이 "아님을 보이라"이지만 (a)는 실제로 동치관계다. C10주차의 걸음 ①이 여기서 값을 한다 — 지시문의 방향을 믿기 전에 작은 값을 몇 개 넣어 판정한다. (b)는 급소 목록(C10주차 §1.4)의 첫 줄인 $0$이 곧바로 걸린다. ::: ### 도전 ●●● **15.** (핵심 정리 완전 증명) "동치관계 $R$의 동치류들이 $A$의 분할을 이룬다"를 세 조건(비공$\cdot$서로소$\cdot$덮음)으로 완전 증명하시오 (예제 2.2를 서로소에 사용). :::{admonition} 힌트 :class: quotebox dropdown 조건 ②의 진술을 정확히 적는 것이 관건이다. 분할이 요구하는 것은 "서로 다른 두 조각이 서로소"이므로, 보일 것은 "$[a] \neq [b]$이면 $[a] \cap [b] = \emptyset$"이다. 예제 2.2는 그 대우를 증명한 것이다. ::: **16.** ($\mathbb{Z}_n$ 역원) $\mathbb{Z}_5$에서 각 0 아닌 원소의 곱셈 역원을 구하시오 ($[a] \cdot [x] = [1]$인 $[x]$): $[1]^{-1}=[1]$, $[2]^{-1}=[3]$ ($2\cdot3=6\equiv1$), $[3]^{-1}=[2]$, $[4]^{-1}=[4]$ ($16\equiv1$). "$\mathbb{Z}_5$의 0 아닌 원소는 모두 역원을 가짐"($\mathbb{Z}_p$가 체) — $\mathbb{Z}_6$과 대조(문제 12). :::{admonition} 새 낱말 — 곱셈 역원과 체 (field) :class: quotebox $[a] \cdot [x] = [1]$인 $[x]$를 $[a]$의 **곱셈 역원**이라 하고 $[a]^{-1}$로 적는다. $[0]$이 아닌 모든 원소가 곱셈 역원을 가지는 무대를 **체**라 한다. 정수 $\mathbb{Z}$는 체가 아니고($[2]$의 역원이 없다) 유리수 $\mathbb{Q}$는 체다. $\mathbb{Z}_n$이 어느 쪽인지는 $n$이 정한다 — 그 판정이 이 문제와 문제 12다. ::: **17.** (관계 합성) 두 동치관계 $R, S$의 교집합 $R \cap S$(둘 다 관계 맺음)가 동치관계임을 증명하시오 (세 성질이 교집합에서 보존). 합집합 $R \cup S$는 왜 일반적으로 동치관계가 아닌지 반례로 (추이 실패). :::{admonition} 관계는 집합이다 — 교집합과 합집합 :class: quotebox 정의 11.1에 의해 $A$ 위의 관계는 $A \times A$의 부분집합이므로, 두 관계의 교집합과 합집합이 그대로 정의된다. 원소 수준으로 풀면 $a \mathrel{(R \cap S)} b \iff a \mathrel{R} b$이고 $a \mathrel{S} b$이며, $a \mathrel{(R \cup S)} b \iff a \mathrel{R} b$이거나 $a \mathrel{S} b$이다. 반례를 찾을 때는 "이거나"가 두 관계를 오가며 사슬을 만들 수 있다는 점을 노린다. ::: **18.** (진단 종합) 다음 제시된 증명을 평가하시오. :::{container} quotebox **Result.** $\mathbb{Z}$ 위 "$a \mathrel{R} b \iff a \mid b$"는 동치관계이다. **증명.** 반사 $a \mid a$ ✓. 추이 $a \mid b, b \mid c \Rightarrow a \mid c$ ✓. 따라서 동치관계. ::: :::{admonition} 힌트 :class: quotebox dropdown 문제 10과 결함의 종류가 다르다. 문제 10은 거짓인 줄을 적었고, 이 답안은 줄 하나를 아예 적지 않았다. 평가에서는 두 가지를 모두 적어야 한다 — 무엇이 빠졌는가, 그리고 그 빠진 것이 실제로 성립하는가. ::: **19.** (well-defined 실패 사례) $\mathbb{Z}_n$에서 "$[a]^{[b]} = [a^b]$" (거듭제곱)가 well-defined가 **아님**을 $\mathbb{Z}_3$에서 반례로 보이시오 (지수가 동치류라 문제 — $[2] = [5]$이나 밑 $[2]$에 대해 $2^2 = 4 \equiv 1$ vs $2^5 = 32 \equiv 2$, 다름). "밑의 연산은 되나 지수의 연산은 안 됨"(S19주차 문제 9$\cdot$17). :::{admonition} 힌트 :class: quotebox dropdown ill-defined를 보이는 것은 반례를 드는 일이므로 C7주차 §1.4의 4단 서식을 쓴다. 증인은 대표원 한 쌍이다 — 같은 동치류의 두 표현을 제시하고(자격), 그 둘에서 규칙이 주는 값이 다름을 계산으로 보인다(사건). ::: **20.** (서술) (a) 동치관계와 분할이 "같은 것의 두 얼굴"임을 예제 2.1(짝수 차 $\to$ 짝$\cdot$홀 분할)과 핵심 정리로 뒷받침하고, C2주차에서 심은 씨앗이 어떻게 꽃폈는지 세 문장 이내로. (b) $\mathbb{Z}_n$ 연산의 well-defined가 왜 필수인지(대표 무관), 합동 보존(C6주차)과의 관계를 두 문장 이내로. :::{admonition} 힌트 :class: quotebox dropdown (a)는 정리 11.2와 11.3을 한 문장씩으로 요약하고, 두 정리가 서로 역방향이라는 점을 셋째 문장에 둔다. (b)는 §1.6의 걸음 삭제 실험이 무엇을 무너뜨렸는지를 첫 문장에, 합동의 (C4)(C5)가 정확히 무엇을 보장하는지를 둘째 문장에 둔다. ::: ## 백지 재현 — 복습 프로토콜 이 과정의 한 주는 다섯 날로 나뉜다. 교안만 보는 주가 아니라 원서와 교안을 번갈아 읽는 주이므로, 백지 재현은 마지막 날에 놓인다. | **요일** | **할 일** | |---|---| | 1일차 | 원서 Chartrand 9장 통독 — 모르는 문장은 표시만 하고 통과한다 | | 2일차 | 교안 §0~§2 — 개념과 예제. 확인 상자를 연필로 먼저 채운다 | | 3일차 | 원서 9장 재독 — 1일차에 표시한 문장을 해결하고, 원서 연습문제 몇 개를 직접 시도한다 | | 4일차 | 교안 §3 빈칸 사다리와 §4 연습문제 20문항 | | 5일차 | 백지 재현 1차(틀 카드)$\cdot$2차(완전 백지) + 체크리스트 | **1차 시도 — 틀 카드 허용.** 세 성질의 이름, 동치관계 답안의 서식 네 걸음, well-defined 검사 세 걸음만 한 장에 적어 펴 놓고, 예제 2.2를 처음부터 끝까지 적는다. 본문과 계산은 보지 않는다. **2차 시도 — 완전 백지.** 아무것도 보지 않고 수행한다. - [ ] 정의 11.1~11.5를 수식으로 썼다 (동치류는 집합 표기 그대로). - [ ] 세 성질 각각이 분할의 어느 조건을 낳는지 §1.3의 표를 재현했다. - [ ] 세 개의 조각 삭제 실험을 반례 관계까지 포함해 하나씩 적었다. - [ ] 정리 11.1의 세 조건을 쓰고, 세 조건이 동치라는 말이 "같거나 서로소"와 같은 뜻임을 한 문장으로 적었다. - [ ] 예제 2.1을 재현했고, 추이 증명에서 $b$를 끼워 넣는 줄의 이유를 말했다. - [ ] 예제 2.2를 재현했고, 대칭과 추이가 각각 몇째 줄에서 소비되는지 짚었다. - [ ] 예제 2.3을 재현했고, well-defined 검사 세 걸음 중 어느 줄이 어느 걸음인지 표시했다. - [ ] $\mathbb{Z}_4$와 $\mathbb{Z}_5$에서 덧셈$\cdot$곱셈을 계산하고, 대표원을 바꿔 검산했다. - [ ] 원서 9장을 두 번 읽었고, 1일차에 표시한 문장이 모두 해결되었다. **막힌 지점별 처방.** 막힌 지점이 무엇을 다시 볼지 알려 준다. | **막힌 지점** | **처방** | |---|---| | 관계 판정의 첫 문장이 나오지 않는다 | 예제 2.1의 1~3단계 — 세 성질은 전부 $\forall$ 명제이므로 첫 문장이 선택법으로 정해져 있다 | | 반례를 적었는데 무엇이 빠졌는지 모르겠다 | C7주차 §1.4의 4단 서식 — 빠지는 것은 대개 걸음 ①(무엇을 증명하는지 선언)과 자격 검증이다 | | 동치류를 구하라는 말이 무엇을 요구하는지 모르겠다 | §1.4 정의 11.4와 확인 5 — 집합 표기를 그대로 적고 서로 다른 것의 개수를 확정한다 | | 동치류가 분할임을 왜 증명해야 하는지 모르겠다 | §1.1 시도 2와 §1.3의 삭제 실험 (나)(다) — 세 성질이 없으면 실제로 겹친다 | | 예제 2.2의 셋째 줄이 나오지 않는다 | §1.3 확인 3 — 방향을 뒤집는 것이 대칭, 이어 붙이는 것이 추이다 | | well-defined 검사에서 무엇을 적어야 할지 모르겠다 | §1.6의 세 걸음 표 — 걸음 ①에서 대표원을 문자로 잡지 않으면 사례 확인이 된다 | | $\mathbb{Z}_n$ 계산 결과를 어디까지 줄여야 할지 모르겠다 | §1.6 표기 상자와 확인 8 — $[0]$부터 $[n-1]$ 사이로 되돌리는 근거는 정리 11.1이다 | 하나라도 실패하면 그 항목만 다시 필사하고 다음날 재시도한다. ## 해설 각 해설은 **접근**(문제 앞에서 무엇을 생각하는가)과 **풀이**로 나뉜다. 막혔을 때는 접근까지만 읽고 연필을 다시 잡는다. ### 빈칸 사다리 — 훈련 1 (1) $-(a-b)$ (2) $3k + 3l = 3(k+l)$ (3) 동치관계 (4) $3$ (5) 11.2 ※ 이 훈련의 관절은 (2)다. 목표 $a - c$에는 $b$가 없는데 재료 두 개에는 $b$가 들어 있으므로, $b$를 더했다가 빼서 두 재료를 잇는 것이 유일한 길이다. 예제 2.1의 추이 증명과 완전히 같은 조작이며, 밑을 $2$에서 $3$으로 바꿔도 이 줄은 변하지 않는다. (4)가 $3$인 근거는 문제 13이 일반적으로 증명한다 — 나눗셈 정리로 모든 정수가 $0, 1, 2$ 중 하나의 나머지를 가지고, 서로 다른 두 나머지의 차는 $3$의 배수가 아니므로 세 동치류가 서로 다르다. ### 빈칸 사다리 — 훈련 2 (1) 11.1 (2) 합동(C6주차 정의 6.2) (3) $(a - a') + (b - b')$ (4) $s + t$ (5) 정수의 합은 정수 (근거 ②) (6) $[2]$ ※ (3)이 이 훈련의 관절이다. 좌변 $(a+b) - (a'+b')$을 그대로 두면 재료와 모양이 맞지 않으므로, 항의 순서를 바꿔 $a$끼리 $b$끼리 묶어야 가정이 준 두 등식이 들어갈 자리가 생긴다. (5)를 빠뜨리는 답안이 많은데, 이 줄이 없으면 $4(s+t)$의 괄호 안이 정수라는 확인이 없어 나눗셈의 정의가 만족되지 않는다. (6)의 검산은 증명이 아니지만, 검산 결과가 어긋나면 증명 어딘가가 틀렸다는 신호이므로 계산 뒤에 한 줄 붙여 둘 값이 있다. ### 빈칸 사다리 — 훈련 3 (1) 세 성질을 각각 증명한다. 반사 — $x \in \mathbb{R}$라 하자. $x - x = 0$이고 $0 \in \mathbb{Z}$이므로 $x \mathrel{R} x$이다. 대칭 — $x \mathrel{R} y$라 하자. 그러면 $x - y \in \mathbb{Z}$이고, $y - x = -(x-y)$이며 정수의 부호를 바꾼 것은 정수이므로 $y - x \in \mathbb{Z}$, 곧 $y \mathrel{R} x$이다. 추이 — $x \mathrel{R} y$이고 $y \mathrel{R} z$라 하자. 그러면 $x - y \in \mathbb{Z}$이고 $y - z \in \mathbb{Z}$이며, $x - z = (x-y) + (y-z)$는 두 정수의 합이므로 정수다(근거 ②). 곧 $x \mathrel{R} z$이다. 세 성질이 모두 성립하므로 $R$는 $\mathbb{R}$ 위의 동치관계다. (2) $[0] = \{x \in \mathbb{R} : x - 0 \in \mathbb{Z}\} = \mathbb{Z}$이고, $\left[\tfrac12\right] = \left\{\ldots, -\tfrac32, -\tfrac12, \tfrac12, \tfrac32, \ldots\right\}$ 곧 $\left\{k + \tfrac12 : k \in \mathbb{Z}\right\}$이다. 일반형은 $[r] = \{r + k : k \in \mathbb{Z}\}$이며, $0 \le r < 1$인 $r$ 하나마다 동치류 하나가 대응하므로 서로 다른 동치류는 $[0, 1)$의 실수만큼 많다. (3) 정리 11.2에 의해 동치류들의 모임은 $\mathbb{R}$의 분할이다. 조건 ①은 반사에서 온다 — $r \in [r]$이므로 각 조각이 비어 있지 않다. 조건 ②는 대칭과 추이에서 온다 — 예제 2.2에 의해 두 동치류는 같거나 서로소다. 조건 ③도 반사에서 온다 — 임의의 실수 $x$가 $[x]$에 속하므로 합집합이 $\mathbb{R}$ 전체다. ※ 무대가 $\mathbb{Z}$에서 $\mathbb{R}$로 바뀌었는데도 세 증명의 줄 수와 순서가 예제 2.1과 같다. 바뀐 것은 "짝수"가 "정수"로 바뀐 것뿐이며, 닫힘성을 쓰는 자리도 그대로다. 동치류의 개수가 유한에서 무한으로 바뀐 것은 정리 11.2의 진술과 무관하다 — 분할의 세 조건 어디에도 조각의 개수가 들어 있지 않기 때문이다(C2주차 정의 2.3). ### 문제 1 **접근.** 암기 항목을 문장으로만 외우면 일부를 잊었을 때 복구할 길이 없다. 이번 주의 암기 대상은 다섯 정의와 세 정리, 그리고 검사 서식 하나다. 정의를 적을 때는 각 조각이 §1.3의 표에서 맡은 역할을 함께 떠올리고, 정리를 적을 때는 그 정리가 어느 조각을 가정으로 쓰는지 확인한다. 그러면 하나를 잊어도 나머지에서 재구성된다. **풀이.** 세 성질 — 반사적: 모든 $a \in A$에 대해 $a \mathrel{R} a$. 대칭적: $a \mathrel{R} b$이면 $b \mathrel{R} a$. 추이적: $a \mathrel{R} b$이고 $b \mathrel{R} c$이면 $a \mathrel{R} c$. 동치관계 — 세 성질을 모두 만족하는 관계. 동치류 — $[a] = \{x \in A : x \mathrel{R} a\}$. 핵심 정리 — 동치관계의 동치류들의 모임은 분할이고(정리 11.2), 분할에서 "같은 조각에 속함"으로 정의한 관계는 동치관계이며 그 동치류가 원래 조각들이다(정리 11.3). well-defined — 같은 대상의 어느 두 표현을 잡아도 정의가 주는 값이 같다는 것. 곧 $[a] = [a']$, $[b] = [b']$이면 $[a] + [b]$의 계산 결과가 대표원 선택과 무관하다는 것이다. **복기.** 자가 채점의 기준은 낱말의 일치가 아니라 조각의 완비다. "존재한다", "모든", "정수"처럼 하나만 빠져도 정의가 무너지는 조각이 들어 있는지 확인한다. 동치류를 적을 때 조건을 $a \mathrel{R} x$로 적었다면 그것도 옳지만, 대칭이 있으므로 같은 집합이 된다는 점을 함께 적어 두면 나중에 헷갈리지 않는다. ### 문제 2 **접근.** 네 문항 모두 세 성질을 **각각** 판정해야 하므로 판정이 열두 번이다. 성립하는 것은 선택법으로 한 줄씩 증명하고, 성립하지 않는 것은 반례를 제시한다. (c)는 수학 기호가 없는 관계라 정의를 그대로 읽는 연습이 되고, 특히 추이의 정의에 "세 사람이 서로 다르다"는 조건이 **없다**는 점이 열쇠다. **풀이.** (a) $\mathbb{Z}$ 위 $a \le b$. 반사 ✓ — 임의의 정수 $a$에 대해 $a \le a$이다. 대칭 ✗ — "$a \le b$이고 $b \not\le a$인 쌍 $(a,b)$가 존재한다"를 증명한다. 반례로 $(a, b) = (1, 2)$를 잡자. 자격: $1, 2 \in \mathbb{Z}$이고 $1 \le 2$이다. 사건: $2 \le 1$은 거짓이다. 추이 ✓ — $a \le b$이고 $b \le c$이면 부등식의 추이성에 의해 $a \le c$이다(근거 ③). (b) $\mathbb{Z}$ 위 $a \mid b$. 반사 ✓ — $a = a \cdot 1$이고 $1 \in \mathbb{Z}$이므로 $a \mid a$이다. 대칭 ✗ — "$a \mid b$이고 $b \nmid a$인 쌍 $(a,b)$가 존재한다"를 증명한다. 반례로 $(a,b) = (2,4)$를 잡자. 자격: $4 = 2 \cdot 2$이므로 $2 \mid 4$이다. 사건: $2 = 4k$인 정수 $k$가 없으므로 $4 \nmid 2$이다. 추이 ✓ — $b = ak$, $c = bl$이면 $c = a(kl)$이고 $kl$은 정수이므로 $a \mid c$이다. (c) 사람들 위 "형제이다". 반사 ✗ — 반례로 아무 사람 $p$를 잡으면 $p$는 자기 자신의 형제가 아니다. 대칭 ✓ — $p$가 $q$의 형제이면 $q$도 $p$의 형제다. 추이 ✗ — "$a$가 $b$의 형제이고 $b$가 $c$의 형제이면서 $a$가 $c$의 형제가 아닌 세 사람 $a, b, c$가 존재한다"를 증명한다. 서로 형제인 두 사람 $p, q$를 잡고 $a = p$, $b = q$, $c = p$로 두자. 자격: $p$가 $q$의 형제이고 $q$가 $p$의 형제다. 사건: 결론이 요구하는 것은 $p$가 $p$의 형제라는 것인데 이는 거짓이다. 추이의 정의에 세 대상이 서로 달라야 한다는 조건이 없으므로 이 세 사람 $p, q, p$가 반례가 된다. (d) $\mathbb{R}$ 위 $a - b \in \mathbb{Z}$. 세 성질이 모두 성립하므로 동치관계다. 반사 — $a - a = 0 \in \mathbb{Z}$. 대칭 — $a - b \in \mathbb{Z}$이면 $b - a = -(a-b) \in \mathbb{Z}$. 추이 — $a - b, b - c \in \mathbb{Z}$이면 $a - c = (a-b) + (b-c) \in \mathbb{Z}$. 증명 전체가 훈련 3에 적혀 있다. **복기.** (a)(b)(c)에서 성립하지 않는 성질이 서로 다르다는 점을 표로 정리해 두면 §1.3의 삭제 실험과 짝이 맞는다. (a)(b)는 대칭만 없고, (c)는 반사와 추이가 없다. 어느 경우든 동치관계가 아니므로 동치류를 만들어도 분할이 나오지 않는다. ### 문제 3 **접근.** 세 조각의 순서가 아니라 각 조각의 첫 문장이 관건이다. 반사는 대상이 하나이므로 "임의의 정수 $a$를 잡자"로, 대칭과 추이는 가정이 있으므로 "$a \mathrel{R} b$라 하자"로 시작한다. 시작 문장이 정해지면 나머지는 정의를 푸는 일과 목표 꼴을 만드는 일뿐이다. **풀이.** (반사) $a \in \mathbb{Z}$라 하자. $a - a = 0 = 2 \cdot 0$이고 $0 \in \mathbb{Z}$이므로 $a - a$는 짝수이며, 따라서 $a \mathrel{R} a$이다. (대칭) $a \mathrel{R} b$라 하자. 정의에 의해 $a - b = 2k$인 정수 $k$가 존재한다. 그러면 $b - a = -(a-b) = -2k = 2(-k)$이고 $-k \in \mathbb{Z}$이므로 $b - a$는 짝수이며, 따라서 $b \mathrel{R} a$이다. (추이) $a \mathrel{R} b$이고 $b \mathrel{R} c$라 하자. 정의에 의해 $a - b = 2k$, $b - c = 2l$인 정수 $k, l$이 존재한다. 그러면 $$ a - c = (a - b) + (b - c) = 2k + 2l = 2(k + l) $$ 이고 $k + l \in \mathbb{Z}$이므로 $a - c$는 짝수이며, 따라서 $a \mathrel{R} c$이다. 세 성질이 모두 성립하므로 $R$는 $\mathbb{Z}$ 위의 동치관계이다. $\blacksquare$ **검산.** $[0]$은 짝수 전체, $[1]$은 홀수 전체이고 둘의 합집합이 $\mathbb{Z}$이며 교집합이 공집합이다 — 정리 11.2가 예고한 분할이 실제로 나온다. ### 문제 4 **접근.** 훈련 1은 예제 2.1에서 밑을 $2$에서 $3$으로 바꾼 것이고, 훈련 2는 예제 2.3에서 법을 $5$에서 $4$로 바꾼 것이며, 훈련 3은 무대를 $\mathbb{Z}$에서 $\mathbb{R}$로 옮긴 것이다. 백지에서는 빈칸이 아니라 답안 전체를 적어야 하므로, 바뀌지 않은 부분이 무엇인지 의식하면서 처음부터 적는다. **풀이.** 훈련 1의 이어 붙인 답안은 다음과 같다. 반사 — $a \in \mathbb{Z}$라 하자. $a - a = 0 = 3 \cdot 0$이고 $0 \in \mathbb{Z}$이므로 $3 \mid (a-a)$이다. 대칭 — $3 \mid (a-b)$라 하면 $a - b = 3k$인 정수 $k$가 존재하고, $b - a = -(a-b) = 3(-k)$이며 $-k \in \mathbb{Z}$이므로 $3 \mid (b-a)$이다. 추이 — $a - b = 3k$, $b - c = 3l$이면 $a - c = (a-b) + (b-c) = 3k + 3l = 3(k+l)$이고 $k + l \in \mathbb{Z}$이므로 $3 \mid (a-c)$이다. 따라서 $R$는 동치관계이고, 동치류는 $[0], [1], [2]$의 세 개이며 정리 11.2에 의해 이 셋의 모임이 $\mathbb{Z}$의 분할이다. 훈련 2와 3의 답안은 위의 사다리 해설에 적힌 그대로 적는다. **복기.** 세 훈련을 나란히 놓으면 바뀌는 자리가 정확히 두 군데뿐이다 — 관계를 정의하는 등식과, 그 등식이 요구하는 닫힘성의 종류. 나머지 문장은 글자 그대로 같다. 이것이 "서식을 외운다"는 말의 실제 내용이다. ### 문제 5 **접근.** 막히는 자리는 대개 셋째 줄이다. 공유 원소 $c$에서 얻는 것은 $c \mathrel{R} a$와 $c \mathrel{R} b$인데, 추이를 쓰려면 화살이 $a \to c \to b$로 이어져야 한다. 방향을 뒤집는 성질이 대칭이고, 이어 붙이는 성질이 추이다. 그리고 목표가 집합의 상등이므로 두 방향의 포함을 각각 보여야 한다. **풀이.** $R$를 $A$ 위의 동치관계라 하고 $[a] \cap [b] \neq \emptyset$이라 하자. 그러면 $c \in [a] \cap [b]$인 원소 $c$가 존재한다. 교집합의 정의에 의해 $c \in [a]$이고 $c \in [b]$이며, 동치류의 정의에 의해 $c \mathrel{R} a$이고 $c \mathrel{R} b$이다. 대칭에 의해 $a \mathrel{R} c$이고, $a \mathrel{R} c$와 $c \mathrel{R} b$에 추이를 쓰면 $a \mathrel{R} b$이다. ($[a] \subseteq [b]$) $x \in [a]$라 하자. 그러면 $x \mathrel{R} a$이고, $a \mathrel{R} b$이므로 추이에 의해 $x \mathrel{R} b$, 곧 $x \in [b]$이다. ($[b] \subseteq [a]$) $x \in [b]$라 하자. 그러면 $x \mathrel{R} b$이다. 위에서 얻은 $a \mathrel{R} b$에 대칭을 쓰면 $b \mathrel{R} a$이고, $x \mathrel{R} b$와 $b \mathrel{R} a$에 추이를 쓰면 $x \mathrel{R} a$, 곧 $x \in [a]$이다. 양방향 포함이 성립하므로 $[a] = [b]$이다. $\blacksquare$ **복기.** 이 증명이 쓰는 성질은 둘뿐이다 — 대칭은 두 번, 추이는 세 번 쓰이고 반사는 한 번도 쓰이지 않는다. 어느 줄에서 무엇이 쓰였는지 세어 보면 대칭은 셋째 줄과 마지막 포함의 첫 줄에서, 추이는 셋째 줄과 두 포함 각각에서 소비된다. 대칭이나 추이가 없으면 §1.3의 삭제 실험 (나)$\cdot$(다)가 반례를 준다. 반사를 빼는 것은 이 보조정리의 반례가 되지 않는다 — 삭제 실험 (가)의 관계 $R = \{(1,1), (2,2), (1,2), (2,1)\}$은 반사적이 아니지만 대칭적이고 추이적이며, 조각은 $C(1) = C(2) = \{1,2\}$와 $C(3) = \emptyset$으로 이 보조정리가 그대로 성립한다. 반사가 일하는 자리는 정리 11.2의 조건 ①$\cdot$③이고, (가)에서 무너진 것도 바로 그 둘이다. ### 문제 6 **접근.** 정의 11.5대로 대표원끼리 계산한 뒤, 결과의 동치류를 $[0] \sim [3]$ 안으로 되돌린다. 되돌리는 근거는 정리 11.1이다 — 두 대표원의 차가 $4$의 배수이면 같은 동치류다. 계산 자체보다 "왜 되돌려도 되는가"를 한 줄로 적는 것이 채점 대상이다. **풀이.** $[2] + [3] = [2+3] = [5]$이고 $5 - 1 = 4$이므로 $4 \mid (5-1)$, 곧 $5 \equiv 1 \pmod 4$이다. 정리 11.1에 의해 $[5] = [1]$이므로 $[2] + [3] = [1]$이다. $[2] \cdot [3] = [2 \cdot 3] = [6]$이고 $6 - 2 = 4$이므로 $[6] = [2]$, 곧 $[2] \cdot [3] = [2]$이다. $[3] + [3] = [3+3] = [6] = [2]$이다. **검산.** 대표원을 바꿔 다시 계산해 본다. $[2] = [6]$이므로 $[6] + [3] = [9]$이고 $9 - 1 = 8$은 $4$의 배수이므로 $[9] = [1]$로 같다. $[6] \cdot [3] = [18]$이고 $18 - 2 = 16$은 $4$의 배수이므로 $[18] = [2]$로 같다. 이 일치를 보장하는 것이 예제 2.3과 문제 9의 well-defined 증명이다. ### 문제 7 **접근.** 세 성질이 전부 등식의 성질에서 곧바로 나온다 — 등식이 반사적$\cdot$대칭적$\cdot$추이적이기 때문이다(근거 ③). 동치류를 구할 때는 조건 $x^2 = a^2$을 $x^2 - a^2 = 0$으로 옮겨 인수분해하면 해가 두 개로 확정된다. 원소를 몇 개 나열하는 것이 아니라 집합을 닫힌 꼴로 적어야 채점 기준 ②를 통과한다. **풀이.** (반사) $a \in \mathbb{Z}$라 하자. $a^2 = a^2$이므로 $a \mathrel{R} a$이다. (대칭) $a \mathrel{R} b$라 하면 $a^2 = b^2$이고, 등식의 대칭성에 의해 $b^2 = a^2$이므로 $b \mathrel{R} a$이다. (추이) $a \mathrel{R} b$이고 $b \mathrel{R} c$라 하면 $a^2 = b^2$이고 $b^2 = c^2$이므로, 등식의 추이성에 의해 $a^2 = c^2$이고 $a \mathrel{R} c$이다. 세 성질이 성립하므로 $R$는 동치관계다. 동치류를 구한다. $[a] = \{x \in \mathbb{Z} : x^2 = a^2\}$이고, $x^2 = a^2$은 $x^2 - a^2 = 0$, 곧 $(x-a)(x+a) = 0$과 동치다. 정수에는 영인자가 없으므로 $x - a = 0$ 또는 $x + a = 0$, 곧 $x = a$ 또는 $x = -a$이다. 따라서 $[a] = \{a, -a\}$이다. $\blacksquare$ **검산.** $a = 3$이면 $[3] = \{3, -3\}$으로 원소가 두 개이고, $a = 0$이면 $[0] = \{0, -0\} = \{0\}$으로 원소가 하나다. 동치류의 크기가 균등하지 않아도 분할은 성립한다 — 분할의 세 조건 어디에도 조각의 크기가 들어 있지 않다. **복기.** 등식으로 정의된 관계는 언제나 동치관계다. "$f(a) = f(b)$일 때 관계 맺는다" 꼴의 관계가 전부 그러하며, 이 문제는 $f(x) = x^2$인 경우다. 문제 2(d)는 $f(x) = x$의 소수부인 경우로 볼 수 있다. ### 문제 8 **접근.** 세 조건의 동치를 보이는 값싼 방법은 순환 고리 하나를 만드는 것이다: ① $\Rightarrow$ ② $\Rightarrow$ ③ $\Rightarrow$ ①. 세 화살로 여섯 방향을 모두 얻는다. 예제 2.2가 ③ $\Rightarrow$ ②를 놓았고 그 논증의 앞부분이 ③ $\Rightarrow$ ①을 그대로 주므로 셋째 화살은 두 줄이면 끝난다. 아래에서는 고리를 자족적으로 다시 그리기 위해 세 화살을 모두 적는다. **풀이.** 조건을 ① $a \mathrel{R} b$, ② $[a] = [b]$, ③ $[a] \cap [b] \neq \emptyset$이라 하자. (① $\Rightarrow$ ②) $a \mathrel{R} b$라 하자. $x \in [a]$라 하면 $x \mathrel{R} a$이고, $a \mathrel{R} b$이므로 추이에 의해 $x \mathrel{R} b$, 곧 $x \in [b]$이다. 따라서 $[a] \subseteq [b]$이다. 거꾸로 $x \in [b]$라 하면 $x \mathrel{R} b$이고, $a \mathrel{R} b$에 대칭을 쓰면 $b \mathrel{R} a$이므로 추이에 의해 $x \mathrel{R} a$, 곧 $x \in [a]$이다. 따라서 $[b] \subseteq [a]$이고, 양방향 포함에서 $[a] = [b]$이다. (② $\Rightarrow$ ③) $[a] = [b]$라 하자. 반사에 의해 $a \mathrel{R} a$이므로 $a \in [a]$이고, 가정에 의해 $a \in [b]$이다. 따라서 $a \in [a] \cap [b]$이므로 이 교집합은 공집합이 아니다. (③ $\Rightarrow$ ①) $[a] \cap [b] \neq \emptyset$이라 하자. 그러면 $c \mathrel{R} a$이고 $c \mathrel{R} b$인 원소 $c$가 존재한다. 대칭에 의해 $a \mathrel{R} c$이고, 추이에 의해 $a \mathrel{R} b$이다. 세 화살이 고리를 이루므로 세 조건은 서로 동치이다. $\blacksquare$ **복기.** 순환 논법으로 동치를 보이는 이 서식은 조건이 셋 이상일 때 표준이다. $n$개의 조건에 대해 화살 $n$개만 그리면 되므로, 쌍마다 증명하는 것보다 훨씬 적게 쓴다. 어느 화살에 어느 성질이 쓰였는지 확인해 두면 §1.3의 표가 완성된다 — ① $\Rightarrow$ ②는 대칭과 추이, ② $\Rightarrow$ ③은 반사, ③ $\Rightarrow$ ①은 대칭과 추이다. ### 문제 9 **접근.** 덧셈에서는 $(a+b) - (a'+b')$이 곧바로 두 재료의 합이 되지만 곱에서는 그렇지 않다. $ab - a'b'$에는 $a$와 $b$가 섞여 있어 $a - a'$이나 $b - b'$ 어느 쪽으로도 바로 묶이지 않는다. 중간항 $a'b$를 더했다가 빼면 두 덩어리로 갈라진다 — 예제 2.1의 추이 증명에서 $b$를 끼워 넣었던 조작과 같은 수법이다. **풀이.** $[a] = [a']$, $[b] = [b']$이라 하자. 정리 11.1에 의해 $a \equiv a' \pmod 5$이고 $b \equiv b' \pmod 5$이므로, 합동의 정의에 의해 $a - a' = 5s$, $b - b' = 5t$인 정수 $s, t$가 존재한다. 그러면 $$ ab - a'b' = ab - a'b + a'b - a'b' = b(a - a') + a'(b - b') = 5bs + 5a't = 5(bs + a't) $$ 이고 $bs + a't$는 정수이므로(정수의 곱과 합은 정수, 근거 ②) $5$가 $ab - a'b'$을 나눈다. 곧 $ab \equiv a'b' \pmod 5$이고, 다시 정리 11.1에 의해 $[ab] = [a'b']$이다. 따라서 곱셈은 well-defined이다. $\blacksquare$ **검산.** $\mathbb{Z}_5$에서 $[3] \cdot [4] = [12] = [2]$이고, $[3]$을 $[8]$로 바꾸면 $[8] \cdot [4] = [32]$이며 $32 - 2 = 30$은 $5$의 배수이므로 $[32] = [2]$로 같다. **복기.** 중간항을 더했다가 빼는 조작은 곱의 차를 다룰 때의 표준이다. 같은 조작이 C6주차 예제 2.2의 (C5) 증명에 쓰였고, 부등식에서는 삼각부등식을 세우는 자리에 쓰인다. 어느 항을 끼워 넣을지는 목표가 정한다 — 여기서는 $a - a'$과 $b - b'$을 둘 다 만들어야 하므로 $a'b$가 유일한 후보다. ### 문제 10 **접근.** 증명 평가의 걸음 ①은 명제 자체의 진위다. 세 성질 중 반사와 대칭은 실제로 성립하고 답안도 정확히 적었으므로, 의심할 곳은 남은 하나다. 추이는 $a$에서 $b$로, $b$에서 $c$로 각각 $1$ 미만씩 움직였을 때 $a$에서 $c$까지의 거리를 묻는다. 두 번 움직이면 $2$ 가까이까지 갈 수 있으므로 이 자리에 반례가 산다. **풀이.** **판정: 틀림.** 결함은 "추이 성립"이라고 적은 셋째 줄이다. 그 줄은 아무 근거 없이 단언되었고(걸음 ②), 게다가 실제로 거짓이다(걸음 ①). 반례를 4단 서식으로 적는다. 명제가 거짓임을 보이므로 "$a_0 \mathrel{R} b_0$이고 $b_0 \mathrel{R} c_0$이면서 $a_0 \not\mathrel{R} c_0$인 실수 $a_0, b_0, c_0$이 존재한다"를 증명한다. $a_0 = 0$, $b_0 = 0.6$, $c_0 = 1.2$로 두자. 자격 — 셋 다 실수이고, $\lvert 0 - 0.6 \rvert = 0.6 < 1$이므로 $a_0 \mathrel{R} b_0$이며 $\lvert 0.6 - 1.2 \rvert = 0.6 < 1$이므로 $b_0 \mathrel{R} c_0$이다. 사건 — $\lvert 0 - 1.2 \rvert = 1.2$이고 $1.2 < 1$은 거짓이므로 $a_0 \not\mathrel{R} c_0$이다. 따라서 추이가 성립하지 않고, 이 관계는 동치관계가 아니다. $\blacksquare$ **복기.** 답안의 처음 두 줄은 옳다. 증명 평가에서 "틀림"이라고만 적으면 0점이고, **어느 줄이 왜** 틀렸는지를 지목해야 한다(C5주차 §1.6). 여기서는 결함이 하나의 줄에 집중되어 있고, 그 줄을 고칠 방법이 없다 — 명제 자체가 거짓이기 때문이다. 수리(C10주차 걸음 ④)는 두 방향으로 할 수 있다. 관계를 바꾸는 쪽이라면 "$a - b \in \mathbb{Z}$"로 옮겨 문제 2(d)의 동치관계를 얻는다. 관계식 $\lvert a - b \rvert < 1$을 그대로 두고 무대를 좁히는 쪽도 실제로 성립한다 — 무대를 $\mathbb{Z}$로 좁히면 서로 다른 두 정수의 차의 절댓값이 $1$ 이상이므로 $\lvert a - b \rvert < 1$은 $a = b$와 같은 조건이 되고, 상등은 동치관계다. 더 일반적으로, 서로 다른 두 점의 거리가 모두 $1$ 이상인 부분집합(예를 들어 $\{0, 5, 10\}$)에서는 이 관계가 상등이 되어 동치관계가 된다. 무대를 한 원소로 줄일 필요는 없다는 뜻이며, 원소가 무한히 많은 수리도 있다. ### 문제 11 **접근.** 정리 11.3을 인용하고 끝낼 수도 있지만, 이 문제는 그 정리의 증명을 구체적인 분할에서 다시 밟아 보라는 것이다. §1.5 확인 6이 세 성질 각각에 어느 분할 조건이 쓰이는지 알려 준다 — 반사에는 덮음, 추이에는 서로소가 필요하다. **풀이.** $E$를 짝수 전체, $O$를 홀수 전체라 하고 $\mathcal{S} = \{E, O\}$라 하자. $\mathcal{S}$가 $\mathbb{Z}$의 분할임은 C2주차 문제 11에서 확인했다. 관계를 "$a \mathrel{R} b \iff a$와 $b$가 $\mathcal{S}$의 같은 조각에 속한다"로 정의한다. (반사) 임의의 정수 $a$는 덮음 조건에 의해 $E$나 $O$ 중 하나에 속하므로, 그 조각을 $X$라 하면 $a$와 $a$가 함께 $X$에 있다. 따라서 $a \mathrel{R} a$이다. (대칭) $a \mathrel{R} b$이면 $a$와 $b$가 같은 조각 $X$에 있고, 이는 $b$와 $a$가 같은 조각에 있다는 말과 같은 문장이므로 $b \mathrel{R} a$이다. (추이) $a \mathrel{R} b$이고 $b \mathrel{R} c$라 하자. $a, b \in X$이고 $b, c \in Y$인 조각 $X, Y$가 있다. 그러면 $b \in X \cap Y$이므로 서로소 조건의 대우에 의해 $X = Y$이고, 따라서 $a$와 $c$가 같은 조각 $X$에 있어 $a \mathrel{R} c$이다. 세 성질이 성립하므로 $R$는 동치관계다. 동치류를 구한다. $a$가 짝수이면 $[a] = \{x : x$와 $a$가 같은 조각$\} = E$이고, $a$가 홀수이면 $[a] = O$이다. 따라서 동치류들의 모임은 $\{E, O\}$이며 원래 분할과 일치한다. $\blacksquare$ **복기.** 정리 11.2와 이 문제를 이어 붙이면 왕복이 완성된다 — 분할 $\{E, O\}$에서 동치관계를 만들고, 그 동치관계에서 다시 동치류를 만들면 $\{E, O\}$로 돌아온다. 같은 왕복을 반대 방향에서 출발해도 성립한다는 것이 문제 20(a)의 내용이다. ### 문제 12 **접근.** 계산은 한 줄이다. 문제가 요구하는 것은 그 한 줄이 무엇을 뜻하는지 — $\mathbb{Z}$에서는 일어나지 않는 일이 $\mathbb{Z}_6$에서는 일어난다는 관찰이다. 그리고 그 차이가 $6$의 어떤 성질에서 오는지를 소수와 대조해 답해야 한다. **풀이.** $[2] \cdot [3] = [2 \cdot 3] = [6]$이고 $6 - 0 = 6$이므로 $6 \mid (6-0)$, 곧 $[6] = [0]$이다. 따라서 $\mathbb{Z}_6$에서 $[2] \cdot [3] = [0]$이다. 그런데 $6 \nmid 2$이므로 $[2] \neq [0]$이고 $6 \nmid 3$이므로 $[3] \neq [0]$이다. 곧 $[0]$이 아닌 두 원소의 곱이 $[0]$이 되었으므로 $[2]$와 $[3]$은 영인자다. $p$가 소수이면 $\mathbb{Z}_p$에는 영인자가 없다. $[a] \cdot [b] = [0]$이라 하면 $p \mid ab$이고, 유클리드 보조정리(1권 33주차 문제 16에서 인정하고 쓴 것)에 의해 $p \mid a$ 또는 $p \mid b$, 곧 $[a] = [0]$ 또는 $[b] = [0]$이기 때문이다. $\mathbb{Z}_6$에서 이 논증이 통하지 않는 이유는 $6$이 합성수라 $6 = 2 \cdot 3$으로 쪼개지고, 두 인수가 각각 $6$의 배수가 아니면서 곱이 $6$의 배수가 되기 때문이다. **검산.** $\mathbb{Z}_6$의 다른 영인자 쌍도 같은 방식으로 나온다 — $[3] \cdot [4] = [12] = [0]$이고 $[4] \cdot [3] = [0]$, $[3] \cdot [2] = [0]$이므로 $[2]$, $[3]$, $[4]$가 모두 영인자다. 영인자는 두 원소의 쌍에 붙는 개념이므로 쌍 단위로 세는 것이 정확하다. $\mathbb{Z}_5$에서는 영인자를 찾으려 해도 $[a][b] = [0]$이 되는 $[0]$ 아닌 쌍이 없다. **복기.** 영인자의 존재는 소거가 불가능하다는 뜻이기도 하다. $[2] \cdot [3] = [2] \cdot [0]$인데 $[3] \neq [0]$이므로 $\mathbb{Z}_6$에서 $[2]$를 소거할 수 없다. 소거가 성립하지 않는 같은 현상을 1권 38주차 문제 11이 다룬다. "어떤 무대에서 나누기가 되는가"라는 물음이 여기서 처음 갈린다. C18$\cdot$C19주차의 군론이 그 물음의 절반(하나의 연산과 역원)을 이어받고, 두 연산을 함께 다루는 환과 체의 이야기는 C20주차 §1의 온라인 장 조망에서 자리를 얻는다. ### 문제 13 **접근.** "정확히 $n$개"는 두 가지 의무다 — 목록 $[0], [1], \ldots, [n-1]$이 전부를 **덮는다**와 그 목록에 **중복이 없다**. 앞쪽은 나눗셈 정리의 존재가 주고, 뒤쪽은 두 나머지의 차의 크기를 재는 계산이 준다. 두 의무 중 하나만 적으면 "목록이 전부를 덮는다"와 "목록에 겹침이 없다" 가운데 하나가 증명되지 않은 채로 남고, 그러면 "정확히 $n$개"라는 결론이 나오지 않는다 — 덮음만 있으면 개수가 $n$ 이하라는 것까지이고, 겹침 없음만 있으면 $n$ 이상이라는 것까지다. **풀이.** (덮음) 임의의 정수 $a$를 잡자. 나눗셈 정리(1권 33주차 예제 2.2)에 의해 $a = nq + r$, $0 \le r < n$인 정수 $q, r$이 존재한다. 그러면 $a - r = nq$이므로 $n \mid (a - r)$, 곧 $a \equiv r \pmod n$이고 정리 11.1에 의해 $[a] = [r]$이다. $r$은 $0$ 이상 $n$ 미만의 정수이므로 목록 안에 있다. 따라서 모든 동치류가 목록에 있다. (중복 없음) $0 \le r < r' < n$인 두 나머지를 잡자. 그러면 $0 < r' - r < n$이므로 $r' - r$은 $n$의 배수가 아니다 — $n$의 배수 중 $0$보다 크고 $n$보다 작은 것은 없기 때문이다. 따라서 $n \nmid (r' - r)$이고 $r \not\equiv r' \pmod n$이며, 정리 11.1의 대우에 의해 $[r] \neq [r']$이다. 목록이 전부를 덮고 중복이 없으므로 동치류는 정확히 $n$개다. $\blacksquare$ **복기.** 개수를 세는 증명의 표준 서식이 여기 있다 — 목록을 하나 제시하고, 그 목록이 빠뜨린 것이 없음(존재)과 겹친 것이 없음(유일)을 각각 보인다. 나눗셈 정리의 존재가 앞쪽을, 유일성(1권 33주차 문제 10)이 뒤쪽을 담당한다고 말할 수도 있다. 위 풀이는 유일성 대신 차의 크기를 직접 재는 방식을 택했고, 두 방식 모두 정답이다. ### 문제 14 **접근.** 지시문이 "동치관계가 아님을 보이라"이지만 (a)는 실제로 동치관계다. C10주차의 걸음 ①이 여기서 값을 한다 — 지시문의 방향을 믿기 전에 작은 값을 몇 개 넣어 판정한다. $a = 1, b = 3, c = 5$를 넣으면 세 성질이 모두 통과하고, 그 통과는 확정이 아니지만 방향을 참 쪽으로 정해 준다. (b)는 급소 목록(C10주차 §1.4)의 첫 줄인 $0$이 곧바로 걸린다. **풀이.** (a) 이 관계는 동치관계다. 반사 — $a + a = 2a$이고 $a$가 정수이므로 짝수다. 따라서 $a \mathrel{R} a$이다. 대칭 — $a + b$가 짝수이면 $b + a = a + b$도 짝수이므로 $b \mathrel{R} a$이다. 추이 — $a + b = 2k$, $b + c = 2l$인 정수 $k, l$이 존재한다고 하자. 그러면 $$ a + c = (a + b) + (b + c) - 2b = 2k + 2l - 2b = 2(k + l - b) $$ 이고 $k + l - b$는 정수이므로 $a + c$는 짝수이며 $a \mathrel{R} c$이다. 세 성질이 성립하므로 동치관계다. 실제로 $a + b$가 짝수라는 것은 $a$와 $b$의 홀짝이 같다는 뜻이므로 이 관계는 $a \equiv b \pmod 2$와 같은 관계이고, 예제 2.1이 이미 증명한 동치관계다. (b) 이 관계는 동치관계가 아니다. 반사가 실패한다. 반례로 $a_0 = 0$을 잡자. 자격 — $0$은 실수다. 사건 — $a_0 \cdot a_0 = 0$이고 $0 > 0$은 거짓이므로 $a_0 \not\mathrel{R} a_0$이다. 따라서 "모든 $a$에 대해 $a \mathrel{R} a$"가 거짓이고 동치관계가 아니다. (대칭과 추이는 성립한다 — $ab > 0$이면 $ba > 0$이고, $ab > 0$이고 $bc > 0$이면 $a$와 $c$가 $b$와 같은 부호를 공유하므로 $ac > 0$이다. 곧 실패하는 것은 반사 하나뿐이며, 무대를 $\mathbb{R} - \{0\}$으로 좁히면 동치관계가 된다 — 1권 36주차 문제 14가 이 수리를 시킨다.) **복기.** (a)는 지시문이 답을 미리 정해 놓지 않는다는 것을 보여 준다. 답안에 적어야 할 것은 "동치관계가 아니다"가 아니라 판정 결과와 그 근거이며, 결과가 지시문의 예상과 달라도 근거가 정확하면 만점이다. C10주차 §1.2의 걸음 ②가 정확히 이 일을 하는 걸음이다. ### 문제 15 **접근.** 조건 ②의 진술을 정확히 적는 것이 관건이다. 분할이 요구하는 것은 "서로 다른 두 조각이 서로소"이므로, 보일 것은 "$[a] \neq [b]$이면 $[a] \cap [b] = \emptyset$"이다. 예제 2.2는 그 대우를 증명한 것이므로 그대로 인용하면 된다. 나머지 두 조건은 반사에서 한 줄씩 나온다. **풀이.** $A$를 공집합이 아닌 집합, $R$를 $A$ 위의 동치관계라 하고 $\mathcal{S} = \{[a] : a \in A\}$라 하자. 무대가 공집합이 아니라는 전제는 C2주차 정의 2.3이 분할을 공집합이 아닌 집합에 대해서만 정의하기 때문에 필요하다. $\mathcal{S}$가 $A$의 분할임을 그 정의의 세 조건으로 보인다. (① 비공집합) $\mathcal{S}$의 임의의 원소는 어떤 $a \in A$에 대한 $[a]$다. 반사에 의해 $a \mathrel{R} a$이므로 $a \in [a]$이고, 따라서 $[a] \neq \emptyset$이다. (② 쌍마다 서로소) $\mathcal{S}$의 서로 다른 두 원소 $[a]$, $[b]$를 잡자. 곧 $[a] \neq [b]$이다. 예제 2.2에 의해 $[a] \cap [b] \neq \emptyset$이면 $[a] = [b]$이므로, 그 대우에 의해 $[a] \neq [b]$이면 $[a] \cap [b] = \emptyset$이다. 따라서 두 조각은 서로소다. (③ 덮음) $\mathcal{S}$의 원소들은 전부 $A$의 부분집합이므로 그 합집합은 $A$에 포함된다. 거꾸로 임의의 $a \in A$에 대해 반사에 의해 $a \in [a]$이고 $[a] \in \mathcal{S}$이므로 $a$는 합집합에 속한다. 양방향 포함에 의해 합집합이 $A$와 같다. 세 조건이 모두 성립하므로 $\mathcal{S}$는 $A$의 분할이다. $\blacksquare$ **복기.** 조건 ③을 "각 $a$가 $[a]$에 속한다"로만 적고 끝내는 답안이 많은데, 분할의 조건 ③은 합집합이 $A$와 **같다**는 집합의 상등이므로 양방향 포함을 적어야 완결된다. 한쪽 방향은 각 조각이 $A$의 부분집합이라는 사실에서 자동으로 나오지만, 그 한 줄이 없으면 합집합이 $A$에 포함된다는 방향이 증명되지 않아 상등이 미완으로 남는다. ### 문제 16 **접근.** $\mathbb{Z}_5$는 원소가 다섯 개뿐이므로 전수 대입으로 확정할 수 있다. $[0]$이 아닌 각 원소에 대해 $[1]$이 나오는 상대를 찾으면 되고, 곱셈이 교환적이므로 한 쌍을 찾으면 두 원소의 역원이 동시에 정해진다. 답만 적지 말고 각 곱을 계산한 줄과 $[1]$로 되돌린 근거를 함께 적는다. **풀이.** $[1] \cdot [1] = [1]$이므로 $[1]^{-1} = [1]$이다. $[2] \cdot [3] = [6]$이고 $6 - 1 = 5$이므로 $[6] = [1]$이다. 따라서 $[2]^{-1} = [3]$이고, 곱셈이 교환적이므로 $[3]^{-1} = [2]$이다. $[4] \cdot [4] = [16]$이고 $16 - 1 = 15 = 5 \cdot 3$이므로 $[16] = [1]$이다. 따라서 $[4]^{-1} = [4]$이다. $[0]$이 아닌 네 원소가 모두 곱셈 역원을 가지므로 $\mathbb{Z}_5$는 체다. $\mathbb{Z}_6$은 그렇지 않다. $[2]$에 역원이 있다면 $[2][x] = [1]$인 $[x]$가 있고, 양변에 $[3]$을 곱하면 $[3][2][x] = [3]$인데 좌변은 $[6][x] = [0][x] = [0]$이므로 $[0] = [3]$이 되어 모순이다. 곧 문제 12의 영인자가 역원의 존재를 막는다. **검산.** 네 역원을 곱해 확인한다 — $1 \cdot 1 = 1$, $2 \cdot 3 = 6 \equiv 1$, $3 \cdot 2 = 6 \equiv 1$, $4 \cdot 4 = 16 \equiv 1 \pmod 5$. 넷 다 $[1]$이 나온다. **복기.** "$\mathbb{Z}_p$는 체이고 $\mathbb{Z}_n$은 $n$이 합성수이면 체가 아니다"가 문제 12와 이 문제를 합친 결론이다. 위 논증은 영인자에서 역원의 부재를 끌어낸 것으로, 일반적으로 영인자는 역원을 가질 수 없다 — $xy = [0]$이고 $y \neq [0]$인데 $x$에 역원 $x^{-1}$이 있다면 $xy = [0]$의 양변에 $x^{-1}$을 곱해 $y = [0]$이 나오는데, $y$는 $[0]$이 아니라고 잡았으므로 모순이다. 영인자와 역원을 가르는 이 관계가 곧 환과 체를 가르는 기준이며, 그 이름과 자리는 C20주차 §1의 온라인 장 조망에서 소개된다. ### 문제 17 **접근.** 정의 11.1에 의해 관계는 $A \times A$의 부분집합이므로 교집합과 합집합이 그대로 정의된다. 원소 수준으로 풀면 "$R \cap S$로 관계 맺음"은 "두 관계 모두에서 관계 맺음"이고, 세 성질의 증명은 각 관계에서 얻은 결론을 "그리고"로 묶는 일이 된다. 합집합에서는 "이거나"가 두 관계를 오가며 사슬을 만들 수 있다는 점이 반례의 급소다. **풀이.** ($R \cap S$가 동치관계) (반사) 임의의 $a \in A$에 대해, $R$가 반사적이므로 $a \mathrel{R} a$이고 $S$가 반사적이므로 $a \mathrel{S} a$이다. 따라서 $a \mathrel{(R \cap S)} a$이다. (대칭) $a \mathrel{(R \cap S)} b$라 하자. 그러면 $a \mathrel{R} b$이고 $a \mathrel{S} b$이며, 각 관계의 대칭성에 의해 $b \mathrel{R} a$이고 $b \mathrel{S} a$이다. 따라서 $b \mathrel{(R \cap S)} a$이다. (추이) $a \mathrel{(R \cap S)} b$이고 $b \mathrel{(R \cap S)} c$라 하자. 그러면 $a \mathrel{R} b$, $b \mathrel{R} c$이므로 $R$의 추이성에 의해 $a \mathrel{R} c$이고, 마찬가지로 $a \mathrel{S} c$이다. 따라서 $a \mathrel{(R \cap S)} c$이다. 세 성질이 성립하므로 $R \cap S$는 동치관계다. ($R \cup S$의 반례) $\mathbb{Z}$ 위에서 $R$를 "$a - b$가 $2$의 배수", $S$를 "$a - b$가 $3$의 배수"로 두자. 둘 다 동치관계다(예제 2.1과 훈련 1). $a_0 = 1$, $b_0 = 3$, $c_0 = 6$으로 두자. 자격 — $1 - 3 = -2$는 $2$의 배수이므로 $1 \mathrel{R} 3$이고 따라서 $1 \mathrel{(R \cup S)} 3$이다. $3 - 6 = -3$은 $3$의 배수이므로 $3 \mathrel{S} 6$이고 따라서 $3 \mathrel{(R \cup S)} 6$이다. 사건 — $1 - 6 = -5$는 $2$의 배수도 아니고 $3$의 배수도 아니므로 $1 \not\mathrel{R} 6$이고 $1 \not\mathrel{S} 6$이며, 따라서 $1 \not\mathrel{(R \cup S)} 6$이다. 곧 추이가 성립하지 않으므로 $R \cup S$는 동치관계가 아니다. $\blacksquare$ **복기.** 두 결과가 갈리는 이유는 논리 연결사에 있다. 세 성질의 결론은 전부 "~이면 ~이다" 꼴이고, "그리고"는 가정과 결론 양쪽에 고르게 분배되지만 "이거나"는 그렇지 않다. 가정이 $R$ 쪽에서 오고 결론이 $S$ 쪽으로 가야 할 때 이어 줄 것이 없다 — 위 반례가 정확히 그 상황을 만든 것이다. ### 문제 18 **접근.** 문제 10과 결함의 종류가 다르다. 문제 10은 거짓인 줄을 적었고, 이 답안은 줄 하나를 아예 적지 않았다. 평가에서는 두 가지를 모두 적어야 한다 — 무엇이 빠졌는가, 그리고 그 빠진 것이 실제로 성립하는가. 빠진 성질이 성립한다면 결함은 전달의 문제이고, 성립하지 않는다면 명제 자체가 거짓이다. **풀이.** **판정: 틀림.** 결함은 두 겹이다. 첫째, 증명 평가의 걸음 ③과 ⑤에 해당하는 결함으로 **대칭을 다루지 않았다.** 정의 11.3은 세 성질을 모두 요구하는데 답안은 둘만 확인하고 "따라서 동치관계"라고 결론을 내렸다. 둘로는 셋을 결론지을 수 없다. 둘째, 걸음 ①에 해당하는 결함으로 **명제 자체가 거짓이다.** 빠뜨린 대칭이 실제로 실패한다. 곧 "$a \mid b$이고 $b \nmid a$인 쌍 $(a,b)$가 존재한다"를 증명한다. 반례로 $(a_0, b_0) = (2, 4)$를 잡자. 자격 — $4 = 2 \cdot 2$이고 $2 \in \mathbb{Z}$이므로 $2 \mid 4$이다. 사건 — $2 = 4k$인 정수 $k$가 존재하지 않으므로 $4 \nmid 2$이다. 따라서 대칭이 성립하지 않고 "$\mid$"는 동치관계가 아니다. 답안의 반사와 추이 줄은 옳으므로 그 두 줄은 그대로 살릴 수 있으나, 결론은 반대로 바뀐다. **복기.** 빠뜨림이 두 종류라는 점을 구분해 두면 평가가 정확해진다. 빠뜨린 성질이 성립하는 경우라면 판정은 "불완전"이고 그 성질을 채워 넣으면 답안이 완성된다. 이 문제처럼 빠뜨린 성질이 거짓이면 판정은 "틀림"이고 채워 넣을 수 없다. 빠진 자리를 찾았을 때 곧바로 그 자리의 진위를 검사해야 하는 이유다. 덧붙여 "$\mid$"는 $\mathbb{Z}$에서 반사적이고 추이적이지만 반대칭적이지는 않다 — $2 \mid (-2)$이고 $(-2) \mid 2$인데 $2 \neq -2$이기 때문이다. 무대를 양의 정수로 좁히면 반대칭성이 성립하고, 반사$\cdot$추이$\cdot$반대칭을 갖춘 관계를 부분순서라 부른다 — 동치관계와 나란히 놓이는 또 하나의 큰 갈래다. 이 문제의 무대가 $\mathbb{Z}$라는 점을 놓치면 반대칭성을 그냥 있다고 적게 되므로, 성질을 말할 때 무대를 함께 밝히는 습관이 여기서도 값을 한다. ### 문제 19 **접근.** ill-defined를 보이는 것은 반례를 드는 일이므로 C7주차 §1.4의 4단 서식을 쓴다. 증인은 **대표원 한 쌍**이다 — 같은 동치류의 두 표현을 제시하고(자격), 그 둘에서 규칙이 주는 값이 다름을 계산으로 보인다(사건). 어느 자리를 흔들지가 관건인데, 밑을 흔들면 곱셈의 well-defined가 막아 주므로 지수를 흔들어야 한다. **풀이.** $\mathbb{Z}_3$에서 규칙 "$[a]^{[b]} = [a^b]$"가 well-defined가 아님을 보인다. 곧 "$[b_0] = [b_0']$이면서 $[a_0^{b_0}] \neq [a_0^{b_0'}]$인 $a_0, b_0, b_0'$이 존재한다"를 증명한다. $a_0 = 2$, $b_0 = 2$, $b_0' = 5$로 두자. 자격 — $5 - 2 = 3$이므로 $3 \mid (5-2)$, 곧 $5 \equiv 2 \pmod 3$이고 정리 11.1에 의해 $[2] = [5]$이다. 지수 자리의 두 표현이 같은 동치류를 가리킨다. 사건 — 규칙이 주는 값을 각각 계산한다. $2^2 = 4$이고 $4 - 1 = 3$이므로 $[4] = [1]$이다. $2^5 = 32$이고 $32 - 2 = 30 = 3 \cdot 10$이므로 $[32] = [2]$이다. 그런데 $2 - 1 = 1$이고 $3 \nmid 1$이므로 $[1] \neq [2]$이다. 같은 동치류의 두 표현에서 규칙이 서로 다른 값을 주므로 이 규칙은 well-defined가 아니다. $\blacksquare$ **복기.** 밑과 지수가 다르게 처리되는 이유는 well-defined 검사의 걸음 ②에서 드러난다. 밑을 바꾸는 것은 $a - a'$이 $n$의 배수라는 정보를 주고, 그 정보는 곱셈 보존(C6주차의 (C5))을 통해 $a^b - a'^b$으로 전달된다. 반면 지수를 바꾸는 것은 $b - b'$이 $n$의 배수라는 정보를 주는데, 그 정보를 $a^b - a^{b'}$으로 옮겨 주는 법칙이 없다. 같은 ill-defined 사례를 S19주차 문제 9가 $\mathbb{Z}_2$에서 다루고, 밑 쪽은 안전하다는 대조를 S19주차 문제 17이 $f([a]) = [a^2]$의 well-defined 증명으로 보인다. 지수 자리를 법 안에서 다루는 도구는 이 과정의 범위 밖이다 — C9주차 문제 16이 같은 경계를 긋고 필요할 때 기성 정리로 인용하라고 남겨 둔다. ### 문제 20 **접근.** (a)는 정리 11.2와 11.3을 한 문장씩으로 요약하고, 두 정리가 서로 역방향이라는 점을 셋째 문장에 둔다. 예제 2.1이 구체 사례를 제공하므로 그것을 먼저 놓고 일반화로 올라가는 순서가 읽기 쉽다. (b)는 §1.6의 걸음 삭제 실험이 무엇을 무너뜨렸는지를 첫 문장에, 합동의 (C4)(C5)가 정확히 무엇을 보장하는지를 둘째 문장에 둔다. **풀이.** (예시 답안) (a) 예제 2.1에서 "차가 짝수"라는 동치관계가 $\mathbb{Z}$를 짝수와 홀수 두 동치류로 갈랐고, 정리 11.2가 이를 일반화해 어떤 동치관계에서도 동치류들이 분할을 이룸을 보장한다. 거꾸로 정리 11.3은 분할이 주어지면 "같은 조각에 속함"이라는 동치관계가 따라 나오고 그 동치류가 원래 조각들과 일치함을 보장한다. 두 정리가 서로 역방향이므로 동치관계 하나와 분할 하나가 정확히 짝을 이루며, C2주차가 분할을 세 조건으로만 세워 두고 남긴 자리가 이 짝짓기로 채워진다. (b) $\mathbb{Z}_n$의 연산은 동치류가 아니라 그 대표원을 통해 계산되므로, 대표원을 바꿨을 때 결과가 달라진다면 같은 대상에 두 값이 붙어 $[1] = [4]$ 같은 거짓 등식이 유도되고 무대 전체의 계산을 신뢰할 수 없게 된다(§1.6의 걸음 삭제 실험). 합동의 합 보존과 곱 보존(1권 20주차의 (C4)(C5), C6주차 예제 2.2)이 정확히 이 대표 무관성을 보장하며, 예제 2.3과 문제 9의 증명이 그 보존 법칙을 동치류의 언어로 다시 적은 것이다. **복기.** 서술 문제의 채점 기준은 문장 수가 아니라 인용의 정확성이다. "두 얼굴"이라는 표현을 쓰더라도 어느 정리가 어느 방향을 담당하는지 번호로 지목해야 한다. (b)에서 "well-defined가 중요하다"로 끝내면 절반이고, 무엇이 무너지는지를 구체적인 거짓 등식 하나로 보여야 완결된다. --- **다음 주 예고 (C12주차):** Chartrand 10장 — 함수. 1권 40~44주차의 함수 소재와 S6주차의 선택법을 Chartrand의 언어로 다시 조직한다. 함수의 정의, 단사와 전사와 전단사, 합성함수, 역함수, 상과 원상이 차례로 나온다. 이번 주의 동치류가 그 첫 절에서 곧바로 다시 쓰인다 — 동치류를 정의역으로 삼는 함수는 대표원으로 값을 정하므로 §1.6의 well-defined 검사 세 걸음을 그대로 받는다. 원서 10장을 통독하고 온다.