C11주차 · 강의 — 예제 · 연습 · 해설#
예제 — 판정부터 함께 만들기#
완성된 답안을 먼저 보이지 않는다. 백지에서 설계부터 한 줄씩 만든다. 각 단계에서 확인 상자의 빈칸을 연필로 먼저 채운 뒤 답을 연다.
예제 2.1 — 동치관계 판정#
명제. \(\mathbb{Z}\) 위의 관계 “\(a \mathrel{R} b \iff a - b\)가 짝수”는 동치관계이다.
설계 — 쓰기 전에 정하는 두 가지. 가정이 주는 것(출발점)과 만들어야 할 것(도착점)을 먼저 정의로 번역한다. 이번 명제는 가정이 관계의 정의 한 줄뿐이고 도착점이 세 개다.
말 |
수식 번역 |
|
|---|---|---|
가정 (주어진 것) |
\(a \mathrel{R} b\) |
\(a - b = 2k\)인 정수 \(k\)가 존재한다 |
목표 (만들 것) |
\(R\)가 동치관계 |
\(\underline{\quad(?)\quad}\) |
확인 10. 목표 칸의 빈칸을 채워 보자. “동치관계임을 보인다”를 정의 11.3으로 번역하면 무엇을 몇 개 증명해야 하는가.
답
세 개의 독립한 \(\forall\) 명제 — 반사, 대칭, 추이를 각각 증명해야 한다.
정의 11.3은 세 성질을 “그리고”로 묶었으므로 하나라도 빠지면 결론이 나오지
않는다. 곧 이 답안은 세 개의 작은 증명이 나란히 놓인 형태가 되고, 각각은
\(\forall\) 명제이므로 선택법으로 임의의 정수를 잡아 시작한다.
1단계 — 반사. 임의의 \(a\)에 대해 \(a \mathrel{R} a\)를 보여야 하므로, \(a - a\)가 짝수임을 정의의 꼴로 제시한다.
확인 11. 첫 조각을 완성해 보자: “\(a \in \mathbb{Z}\)라 하자. \(a - a = \underline{\quad} = 2 \cdot \underline{\quad}\)이고 \(\underline{\quad}\)는 정수이므로 \(a \mathrel{R} a\)이다.”
답
\(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\)의 꼴을 만들어 제시한다.
확인 12. 둘째 조각을 완성해 보자: “\(a \mathrel{R} b\)라 하자. 정의에 의해 \(a - b = 2k\)인 정수 \(k\)가 존재한다. 그러면 \(b - a = \underline{\quad} = 2(\underline{\quad})\)이고 \(\underline{\quad}\)는 정수이므로 \(b \mathrel{R} a\)이다.”
답
\(b - a = -(a-b) = -2k = 2(-k)\)이고 \(-k\)는 정수이므로 \(b \mathrel{R} a\)이다.
핵심은 \(b - a\)를 가정이 준 재료 \(a - b\)로 바꿔 적는 첫 등호다. 재료가 하나뿐일
때는 목표를 그 재료의 식으로 다시 쓰는 것이 유일한 출발이다.
3단계 — 추이. 가정이 둘이므로 정수도 둘 받아 오고, 목표 \(a - c\)를 두 재료의 합으로 만든다.
확인 13. 셋째 조각을 완성해 보자: “\(a \mathrel{R} b\)이고 \(b \mathrel{R} c\)라 하자. 정의에 의해 \(a - b = 2k\), \(b - c = 2l\)인 정수 \(k, l\)이 존재한다. 그러면 \(a - c = \underline{\quad} = 2(\underline{\quad})\)이다.”
답
\(a - c = (a-b) + (b-c) = 2k + 2l = 2(k+l)\)이다.
가운데 항 \(b\)가 더해지고 빼지며 사라지는 것이 이 줄의 전부다. 목표에 없는
문자를 끼워 넣었다가 소거하는 이 조작은 합동\(\cdot\)부등식\(\cdot\)집합에서 되풀이해서
쓰이며, C6주차 예제 2.1의 선형결합도 같은 조작이었다.
4단계 — 결론과 동치류. 세 성질이 모두 성립했으므로 정의 11.3으로 결론을 선언하고, 정리 11.2가 주는 분할이 무엇인지 확인한다.
확인 14. 이 동치관계의 서로 다른 동치류는 몇 개이고 각각 무엇인가. 정리 11.1을 써서 \([0] = [2]\)와 \([0] \neq [1]\)을 판정해 보자.
답
두 개다 — \([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]\)이다.
이번에는 설계만 함께 하고, 본문은 완성본으로 본다.
확인 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}\)를 각각 보인다.
답
가정: 그런 원소 \(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이다.
이번에는 설계부터 스스로 해 보자.
확인 16. 번역표를 채워 보자. 가정 “\([a] = [a']\)이고 \([b] = [b']\)”을 정리 11.1과 합동의 정의로 풀면 무엇이 되는가. 목표 “\([a+b] = [a'+b']\)”은 같은 번역을 거꾸로 하면 무엇을 보이는 일이 되는가.
답
가정: \(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\)가 존재한다. 그러면
이고 \(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}\) |
확인 17. (1)(2)(3)을 채우고, 세 예제가 공통으로 밟은 순서를 한 문장으로 적어 보자.
답
(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이다.
공통 순서: **가정과 목표를 각각 정의로 끝까지 풀어 계산 가능한 등식으로 바꾸고,
재료에서 목표 꼴을 만든 뒤 정의를 거꾸로 밟아 원래 언어로 되돌린다.**
이번 주에 새로 붙은 것은 푸는 겹이 하나 늘었다는 점뿐이다 — 동치류는 집합이므로
집합 표기를 관계로, 관계를 나눗셈 등식으로 두 번 풀어야 계산이 시작된다.
방금 확인한 뼈대에 이름을 붙인다.
백지 암기 대상
동치관계 답안의 서식
① 판정 — 세 성질을 각각 증명하거나 반례를 든다. 하나라도 빠지면 동치관계라고 부를 수 없다.
② 조각 — 동치류를 정의대로 적고, 서로 다른 동치류의 목록과 개수를 확정한다.
③ 왕복 — 정리 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\)가 존재한다.
걸음 ③. 그러면
이고, \(\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\) 그래도 안 되면 풀이를 읽는다.
이번 주의 채점 기준
답이 아니라 근거가 점수다. 이번 주 답안에는 채점 항목이 넷이다.
① 관계 판정에서 세 성질을 각각 다뤘는가. 성립은 선택법으로 증명하고, 불성립은 반례를 C7주차 §1.4의 4단 서식으로 적는다. “동치관계이다”라는 낱말만 적으면 0점이다.
② 동치류를 물었으면 정의대로 \(\{x : x \mathrel{R} a\}\)를 적고, 서로 다른 동치류가 몇 개인지 확정했는가. 예시 원소 나열만으로는 개수가 확정되지 않는다.
③ 분할을 주장했으면 세 조건이 각각 어느 성질에서 오는지 밝혔는가. 정리 11.2를 인용해도 되지만 인용했음을 적어야 한다.
④ 동치류 위의 연산을 다뤘으면 well-defined 검사 세 걸음이 있는가. 대표원을 문자로 잡지 않은 검사는 사례 확인이다.
난이도와 무관하게, 힌트 상자는 5분 이상 막힌 뒤에만 연다.
기본 ●○○#
1. [백지] 세 성질 정의, 동치관계\(\cdot\)동치류 정의, 핵심 정리(동치관계\(\leftrightarrow\)분할), well-defined의 뜻을 쓰시오.
힌트
정의 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}\)”
힌트
네 문항 모두 §1.2의 표에 이미 재료가 있다. (c)에서 추이를 검사할 때는 세 사람이
서로 달라야 한다는 조건이 없다는 점을 이용한다 — 셋째 사람으로 첫째 사람을
다시 쓰면 무엇이 나오는가. (d)는 훈련 3에서 뼈대를 세운 그 관계다.
3. 예제 2.1(짝수 차 동치관계)을 백지 재현하시오.
힌트
세 조각의 순서가 아니라 각 조각의 첫 문장이 관건이다. 반사는 “\(a\)를 임의의
정수라 하자”, 대칭과 추이는 “\(a \mathrel{R} b\)라 하자”로 시작한다. 시작 문장이
정해지면 나머지는 정의를 푸는 일뿐이다.
4. 빈칸 훈련을 백지에서 완성하시오.
힌트
훈련 1은 예제 2.1에서 \(2\)를 \(3\)으로 바꾼 것이고, 훈련 2는 예제 2.3에서 \(5\)를
\(4\)로 바꾼 것이다. 바뀌지 않은 것이 무엇인지 확인하면서 적는다.
5. 예제 2.2(핵심 보조정리)를 백지 재현하시오.
힌트
막히는 자리는 대개 셋째 줄이다. 공유 원소 \(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]\)을 계산하시오.
힌트
정의 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\}\)).
힌트
세 성질이 전부 등식의 성질에서 곧바로 나온다 — 등식이 반사적\(\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\)”의 동치를 완성하시오.
힌트
세 조건의 동치를 보이는 값싼 방법은 순환 고리 하나를 만드는 것이다:
① \(\Rightarrow\) ② \(\Rightarrow\) ③ \(\Rightarrow\) ①. 예제 2.2가 ③ \(\Rightarrow\) ②를
증명했고 그 논증의 앞부분(공유 원소에 대칭과 추이를 쓰는 두 줄)이 곧
③ \(\Rightarrow\) ①이므로, 그 두 줄을 그대로 옮겨 쓰면 된다. ②에서 ③으로 가는
화살에는 반사가 필요하다 — \(a\)가 어느 동치류에 들어 있는가.
9. \(\mathbb{Z}_5\)에서 \([a] \cdot [b] = [ab]\)가 well-defined임을 증명하시오 (예제 2.3의 곱셈판 — 합동 곱셈 보존, C6주차 예제 2.2).
힌트
덧셈에서는 \((a+b) - (a'+b')\)이 곧바로 두 재료의 합이 되지만, 곱에서는 그렇지
않다. \(ab - a'b'\)에 \(a'b\)를 더했다가 빼면 두 덩어리로 갈라진다. 예제 2.1의 추이
증명에서 \(b\)를 끼워 넣었던 조작과 같은 수법이다.
10. 다음 제시된 증명을 평가하시오 (C5주차의 증명 평가 다섯 걸음).
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\) ✓. 추이 성립. 따라서 동치관계.
힌트
증명 평가의 걸음 ①은 명제 자체의 진위다. 세 성질 중 두 개는 실제로 성립하므로,
의심할 곳은 남은 하나다. 추이는 \(a\)에서 \(b\)로, \(b\)에서 \(c\)로 각각 \(1\) 미만씩
움직였을 때 \(a\)에서 \(c\)까지의 거리를 묻는다 — 두 번 움직이면 얼마까지 갈 수 있는가.
11. 분할 \(\to\) 동치관계: \(\mathbb{Z}\)의 분할 \(\{짝수, 홀수\}\)에서 “같은 조각에 속함” 관계가 동치관계이고 그 동치류가 짝수\(\cdot\)홀수임을 확인하시오 (핵심 정리의 역방향).
힌트
정리 11.3을 인용해도 되지만, 이 문제는 그 정리의 증명을 구체적인 분할에서
다시 밟아 보라는 것이다. §1.5 확인 6이 세 성질 각각에 어느 분할 조건이
쓰이는지 알려 준다.
12. \(\mathbb{Z}_6\)의 곱셈표에서 \([2] \cdot [3] = [0]\)임을 계산하고, “0이 아닌 두 원소의 곱이 0”(\(\mathbb{Z}_6\)의 영인자)이 됨을 관찰하시오 (\(\mathbb{Z}_p\) \(p\) 소수와의 차이 — C18주차 예고).
새 낱말 — 영인자 (zero divisor)
곱셈이 있는 무대에서 \(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\)이 서로 다른 동치류이고 전부를 덮음 — 나눗셈 정리).
힌트
“정확히 \(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\)).
힌트
지시문이 “아님을 보이라”이지만 (a)는 실제로 동치관계다. C10주차의 걸음 ①이
여기서 값을 한다 — 지시문의 방향을 믿기 전에 작은 값을 몇 개 넣어 판정한다.
(b)는 급소 목록(C10주차 §1.4)의 첫 줄인 \(0\)이 곧바로 걸린다.
도전 ●●●#
15. (핵심 정리 완전 증명) “동치관계 \(R\)의 동치류들이 \(A\)의 분할을 이룬다”를 세 조건(비공\(\cdot\)서로소\(\cdot\)덮음)으로 완전 증명하시오 (예제 2.2를 서로소에 사용).
힌트
조건 ②의 진술을 정확히 적는 것이 관건이다. 분할이 요구하는 것은 “서로 다른
두 조각이 서로소”이므로, 보일 것은 “\([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).
새 낱말 — 곱셈 역원과 체 (field)
\([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\)는 왜 일반적으로 동치관계가 아닌지 반례로 (추이 실패).
관계는 집합이다 — 교집합과 합집합
정의 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. (진단 종합) 다음 제시된 증명을 평가하시오.
Result. \(\mathbb{Z}\) 위 “\(a \mathrel{R} b \iff a \mid b\)”는 동치관계이다.
증명. 반사 \(a \mid a\) ✓. 추이 \(a \mid b, b \mid c \Rightarrow a \mid c\) ✓. 따라서 동치관계.
힌트
문제 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).
힌트
ill-defined를 보이는 것은 반례를 드는 일이므로 C7주차 §1.4의 4단 서식을 쓴다.
증인은 대표원 한 쌍이다 — 같은 동치류의 두 표현을 제시하고(자격), 그 둘에서
규칙이 주는 값이 다름을 계산으로 보인다(사건).
20. (서술) (a) 동치관계와 분할이 “같은 것의 두 얼굴”임을 예제 2.1(짝수 차 \(\to\) 짝\(\cdot\)홀 분할)과 핵심 정리로 뒷받침하고, C2주차에서 심은 씨앗이 어떻게 꽃폈는지 세 문장 이내로. (b) \(\mathbb{Z}_n\) 연산의 well-defined가 왜 필수인지(대표 무관), 합동 보존(C6주차)과의 관계를 두 문장 이내로.
힌트
(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\)이 존재한다. 그러면
이고 \(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\)가 존재한다. 그러면
이고 \(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\)이 존재한다고 하자. 그러면
이고 \(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장을 통독하고 온다.