# 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}$ | :::{container} quotebox **확인 11.** 목표 칸의 빈칸을 채워 보자. 정리 1.3을 쓰기로 정했다면 답안이 실제로 만들어 내놓아야 하는 것은 무엇인가. ::: :::{admonition} 답 :class: quotebox dropdown **단사 $f : (0,1) \to [0,1]$ 하나와 단사 $g : [0,1] \to (0,1)$ 하나.** 전단사를 만들 의무는 없다. C13주차 문제 19가 이 두 집합 사이의 전단사를 네 갈래 규칙으로 만들었는데, 이번 설계에는 그 규칙이 필요 없다. 출발점(두 무대의 포함 관계)과 도착점(제작할 함수 두 개)이 정해졌다. ::: **1단계 — 쉬운 쪽 단사를 만든다.** $(0,1)$의 원소는 이미 $[0,1]$의 원소다. 그러면 아무것도 옮기지 않는 대응이 곧 단사다. :::{container} quotebox **확인 12.** $f : (0,1) \to [0,1]$의 식을 적고, 값이 무대에 들어가는지와 겹침이 없는지를 각각 한 줄로 확인해 보자. ::: :::{admonition} 답 :class: quotebox dropdown $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)$ 안으로 밀어 넣어야 한다. 끝점을 다른 곳으로 옮기지 않으면 값이 무대 밖으로 나간다. :::{container} quotebox **확인 13.** $[0,1]$ 전체를 $(0,1)$ 안쪽으로 옮겨 놓으려면 어떤 종류의 조작이 필요한가. 일차함수 $g(x) = ax + b$로 하려면 $a$와 $b$에 어떤 조건이 붙는가. ::: :::{admonition} 답 :class: quotebox dropdown **축소한 뒤 안쪽으로 평행이동**하는 조작이다. $a > 0$이면 상이 $[b, a+b]$이므로, 이 구간이 $(0,1)$ 안에 들어가려면 $b > 0$이고 $a + b < 1$이면 된다. 이 조건을 만족하는 가장 간단한 선택 하나가 $a = b = \frac13$, 곧 $g(x) = \dfrac{x+1}{3}$이다. 상은 $[\frac13, \frac23]$이 된다. ::: :::{container} quotebox **확인 14.** $g(x) = \frac{x+1}{3}$의 값이 실제로 $(0,1)$에 들어감을 부등식으로 확인해 보자. ::: :::{admonition} 답 :class: quotebox dropdown $0 \le x \le 1$의 각 변에 1을 더하면 $1 \le x + 1 \le 2$이고, 각 변을 3으로 나누면 $$ \frac13 \le \frac{x+1}{3} \le \frac23 $$ 이다(근거 ③). 그리고 $0 < \frac13$이고 $\frac23 < 1$이므로 $0 < g(x) < 1$, 곧 $g(x) \in (0,1)$이다. 무대 확인은 이 두 줄로 끝난다. ::: :::{container} quotebox **확인 15.** $g$의 단사 증명 두 문장을 완성해 보자. "$g(x_1) = g(x_2)$라 하자. 곧 $\underline{\qquad}$이고, 양변에 $\underline{\quad}$을 곱한 뒤 $\underline{\quad}$을 빼면 $x_1 = x_2$이다." ::: :::{admonition} 답 :class: quotebox dropdown "$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단계 — 정리를 인용해 마무리한다.** :::{container} quotebox **확인 16.** 마지막 문장을 완성해 보자. "$|(0,1)| \le |[0,1]|$이고 $|[0,1]| \le |(0,1)|$이므로 $\underline{\qquad}$에 의해 $\underline{\qquad}$이다. $\blacksquare$" ::: :::{admonition} 답 :class: quotebox dropdown "$|(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}|$. 이번에는 설계만 함께 하고, 본문은 완성본으로 본다. :::{container} quotebox **확인 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}$. ::: :::{admonition} 답 :class: quotebox dropdown $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|$. 이번에는 설계부터 스스로 해 보자. :::{container} quotebox **확인 18.** 만들어야 할 단사 두 개를 각각 한 줄로 설계해 보자. 어려운 쪽은 §1.1의 자리 엮기를 어디에 어떻게 끼워 넣으면 되는지까지 적어 보자. ::: :::{admonition} 답 :class: quotebox dropdown 쉬운 쪽: $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 : \mathbb{R}^2 \to (0,1)^2, \qquad \Phi(x, y) = \big(\varphi(x), \varphi(y)\big) $$ 을 정의하면 $\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), $$ \Lambda : (0,1)^2 \to (0,1), \qquad \Lambda(0.a_1a_2a_3\cdots,\ 0.b_1b_2b_3\cdots) = 0.a_1b_1a_2b_2a_3b_3\cdots $$ 으로 정의한다. 엮어 만든 자리열은 전부 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}$ | :::{container} quotebox **확인 19.** 표의 (1)~(4)를 채워 보자. ::: :::{admonition} 답 :class: quotebox dropdown (1) $x \mapsto (x, 0)$. (2) $\varphi$로 무대를 $(0,1)^2$로 옮긴 뒤 자리를 엮고 포함사상으로 되돌리는 합성. (3) 홀짝 논증 — $3^{n}$이 홀수임을 써서 2의 지수를 먼저 맞춘다. (4) 정리 1.3 인용. ::: :::{container} quotebox **확인 20.** 세 예제가 공통으로 한 일을 한 문장으로 적어 보자. 그리고 어려운 쪽 단사를 만들 때 쓴 수단들을 모아 보자. ::: :::{admonition} 답 :class: quotebox dropdown 공통으로 한 일: **서로 반대 방향의 단사를 하나씩 제작하고, 각각에 무대 확인과 겹침 없음 검증을 붙인 뒤 정리 1.3을 인용했다.** 전사는 한 번도 검증하지 않았다. 어려운 쪽에서 쓴 수단은 셋이다 — 큰 집합을 **축소해 안쪽으로 밀어 넣기**(예제 2.1), 두 자리를 **서로 다른 소수의 지수에 심기**(예제 2.2), 두 전개의 **자리를 번갈아 엮기**(예제 2.3). 세 수단 모두 "정보를 잃지 않고 접는 방법"이라는 점이 같다. ::: 방금 확인한 뼈대에 이름을 붙인다. :::{admonition} 백지 암기 대상 :class: keybox **큰 쪽을 작은 쪽 안에 심는 네 가지 수단** ① **포함사상** — 부분집합 관계가 있으면 그대로 단사다. ② **축소와 평행이동** — 닫힌 구간을 열린 구간 안으로, 큰 구간을 작은 구간 안으로 옮긴다. ③ **부호나 갈래로 자리 나누기** — 정의역을 갈래로 나눠 상이 겹치지 않는 구역에 각각 심는다(문제 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을 인용한다. :::{admonition} 이번 주의 채점 기준 :class: quotebox 답이 아니라 **근거**가 점수다. CSB 답안에는 채점 항목이 넷이다. ① 두 단사가 **서로 반대 방향**으로 명시되어 있는가. 방향이 같은 두 함수는 정리 1.3의 가정이 아니다. ② 각 함수의 **값이 무대에 들어감**을 확인했는가. 식만 적으면 함수가 정의되지 않는다. ③ 각 함수의 **겹침 없음**을 증명했는가. "단사임은 자명하다"는 증명이 아니다. ④ 마지막 줄에서 **정리 1.3을 인용**했는가. 두 부등식 아래에 등호만 적으면 근거가 빠진다. 전사는 채점 항목이 아니다 — 검증할 필요도, 성립할 필요도 없다. 난이도와 무관하게, 힌트 상자는 5분 이상 막힌 뒤에만 연다. ::: ### 기본 ●○○ **1.** [백지] $|A| \le |B|$의 정의(단사), CSB 정리, CSB 활용 3단계를 쓰시오. :::{admonition} 힌트 :class: quotebox dropdown 정의는 문장을 통째로 외우기보다 §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}|$ :::{admonition} 힌트 :class: quotebox dropdown 네 칸 중 셋은 포함사상 한 줄로 끝난다. 나머지 하나는 "단사가 존재하지 않는다"는 **비존재** 주장이므로 함수를 하나 못 만든 것으로는 끝나지 않는다 — §1.6 확인 8의 논증을 그대로 옮겨 쓴다. ::: **3.** 예제 2.1($|(0,1)| = |[0,1]|$)을 백지 재현하시오. :::{admonition} 힌트 :class: quotebox dropdown §1.6의 3단 서식 세 칸을 먼저 적고 각 칸에 예제 2.1의 문장을 채워 넣는다. 자주 빠지는 것은 걸음 ②의 무대 확인 — $\frac{x+1}{3}$이 실제로 $(0,1)$ 안에 있다는 부등식 두 줄이다. ::: **4.** 빈칸 훈련을 백지에서 완성하시오. :::{admonition} 힌트 :class: quotebox dropdown 훈련 1은 $M$의 가장 작은 원소가 무엇인지 보면 $f$의 식이 나오고, 훈련 2는 어느 쪽 구간이 끝점을 갖는지 보면 어느 방향이 어려운 쪽인지 정해진다. 훈련 3은 예제 2.2의 밑 두 개를 세 개로 늘리는 것이 전부다. ::: **5.** 예제 2.2($|\mathbb{N}| = |\mathbb{N} \times \mathbb{N}|$)를 백지 재현하시오 — 소인수 단사. :::{admonition} 힌트 :class: quotebox dropdown 관절은 $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)$). :::{admonition} 힌트 :class: quotebox dropdown 요구되는 것은 정의 1.1이 요구하는 것 하나 — 단사의 제시다. 값이 곱집합에 들어가려면 두 좌표가 **모두** 자연수여야 한다는 확인을 빠뜨리지 않는다. ::: ### 표준 ●●○ **7.** CSB로 $|[0,1]| = |[0,2]|$를 증명하시오 (두 단사 — 포함 + 축소, 또는 $x \mapsto 2x$가 이미 전단사이나 CSB 연습으로). :::{admonition} 힌트 :class: quotebox dropdown 포함사상 쪽은 $[0,1] \subseteq [0,2]$에서 곧바로 나온다. 반대 방향은 길이 2인 구간을 길이 1인 구간 안으로 넣어야 하므로 예제 2.1의 수단 ②(축소)를 쓴다. ::: **8.** CSB로 $|(0,1)| = |(0,1) \cup \{2\}|$ (한 점 추가)를 증명하시오 (단사 $f(x) = x$, $g$는 점 2를 구간 안으로). :::{admonition} 힌트 :class: quotebox dropdown $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의 증명 평가 다섯 걸음으로). :::{container} quotebox **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}|$이다. ::: :::{admonition} 힌트 :class: quotebox dropdown 걸음 ①에서 이미 결론이 나오지만, 그것만 적으면 이 답안이 **어디서** 무너졌는지는 밝히지 못한다. 두 함수를 각각 채점표 ②(무대)와 ③(겹침)에 걸어 보고, 반례가 되는 구체적인 두 수를 답안에 적는다. ::: **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$)). :::{admonition} 힌트 :class: quotebox dropdown 갈래가 둘인 함수의 단사 증명은 문제 8과 같은 구조다. 갈래 사이를 막아 주는 것을 찾는다 — 한쪽 갈래의 값은 전부 짝수이고 다른 쪽은 전부 홀수다. ::: **12.** 무한 부분집합: $A$가 가산무한이고 $B \subseteq A$가 무한이면 $|B| = |A|$임을 CSB로 설명하시오 ($B \subseteq A$라 $|B| \le |A|$; $A$ 가산이라 $|A| = |\mathbb{N}| \le |B|$ — 무한 부분집합도 가산). :::{admonition} 힌트 :class: quotebox dropdown 어려운 쪽은 $\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$류). :::{admonition} 힌트 :class: quotebox dropdown 반대 방향의 함수는 치역이 $(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})|$를 결론하시오. :::{admonition} 힌트 :class: quotebox dropdown 정의 1.2를 그대로 따르면 할 일이 둘이다 — 단사 하나를 제시하고, 전단사가 없음을 인용한다. 앞쪽은 두 줄이고 뒤쪽은 출처를 대면 한 줄이다. ::: ### 도전 ●●● :::{admonition} 이 문제들이 빌려 쓰는 도구 — 전단사를 멱집합으로 올리기 :class: quotebox $\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}$". :::{admonition} 힌트 :class: quotebox dropdown 부분집합을 소수로 옮길 때 자릿수를 $0$과 $1$만 쓰면 9의 꼬리가 생기지 않으므로 이중 표기 문제가 아예 발생하지 않는다(C13주차 §1.6). 절단 쪽의 단사성은 "서로 다른 두 실수 사이에 유리수가 있다"는 사실 하나로 끝난다. ::: **16.** ($\mathbb{R}^2$ 종합) 예제 2.3의 교대 엮기 단사 $g: \mathbb{R}^2 \to \mathbb{R}$가 왜 단사인지 상세히 설명하고, 왜 전사가 **아닌지**(엮음으로 안 나오는 실수 존재) 예를 드시오. "CSB가 전사 부족을 흡수한다". :::{admonition} 힌트 :class: quotebox dropdown 전사가 아님을 보이려면 상에 없는 실수를 **하나** 제시하고 그것이 상에 없음을 논증하면 된다. §1.1 확인 1이 그 실수 하나를 이미 만들어 두었다. ::: :::{admonition} 이 문제가 빌려 쓰는 약속 — 기수의 덧셈과 서로소 사본 :class: quotebox $\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}$의 빈 곳에 심기). :::{admonition} 힌트 :class: quotebox dropdown 어려운 쪽 단사의 설계는 "겹치지 않는 두 구역에 각각 심기"다(§2 관찰의 수단 ③). $\mathbb{R}$ 쪽 전체를 $(0,1)$ 안으로 밀어 넣으면(문제 13) $(0,1)$ 바깥이 통째로 비므로, 사본의 자연수들은 그 빈 곳에 심으면 된다. ::: **18.** (진단 종합) 다음 제시된 증명을 평가하시오. :::{container} quotebox **Result.** $|A| = |B|$이면 $|A| \le |B|$이다. **제시된 증명.** $|A| = |B|$이면 전단사 $f: A \to B$가 있고, 전단사는 단사이므로 $|A| \le |B|$이다. ::: :::{admonition} 힌트 :class: quotebox dropdown 평가의 결과가 언제나 "틀림"인 것은 아니다. 다섯 걸음을 순서대로 돌려 보고, 각 걸음에서 결함이 없음을 확인한 뒤 판정을 적는다. 특히 걸음 ②에서 "전단사는 단사이다"가 어느 정의에서 나오는지 출처를 댈 수 있는지 확인한다. ::: **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의 유계판. :::{admonition} 힌트 :class: quotebox dropdown 교대 엮기는 $(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)과 비교해 두 문장 이내 설명하시오. :::{admonition} 힌트 :class: quotebox dropdown (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으로 나누면 $$ \frac13 \le \frac{x+1}{3} \le \frac23 $$ 이므로 $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}$으로 나누어 $$ 3^{n_1} = 2^{m_2 - m_1} 3^{n_2} $$ 를 얻는데, 좌변은 홀수끼리의 곱이므로 홀수이고(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$을 더하면 $$ 0 < \frac1\pi \arctan x + \frac12 < 1 $$ 이므로 $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 : [0,1]^2 \to (0,1)^2, \qquad \Gamma(s, t) = \big(g(s),\, g(t)\big) $$ 로 두면 $\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장을 통독하고 온다.