C14주차 · 강의 — 예제 · 연습 · 해설#
예제 — 두 단사로 상등을 만들기#
완성된 증명을 먼저 보이지 않는다. 백지에서 시작해 한 줄씩 만든다. 각 단계에서 확인 상자의 빈칸을 연필로 먼저 채운 뒤 답을 연다.
예제 2.1 — CSB로 \(|(0,1)| = |[0,1]|\)#
명제. \(|(0,1)| = |[0,1]|\).
설계 — 쓰기 전에 정하는 두 가지. 증명을 쓰기 전에 가정이 주는 것(출발점)과 만들어야 할 것(도착점)을 정한다. 둘 다 정의로 번역해서 얻는다.
말 |
수식 번역 |
|
|---|---|---|
가정 (주어진 것) |
두 무대는 \((0,1)\)과 \([0,1]\)이다 |
\((0,1) \subseteq [0,1]\)이고 두 집합은 끝점 \(0\), \(1\) 두 개만 다르다 |
목표 (만들 것) |
두 집합이 같은 크기 |
\(\underline{\quad(?)\quad}\) |
확인 11. 목표 칸의 빈칸을 채워 보자. 정리 1.3을 쓰기로 정했다면 답안이 실제로 만들어 내놓아야 하는 것은 무엇인가.
답
단사 \(f : (0,1) \to [0,1]\) 하나와 단사 \(g : [0,1] \to (0,1)\) 하나. 전단사를
만들 의무는 없다. C13주차 문제 19가 이 두 집합 사이의 전단사를 네 갈래
규칙으로 만들었는데, 이번 설계에는 그 규칙이 필요 없다.
출발점(두 무대의 포함 관계)과 도착점(제작할 함수 두 개)이 정해졌다.
1단계 — 쉬운 쪽 단사를 만든다. \((0,1)\)의 원소는 이미 \([0,1]\)의 원소다. 그러면 아무것도 옮기지 않는 대응이 곧 단사다.
확인 12. \(f : (0,1) \to [0,1]\)의 식을 적고, 값이 무대에 들어가는지와 겹침이 없는지를 각각 한 줄로 확인해 보자.
답
\(f(x) = x\) (포함사상). 무대 확인: \((0,1) \subseteq [0,1]\)이므로 \(x \in (0,1)\)이면
\(x \in [0,1]\)이다. 겹침 없음: \(f(x_1) = f(x_2)\)라 하면 곧 \(x_1 = x_2\)이다.
따라서 정의 1.1에 의해 \(|(0,1)| \le |[0,1]|\)이다.
포함사상이 단사라는 사실은 이번 주 내내 걸음 ①의 기본값이 된다.
2단계 — 어려운 쪽 단사를 만든다. 이번에는 끝점 \(0\)과 \(1\)을 포함한 \([0,1]\) 전체를 열린 구간 \((0,1)\) 안으로 밀어 넣어야 한다. 끝점을 다른 곳으로 옮기지 않으면 값이 무대 밖으로 나간다.
확인 13. \([0,1]\) 전체를 \((0,1)\) 안쪽으로 옮겨 놓으려면 어떤 종류의 조작이 필요한가. 일차함수 \(g(x) = ax + b\)로 하려면 \(a\)와 \(b\)에 어떤 조건이 붙는가.
답
축소한 뒤 안쪽으로 평행이동하는 조작이다. \(a > 0\)이면 상이 \([b, a+b]\)이므로,
이 구간이 \((0,1)\) 안에 들어가려면 \(b > 0\)이고 \(a + b < 1\)이면 된다.
이 조건을 만족하는 가장 간단한 선택 하나가 \(a = b = \frac13\), 곧
\(g(x) = \dfrac{x+1}{3}\)이다. 상은 \([\frac13, \frac23]\)이 된다.
확인 14. \(g(x) = \frac{x+1}{3}\)의 값이 실제로 \((0,1)\)에 들어감을 부등식으로 확인해 보자.
답
\(0 \le x \le 1\)의 각 변에 1을 더하면 \(1 \le x + 1 \le 2\)이고, 각 변을 3으로 나누면
이다(근거 ③). 그리고 \(0 < \frac13\)이고 \(\frac23 < 1\)이므로 \(0 < g(x) < 1\),
곧 \(g(x) \in (0,1)\)이다. 무대 확인은 이 두 줄로 끝난다.
확인 15. \(g\)의 단사 증명 두 문장을 완성해 보자.
“\(g(x_1) = g(x_2)\)라 하자. 곧 \(\underline{\qquad}\)이고, 양변에 \(\underline{\quad}\)을 곱한 뒤 \(\underline{\quad}\)을 빼면 \(x_1 = x_2\)이다.”
답
“\(g(x_1) = g(x_2)\)라 하자. 곧 \(\dfrac{x_1+1}{3} = \dfrac{x_2+1}{3}\)이고, 양변에
\(3\)을 곱한 뒤 \(1\)을 빼면 \(x_1 = x_2\)이다.” 근거 ③이다.
따라서 \(g\)는 단사이고 정의 1.1에 의해 \(|[0,1]| \le |(0,1)|\)이다.
3단계 — 정리를 인용해 마무리한다.
확인 16. 마지막 문장을 완성해 보자.
“\(|(0,1)| \le |[0,1]|\)이고 \(|[0,1]| \le |(0,1)|\)이므로 \(\underline{\qquad}\)에 의해 \(\underline{\qquad}\)이다. \(\blacksquare\)”
답
“\(|(0,1)| \le |[0,1]|\)이고 \(|[0,1]| \le |(0,1)|\)이므로 **정리 1.3(슈뢰더-번슈타인)**에
의해 \(|(0,1)| = |[0,1]|\)이다. \(\blacksquare\)”
인용하는 정리의 이름 또는 번호를 반드시 적는다. 두 부등식을 나란히 적어 놓고
곧바로 등호를 쓰면 근거가 빠진 답안이 된다.
완성본. 방금 만든 문장을 이어 붙이면 아래 왼쪽 열이 된다. 손으로 베껴 쓰면서 각 줄 옆의 “왜?”에 스스로 답해 본다.
증명의 한 줄 |
왜 이 줄을 쓰는가? |
|---|---|
\(f : (0,1) \to [0,1]\)을 \(f(x) = x\)로 정의한다. \((0,1) \subseteq [0,1]\)이므로 값이 무대에 들어간다. |
걸음 ① 전반부. 식과 무대 확인이 한 쌍이다 — 식만 적으면 함수가 정의되지 않는다. |
\(f(x_1) = f(x_2)\)라 하면 곧 \(x_1 = x_2\)이므로 \(f\)는 단사이고, 정의 1.1에 의해 \(\vert(0,1)\vert \le \vert[0,1]\vert\)이다. |
걸음 ① 후반부. 겹침 없음을 실제로 보인 뒤 부등식을 선언한다. |
\(g : [0,1] \to (0,1)\)을 \(g(x) = \frac{x+1}{3}\)로 정의한다. \(0 \le x \le 1\)이면 \(\frac13 \le g(x) \le \frac23\)이므로 값이 \((0,1)\)에 들어간다. |
걸음 ② 전반부. 끝점을 안쪽으로 옮기는 것이 이 함수의 목적이며, 부등식 두 줄이 그 목적의 달성을 확인한다(근거 ③). |
\(g(x_1) = g(x_2)\)라 하면 \(\frac{x_1+1}{3} = \frac{x_2+1}{3}\)이고, 양변에 3을 곱한 뒤 1을 빼면 \(x_1 = x_2\)이다. 따라서 \(\vert[0,1]\vert \le \vert(0,1)\vert\)이다. |
걸음 ② 후반부. 일차식의 소거가 단사 증명의 본체다. |
두 부등식에 정리 1.3을 적용하면 \(\vert(0,1)\vert = \vert[0,1]\vert\)이다. \(\blacksquare\) |
걸음 ③. 인용한 정리를 명시하며 상등을 선언한다. |
두 함수 모두 전사가 아니다. \(f\)의 상은 \((0,1)\)이므로 \(0\)과 \(1\)을 빠뜨리고, \(g\)의 상은 \([\frac13, \frac23]\)이므로 \((0,1)\)의 대부분을 빠뜨린다. 그럼에도 결론이 나온다는 것이 정리 1.3의 내용이다. C13주차 문제 19와 1권 49주차 문제 17은 같은 결론을 위해 규칙을 여러 갈래로 갈라 \(\frac1n \mapsto \frac1{n+2}\)처럼 가산 부분을 밀어내면서 빠짐 없음까지 확보해야 했는데, 이번 답안은 다섯 줄이다. 1권에서 요령으로 해내던 그 밀어내기가 여기서는 아예 필요하지 않다.
예제 2.2 — CSB로 \(|\mathbb{N}| = |\mathbb{N} \times \mathbb{N}|\)#
명제. \(|\mathbb{N}| = |\mathbb{N} \times \mathbb{N}|\).
이번에는 설계만 함께 하고, 본문은 완성본으로 본다.
확인 17. 번역표를 채워 보자.
만들 것 1: 단사 \(f : \mathbb{N} \to \mathbb{N} \times \mathbb{N}\) — 자연수 하나를 쌍으로 만들되 겹치지 않게 하려면 \(f(n) = \underline{\qquad}\).
만들 것 2: 단사 \(g : \mathbb{N} \times \mathbb{N} \to \mathbb{N}\) — 쌍 \((m,n)\)을 자연수 하나로 접되 되돌릴 수 있게 하려면 \(g(m,n) = \underline{\qquad}\).
답
\(f(n) = (n, 1)\). 둘째 좌표를 고정해 두면 첫째 좌표가 그대로 남으므로 겹침이 없다.
\(g(m, n) = 2^m 3^n\). 서로 다른 밑 두 개의 지수 자리에 \(m\)과 \(n\)을 각각 심는다.
되돌릴 수 있는 이유는 한 수를 2로 몇 번 나눌 수 있는지가 그 수만으로 정해지기
때문이며, 그 사실을 답안에서 실제로 논증하는 것이 아래 셋째 줄이다.
밑을 \(2\)와 \(4\)로 잡으면 실패한다 — \(4 = 2^2\)이라 \(2^m 4^n = 2^{m + 2n}\)이 되고,
\(m + 2n\)만 같으면 값이 같아지기 때문이다. 실제로 \(2^3 4^1 = 32 = 2^1 4^2\)이므로
\((m,n) = (3,1)\)과 \((1,2)\)가 같은 값을 준다. 서로 다른 소수를 밑으로 잡는 것이
이 수단의 핵심이다.
증명의 한 줄 |
왜 이 줄을 쓰는가? |
|---|---|
\(f : \mathbb{N} \to \mathbb{N} \times \mathbb{N}\)을 \(f(n) = (n, 1)\)로 정의한다. \(n \in \mathbb{N}\)이고 \(1 \in \mathbb{N}\)이므로 값이 무대에 들어간다. |
걸음 ① 전반부. 곱집합의 원소는 두 좌표가 모두 자격을 갖춰야 한다. |
\(f(n_1) = f(n_2)\)라 하면 \((n_1, 1) = (n_2, 1)\)이고, 순서쌍의 상등은 좌표별 상등이므로 \(n_1 = n_2\)이다. 따라서 \(\vert\mathbb{N}\vert \le \vert\mathbb{N} \times \mathbb{N}\vert\)이다. |
걸음 ① 후반부. 순서쌍의 상등 기준 — 첫 성분끼리 같고 둘째 성분끼리 같다 — 이 근거다. |
\(g : \mathbb{N} \times \mathbb{N} \to \mathbb{N}\)을 \(g(m, n) = 2^m 3^n\)으로 정의한다. \(m, n \in \mathbb{N}\)이면 \(2^m 3^n\)은 자연수이므로 값이 무대에 들어간다. |
걸음 ② 전반부. 두 자리를 서로 다른 소수의 지수에 심는다. |
\(g(m_1, n_1) = g(m_2, n_2)\)라 하자. 곧 \(2^{m_1} 3^{n_1} = 2^{m_2} 3^{n_2}\)이다. \(m_1 < m_2\)라 하면 양변을 \(2^{m_1}\)으로 나누어 \(3^{n_1} = 2^{m_2 - m_1} 3^{n_2}\)을 얻는데, 좌변은 홀수끼리의 곱이므로 홀수이고(1권 1주차 문제 8을 \(n_1\)에 대한 귀납으로 반복 적용한다) 우변은 짝수이므로 모순이다. \(m_2 < m_1\)도 같은 이유로 모순이므로 \(m_1 = m_2\)이다. |
걸음 ② 후반부의 앞쪽. 소인수분해의 유일성을 인용하면 한 줄로 끝나지만(C15주차), 이 경우는 홀짝만으로 자립적으로 처리된다. |
그러면 \(3^{n_1} = 3^{n_2}\)이고, \(n_1 < n_2\)라 하면 양변을 \(3^{n_1}\)으로 나누어 \(1 = 3^{n_2 - n_1} \ge 3\)이 되어 모순이므로 \(n_1 = n_2\)이다. 따라서 \(g\)는 단사이고 \(\vert\mathbb{N} \times \mathbb{N}\vert \le \vert\mathbb{N}\vert\)이다. |
걸음 ② 후반부의 뒤쪽. 지수가 커지면 값이 커진다는 사실만 쓴다. |
두 부등식에 정리 1.3을 적용하면 \(\vert\mathbb{N}\vert = \vert\mathbb{N} \times \mathbb{N}\vert\)이다. \(\blacksquare\) |
걸음 ③. |
C13주차 문제 9와 비교. 거기서는 대각선 나열의 순번을 식으로 적어 전사와 단사를 모두 검증했다. 이번 답안의 \(g\)는 전사가 아니다 — \(5\)나 \(7\)은 \(2^m 3^n\) 꼴이 아니므로 상에 없다. 그럼에도 결론이 같다는 것이 정리 1.3이 하는 일이다.
예제 2.3 — CSB로 \(|\mathbb{R}| = |\mathbb{R}^2|\)#
명제. \(|\mathbb{R}| = |\mathbb{R}^2|\).
이번에는 설계부터 스스로 해 보자.
확인 18. 만들어야 할 단사 두 개를 각각 한 줄로 설계해 보자. 어려운 쪽은 §1.1의 자리 엮기를 어디에 어떻게 끼워 넣으면 되는지까지 적어 보자.
답
쉬운 쪽: \(f : \mathbb{R} \to \mathbb{R}^2\), \(f(x) = (x, 0)\). 직선을 평면의 가로축에 얹는다.
어려운 쪽: 자리 엮기는 \((0,1)^2\)에서만 쓸 수 있으므로 무대를 먼저 옮긴다.
C13주차 문제 13이 전단사 \(\psi : (0,1) \to \mathbb{R}\)을 주므로 그 역함수
\(\varphi = \psi^{-1} : \mathbb{R} \to (0,1)\)이 전단사이고(C12주차 문제 12), 특히 단사다.
그러면 \(\mathbb{R}^2 \to (0,1)^2 \to (0,1) \to \mathbb{R}\)의 세 걸음을 이어 붙이면
되고, 합성의 단사 보존(C12주차 문제 8)이 이어 붙인 결과가 단사임을 보증한다.
§1.1이 실패한 이유는 자리 엮기가 전사가 아니라는 것뿐이었으므로, 전사를
요구하지 않는 이번 설계에서는 그 실패가 결함이 아니다.
증명. ① \(f : \mathbb{R} \to \mathbb{R}^2\)를 \(f(x) = (x, 0)\)으로 정의한다. \(f(x_1) = f(x_2)\)라 하면 \((x_1, 0) = (x_2, 0)\)이고 좌표별 상등에서 \(x_1 = x_2\)이다. 따라서 \(f\)는 단사이고 \(|\mathbb{R}| \le |\mathbb{R}^2|\)이다.
② 반대 방향을 세 걸음으로 만든다. C13주차 문제 13에 의해 전단사 \(\psi : (0,1) \to \mathbb{R}\)이 존재하므로, C12주차 문제 12에 의해 그 역함수 \(\varphi = \psi^{-1} : \mathbb{R} \to (0,1)\)도 전단사이고 특히 단사다. 이것으로
을 정의하면 \(\Phi\)는 단사다 — \(\Phi(x_1,y_1) = \Phi(x_2,y_2)\)이면 좌표별로 \(\varphi(x_1) = \varphi(x_2)\)이고 \(\varphi(y_1) = \varphi(y_2)\)이므로, \(\varphi\)가 단사라 \(x_1 = x_2\)이고 \(y_1 = y_2\)이다. 다음으로 \((0,1)\)의 각 원소의 십진 전개를 9의 꼬리가 없는 쪽으로 하나 고정하고(C13주차 §1.6),
으로 정의한다. 엮어 만든 자리열은 전부 0일 수 없고(두 전개가 모두 전부 0이어야 하는데 \((0,1)\)의 원소는 그런 전개를 갖지 않는다) 꼬리가 전부 9일 수도 없으므로 (그러려면 두 전개가 모두 9의 꼬리를 가져야 하는데 약속에 의해 그런 전개는 없다), \(\Lambda\)의 값은 실제로 \((0,1)\)에 있고 그 자리열이 곧 그 값의 유일한 전개다. \(\Lambda(x_1,y_1) = \Lambda(x_2,y_2)\)라 하면 두 값이 같고 전개가 유일하므로 자리열이 같고, 홀수 자리끼리 비교하면 \(x_1\)과 \(x_2\)의 전개가, 짝수 자리끼리 비교하면 \(y_1\)과 \(y_2\)의 전개가 각각 일치한다. 따라서 \(x_1 = x_2\), \(y_1 = y_2\)이고 \(\Lambda\)는 단사다. 끝으로 포함사상 \(\iota : (0,1) \to \mathbb{R}\)은 단사이므로, \(g = \iota \circ \Lambda \circ \Phi : \mathbb{R}^2 \to \mathbb{R}\)은 단사의 합성으로서 단사다(C12주차 문제 8). 그러므로 \(|\mathbb{R}^2| \le |\mathbb{R}|\)이다.
③ 두 부등식에 정리 1.3을 적용하면 \(|\mathbb{R}| = |\mathbb{R}^2|\)이다. \(\blacksquare\)
이번 증명은 표 없이 산문으로 적었다. 표는 연습 단계의 장치이고, 실전의 증명은 처음부터 끝까지 이런 산문이다. 결과 자체는 유한 직관과 크게 어긋난다 — 평면의 점의 개수가 직선의 점의 개수와 같다. 어긋나 보이는 이유는 “크기”와 “차원”이 서로 다른 개념인데 일상의 직관이 둘을 붙여 놓기 때문이다. 크기는 짝짓기가 정하고, 차원은 이 과정 밖의 다른 잣대가 정한다.
관찰 — 세 예제의 같은 뼈대#
세 예제는 무대가 전혀 다르지만 밟은 순서는 같다. 대응표의 빈칸을 채워 보자.
걸음 |
예제 2.1 |
예제 2.2 |
예제 2.3 |
|---|---|---|---|
무대 \(A\), \(B\) |
\((0,1)\), \([0,1]\) |
\(\mathbb{N}\), \(\mathbb{N} \times \mathbb{N}\) |
\(\mathbb{R}\), \(\mathbb{R}^2\) |
① 단사 \(A \to B\) |
포함사상 \(x \mapsto x\) |
\(n \mapsto (n, 1)\) |
\(\underline{\quad(1)\quad}\) |
② 단사 \(B \to A\) |
\(x \mapsto \frac{x+1}{3}\) |
\((m,n) \mapsto 2^m 3^n\) |
\(\underline{\quad(2)\quad}\) |
② 검증의 본체 |
일차식의 소거 |
\(\underline{\quad(3)\quad}\) |
십진 전개의 유일성 |
③ 마무리 |
정리 1.3 인용 |
정리 1.3 인용 |
\(\underline{\quad(4)\quad}\) |
확인 19. 표의 (1)~(4)를 채워 보자.
답
(1) \(x \mapsto (x, 0)\).
(2) \(\varphi\)로 무대를 \((0,1)^2\)로 옮긴 뒤 자리를 엮고 포함사상으로 되돌리는 합성.
(3) 홀짝 논증 — \(3^{n}\)이 홀수임을 써서 2의 지수를 먼저 맞춘다.
(4) 정리 1.3 인용.
확인 20. 세 예제가 공통으로 한 일을 한 문장으로 적어 보자. 그리고 어려운 쪽 단사를 만들 때 쓴 수단들을 모아 보자.
답
공통으로 한 일: **서로 반대 방향의 단사를 하나씩 제작하고, 각각에 무대 확인과
겹침 없음 검증을 붙인 뒤 정리 1.3을 인용했다.** 전사는 한 번도 검증하지 않았다.
어려운 쪽에서 쓴 수단은 셋이다 — 큰 집합을 축소해 안쪽으로 밀어 넣기(예제 2.1),
두 자리를 서로 다른 소수의 지수에 심기(예제 2.2), 두 전개의 **자리를 번갈아
엮기**(예제 2.3). 세 수단 모두 “정보를 잃지 않고 접는 방법”이라는 점이 같다.
방금 확인한 뼈대에 이름을 붙인다.
백지 암기 대상
큰 쪽을 작은 쪽 안에 심는 네 가지 수단
① 포함사상 — 부분집합 관계가 있으면 그대로 단사다.
② 축소와 평행이동 — 닫힌 구간을 열린 구간 안으로, 큰 구간을 작은 구간 안으로 옮긴다.
③ 부호나 갈래로 자리 나누기 — 정의역을 갈래로 나눠 상이 겹치지 않는 구역에 각각 심는다(문제 11).
④ 자리에 심기 — 서로 다른 소수의 지수(예제 2.2)나 십진 전개의 홀\(\cdot\)짝 자리(예제 2.3)에 정보를 나눠 넣는다.
어느 수단을 쓰든 답안에 붙는 검증은 둘뿐이다 — 값이 무대에 들어가는가, 겹치지 않는가.
빈칸 사다리 — 지지대를 하나씩 빼며#
예제의 필사에서 자립으로 넘어가는 다리다. 훈련이 진행될수록 빈칸이 커진다. 베끼지 말고 빈칸만 스스로 채운다. 답은 §6에 있다 — 다 채운 뒤에 대조한다.
훈련 1 ●○○ — 수식과 절차의 빈칸#
명제. \(M = \{2, 3, 4, \ldots\}\)라 할 때 \(|\mathbb{N}| = |M|\)이다.
증명. ① \(f : \mathbb{N} \to M\)을 \(f(n) = \underline{\quad(1)\quad}\)로 정의한다. \(n \in \mathbb{N}\)이면 \(n \ge 1\)이므로 이 값은 2 이상의 자연수이고 \(M\)에 들어간다. \(f(n_1) = f(n_2)\)라 하자. 곧 \(n_1 + 1 = n_2 + 1\)이고, 양변에서 1을 빼면 \(\underline{\quad(2)\quad}\)이다. 따라서 \(f\)는 단사이고 \(|\mathbb{N}| \le |M|\)이다.
② \(g : M \to \mathbb{N}\)을 \(g(m) = m\)(포함사상)으로 정의한다. \(M \subseteq \mathbb{N}\)이므로 값이 무대에 들어가고, \(g(m_1) = g(m_2)\)이면 곧 \(m_1 = m_2\)이므로 단사다. 따라서 \(|M| \underline{\quad(3)\quad} |\mathbb{N}|\)이다.
③ 두 부등식에 \(\underline{\quad(4)\quad}\) 정리를 적용하면 \(|\mathbb{N}| = |M|\)이다. \(\blacksquare\)
검산. \(f(1) = 2\), \(f(2) = \underline{\quad(5)\quad}\), \(f(3) = 4\).
훈련 2 ●●○ — 수식과 근거를 함께#
이번에는 구조 낱말과 근거 문장도 빈칸이다.
명제. \(|(0,1)| = |(0,1]|\).
증명. ① \(f : (0,1) \to (0,1]\)을 \(f(x) = x\)로 정의한다. \((0,1) \underline{\quad(1)\quad} (0,1]\)이므로 값이 무대에 들어간다. \(f(x_1) = f(x_2)\)이면 곧 \(x_1 = x_2\)이므로 \(f\)는 \(\underline{\quad(2)\quad}\)이고, 따라서 \(|(0,1)| \le |(0,1]|\)이다.
② \(g : (0,1] \to (0,1)\)을 \(g(x) = \underline{\quad(3)\quad}\)로 정의한다. \(0 < x \le 1\)이면 \(0 < g(x) \le \frac12 < 1\)이므로 값이 \((0,1)\)에 들어간다. \(g(x_1) = g(x_2)\)라 하자. 곧 \(\frac{x_1}{2} = \frac{x_2}{2}\)이고, \(\underline{\quad(4)\quad}\)이므로 \(x_1 = x_2\)이다. 따라서 \(|(0,1]| \le |(0,1)|\)이다.
③ 두 부등식에 \(\underline{\quad(5)\quad}\)을 적용하면 \(|(0,1)| = |(0,1]|\)이다. \(\blacksquare\)
복기. \(g\)가 전사가 아님을 확인해 두자 — \(g\)의 상은 \(\underline{\quad(6)\quad}\)이므로 \(0.9\)는 상에 없다. 그럼에도 결론이 나오는 이유는 정리 1.3이 요구하는 것이 \(\underline{\quad(7)\quad}\)뿐이기 때문이다.
훈련 3 ●●● — 뼈대만 남기고#
이번에는 §1.6의 3단 서식 세 칸을 통째로 채운다. 예제 2.2의 수단을 한 자리 늘리면 된다.
명제. \(|\mathbb{N} \times \mathbb{N} \times \mathbb{N}| = |\mathbb{N}|\).
답안의 뼈대.
① 단사 \(f : \mathbb{N} \to \mathbb{N} \times \mathbb{N} \times \mathbb{N}\)의 제작과 검증: \(\underline{\quad(1)\quad}\)
② 단사 \(g : \mathbb{N} \times \mathbb{N} \times \mathbb{N} \to \mathbb{N}\)의 제작과 검증: \(\underline{\quad(2)\quad}\)
③ 마무리: \(\underline{\quad(3)\quad}\)
(안내: 걸음 ②에서 밑을 \(2\), \(3\), \(4\)로 잡으면 실패한다. \(4\)가 \(2\)의 거듭제곱이라 두 지수가 하나로 섞이는 것 — 확인 17에서 본 이유 — 이 그대로 재연되기 때문이다. 그리고 이 결과를 (Q2)와 나란히 놓으면 \(\aleph_0 \cdot \aleph_0 \cdot \aleph_0 = \aleph_0\)이 된다.)
연습문제 (20문항)#
해설을 보기 전에 문제당 최소 10분 스스로 시도한다. 막히면 곧바로 풀이를 읽지 말고, 해설의 ‘접근’까지만 읽고 다시 시도한다 \(\to\) 그래도 안 되면 풀이를 읽는다.
CSB를 쓰는 문제는 두 단사를 각각 명시하고, 각각에 무대 확인과 겹침 없음 검증을 붙인 뒤 정리 1.3을 인용한다.
이번 주의 채점 기준
답이 아니라 근거가 점수다. CSB 답안에는 채점 항목이 넷이다.
① 두 단사가 서로 반대 방향으로 명시되어 있는가. 방향이 같은 두 함수는 정리 1.3의 가정이 아니다.
② 각 함수의 값이 무대에 들어감을 확인했는가. 식만 적으면 함수가 정의되지 않는다.
③ 각 함수의 겹침 없음을 증명했는가. “단사임은 자명하다”는 증명이 아니다.
④ 마지막 줄에서 정리 1.3을 인용했는가. 두 부등식 아래에 등호만 적으면 근거가 빠진다.
전사는 채점 항목이 아니다 — 검증할 필요도, 성립할 필요도 없다.
난이도와 무관하게, 힌트 상자는 5분 이상 막힌 뒤에만 연다.
기본 ●○○#
1. [백지] \(|A| \le |B|\)의 정의(단사), CSB 정리, CSB 활용 3단계를 쓰시오.
힌트
정의는 문장을 통째로 외우기보다 §1.3의 조각 표와 함께 외운다 — 조각을 지우면
무엇이 무너지는지 알아 두면 잊은 조각을 복구할 수 있다. 3단 서식은 §1.6이고,
걸음마다 “빼면 무엇이 무너지는가”가 한 쌍으로 붙어 있다.
2. 다음 기수 비교의 참\(\cdot\)거짓을 답하시오. (a) \(|\mathbb{N}| \le |\mathbb{Z}|\) (b) \(|\mathbb{N}| \le |\mathbb{R}|\) (c) \(|\mathbb{R}| \le |\mathbb{N}|\) (d) \(|\mathbb{Q}| \le |\mathbb{R}|\)
힌트
네 칸 중 셋은 포함사상 한 줄로 끝난다. 나머지 하나는 “단사가 존재하지 않는다”는
비존재 주장이므로 함수를 하나 못 만든 것으로는 끝나지 않는다 — §1.6 확인 8의
논증을 그대로 옮겨 쓴다.
3. 예제 2.1(\(|(0,1)| = |[0,1]|\))을 백지 재현하시오.
힌트
§1.6의 3단 서식 세 칸을 먼저 적고 각 칸에 예제 2.1의 문장을 채워 넣는다.
자주 빠지는 것은 걸음 ②의 무대 확인 — \(\frac{x+1}{3}\)이 실제로 \((0,1)\) 안에
있다는 부등식 두 줄이다.
4. 빈칸 훈련을 백지에서 완성하시오.
힌트
훈련 1은 \(M\)의 가장 작은 원소가 무엇인지 보면 \(f\)의 식이 나오고, 훈련 2는
어느 쪽 구간이 끝점을 갖는지 보면 어느 방향이 어려운 쪽인지 정해진다.
훈련 3은 예제 2.2의 밑 두 개를 세 개로 늘리는 것이 전부다.
5. 예제 2.2(\(|\mathbb{N}| = |\mathbb{N} \times \mathbb{N}|\))를 백지 재현하시오 — 소인수 단사.
힌트
관절은 \(2^{m_1}3^{n_1} = 2^{m_2}3^{n_2}\)에서 \(m_1 = m_2\)를 끌어내는 자리다.
소인수분해의 유일성을 인용하면 한 줄이고, 인용하지 않으려면 양변을 \(2^{m_1}\)로
나눈 뒤 홀짝을 보면 된다.
6. “\(|\mathbb{N}| \le |\mathbb{N} \times \mathbb{N}|\)”의 단사를 하나 만드시오 (\(f(n) = (n, 1)\)).
힌트
요구되는 것은 정의 1.1이 요구하는 것 하나 — 단사의 제시다. 값이 곱집합에
들어가려면 두 좌표가 모두 자연수여야 한다는 확인을 빠뜨리지 않는다.
표준 ●●○#
7. CSB로 \(|[0,1]| = |[0,2]|\)를 증명하시오 (두 단사 — 포함 + 축소, 또는 \(x \mapsto 2x\)가 이미 전단사이나 CSB 연습으로).
힌트
포함사상 쪽은 \([0,1] \subseteq [0,2]\)에서 곧바로 나온다. 반대 방향은 길이 2인
구간을 길이 1인 구간 안으로 넣어야 하므로 예제 2.1의 수단 ②(축소)를 쓴다.
8. CSB로 \(|(0,1)| = |(0,1) \cup \{2\}|\) (한 점 추가)를 증명하시오 (단사 \(f(x) = x\), \(g\)는 점 2를 구간 안으로).
힌트
\(g\)는 갈래가 둘로 갈린다 — 점 \(2\)에 값 하나를 주고, \((0,1)\)의 원소에는 다른 식을
준다. 갈래가 갈리면 검증도 갈린다: 각 갈래 안에서의 겹침과 갈래 사이의 겹침을
따로 확인해야 하고, 뒤쪽은 두 갈래의 상이 만나지 않음을 보이는 일이다.
9. \(|A| \le |B|\)의 추이성을 증명하시오 (단사 \(f: A \to B\), \(g: B \to C\)의 합성 \(g \circ f\)가 단사 — C12주차 문제 8).
10. 다음 제시된 증명을 평가하시오 (C5주차 §1.6의 증명 평가 다섯 걸음으로).
Result. \(|\mathbb{N}| = |\mathbb{R}|\).
제시된 증명. \(f: \mathbb{N} \to \mathbb{R}\), \(f(n) = n\)은 단사이고, \(g: \mathbb{R} \to \mathbb{N}\), \(g(x) = \lfloor x \rfloor\)도 단사이다. CSB에 의해 \(|\mathbb{N}| = |\mathbb{R}|\)이다.
힌트
걸음 ①에서 이미 결론이 나오지만, 그것만 적으면 이 답안이 어디서 무너졌는지는
밝히지 못한다. 두 함수를 각각 채점표 ②(무대)와 ③(겹침)에 걸어 보고,
반례가 되는 구체적인 두 수를 답안에 적는다.
11. CSB로 \(|\mathbb{Z}| = |\mathbb{N}|\)을 증명하시오 (C13주차 예제 2.2를 CSB로 — 두 단사: 포함 \(\mathbb{N} \hookrightarrow \mathbb{Z}\), 그리고 \(\mathbb{Z} \to \mathbb{N}\)은 부호를 나눠 심는 단사 — 예 \(n \mapsto 2n\) (\(n > 0\)), \(-2n + 1\) (\(n \le 0\))).
힌트
갈래가 둘인 함수의 단사 증명은 문제 8과 같은 구조다. 갈래 사이를 막아 주는 것을
찾는다 — 한쪽 갈래의 값은 전부 짝수이고 다른 쪽은 전부 홀수다.
12. 무한 부분집합: \(A\)가 가산무한이고 \(B \subseteq A\)가 무한이면 \(|B| = |A|\)임을 CSB로 설명하시오 (\(B \subseteq A\)라 \(|B| \le |A|\); \(A\) 가산이라 \(|A| = |\mathbb{N}| \le |B|\) — 무한 부분집합도 가산).
힌트
어려운 쪽은 \(\mathbb{N} \to B\) 단사다. \(A\)가 가산무한이므로 목록
\(a_1, a_2, a_3, \ldots\)이 있고, 그 목록에서 \(B\)에 속하는 항만 순서대로 남기면
무엇이 생기는가. \(B\)가 무한이라는 가정이 그 목록이 끝나지 않음을 보장한다.
13. CSB로 \(|(0,1)| = |\mathbb{R}|\)을 재증명하시오 (C13주차 문제 13은 tan 전단사; 이번엔 CSB — 단사 \((0,1) \hookrightarrow \mathbb{R}\) 포함, \(\mathbb{R} \to (0,1)\)은 \(\frac1\pi \arctan(x) + \frac12\)류).
힌트
반대 방향의 함수는 치역이 \((0,1)\) 안에 들어가는지부터 확인한다 — 아크탄젠트의
치역이 \((-\frac\pi2, \frac\pi2)\)라는 사실(§1.8에서 인정하고 쓴다)을 부등식으로
옮겨 적으면 된다. 단사임은 순증가에서 나온다.
14. 멱집합 비교: \(|\mathbb{N}| \le |\mathcal{P}(\mathbb{N})|\)의 단사를 만들고(\(n \mapsto \{n\}\)), \(|\mathbb{N}| \neq |\mathcal{P}(\mathbb{N})|\)(칸토어, C13주차 문제 14)과 합쳐 \(|\mathbb{N}| < |\mathcal{P}(\mathbb{N})|\)를 결론하시오.
힌트
정의 1.2를 그대로 따르면 할 일이 둘이다 — 단사 하나를 제시하고, 전단사가 없음을
인용한다. 앞쪽은 두 줄이고 뒤쪽은 출처를 대면 한 줄이다.
도전 ●●●#
이 문제들이 빌려 쓰는 도구 — 전단사를 멱집합으로 올리기
\(\varphi : X \to Y\)가 전단사이면, 각 부분집합 \(S \subseteq X\)를 그 상
\(\varphi[S] = \{\varphi(s) : s \in S\}\)로 보내는 대응 \(\Phi : \mathcal{P}(X) \to \mathcal{P}(Y)\)도
전단사다. 역대응이 \(T \mapsto \varphi^{-1}[T]\)이기 때문이다(C12주차 정의 12.5의
상과 원상). 따라서 \(|X| = |Y|\)이면 \(|\mathcal{P}(X)| = |\mathcal{P}(Y)|\)이다.
이 사실은 지금은 인정하고 쓴다 — 검증은 \(\varphi\)가 전단사일 때
\(\varphi^{-1}[\varphi[S]] = S\)와 \(\varphi[\varphi^{-1}[T]] = T\)를 각각 두 겹 포함으로
보이는 일이며(C12주차 정의 12.5와 문제 12), 문제 15에서
\(\mathcal{P}(\mathbb{Q})\)를 \(\mathcal{P}(\mathbb{N})\)으로 바꿔 놓는 데 쓰인다.
15. (CSB 대작) \(|\mathbb{R}| = |\mathcal{P}(\mathbb{N})|\)임을 CSB로 증명하시오 (두 단사: \(\mathbb{R} \to \mathcal{P}(\mathbb{Q})\)류 — 각 실수를 그보다 작은 유리수 집합(데데킨트 절단)으로; \(\mathcal{P}(\mathbb{N}) \to \mathbb{R}\)은 각 부분집합을 이진 소수로. 스케치 수준). “연속체 = \(2^{\aleph_0}\)”.
힌트
부분집합을 소수로 옮길 때 자릿수를 \(0\)과 \(1\)만 쓰면 9의 꼬리가 생기지 않으므로
이중 표기 문제가 아예 발생하지 않는다(C13주차 §1.6). 절단 쪽의 단사성은
“서로 다른 두 실수 사이에 유리수가 있다”는 사실 하나로 끝난다.
16. (\(\mathbb{R}^2\) 종합) 예제 2.3의 교대 엮기 단사 \(g: \mathbb{R}^2 \to \mathbb{R}\)가 왜 단사인지 상세히 설명하고, 왜 전사가 아닌지(엮음으로 안 나오는 실수 존재) 예를 드시오. “CSB가 전사 부족을 흡수한다”.
힌트
전사가 아님을 보이려면 상에 없는 실수를 하나 제시하고 그것이 상에 없음을
논증하면 된다. §1.1 확인 1이 그 실수 하나를 이미 만들어 두었다.
이 문제가 빌려 쓰는 약속 — 기수의 덧셈과 서로소 사본
\(\kappa + \lambda\)는 \(|X| = \kappa\), \(|Y| = \lambda\)이고 \(X \cap Y = \varnothing\)인
두 집합을 골라 \(|X \cup Y|\)로 정한다. 서로소 조건이 붙는 이유는 겹치는 원소를
두 번 세지 않기 위해서다. \(\mathbb{N} \subseteq \mathbb{R}\)이므로
\(\mathbb{N} \cup \mathbb{R} = \mathbb{R}\)이 되어 그대로는 덧셈이 되지 않으며,
\(\mathbb{R}\)과 서로소인 사본을 하나 잡아야 한다. 이 약속은 지금은 인정하고 쓴다.
17. (기수 산술) \(\aleph_0 + \mathfrak{c} = \mathfrak{c}\)임을 CSB로 논하시오 (\(|\mathbb{N} \cup \mathbb{R}| = |\mathbb{R}|\) — 단사 \(\mathbb{R} \hookrightarrow \mathbb{N} \cup \mathbb{R}\), 그리고 \(\mathbb{N} \cup \mathbb{R} \to \mathbb{R}\)은 \(\mathbb{N}\)을 \(\mathbb{R}\)의 빈 곳에 심기).
힌트
어려운 쪽 단사의 설계는 “겹치지 않는 두 구역에 각각 심기”다(§2 관찰의 수단 ③).
\(\mathbb{R}\) 쪽 전체를 \((0,1)\) 안으로 밀어 넣으면(문제 13) \((0,1)\) 바깥이 통째로
비므로, 사본의 자연수들은 그 빈 곳에 심으면 된다.
18. (진단 종합) 다음 제시된 증명을 평가하시오.
Result. \(|A| = |B|\)이면 \(|A| \le |B|\)이다.
제시된 증명. \(|A| = |B|\)이면 전단사 \(f: A \to B\)가 있고, 전단사는 단사이므로 \(|A| \le |B|\)이다.
힌트
평가의 결과가 언제나 “틀림”인 것은 아니다. 다섯 걸음을 순서대로 돌려 보고,
각 걸음에서 결함이 없음을 확인한 뒤 판정을 적는다. 특히 걸음 ②에서 “전단사는
단사이다”가 어느 정의에서 나오는지 출처를 댈 수 있는지 확인한다.
19. (설계) CSB의 위력 체감: \(|[0,1] \times [0,1]| = |[0,1]|\) (정사각형과 변이 같은 크기)를 CSB로 증명하시오 (단사 \([0,1] \to [0,1]^2\): \(x \mapsto (x, 0)\); \([0,1]^2 \to [0,1]\): 교대 엮기). 예제 2.3의 유계판.
힌트
교대 엮기는 \((0,1)\)에서만 쓸 수 있다 — 끝점 \(0\)과 \(1\)의 십진 전개가 말썽이기
때문이다. 예제 2.1의 \(g\)를 앞에 한 번 끼워 넣으면 무대가 \((0,1)^2\)으로 옮겨진다.
20. (서술) (a) CSB가 왜 “증명의 우회로”인지 예제 2.1\(\cdot\)2.3으로 뒷받침하고, 전단사 구성보다 양방향 단사가 쉬운 이유를 세 문장 이내로. (b) CSB가 기수의 “반대칭성”(\(\le\)\(\cdot\)\(\ge\) \(\Rightarrow\) \(=\))을 무한으로 확장함을, 순서의 반대칭(C11주차 문제 18 \(\cdot\) S7주차 문제 16)과 비교해 두 문장 이내 설명하시오.
힌트
(a)는 “CSB가 쉽다”는 인상이 아니라 사라진 검증을 지목하는 문항이다. §1.1에서
전단사 시도가 어디서 멈췄는지, 그리고 예제 2.1과 2.3의 답안에 무엇이 한 번도
등장하지 않는지를 각각 한 줄로 적어 보면 지목할 대상이 드러난다.
(b)는 S7주차 문제 16과 C11주차 문제 18의 반대칭성을 정리 1.3과 나란히 놓는다.
문장은 같고 근거가 다르다는 대비를 세우면 두 문장으로 끝난다 — 실수 쪽의 근거는
§1.4가, 기수 쪽의 근거는 §1.5의 확인 7이 각각 적어 두었다.
백지 재현 — 복습 프로토콜#
이 과정의 한 주는 다섯 날로 나뉜다. 교안만 보는 주가 아니라 원서와 교안을 번갈아 읽는 주이므로, 백지 재현은 마지막 날에 놓인다.
요일 |
할 일 |
|---|---|
1일차 |
원서 Chartrand 11.4~11.5 통독 — 모르는 문장은 표시만 하고 통과한다 |
2일차 |
교안 §0~§2 — 개념과 예제. 확인 상자를 연필로 먼저 채운다 |
3일차 |
원서 11.4~11.5 재독 — 1일차에 표시한 문장을 해결하고, 원서 연습문제 몇 개를 직접 시도한다 |
4일차 |
교안 §3 빈칸 사다리와 §4 연습문제 20문항 |
5일차 |
백지 재현 1차(틀 카드)\(\cdot\)2차(완전 백지) + 체크리스트 |
1차 시도 — 틀 카드 허용. CSB 활용의 3단 서식(§1.6)과 “큰 쪽을 작은 쪽 안에 심는 네 가지 수단”(§2 관찰)만 한 장에 적어 펴 놓고, 예제 2.1을 처음부터 끝까지 적는다. 정의와 본문은 보지 않는다.
2차 시도 — 완전 백지. 아무것도 보지 않고 수행한다.
정의 1.1과 1.2를 조각 그대로 썼다 (“단사가 존재하면”, “전단사가 존재하지 않는다”까지).
정리 1.3을 진술했고, 유한에서 자명하고 무한에서 자명하지 않은 이유를 각각 한 줄로 적었다.
CSB 활용의 3단 서식을 쓰고, 걸음마다 그것을 빼면 무엇이 무너지는지 한 줄씩 적었다.
예제 2.1을 재현했고, 두 함수가 모두 전사가 아님을 확인하고도 결론이 나오는 이유를 말했다.
예제 2.2를 재현했고, \(2^m3^n\)의 단사성 논증을 인용 없이 홀짝으로 적었다.
예제 2.3을 재현했고, 자리 엮기를 쓰기 전에 무대를 \((0,1)^2\)으로 옮기는 이유를 짚었다.
§1.4의 반사\(\cdot\)추이를 각각 한 줄로 증명하고, 남은 성질이 왜 정리가 되는지 말했다.
§1.7의 (Q1)~(Q6)을 진술하고 각각의 출처를 댔다.
원서 11.4~11.5를 두 번 읽었고, 1일차에 표시한 문장이 모두 해결되었다.
막힌 지점별 처방. 막힌 지점이 무엇을 다시 볼지 알려 준다.
막힌 지점 |
처방 |
|---|---|
무엇을 만들어야 할지 몰라 첫 줄이 나오지 않는다 |
§1.6의 3단 서식 — 목표가 상등이면 만들 것은 언제나 반대 방향의 단사 두 개다 |
부등호의 방향이 헷갈린다 |
§1.3 확인 3 — 부등호에서 왼쪽에 적힌 집합이 정의역이다 |
어려운 쪽 단사가 떠오르지 않는다 |
§2 관찰의 네 가지 수단 — 포함\(\cdot\)축소\(\cdot\)갈래 나누기\(\cdot\)자리에 심기를 차례로 시도한다 |
갈래로 나눈 함수의 단사 증명이 반쪽이 된다 |
문제 8과 문제 11의 힌트 — 갈래 안의 겹침과 갈래 사이의 겹침은 별개의 검증이다 |
단사를 만들고도 결론을 못 낸다 |
§1.6 걸음 ③ — 두 부등식 아래에 등호만 적으면 근거가 빠진다. 정리 1.3을 이름으로 인용한다 |
전사를 자꾸 검증하려 한다 |
§2 예제 2.1의 마지막 문단 — 두 함수 모두 전사가 아닌데도 결론이 나온다 |
크기가 다름을 보이려는데 방법이 없다 |
정의 1.2 — 다름은 비존재 주장이므로 대각선 논법(C13주차 §1.6)이나 (Q6)을 인용한다 |
하나라도 실패하면 그 항목만 다시 필사하고 다음날 재시도한다.
해설#
각 해설은 접근(문제 앞에서 무엇을 생각하는가)과 풀이로 나뉜다. 막혔을 때는 접근까지만 읽고 연필을 다시 잡는다.
빈칸 사다리 — 훈련 1#
(1) \(n + 1\) (2) \(n_1 = n_2\) (3) \(\le\) (4) 슈뢰더-번슈타인(정리 1.3, CSB) (5) \(3\)
※ 이 훈련의 관절은 (3)이다. 부등호의 방향은 함수의 방향이 정한다 — 걸음 ②의 함수는 \(M \to \mathbb{N}\)이므로 정의역인 \(M\)이 왼쪽에 오고 \(|M| \le |\mathbb{N}|\)이 된다. 1권 48주차 문제 12는 같은 명제를 전단사 \(n \mapsto n+1\)로 직접 증명했고 전사까지 검증했다. 이번 훈련은 그 전사 검증을 걸음 ②의 포함사상 세 줄로 바꾼 것이며, 답안 길이는 오히려 늘었지만 각 줄이 하는 일은 훨씬 단순하다. CSB의 이득은 짧은 답안이 아니라 어려운 검증이 사라진 답안이다.
빈칸 사다리 — 훈련 2#
(1) \(\subseteq\) (2) 단사 (3) \(\frac x2\) (4) 양변에 2를 곱하면 (근거 ③) (5) 정리 1.3 (슈뢰더-번슈타인) (6) \((0, \frac12]\) (7) 서로 반대 방향의 단사 두 개
※ (6)에서 상을 실제로 계산해 두는 것이 이 훈련의 목적이다. \(0 < x \le 1\)이면 \(0 < \frac x2 \le \frac12\)이므로 상은 \((0,\frac12]\)이고, \(0.9\)는 그 안에 없다. 곧 걸음 ②의 함수는 전사가 아니다. 그럼에도 결론이 나오는 이유가 (7)이며, 채점 기준에 전사가 없는 이유도 같다. 참고로 이 명제의 전단사를 직접 만들려면 C13주차 문제 19처럼 \(1 \mapsto \frac12\), \(\frac1n \mapsto \frac1{n+1}\), 나머지 고정과 같은 갈래 규칙이 필요하다 — 두 답안을 나란히 적어 두면 차이가 분명해진다.
빈칸 사다리 — 훈련 3#
(1) \(f(n) = (n, 1, 1)\)로 정의한다. \(n \in \mathbb{N}\)이고 \(1 \in \mathbb{N}\)이므로 값이 무대에 들어간다. \(f(n_1) = f(n_2)\)이면 \((n_1,1,1) = (n_2,1,1)\)이고 좌표별 상등에서 \(n_1 = n_2\)이므로 \(f\)는 단사이고 \(|\mathbb{N}| \le |\mathbb{N} \times \mathbb{N} \times \mathbb{N}|\)이다.
(2) \(g(a, b, c) = 2^a 3^b 5^c\)로 정의한다. \(a, b, c \in \mathbb{N}\)이면 값은 자연수이므로 무대에 들어간다. \(2^{a_1}3^{b_1}5^{c_1} = 2^{a_2}3^{b_2}5^{c_2}\)라 하자. \(a_1 < a_2\)이면 양변을 \(2^{a_1}\)으로 나누어 \(3^{b_1}5^{c_1} = 2^{a_2-a_1}3^{b_2}5^{c_2}\)을 얻는데 좌변은 홀수끼리의 곱이므로 홀수이고(1권 1주차 문제 8을 인수의 개수에 대한 귀납으로 반복 적용한다) 우변은 짝수이므로 모순이다. \(a_2 < a_1\)도 같으므로 \(a_1 = a_2\)이고, 양변에서 \(2^{a_1}\)을 지우면 \(3^{b_1}5^{c_1} = 3^{b_2}5^{c_2}\)이다. 같은 방식으로 3을 다룬다 — \(b_1 < b_2\)이면 양변을 \(3^{b_1}\)으로 나누어 \(5^{c_1} = 3^{b_2-b_1}5^{c_2}\)이 되는데, \(b_2 - b_1 \ge 1\)이므로 우변은 3의 배수다. 좌변은 3의 배수가 아니다 — \(5 \equiv -1 \pmod 3\)이므로 합동의 곱 보존(C6주차 예제 2.2)을 \(c_1\)에 대한 귀납으로 되풀이하면 \(5^{c_1} \equiv (-1)^{c_1} \pmod 3\)이고, \((-1)^{c_1}\)은 \(1\) 또는 \(-1\)이라 \(5^{c_1}\)을 3으로 나눈 나머지가 \(1\) 또는 \(2\)이기 때문이다(C6주차 정의 6.2). 따라서 모순이고 \(b_1 = b_2\)이며, 남은 \(5^{c_1} = 5^{c_2}\)에서 \(c_1 < c_2\)라 하면 \(1 = 5^{c_2-c_1} \ge 5\)가 되어 모순이므로 \(c_1 = c_2\)이다. 곧 \(g\)는 단사이고 \(|\mathbb{N} \times \mathbb{N} \times \mathbb{N}| \le |\mathbb{N}|\)이다.
(3) 두 부등식에 정리 1.3을 적용하면 \(|\mathbb{N} \times \mathbb{N} \times \mathbb{N}| = |\mathbb{N}|\)이다. \(\blacksquare\)
※ 밑을 \(2, 3, 4\)로 잡으면 실패한다 — \(4 = 2^2\)이라 \(2^a 3^b 4^c = 2^{a + 2c} 3^b\)이 되고, \(a + 2c\)와 \(b\)만 같으면 값이 같아지기 때문이다. 실제로 \(2^3 3^1 4^1 = 96 = 2^1 3^1 4^2\)이므로 \((a,b,c) = (3,1,1)\)과 \((1,1,2)\)가 같은 값을 준다. 서로 다른 소수를 밑으로 잡아야 지수를 바깥에서부터 하나씩 벗겨 낼 수 있다 — 밑 하나를 지울 때마다 “남은 곱은 그 밑의 배수가 아니다”를 대야 하고, 위 풀이의 홀짝 논증과 합동 논증이 각각 그 자리다. 이 결과를 (Q2)와 나란히 놓으면 \(\aleph_0 \cdot \aleph_0 \cdot \aleph_0 = \aleph_0\)이고, 같은 방식으로 자리를 몇 개로 늘려도 결과는 \(\aleph_0\)이다.
문제 1#
접근. 암기 항목을 문장으로만 외우면 일부를 잊었을 때 복구할 길이 없다. 정의는 §1.3의 조각 표와 함께 외우고, 서식은 §1.6의 걸음마다 붙은 “빼면 무엇이 무너지는가”와 함께 외운다. 그러면 남은 조각에서 잊은 조각을 재구성할 수 있다.
풀이. 기수 비교의 정의. 집합 \(A\), \(B\)에 대해 단사 \(f : A \to B\)가 존재하면 \(|A| \le |B|\)로 쓴다. 조각은 셋이다 — “단사”(겹침 없음만 요구하고 전사 의무를 지운다), “\(f : A \to B\)”(방향 고정. 왼쪽에 적힌 집합이 정의역이다), “존재하면”(하나를 제시하면 판정이 끝나고, 실패한 함수 하나는 반증이 되지 않는다). 여기에 \(|A| \le |B|\)이고 \(|A| \ne |B|\)일 때 \(|A| < |B|\)로 쓴다는 진부등호의 정의가 붙는다.
슈뢰더-번슈타인 정리. 단사 \(f : A \to B\)와 단사 \(g : B \to A\)가 모두 존재하면 전단사 \(h : A \to B\)가 존재한다. 곧 \(|A| \le |B|\)이고 \(|B| \le |A|\)이면 \(|A| = |B|\)이다.
CSB 활용의 3단계. ① 단사 \(f : A \to B\)를 제작한다 — 식을 명시하고 값이 \(B\)에 들어감을 확인한 뒤 단사임을 증명한다. 이로써 \(|A| \le |B|\). ② 같은 요령으로 단사 \(g : B \to A\)를 제작한다. 이로써 \(|B| \le |A|\). ③ 두 부등식에 정리 1.3을 인용해 \(|A| = |B|\)를 선언한다.
복기. 세 항목이 서로를 떠받친다. 정의가 “단사”만 요구하기 때문에 걸음 ①②가 쉬워지고, 그렇게 얻은 반쪽짜리 정보 두 개를 상등으로 바꿔 주는 것이 정리이며, 그 정리 없이는 3단 서식의 걸음 ③이 성립하지 않는다. 셋 중 하나만 외우면 나머지 둘의 필요성이 보이지 않는다.
문제 2#
접근. 네 칸 중 셋은 “포함사상이 단사”라는 한 줄로 끝난다. 나머지 하나 (c)는 비존재 주장이므로 함수를 하나 만들어 실패한 것으로는 답이 되지 않는다. §1.3의 셋째 조각이 말한 대로, 실패한 함수 하나는 \(\le\)의 반증이 아니다. 그러므로 \(\le\)가 성립한다고 가정하고 모순을 이끄는 길을 택한다.
풀이. (a) 참. \(f : \mathbb{N} \to \mathbb{Z}\), \(f(n) = n\)으로 두면 \(\mathbb{N} \subseteq \mathbb{Z}\)이므로 값이 무대에 들어가고, \(f(n_1) = f(n_2)\)이면 곧 \(n_1 = n_2\)이므로 단사다. 정의 1.1에 의해 \(|\mathbb{N}| \le |\mathbb{Z}|\)이다.
(b) 참. 같은 포함사상 \(f(n) = n\)을 \(\mathbb{N} \to \mathbb{R}\)로 두면 된다. \(\mathbb{N} \subseteq \mathbb{R}\)이고 단사이므로 \(|\mathbb{N}| \le |\mathbb{R}|\)이다.
(c) 거짓. 단사 \(g : \mathbb{R} \to \mathbb{N}\)이 존재한다고 가정하자. 그러면 \(|\mathbb{R}| \le |\mathbb{N}|\)이다. 한편 (b)에서 \(|\mathbb{N}| \le |\mathbb{R}|\)이므로, 두 부등식에 정리 1.3을 적용하면 \(|\mathbb{N}| = |\mathbb{R}|\)이 되어 \(\mathbb{R}\)가 가산무한이 된다. 이것은 C13주차 예제 2.3(대각선 논법으로 \((0,1)\)이 비가산이고 따라서 \(\mathbb{R}\)도 비가산)과 모순이다. 따라서 그러한 \(g\)는 존재하지 않고 \(|\mathbb{R}| \le |\mathbb{N}|\)은 거짓이다.
(d) 참. 포함사상 \(f : \mathbb{Q} \to \mathbb{R}\), \(f(q) = q\)가 단사이므로 \(|\mathbb{Q}| \le |\mathbb{R}|\)이다.
복기. (c)의 논증이 이번 주의 새 쓰임이다. 정리 1.3은 상등을 세울 때만 쓰는 것이 아니라, 단사가 존재하지 않음을 보이는 데도 쓰인다 — 존재한다고 가정하면 이미 알고 있는 상등 부정과 충돌하기 때문이다. 이 방향의 사용이 문제 10의 답안이 왜 틀렸는지도 설명해 준다.
문제 3#
접근. 재현의 뼈대는 §1.6의 3단 서식이다. 서식 세 칸을 먼저 적고 각 칸을 채운다. 자주 빠지는 것은 걸음 ②의 무대 확인이며, 그 확인은 부등식 계산 두 줄이다.
풀이. \(f : (0,1) \to [0,1]\)을 \(f(x) = x\)로 정의한다. \((0,1) \subseteq [0,1]\)이므로 값이 무대에 들어가고, \(f(x_1) = f(x_2)\)라 하면 곧 \(x_1 = x_2\)이므로 \(f\)는 단사다. 정의 1.1에 의해 \(|(0,1)| \le |[0,1]|\)이다.
\(g : [0,1] \to (0,1)\)을 \(g(x) = \dfrac{x+1}{3}\)로 정의한다. \(0 \le x \le 1\)의 각 변에 1을 더하면 \(1 \le x+1 \le 2\)이고, 각 변을 3으로 나누면
이므로 \(0 < g(x) < 1\), 곧 값이 \((0,1)\)에 들어간다. \(g(x_1) = g(x_2)\)라 하면 \(\frac{x_1+1}{3} = \frac{x_2+1}{3}\)이고, 양변에 3을 곱한 뒤 1을 빼면 \(x_1 = x_2\)이다. 따라서 \(g\)는 단사이고 \(|[0,1]| \le |(0,1)|\)이다.
두 부등식에 정리 1.3을 적용하면 \(|(0,1)| = |[0,1]|\)이다. \(\blacksquare\)
검산. \(g(0) = \frac13\), \(g(1) = \frac23\), \(g(\frac12) = \frac12\) — 세 값이 모두 \((0,1)\) 안에 있고 서로 다르다. 검산은 증명이 아니지만 무대 확인의 오류 탐지기로는 훌륭하다.
문제 4#
접근. 사다리의 답을 외워 적는 것이 아니라 빈칸이 있던 자리를 스스로 만들어 내는 것이 이 문항의 목적이다. 훈련 1은 목록의 첫 항이 \(f\)의 식을 정하고, 훈련 2는 어느 쪽 구간이 끝점을 갖는지가 어려운 방향을 정하며, 훈련 3은 예제 2.2의 밑을 하나 더 늘리면 된다.
풀이 (훈련 1을 산문으로). \(M = \{2,3,4,\ldots\}\)라 하자. \(f : \mathbb{N} \to M\)을 \(f(n) = n+1\)로 정의한다. \(n \ge 1\)이므로 \(n+1 \ge 2\)이고 값이 \(M\)에 들어간다. \(f(n_1) = f(n_2)\)이면 \(n_1 + 1 = n_2 + 1\)이고 양변에서 1을 빼면 \(n_1 = n_2\)이므로 \(f\)는 단사이고 \(|\mathbb{N}| \le |M|\)이다. 다음으로 \(g : M \to \mathbb{N}\)을 \(g(m) = m\)으로 정의한다. \(M \subseteq \mathbb{N}\)이므로 값이 무대에 들어가고, \(g(m_1) = g(m_2)\)이면 곧 \(m_1 = m_2\)이므로 단사이며 \(|M| \le |\mathbb{N}|\)이다. 두 부등식에 정리 1.3을 적용하면 \(|\mathbb{N}| = |M|\)이다. \(\blacksquare\)
자가 채점. 훈련 2와 훈련 3의 답은 §6 앞부분의 사다리 해설과 대조한다. 세 훈련 모두에서 확인할 것은 같다 — 두 함수의 방향이 서로 반대인가, 각 함수에 무대 확인과 겹침 없음 검증이 붙어 있는가, 마지막 줄에 정리 1.3의 이름이 있는가.
문제 5#
접근. 두 단사 중 하나는 좌표를 고정하는 한 줄이고, 다른 하나가 이 문제의 본체다. \(2^m3^n\)이 단사인 이유를 “소인수분해가 유일하니까”로 한 줄에 끝낼 수도 있지만, 그 정리는 C15주차에서 증명하므로 이번 주에는 홀짝만으로 자립적으로 적어 두는 편이 낫다.
풀이. \(f : \mathbb{N} \to \mathbb{N} \times \mathbb{N}\)을 \(f(n) = (n, 1)\)로 정의한다. \(n \in \mathbb{N}\)이고 \(1 \in \mathbb{N}\)이므로 값이 무대에 들어간다. \(f(n_1) = f(n_2)\)이면 \((n_1, 1) = (n_2, 1)\)이고 순서쌍의 상등은 좌표별 상등이므로 \(n_1 = n_2\)이다. 따라서 \(|\mathbb{N}| \le |\mathbb{N} \times \mathbb{N}|\)이다.
\(g : \mathbb{N} \times \mathbb{N} \to \mathbb{N}\)을 \(g(m, n) = 2^m 3^n\)으로 정의한다. \(m, n \in \mathbb{N}\)이면 \(2^m3^n\)은 자연수이므로 값이 무대에 들어간다. \(g(m_1, n_1) = g(m_2, n_2)\), 곧 \(2^{m_1}3^{n_1} = 2^{m_2}3^{n_2}\)이라 하자. \(m_1 < m_2\)라 하면 양변을 \(2^{m_1}\)으로 나누어
를 얻는데, 좌변은 홀수끼리의 곱이므로 홀수이고(1권 1주차 문제 8을 \(n_1\)에 대한 귀납으로 반복 적용한다) 우변은 \(m_2 - m_1 \ge 1\)이라 짝수이므로 모순이다. \(m_2 < m_1\)도 좌우를 바꾸면 같은 모순이므로 \(m_1 = m_2\)이다. 그러면 양변에서 \(2^{m_1}\)을 지워 \(3^{n_1} = 3^{n_2}\)을 얻고, \(n_1 < n_2\)라 하면 양변을 \(3^{n_1}\)으로 나누어 \(1 = 3^{n_2 - n_1} \ge 3\)이 되어 모순이므로 \(n_1 = n_2\)이다. 따라서 \(g\)는 단사이고 \(|\mathbb{N} \times \mathbb{N}| \le |\mathbb{N}|\)이다.
두 부등식에 정리 1.3을 적용하면 \(|\mathbb{N}| = |\mathbb{N} \times \mathbb{N}|\)이다. \(\blacksquare\)
복기. “지수 자리에 정보를 심고 밑의 소수로 되찾는다”는 수단은 자리 수를 늘려도 그대로 작동한다 — 훈련 3이 그 확장이다. 되찾기가 가능한 이유는 밑들이 서로 다른 소수여서 한 밑의 지수를 다른 밑이 흉내 낼 수 없기 때문이다.
문제 6#
접근. 요구되는 것은 정의 1.1이 요구하는 것 하나 — 단사의 제시다. 곱집합이 무대이므로 값의 자격 확인이 좌표마다 필요하고, 겹침 없음은 순서쌍의 상등 기준을 쓰면 두 줄이다.
풀이. \(f : \mathbb{N} \to \mathbb{N} \times \mathbb{N}\)을 \(f(n) = (n, 1)\)로 정의한다. \(n \in \mathbb{N}\)이고 \(1 \in \mathbb{N}\)이므로 \((n,1) \in \mathbb{N} \times \mathbb{N}\)이다. \(f(n_1) = f(n_2)\)라 하자. 곧 \((n_1, 1) = (n_2, 1)\)이고, 순서쌍이 같다는 것은 첫째 좌표끼리 같고 둘째 좌표끼리 같다는 뜻이므로 \(n_1 = n_2\)이다. 따라서 \(f\)는 단사이고, 정의 1.1에 의해 \(|\mathbb{N}| \le |\mathbb{N} \times \mathbb{N}|\)이다. \(\blacksquare\)
복기. 둘째 좌표에 넣은 값은 1일 필요가 없다 — \(f(n) = (n, 7)\)도 단사다. 중요한 것은 첫째 좌표가 그대로 남는다는 것뿐이고, 이것이 “한 좌표 고정”이라는 수단의 원리다. 거꾸로 \(f(n) = (1, 1)\)처럼 두 좌표를 모두 고정하면 상수함수가 되어 겹침이 생긴다.
문제 7#
접근. \([0,1] \subseteq [0,2]\)이므로 한쪽은 포함사상으로 끝난다. 반대쪽은 길이 2인 구간을 길이 1인 구간 안에 넣어야 하므로 §2 관찰의 수단 ②(축소)를 쓴다. 축소 비율은 상이 무대 안에 들어가도록 정한다.
풀이. \(f : [0,1] \to [0,2]\)를 \(f(x) = x\)로 정의한다. \(0 \le x \le 1 \le 2\)이므로 값이 무대에 들어가고, \(f(x_1) = f(x_2)\)이면 곧 \(x_1 = x_2\)이므로 단사다. 따라서 \(|[0,1]| \le |[0,2]|\)이다.
\(g : [0,2] \to [0,1]\)을 \(g(x) = \dfrac x2\)로 정의한다. \(0 \le x \le 2\)의 각 변을 2로 나누면 \(0 \le \frac x2 \le 1\)이므로 값이 \([0,1]\)에 들어간다. \(g(x_1) = g(x_2)\)이면 \(\frac{x_1}2 = \frac{x_2}2\)이고 양변에 2를 곱하면 \(x_1 = x_2\)이므로 단사다. 따라서 \(|[0,2]| \le |[0,1]|\)이다. 두 부등식에 정리 1.3을 적용하면 \(|[0,1]| = |[0,2]|\)이다. \(\blacksquare\)
복기. 이 문제에서는 \(g\)가 사실 전단사이므로 C13주차 정의 1.1로 곧바로 끝낼 수도 있다 — \(g\)가 전사임까지 보이려면 임의의 \(y \in [0,1]\)에 대해 \(x = 2y \in [0,2]\)가 원상임을 확인하는 한 줄이 더 필요하다. 두 답안을 모두 적어 보면 CSB가 절약해 주는 것이 정확히 그 전사 검증임이 보인다. 이 문제에서는 한 줄이지만, 예제 2.1과 2.3에서는 그 한 줄이 만들어지지 않는다.
문제 8#
접근. 한쪽은 포함사상이다. 반대쪽에서는 \((0,1)\) 밖에 있는 점 \(2\)를 구간 안으로 들여와야 하는데, 그 점이 원래 구간의 원소들과 부딪히면 안 된다. 그래서 함수를 두 갈래로 갈라 상이 겹치지 않는 두 구역에 각각 심는다.
풀이. \(f : (0,1) \to (0,1) \cup \{2\}\)를 \(f(x) = x\)로 정의한다. \((0,1) \subseteq (0,1) \cup \{2\}\)이므로 값이 무대에 들어가고, \(f(x_1) = f(x_2)\)이면 곧 \(x_1 = x_2\)이므로 단사다. 따라서 \(|(0,1)| \le |(0,1) \cup \{2\}|\)이다.
\(g : (0,1) \cup \{2\} \to (0,1)\)을 다음으로 정의한다 — \(x \in (0,1)\)이면 \(g(x) = \dfrac x3\), 그리고 \(g(2) = \dfrac12\). 무대 확인: \(0 < x < 1\)이면 \(0 < \frac x3 < \frac13 < 1\)이고 \(\frac12 \in (0,1)\)이므로 모든 값이 \((0,1)\)에 있다.
겹침 없음을 세 경우로 확인한다. ① 두 입력이 모두 \((0,1)\)에 있을 때: \(\frac{x_1}3 = \frac{x_2}3\)이면 양변에 3을 곱해 \(x_1 = x_2\)이다. ② 두 입력이 모두 \(2\)일 때: 같은 입력이므로 확인할 것이 없다. ③ 한 입력이 \((0,1)\)에 있고 다른 하나가 \(2\)일 때: 앞쪽의 값은 \(\frac x3 < \frac13\)이고 뒤쪽의 값은 \(\frac12 > \frac13\)이므로 두 값은 같을 수 없다. 세 경우에서 겹침이 없으므로 \(g\)는 단사이고 \(|(0,1) \cup \{2\}| \le |(0,1)|\)이다.
두 부등식에 정리 1.3을 적용하면 \(|(0,1)| = |(0,1) \cup \{2\}|\)이다. \(\blacksquare\)
복기. 갈래로 갈린 함수의 단사 증명에서 채점의 핵심은 경우 ③이다. 각 갈래 안에서의 단사성만 보이고 갈래 사이를 확인하지 않으면, 두 갈래가 같은 값을 내는 함수도 통과한다. \(\frac13\)이라는 경계가 두 구역을 갈라 놓는다는 사실을 답안에 적는 것이 그 확인이다. 같은 구조가 문제 11과 문제 17에서 반복된다.
문제 9#
접근. 가정이 주는 것은 단사 두 개이고 결론이 요구하는 것은 단사 하나다. 그러면 만들 후보는 합성뿐이다. C12주차 문제 8을 인용하면 한 줄이지만, 이 문제는 그 논증을 처음부터 적는 것이 목적이므로 단사의 정의를 그대로 펼친다.
풀이. \(|A| \le |B|\)이고 \(|B| \le |C|\)라 하자. 정의 1.1에 의해 단사 \(f : A \to B\)와 단사 \(g : B \to C\)가 존재한다. 합성 \(g \circ f : A \to C\)를 잡는다. 이것이 단사임을 보이자.
\((g \circ f)(a_1) = (g \circ f)(a_2)\)라 하자. 곧 \(g(f(a_1)) = g(f(a_2))\)이다. \(g\)가 단사이므로 \(f(a_1) = f(a_2)\)이고, 다시 \(f\)가 단사이므로 \(a_1 = a_2\)이다. 따라서 \(g \circ f\)는 단사이고, 정의 1.1에 의해 \(|A| \le |C|\)이다. \(\blacksquare\)
복기. 두 단사를 벗기는 순서가 정해져 있다는 점이 이 증명의 요점이다. 바깥에 있는 \(g\)를 먼저 벗겨 \(f(a_1) = f(a_2)\)를 얻고, 그다음 \(f\)를 벗긴다. 순서를 바꾸면 벗길 것이 없다 — 등식의 양변이 \(g\)의 값이기 때문이다. 이 논증이 §1.4의 추이성이고, 반사성과 함께 기수의 \(\le\)가 순서처럼 행동하기 위한 두 조건을 채운다.
문제 10#
접근. C5주차 §1.6의 다섯 걸음을 순서대로 돌린다. 걸음 ①에서 이미 결론이 나오지만, 그것만 적으면 이 답안이 어디서 무너졌는지는 밝히지 못한다. 두 함수를 각각 채점표 ②(무대)와 ③(겹침)에 걸어 본다.
풀이. 판정은 틀림이다.
걸음 ① 명제 진위. 명제 자체가 거짓이다. C13주차 예제 2.3이 \((0,1)\)의 비가산성을 주고 \((0,1) \subseteq \mathbb{R}\)이므로 \(\mathbb{R}\)는 비가산이며, 따라서 \(|\mathbb{N}| \ne |\mathbb{R}|\)이다. 거짓 명제에 붙은 증명은 반드시 어딘가가 틀렸다.
걸음 ② 논리 — 둘째 함수의 겹침. 결함은 “\(g(x) = \lfloor x \rfloor\)도 단사이다”라는 줄에 있다. \(\lfloor 1.5 \rfloor = 1\)이고 \(\lfloor 1.3 \rfloor = 1\)인데 \(1.5 \ne 1.3\)이므로 \(g\)는 서로 다른 두 입력을 같은 값으로 보낸다. 곧 \(g\)는 단사가 아니고, \(|\mathbb{R}| \le |\mathbb{N}|\)이 성립하지 않는다. 정리 1.3의 가정 하나가 채워지지 않았으므로 정리를 적용할 수 없다.
걸음 ② 논리 — 둘째 함수의 무대. 결함이 하나 더 있다. \(g\)는 애초에 \(\mathbb{R} \to \mathbb{N}\) 함수가 아니다. \(\lfloor 0.5 \rfloor = 0\)이고 \(\lfloor -3.2 \rfloor = -4\)인데 \(0\)과 \(-4\)는 자연수가 아니므로, 값이 공역 밖으로 나간다. 채점표 ②(무대 확인)를 통과하지 못한다.
걸음 ③ 가정 사용 \(\cdot\) ④ 양화사와 자격 \(\cdot\) ⑤ 전달. 첫 함수 \(f(n) = n\)은 실제로 단사이고 이 부분에는 결함이 없다. 문자 소개와 서술도 문제가 없다. 결함은 오직 \(g\)에 있다.
복기. 이 답안이 그럴듯해 보이는 이유는 서식이 완전히 맞기 때문이다 — 두 함수를 서로 반대 방향으로 제시했고 마지막 줄에서 정리의 이름도 댔다. 무너진 것은 서식이 아니라 각 함수에 붙어야 할 두 검증이다. 채점 기준 ②와 ③이 형식적 절차처럼 보여도 빼지 않는 이유가 여기에 있다. 참고로 \(|\mathbb{R}| \le |\mathbb{N}|\)이 왜 어떤 함수로도 성립할 수 없는지는 문제 2 (c)가 답한다.
문제 11#
접근. \(\mathbb{N} \subseteq \mathbb{Z}\)이므로 한쪽은 포함사상이다. 반대쪽에서는 \(\mathbb{Z}\)의 양수와 0 이하를 서로 다른 구역에 심어야 하고, 그 두 구역을 갈라 놓을 성질로 짝수와 홀수를 쓴다.
풀이. \(f : \mathbb{N} \to \mathbb{Z}\)를 \(f(n) = n\)으로 정의한다. \(\mathbb{N} \subseteq \mathbb{Z}\)이므로 값이 무대에 들어가고, \(f(n_1) = f(n_2)\)이면 곧 \(n_1 = n_2\)이므로 단사다. 따라서 \(|\mathbb{N}| \le |\mathbb{Z}|\)이다.
\(g : \mathbb{Z} \to \mathbb{N}\)을 다음으로 정의한다 — \(n > 0\)이면 \(g(n) = 2n\), \(n \le 0\)이면 \(g(n) = -2n + 1\). 무대 확인: \(n > 0\)이면 \(2n \ge 2\)이고, \(n \le 0\)이면 \(-n \ge 0\)이라 \(-2n + 1 \ge 1\)이므로, 두 경우 모두 값이 자연수다.
겹침 없음을 세 경우로 확인한다. ① 둘 다 양수일 때: \(2n_1 = 2n_2\)이면 양변을 2로 나누어 \(n_1 = n_2\)이다. ② 둘 다 0 이하일 때: \(-2n_1 + 1 = -2n_2 + 1\)이면 양변에서 1을 빼고 \(-2\)로 나누어 \(n_1 = n_2\)이다. ③ 하나가 양수이고 다른 하나가 0 이하일 때: 앞쪽의 값은 \(2n\) 꼴이라 짝수이고 뒤쪽의 값은 \(-2n+1\) 꼴이라 홀수이므로, 두 값은 같을 수 없다(1권 1주차의 짝수\(\cdot\)홀수 정의). 따라서 \(g\)는 단사이고 \(|\mathbb{Z}| \le |\mathbb{N}|\)이다.
두 부등식에 정리 1.3을 적용하면 \(|\mathbb{Z}| = |\mathbb{N}|\)이다. \(\blacksquare\)
검산. \(g(1) = 2\), \(g(2) = 4\), \(g(0) = 1\), \(g(-1) = 3\), \(g(-2) = 5\) — 값이 모두 자연수이고 서로 다르다. C13주차 예제 2.2는 같은 결론을 얻기 위해 갈래로 갈린 전단사를 만들고 전사까지 검증했는데, 이번 답안에서는 전사 검증이 통째로 사라졌다.
복기. 갈래를 가를 성질로 짝\(\cdot\)홀을 쓰는 것은 이 수단의 표준이다. 두 구역이 겹치지 않음을 보이려면 “한쪽 값이 가진 성질을 다른 쪽 값은 갖지 못한다”를 지목하면 되고, 짝수와 홀수는 그 지목이 가장 짧게 되는 성질이다. 문제 8에서는 같은 일을 \(\frac13\)이라는 경계가 했다.
문제 12#
접근. 쉬운 쪽은 포함사상이다. 어려운 쪽은 \(\mathbb{N} \to B\) 단사이고, 재료는 \(A\)가 가산무한이라는 가정뿐이다. 가산무한은 \(A\)의 목록을 주므로, 그 목록에서 \(B\)에 속하는 항만 남긴다. \(B\)가 무한이라는 가정이 남은 목록이 끝나지 않음을 보장한다 — 이 가정이 없으면 결론이 거짓이다.
풀이. \(A\)가 가산무한이므로 전단사 \(\varphi : \mathbb{N} \to A\)가 존재한다. \(a_n = \varphi(n)\)이라 두면 \(A = \{a_1, a_2, a_3, \ldots\}\)이고 이 목록에는 겹침이 없다.
한쪽 부등식. 포함사상 \(\iota : B \to A\), \(\iota(b) = b\)는 \(B \subseteq A\)이므로 값이 무대에 들어가고, \(\iota(b_1) = \iota(b_2)\)이면 곧 \(b_1 = b_2\)이므로 단사다. 따라서 \(|B| \le |A|\)이다.
반대쪽 부등식. \(I = \{n \in \mathbb{N} : a_n \in B\}\)라 하자. 목록이 \(A\) 전체를 덮고 \(B \subseteq A\)이므로 \(B\)의 각 원소는 어떤 \(a_n\)과 같고, 따라서 \(I\)의 원소 하나가 \(B\)의 원소 하나에 대응한다. \(B\)가 무한이므로 \(I\)도 무한집합이다. \(I\)의 원소를 작은 것부터 \(n_1 < n_2 < n_3 < \cdots\)로 늘어놓는다 — 자연수의 비어 있지 않은 부분집합에는 최소원소가 있고(1권 33주차 최소원리), \(I\)가 무한이므로 이 뽑기는 어느 단계에서도 멈추지 않는다. 이제 \(h : \mathbb{N} \to B\)를 \(h(k) = a_{n_k}\)로 정의한다. \(n_k \in I\)이므로 \(a_{n_k} \in B\)이고 값이 무대에 들어간다. \(k_1 \ne k_2\)이면 \(n_{k_1} \ne n_{k_2}\)이고, 목록에 겹침이 없으므로 \(a_{n_{k_1}} \ne a_{n_{k_2}}\)이다. 따라서 \(h\)는 단사이고 \(|\mathbb{N}| \le |B|\)이다. 한편 \(\varphi^{-1} : A \to \mathbb{N}\)이 전단사이므로 특히 단사이고, \(h \circ \varphi^{-1} : A \to B\)는 단사의 합성으로서 단사다(문제 9). 곧 \(|A| \le |B|\)이다.
마무리. 두 부등식에 정리 1.3을 적용하면 \(|B| = |A|\)이다. \(\blacksquare\)
복기. “\(B\)가 무한”이라는 가정이 쓰인 자리는 정확히 한 곳 — \(I\)가 무한이어서 뽑기가 멈추지 않는다는 줄이다. 그 가정을 빼면 \(B = \{a_1, a_2\}\) 같은 유한집합이 반례가 된다. 가정이 어느 줄에서 소비되는지 짚어 두는 것은 C5주차 증명 평가의 걸음 ③이 요구하는 습관이며, 그 자리를 알면 명제를 잘못 일반화하는 일이 줄어든다.
문제 13#
접근. 쉬운 쪽은 포함사상 \((0,1) \to \mathbb{R}\)이다. 어려운 쪽은 실직선 전체를 길이 1짜리 구간 안으로 접어 넣는 함수이고, 아크탄젠트가 그 일을 한다 — 치역이 유계이고 순증가라서 겹침이 없기 때문이다.
풀이. \(f : (0,1) \to \mathbb{R}\)을 \(f(x) = x\)로 정의한다. \((0,1) \subseteq \mathbb{R}\)이므로 값이 무대에 들어가고, \(f(x_1) = f(x_2)\)이면 곧 \(x_1 = x_2\)이므로 단사다. 따라서 \(|(0,1)| \le |\mathbb{R}|\)이다.
\(g : \mathbb{R} \to (0,1)\)을 \(g(x) = \dfrac1\pi \arctan x + \dfrac12\)로 정의한다. 무대 확인: 모든 실수 \(x\)에 대해 \(-\frac\pi2 < \arctan x < \frac\pi2\)이므로(§1.8에서 인정하고 쓴다), 각 변을 \(\pi > 0\)으로 나누면 \(-\frac12 < \frac1\pi\arctan x < \frac12\)이고, 각 변에 \(\frac12\)을 더하면
이므로 \(g(x) \in (0,1)\)이다. 겹침 없음: \(g(x_1) = g(x_2)\)라 하면 양변에서 \(\frac12\)을 빼고 \(\pi\)를 곱해 \(\arctan x_1 = \arctan x_2\)을 얻는다. 아크탄젠트는 \(\mathbb{R}\)에서 순증가하므로 \(x_1 < x_2\)이면 \(\arctan x_1 < \arctan x_2\)이고 \(x_2 < x_1\)이면 부등호가 반대가 되어, 어느 쪽이든 위 등식과 어긋난다. 삼분법에 의해 남는 경우는 \(x_1 = x_2\)뿐이다. 따라서 \(g\)는 단사이고 \(|\mathbb{R}| \le |(0,1)|\)이다.
두 부등식에 정리 1.3을 적용하면 \(|(0,1)| = |\mathbb{R}|\)이다. \(\blacksquare\)
복기. 순증가에서 단사로 가는 이 논증 — 두 경우를 삼분법으로 배제하고 남는 경우를 취한다 — 은 순증가 함수라면 어디서나 그대로 쓰인다. C13주차 문제 13은 같은 결론을 전단사로 얻었고 전사 검증(임의의 실수 \(y\)에 대해 원상을 구성)이 필요했는데, 이번 답안에서는 그 부분이 사라졌다. 이 결과는 예제 2.1과 합쳐 (Q3)의 둘째 등호 \(|[0,1]| = |\mathbb{R}|\)을 세운다(마지막 등호 \(|\mathbb{R}| = \mathfrak{c}\)는 \(\mathfrak{c}\)의 정의이므로 증명할 것이 없다 — C13주차 §1.4). 그리고 예제 2.3이 무대를 \((0,1)\)로 옮길 때 쓴 것이 바로 이 전단사다.
문제 14#
접근. 정의 1.2를 그대로 따르면 할 일이 둘이다 — 단사 하나를 제시해 \(\le\)를 얻고, 전단사가 없음을 인용해 \(\ne\)를 얻는다. 앞쪽은 두 줄이고 뒤쪽은 출처를 대면 한 줄이다. 뒤쪽을 스스로 증명하려 들면 대각선 논법을 다시 쓰게 되므로, 인용이 정답이다.
풀이. \(f : \mathbb{N} \to \mathcal{P}(\mathbb{N})\)을 \(f(n) = \{n\}\)으로 정의한다. \(\{n\}\)은 \(\mathbb{N}\)의 부분집합이므로 값이 무대에 들어간다. \(f(n_1) = f(n_2)\)라 하면 \(\{n_1\} = \{n_2\}\)이고, 한 원소 집합이 같다는 것은 그 원소가 같다는 뜻이므로 \(n_1 = n_2\)이다. 따라서 \(f\)는 단사이고 정의 1.1에 의해 \(|\mathbb{N}| \le |\mathcal{P}(\mathbb{N})|\)이다.
한편 C13주차 문제 14(칸토어)에 의해 \(\mathbb{N}\)에서 \(\mathcal{P}(\mathbb{N})\)으로 가는 전단사는 존재하지 않으므로 \(|\mathbb{N}| \ne |\mathcal{P}(\mathbb{N})|\)이다. 두 사실을 정의 1.2에 넣으면 \(|\mathbb{N}| < |\mathcal{P}(\mathbb{N})|\)이다. \(\blacksquare\)
복기. 진부등호의 답안은 언제나 이 두 조각이다 — 만드는 일과 배제하는 일. 만드는 일은 함수 하나로 끝나고, 배제하는 일은 대각선이나 그 일반형(C13주차 문제 15)을 인용해야 한다. 두 조각의 난이도가 크게 다르다는 것이 C13주차 §1.2 확인 2의 비대칭이며, 이번 주 내내 반복되는 구도다.
문제 15#
접근. 양쪽 모두 어려운 쪽이다. \(\mathcal{P}(\mathbb{N}) \to \mathbb{R}\)은 부분집합을 소수의 자릿수로 심으면 되고, 자릿수를 0과 1만 쓰면 9의 꼬리가 생기지 않아 이중 표기 문제가 아예 발생하지 않는다. 반대 방향은 실수를 유리수의 집합으로 바꾸는 데데킨트 절단을 쓰고, 그 뒤 \(\mathcal{P}(\mathbb{Q})\)를 \(\mathcal{P}(\mathbb{N})\)으로 옮기는 데 문제 15 앞의 도입 상자를 인용한다.
풀이. ① \(|\mathcal{P}(\mathbb{N})| \le |\mathbb{R}|\). \(\alpha : \mathcal{P}(\mathbb{N}) \to \mathbb{R}\)을 다음으로 정의한다 — \(S \subseteq \mathbb{N}\)에 대해 \(\alpha(S) = 0.b_1b_2b_3\cdots\), 여기서 \(n \in S\)이면 \(b_n = 1\)이고 \(n \notin S\)이면 \(b_n = 0\)이다. 값은 실수이므로 무대에 들어간다. 이 전개는 자릿수가 0과 1뿐이라 9로 이어지는 꼬리를 갖지 않으므로 그 값의 유일한 십진 표기다(C13주차 §1.6). 따라서 \(\alpha(S) = \alpha(T)\)이면 두 값의 전개가 같고, 자리마다 \(b_n\)이 일치하므로 각 \(n\)에 대해 “\(n \in S\)”와 “\(n \in T\)”가 동치이며, 곧 \(S = T\)이다. \(\alpha\)는 단사다.
② \(|\mathbb{R}| \le |\mathcal{P}(\mathbb{N})|\). 먼저 \(\beta : \mathbb{R} \to \mathcal{P}(\mathbb{Q})\)를 \(\beta(r) = \{q \in \mathbb{Q} : q < r\}\)로 정의한다(데데킨트 절단). 값은 \(\mathbb{Q}\)의 부분집합이므로 무대에 들어간다. \(r \ne r'\)이라 하고 일반성을 잃지 않고 \(r < r'\)이라 하자. 서로 다른 두 실수 사이에는 유리수가 있으므로(§1.8에서 인정하고 쓴다) \(r < q < r'\)인 \(q \in \mathbb{Q}\)가 존재한다. 그러면 \(q \in \beta(r')\)이고 \(q \notin \beta(r)\)이므로 \(\beta(r) \ne \beta(r')\)이다. 곧 \(\beta\)는 단사이고 \(|\mathbb{R}| \le |\mathcal{P}(\mathbb{Q})|\)이다. 한편 \(\mathbb{Q}\)는 가산무한이므로(C13주차 문제 11과 문제 2) \(|\mathbb{Q}| = |\mathbb{N}|\)이고, 문제 15 앞의 도입 상자에 의해 \(|\mathcal{P}(\mathbb{Q})| = |\mathcal{P}(\mathbb{N})|\)이다. 그 전단사를 \(\beta\) 뒤에 합성하면 \(\mathbb{R} \to \mathcal{P}(\mathbb{N})\) 단사가 되므로 (문제 9) \(|\mathbb{R}| \le |\mathcal{P}(\mathbb{N})|\)이다.
③ 마무리. 두 부등식에 정리 1.3을 적용하면 \(|\mathbb{R}| = |\mathcal{P}(\mathbb{N})|\)이다. \(\blacksquare\)
복기. \(\mathcal{P}(\mathbb{N})\)의 기수를 \(2^{\aleph_0}\)로 쓰는 이유는 부분집합 하나를 정하는 일이 각 자연수마다 “넣는다”와 “뺀다” 두 선택을 하는 일과 같기 때문이다 — ①의 \(\alpha\)가 그 두 선택을 자릿수 1과 0으로 적은 것이다. 그러므로 이 문제의 결론은 \(\mathfrak{c} = 2^{\aleph_0}\)으로도 적힌다. 이 등식과 (Q6)을 합치면 \(\aleph_0 < \mathfrak{c}\)가 다시 나오고(칸토어 정리를 \(A = \mathbb{N}\)에 적용), 연속체 가설이 묻는 것은 이 두 기수 사이의 빈 자리다(§1.7).
문제 16#
접근. 두 가지를 따로 해야 한다. 단사성은 십진 전개의 유일성을 어디서 쓰는지 드러나게 적는 것이 핵심이고, 전사가 아님은 상에 없는 실수를 하나 제시하고 그것이 상에 없음을 논증하면 끝난다. 그 실수는 §1.1 확인 1이 이미 만들어 두었다.
풀이. 예제 2.3에서처럼 \((0,1)\)의 각 원소의 십진 전개를 9의 꼬리가 없는 쪽으로 하나 고정하고, \(\Lambda : (0,1)^2 \to (0,1)\)을 \(\Lambda(0.a_1a_2\cdots,\ 0.b_1b_2\cdots) = 0.a_1b_1a_2b_2\cdots\)로 둔다. 예제 2.3의 \(g\)는 \(\Lambda\)의 앞뒤에 전단사와 포함사상을 붙인 것이므로, 엮기 자체의 성질을 보면 된다.
단사인 이유. \(\Lambda(x_1, y_1) = \Lambda(x_2, y_2)\)라 하자. 엮어 만든 자리열은 꼬리가 전부 9일 수 없으므로 — 그러려면 홀수 자리와 짝수 자리가 모두 9의 꼬리를 가져야 하고, 곧 \(x\)와 \(y\)의 전개가 모두 9의 꼬리를 가져야 하는데 약속에 의해 그런 전개는 없다 — 그 자리열이 곧 값의 유일한 십진 표기다. 두 값이 같으므로 표기가 같고, 자리마다 숫자가 일치한다. 홀수 자리끼리 비교하면 \(x_1\)과 \(x_2\)의 전개가 자리마다 같으므로 \(x_1 = x_2\)이고, 짝수 자리끼리 비교하면 \(y_1 = y_2\)이다. 곧 \(\Lambda\)는 단사다. 십진 표기의 유일성이 쓰인 자리는 “값이 같으므로 자리열이 같다”로 넘어가는 줄이며, 그 유일성이 없으면 이 줄이 성립하지 않는다.
전사가 아닌 이유. \(z = 0.190909\cdots\)을 잡자. 이 수의 홀수 자리는 \(1, 0, 0, 0, \ldots\)이고 짝수 자리는 \(9, 9, 9, \ldots\)이며, 자리열 전체가 9로 끝나지 않으므로 이것이 \(z\)의 유일한 십진 표기다. 만약 \(z = \Lambda(x, y)\)인 쌍이 있다면 위의 단사 논증과 같은 이유로 \(x\)의 전개는 \(0.1000\cdots\)이고 \(y\)의 전개는 \(0.999\cdots\)이어야 한다. 그런데 약속에 의해 \((0,1)\)의 어떤 원소도 9의 꼬리를 갖는 전개로 적히지 않으므로 그러한 \(y\)는 없다. 따라서 \(z\)는 \(\Lambda\)의 상에 없고 \(\Lambda\)는 전사가 아니다. \(\blacksquare\)
복기. 예제 2.3이 성립하는 이유는 이 결함이 결론에 아무 영향도 주지 않기 때문이다. 정리 1.3이 요구하는 것은 반대 방향의 단사 두 개뿐이고, 전사는 요구하지 않는다. 곧 CSB는 “겹침 없음은 쉽고 빠짐 없음은 어렵다”는 §1.1의 비대칭을 그대로 받아들인 뒤, 어려운 쪽을 답안에서 제거해 준다. 이 문제는 그 제거가 실제로 무엇을 제거했는지를 눈으로 확인하는 자리다.
문제 17#
접근. 먼저 문제의 등식을 어떻게 읽을지 정해야 한다. 문자 그대로 \(\mathbb{N} \cup \mathbb{R}\)로 읽으면 \(\mathbb{N} \subseteq \mathbb{R}\)이므로 이 합집합은 \(\mathbb{R}\) 자신이고 등식이 자명하게 성립한다. 그러나 그 읽기로는 기수의 덧셈이 되지 않는다 — 겹치는 원소를 두 번 세지 않으려면 서로소여야 하기 때문이다 (문제 17 앞의 도입 상자). 그러므로 \(\mathbb{R}\)와 서로소인 가산무한 사본을 하나 잡아 그것과 \(\mathbb{R}\)의 합집합을 무대로 삼는다.
풀이. \(N\)을 \(\mathbb{R}\)와 서로소이고 가산무한인 집합이라 하고, 전단사 \(\nu : \mathbb{N} \to N\)을 하나 고정하자. \(U = N \cup \mathbb{R}\)로 두면 정의에 의해 \(|U| = \aleph_0 + \mathfrak{c}\)이다.
① \(\mathfrak{c} \le |U|\). 포함사상 \(\iota : \mathbb{R} \to U\), \(\iota(x) = x\)는 \(\mathbb{R} \subseteq U\)이므로 값이 무대에 들어가고, \(\iota(x_1) = \iota(x_2)\)이면 곧 \(x_1 = x_2\)이므로 단사다. 따라서 \(|\mathbb{R}| \le |U|\)이다.
② \(|U| \le \mathfrak{c}\). 문제 13의 \(g(x) = \frac1\pi\arctan x + \frac12\)는 단사이고 치역이 \((0,1)\) 안에 있다. 이것을 써서 \(G : U \to \mathbb{R}\)을 다음으로 정의한다 — \(x \in \mathbb{R}\)이면 \(G(x) = g(x)\), \(u \in N\)이면 \(G(u) = -\nu^{-1}(u)\). \(U = N \cup \mathbb{R}\)이고 두 집합이 서로소이므로 각 원소가 정확히 한 갈래에 들어가며, 따라서 \(G\)는 잘 정의된다. 값은 모두 실수이므로 무대에 들어간다.
겹침 없음을 세 경우로 확인한다. ① 두 입력이 모두 \(\mathbb{R}\)에 있을 때: \(g\)가 단사이므로 값이 같으면 입력이 같다. ② 두 입력이 모두 \(N\)에 있을 때: \(-\nu^{-1}(u_1) = -\nu^{-1}(u_2)\)이면 양변에 \(-1\)을 곱해 \(\nu^{-1}(u_1) = \nu^{-1}(u_2)\)이고, \(\nu^{-1}\)가 단사이므로 \(u_1 = u_2\)이다. ③ 한 입력이 \(\mathbb{R}\)에 있고 다른 하나가 \(N\)에 있을 때: 앞쪽의 값은 \((0,1)\)에 있어 양수이고, 뒤쪽의 값은 \(\nu^{-1}(u) \ge 1\)이라 \(-\nu^{-1}(u) \le -1 < 0\)이므로 음수다. 두 값은 같을 수 없다. 따라서 \(G\)는 단사이고 \(|U| \le |\mathbb{R}|\)이다.
③ 마무리. 두 부등식에 정리 1.3을 적용하면 \(|U| = |\mathbb{R}|\), 곧 \(\aleph_0 + \mathfrak{c} = \mathfrak{c}\)이다. \(\blacksquare\)
복기. 설계의 요령은 “큰 쪽을 먼저 좁은 방에 몰아넣고, 남는 자리에 작은 쪽을 심는다”이다. \(\mathbb{R}\) 전체를 \((0,1)\)로 접어 넣으면 \((0,1)\) 바깥이 통째로 비므로 가산무한 개를 심을 자리가 넘치게 남는다. 같은 설계로 \(\mathfrak{c} + \mathfrak{c} = \mathfrak{c}\)도 얻어진다 — 한 사본은 \((0,1)\)에, 다른 사본은 \((2,3)\)에 심으면 된다. 무한 기수의 덧셈이 큰 쪽을 그대로 두는 이유가 이 여유이며, 유한에서는 없는 여유다.
문제 18#
접근. 평가의 결과가 언제나 “틀림”인 것은 아니다. C5주차 §1.6의 다섯 걸음을 순서대로 돌려 각 걸음에서 결함이 없음을 확인한 뒤 판정을 적는다. 특히 걸음 ②에서 “전단사는 단사이다”가 어느 정의에서 나오는지 출처를 댈 수 있는지 본다.
풀이. 판정은 옳음이다.
걸음 ① 명제 진위. 명제는 참이다. 아래 걸음 ②가 그 증명을 확인해 준다.
걸음 ② 논리. 두 줄 모두 근거가 있다. 첫 줄 “\(|A| = |B|\)이면 전단사 \(f : A \to B\)가 있다”는 C13주차 정의 1.1을 그대로 푼 것이다. 둘째 줄 “전단사는 단사이다”는 전단사의 정의(단사이면서 전사인 함수, C12주차 정의 12.2)에서 곧바로 나온다. 그러면 단사 \(f : A \to B\)가 존재하므로 이번 주 정의 1.1에 의해 \(|A| \le |B|\)이다. 세 줄의 연결에 빈틈이 없다.
걸음 ③ 가정 사용. 가정 \(|A| = |B|\)가 첫 줄에서 실제로 소비되어 전단사를 공급한다. 가정을 쓰지 않고 결론이 나오는 자명한 증명이 아니다.
걸음 ④ 양화사와 자격. 특정 집합이나 특정 함수를 예로 들지 않았고, 임의의 \(A\), \(B\)에 대해 성립하는 논증이다. \(f\)에 붙은 자격(전단사)도 지켜졌다.
걸음 ⑤ 전달. 문자 \(f\)가 소개되었고 각 문장이 완결되어 있다.
복기. 이 명제가 말하는 것은 \(=\)가 \(\le\)를 함의한다는 것, 곧 두 관계가 서로 어긋나지 않는다는 것이다. 역은 성립하지 않는다 — \(|\mathbb{N}| \le |\mathbb{R}|\)이지만 \(|\mathbb{N}| \ne |\mathbb{R}|\)이다(문제 2). 그러므로 이 명제와 그 역을 구별하지 못하면 §1.6의 삭제 실험에 나온 답안을 쓰게 된다. 당연해 보이는 명제를 정의로부터 정확히 유도해 두는 일의 값이 여기에 있다.
문제 19#
접근. 쉬운 쪽은 한 좌표를 고정하는 한 줄이다. 어려운 쪽에서 자리 엮기를 쓰려는데, 엮기는 \((0,1)\)에서만 정의되어 있고 무대는 \([0,1]\)이라 끝점 \(0\)과 \(1\)이 걸린다. 그러면 예제 2.1의 \(g\)를 앞에 끼워 넣어 무대를 먼저 옮긴다. 이 문제는 “부품을 이어 붙여 단사를 만든다”는 설계의 연습이다.
풀이. ① \(f : [0,1] \to [0,1] \times [0,1]\)을 \(f(x) = (x, 0)\)으로 정의한다. \(x \in [0,1]\)이고 \(0 \in [0,1]\)이므로 값이 무대에 들어간다. \(f(x_1) = f(x_2)\)이면 \((x_1, 0) = (x_2, 0)\)이고 좌표별 상등에서 \(x_1 = x_2\)이므로 단사다. 따라서 \(|[0,1]| \le |[0,1] \times [0,1]|\)이다.
② 반대 방향을 세 부품으로 만든다. 먼저 예제 2.1의 \(g(x) = \frac{x+1}{3}\)은 \([0,1] \to (0,1)\) 단사였으므로,
로 두면 \(\Gamma\)는 단사다 — \(\Gamma(s_1,t_1) = \Gamma(s_2,t_2)\)이면 좌표별로 \(g(s_1) = g(s_2)\)이고 \(g(t_1) = g(t_2)\)이므로, \(g\)가 단사라 \(s_1 = s_2\)이고 \(t_1 = t_2\)이다. 다음으로 예제 2.3의 자리 엮기 \(\Lambda : (0,1)^2 \to (0,1)\)이 단사이고(문제 16), 끝으로 포함사상 \(\iota : (0,1) \to [0,1]\)이 단사다. 세 부품을 이어 붙인 \(G = \iota \circ \Lambda \circ \Gamma : [0,1]^2 \to [0,1]\)은 단사의 합성이므로 단사다 (문제 9). 따라서 \(|[0,1] \times [0,1]| \le |[0,1]|\)이다.
③ 두 부등식에 정리 1.3을 적용하면 \(|[0,1] \times [0,1]| = |[0,1]|\)이다. \(\blacksquare\)
복기. 예제 2.3과 이 문제의 차이는 무대가 유계인가 아닌가뿐이고, 설계는 같다 — 무대를 \((0,1)\)로 옮긴 뒤 엮고, 다시 원래 무대로 되돌린다. 이 결과를 (Q3)과 합치면 \(\mathfrak{c} \cdot \mathfrak{c} = \mathfrak{c}\)가 되고, 곧 단위 정사각형의 점의 개수가 한 변의 점의 개수와 같다. 참고로 이 상등을 연속인 전단사로 실현할 수는 없으며, 그 사실의 증명은 이 과정 밖의 주제다. 기수가 같다는 것과 두 도형이 같은 모양이라는 것은 전혀 다른 주장이다.
문제 20#
접근. (a)는 예제 2.1과 2.3에서 실제로 절약된 것이 무엇인지를 답안의 말로 지목해야 한다 — “쉽다”는 인상이 아니라 “어떤 검증이 사라졌는가”를 적는다. (b)는 S7주차 문제 16과 C11주차 문제 18에서 본 반대칭성과 정리 1.3을 나란히 놓고, 같은 점과 다른 점을 한 문장씩 적는다.
풀이 (예시 답안). (a) 예제 2.1에서 \(|(0,1)| = |[0,1]|\)을 전단사로 직접 보이려면 끝점 두 개를 받아 낼 자리를 만들기 위해 규칙을 여러 갈래로 갈라야 하고(C13주차 문제 19), 예제 2.3에서 \(|\mathbb{R}| = |\mathbb{R}^2|\)의 전단사를 직접 만드는 일은 자리 엮기가 전사가 아니라는 §1.1의 장벽에 막힌다. CSB는 두 경우 모두 포함사상과 축소, 자리 엮기라는 한 줄짜리 단사 두 개로 결론을 대신하게 해 준다. 양방향 단사가 쉬운 이유는 단사에 붙는 검증이 “겹치지 않는가” 하나뿐이고, 전단사에 붙는 검증 가운데 어려운 쪽인 “무대를 빠짐없이 덮는가”가 요구되지 않기 때문이다.
(b) S7주차 문제 16에서 실수의 \(\le\)가 “\(a \le b\)이고 \(b \le a\)이면 \(a = b\)”를 만족함을 보았고 C11주차 문제 18에서 반사\(\cdot\)추이\(\cdot\)반대칭을 갖춘 관계를 부분순서라 불렀는데, 정리 1.3은 기수의 \(\le\)가 무한집합에서도 그 반대칭성을 갖춤을 말한다. 다른 점은 근거의 종류다 — 실수에서는 삼분법이라는 순서의 성질에서 한 줄로 나오지만, 기수에서는 경유할 수가 없어 두 단사로부터 전단사를 실제로 제작해야 하며 그 제작 가능성이 곧 정리의 내용이다.
채점 항목. (a)에서는 “사라진 검증이 전사”라는 지목이 있어야 한다. “CSB가 쉽다”만 적으면 근거가 없다. (b)에서는 “같은 문장이 성립한다”와 “근거가 다르다”가 둘 다 있어야 한다. 성립한다는 사실만 적으면 유한과 무한의 차이가 드러나지 않고, 그 차이가 이 정리가 정리인 이유다.
다음 주 예고 (C15): Chartrand 12장 — 정수론. 최대공약수와 유클리드 호제법, 베주 항등식, 유클리드 보조정리, 그리고 산술의 기본정리의 유일성을 차례로 세운다. 이번 주 예제 2.2와 훈련 3에서 \(2^m3^n\)과 \(2^a3^b5^c\)의 단사성을 홀짝과 합동 논증으로 우회했는데, 소인수분해의 유일성이 서면 그 논증이 한 줄로 줄어든다. C7주차\(\cdot\)C8주차\(\cdot\)C11주차\(\cdot\)C13주차\(\cdot\)C14주차가 “인정하고 쓴다”로 미뤄 온 유클리드 보조정리와 소인수분해 유일성이 거기서 증명되고, 1권 33주차가 남긴 가장 큰 외상이 청산된다. 원서 12장을 통독하고 온다.