C13주차 · 강의 — 예제 · 연습 · 해설

C13주차 · 강의 — 예제 · 연습 · 해설#

예제 — 크기 판정을 함께 만들기#

완성된 증명을 먼저 보이지 않는다. 백지에서 시작해 한 줄씩 만든다. 각 단계에서 확인 상자의 빈칸을 연필로 먼저 채운 뒤 답을 연다.

예제 2.1 — 짝수는 \(\mathbb{N}\)과 같은 크기#

명제. 양의 짝수 전체의 집합 \(2\mathbb{N} = \{2, 4, 6, \ldots\}\)은 가산무한이다.

설계 — 쓰기 전에 정하는 두 가지. 증명을 쓰기 전에 가정이 주는 것(출발점)과 만들어야 할 것(도착점)을 정한다. 둘 다 정의로 번역해서 얻는다.

말

수식 번역

가정 (주어진 것)

\(2\mathbb{N}\)은 양의 짝수 전체

\(m \in 2\mathbb{N}\) \(\iff\) \(m = 2k\)인 \(k \in \mathbb{N}\)이 존재

목표 (만들 것)

\(2\mathbb{N}\)이 가산무한

\(\underline{\quad(?)\quad}\)

확인 11. 목표 칸의 빈칸을 채워 보자. “\(2\mathbb{N}\)이 가산무한임을 보인다”를 정의 1.2와 1.1로 두 걸음 번역하면 무엇을 만들어야 하는가.

답

정의 1.2로 한 걸음: \(|2\mathbb{N}| = |\mathbb{N}|\)을 보인다.

정의 1.1로 또 한 걸음: 전단사 \(f : \mathbb{N} \to 2\mathbb{N}\)을 하나 제작해 제시한다.

§1.3의 표에서 본 대로 “존재하면”이 목표 쪽에 있으므로, 답안 쪽에서 실제로 하나를

만들어 내놓아야 한다. 출발점(짝수의 등식)과 도착점(제작할 함수)이 정해졌다.

1단계 — 규칙을 제작한다. 목록을 먼저 떠올린다: \(2, 4, 6, 8, \ldots\) \(n\)번째 항이 무엇인지 적으면 그것이 곧 \(f\)의 식이다.

확인 12. \(f : \mathbb{N} \to 2\mathbb{N}\)의 식을 완성해 보자: \(f(n) = \underline{\quad}\). 그리고 이 값이 실제로 \(2\mathbb{N}\)에 들어가는지 한 줄로 확인해 보자.

답

\(f(n) = 2n\). 값이 무대에 들어가는지의 확인: \(n \in \mathbb{N}\)이므로 \(2n\)은

\(2 \times (\text{자연수})\) 꼴이고, 곧 양의 짝수다. 이 한 줄이 걸음 ①의 후반부다 —

식만 적고 무대 소속을 확인하지 않으면 함수가 정의되었다고 말할 수 없다.

2단계 — 빠짐 없음을 보인다. 임의의 짝수를 잡아 그 짝을 실제로 구성한다.

확인 13. 전사 증명의 두 문장을 완성해 보자.

“임의의 \(m \in 2\mathbb{N}\)을 잡자. 짝수의 정의에 의해 \(m = 2k\)인 \(k \in \underline{\quad}\)이 존재한다. 그러면 \(f(\underline{\quad}) = \underline{\quad} = m\)이다.”

답

“임의의 \(m \in 2\mathbb{N}\)을 잡자. 짝수의 정의에 의해 \(m = 2k\)인 \(k \in \mathbb{N}\)이

존재한다. 그러면 \(f(k) = 2k = m\)이다.”

\(k\)가 자연수라는 확인이 빠지면 \(f\)의 정의역 밖의 값을 원상으로 내놓은 셈이 된다.

\(m\)이 양의 짝수이므로 \(m \ge 2\)이고 따라서 \(k = \frac m2 \ge 1\)이다.

3단계 — 겹침 없음을 보인다. C12주차 §1.3의 단사 증명 서식을 그대로 쓴다.

확인 14. 단사 증명의 두 문장을 완성해 보자.

“\(f(n_1) = f(n_2)\)라 하자. 곧 \(\underline{\quad} = \underline{\quad}\)이다. 양변을 2로 나누면 \(\underline{\quad}\)이다.”

답

“\(f(n_1) = f(n_2)\)라 하자. 곧 \(2n_1 = 2n_2\)이다. 양변을 2로 나누면 \(n_1 = n_2\)이다.”

근거 ③이다. 단사 증명의 본체는 언제나 이 한 줄의 대수 조작이며, 어려운 부분은

식이 아니라 어느 쪽을 가정하고 어느 쪽을 유도하는지의 방향이다.

4단계 — 결론을 선언한다.

확인 15. 마지막 문장을 완성해 보자.

“\(f\)는 전단사이므로 정의 1.1에 의해 \(\underline{\qquad}\)이고, 정의 1.2에 의해 \(2\mathbb{N}\)은 \(\underline{\qquad}\)이다. \(\blacksquare\)”

답

“\(f\)는 전단사이므로 정의 1.1에 의해 \(|2\mathbb{N}| = |\mathbb{N}|\)이고, 정의 1.2에

의해 \(2\mathbb{N}\)은 가산무한이다. \(\blacksquare\)”

완성본. 방금 만든 문장을 이어 붙이면 아래 왼쪽 열이 된다. 손으로 베껴 쓰면서 각 줄 옆의 “왜?”에 스스로 답해 본다.

증명의 한 줄

왜 이 줄을 쓰는가?

\(f : \mathbb{N} \to 2\mathbb{N}\)을 \(f(n) = 2n\)으로 정의한다. \(n \in \mathbb{N}\)이면 \(2n\)은 양의 짝수이므로 값이 \(2\mathbb{N}\)에 들어간다.

걸음 ① 규칙 제작. 식과 무대 소속 확인이 한 쌍이다 — 식만 적으면 함수가 정의되지 않는다.

(전사) 임의의 \(m \in 2\mathbb{N}\)을 잡자. 짝수의 정의에 의해 \(m = 2k\)인 \(k \in \mathbb{N}\)이 존재한다. 그러면 \(f(k) = 2k = m\)이다.

걸음 ② 빠짐 없음. 원상을 구성해 제시한다(C12주차 §1.3의 전사 증명 서식). \(k \in \mathbb{N}\)의 확인이 정의역 소속을 보증한다.

(단사) \(f(n_1) = f(n_2)\)라 하자. 곧 \(2n_1 = 2n_2\)이고, 양변을 2로 나누면 \(n_1 = n_2\)이다.

걸음 ③ 겹침 없음(근거 ③). 방향은 “값이 같다”에서 “입력이 같다”로 간다.

\(f\)는 전단사이므로 \(\vert 2\mathbb{N}\vert = \vert\mathbb{N}\vert\)이고, \(2\mathbb{N}\)은 가산무한이다. \(\blacksquare\)

정의 1.1과 1.2를 차례로 인용하며 마무리한다.

이 결과가 유한 직관과 어긋나는 자리. \(2\mathbb{N}\)은 \(\mathbb{N}\)의 진부분집합인데 \(\mathbb{N}\)과 같은 크기다. 유한집합에서는 이런 일이 일어나지 않는다 — 준비 운동 유형 1이 기대던 그 보증이 여기서 깨진다. 이것은 모순이 아니라 무한집합의 성질이며, 데데킨트는 “자신의 진부분집합과 같은 크기인 집합”을 무한집합의 정의로 삼았다.

예제 2.2 — \(\mathbb{Z}\)는 가산무한#

명제. \(\mathbb{Z}\)는 가산무한이다.

이번에는 설계만 함께 하고, 본문은 완성본으로 본다.

확인 16. \(\mathbb{Z}\)는 0을 기준으로 양쪽으로 뻗어 있고 \(\mathbb{N}\)은 한쪽으로만 뻗어 있다. 양쪽 무한을 한쪽으로 접으려면 목록을 어떤 순서로 만들어야 하는가. 첫 다섯 항을 적어 보자.

답

0에서 시작해 좌우를 번갈아 집는다: \(0, 1, -1, 2, -2, \ldots\)

이 순서가 필요한 이유는 걸음 ②의 셋째 줄 때문이다 — “각 원소의 등장 순번이

유한해야” 한다. \(\ldots, -2, -1, 0, 1, 2, \ldots\) 순서로는 0이 몇 번째인지 말할 수

없다. 앞쪽이 무한하면 그것은 목록이 아니다.

확인 17. 위 목록을 식으로 옮겨 보자. \(n\)이 짝수일 때와 홀수일 때로 갈라, \(f(n)\)을 각각 \(n\)의 식으로 적어 보자. (\(f(2) = 1\), \(f(4) = 2\), \(f(1) = 0\), \(f(3) = -1\)이 되도록.)

답

짝수 쪽: \(f(2) = 1\), \(f(4) = 2\), \(f(6) = 3\)이므로 \(f(n) = \dfrac n2\).

홀수 쪽: \(f(1) = 0\), \(f(3) = -1\), \(f(5) = -2\)이므로 \(f(n) = -\dfrac{n-1}2\).

두 식을 한 함수로 묶어 적는다. 경우로 갈린 식이 함수가 되려면 두 경우가 겹치지도

빠지지도 않아야 하는데, 모든 자연수는 짝수이거나 홀수이고 둘 다일 수는 없으므로

(1권 17주차) 그 조건이 충족된다.

증명. \(f : \mathbb{N} \to \mathbb{Z}\)를 다음과 같이 정의한다.

\[\begin{split} \begin{aligned}f(n) = \begin{cases} \dfrac n2 & (n \text{ 이 짝수}) \\[6pt] -\dfrac{n-1}2 & (n \text{ 이 홀수}) \end{cases}\end{aligned} \end{split}\]

증명의 한 줄

왜 이 줄을 쓰는가?

모든 자연수는 짝수이거나 홀수이고 둘 다는 아니므로(1권 17주차) 각 \(n\)에 값이 정확히 하나 정해진다. \(n = 2k\)이면 \(f(n) = k \in \mathbb{Z}\)이고, \(n = 2k+1\)이면 \(f(n) = -k \in \mathbb{Z}\)이므로 값이 모두 \(\mathbb{Z}\)에 들어간다.

걸음 ①. 경우로 갈린 식은 정확히 하나의 값이 정해지는지부터 확인해야 함수가 된다(C12주차 정의 1.1).

목록으로 펼치면 \(f(1) = 0\), \(f(2) = 1\), \(f(3) = -1\), \(f(4) = 2\), \(f(5) = -2\)이다.

식이 의도한 순서를 실제로 낳는지 대조하는 자리. 검산은 증명이 아니지만 식을 잘못 적었을 때 그 자리를 드러낸다.

(전사) 임의의 \(m \in \mathbb{Z}\)을 잡자. \(m \ge 1\)이면 \(2m \in \mathbb{N}\)이고 짝수이므로 \(f(2m) = m\)이다. \(m \le 0\)이면 \(-2m + 1 \in \mathbb{N}\)이고 홀수이므로 \(f(-2m+1) = -\frac{(-2m+1)-1}{2} = m\)이다.

걸음 ②. 정수는 양\(\cdot\)0\(\cdot\)음의 세 갈래인데 목록이 두 갈래이므로, 원상 구성도 두 갈래로 나눈다. \(m = 0\)은 아래쪽에서 \(f(1) = 0\)으로 덮인다.

(단사) \(f(n_1) = f(n_2)\)라 하자. 짝수 입력의 값은 \(\frac n2 \ge 1\)이라 양의 정수이고 홀수 입력의 값은 \(-\frac{n-1}2 \le 0\)이라 0 이하이므로, 두 값이 같으려면 \(n_1\)과 \(n_2\)의 홀짝이 같아야 한다. 둘 다 짝수이면 \(\frac{n_1}2 = \frac{n_2}2\)에서 \(n_1 = n_2\)이고, 둘 다 홀수이면 \(-\frac{n_1-1}2 = -\frac{n_2-1}2\)에서 역시 \(n_1 = n_2\)이다.

걸음 ③. 경우로 갈린 함수의 단사 증명은 갈래 사이와 갈래 안을 모두 봐야 한다. 갈래 사이를 막는 것이 값의 부호이고, 그것을 적지 않으면 증명에 구멍이 남는다.

\(f\)는 전단사이므로 \(\vert\mathbb{Z}\vert = \vert\mathbb{N}\vert\)이고, \(\mathbb{Z}\)는 가산무한이다. \(\blacksquare\)

정의 1.1과 1.2로 마무리.

\(\mathbb{Z}\)는 \(\mathbb{N}\)을 두 벌 붙여 놓은 것처럼 보이지만 크기가 같다. 예제 2.1이 “절반이 전체와 같다”였다면 이번 것은 “두 배가 전체와 같다”이고, 둘은 같은 현상의 양면이다.

예제 2.3 — \((0,1)\)은 비가산#

명제. 구간 \((0,1)\)은 비가산이다.

이번에는 설계부터 스스로 해 보자.

확인 18. 목표 “비가산”을 정의 1.3으로 번역해 보자. 그러면 무엇을 보여야 하는가. 그리고 그 목표에는 예제 2.1\(\cdot\)2.2와 결정적으로 다른 점이 하나 있다 — 무엇인가.

답

두 가지를 보여야 한다: ① \((0,1)\)이 유한하지 않다 ② \(\mathbb{N}\)에서 \((0,1)\)로 가는

전단사가 존재하지 않는다.

결정적으로 다른 점: 예제 2.1\(\cdot\)2.2의 목표는 함수 하나를 제시하는 것이었으나,

여기서는 모든 함수를 배제해야 한다. 하나씩 제시하는 방식으로는 끝나지 않는

작업이므로, 하나가 있다고 가정해 놓고 그 하나를 재료로 삼아 무너뜨린다 —

§1.6의 걸음 ②가 그 거래다.

증명. ① 먼저 \((0,1)\)은 유한하지 않다. \(\frac12, \frac13, \frac14, \ldots\)은 모두 \((0,1)\)의 원소이고 서로 다르므로, 어떤 자연수 \(n\)에 대해서도 \((0,1)\)이 \(n\)개의 원소를 가질 수 없다.

② \((0,1)\)이 가산이라 가정하자. ①에 의해 유한이 아니므로 가산무한이고, 따라서 전단사 \(g : \mathbb{N} \to (0,1)\)이 존재한다. \(x_k = g(k)\)로 두면 \(g\)가 전사이므로 목록 \(x_1, x_2, x_3, \ldots\)에 \((0,1)\)의 모든 원소가 등장한다.

③ 각 \(x_k\)의 십진 전개를 하나 고정한다(두 표기를 갖는 수는 0이 이어지는 쪽으로 정한다).

\[ x_k = 0.d_{k1} d_{k2} d_{k3} \cdots \qquad (d_{kj} \in \{0, 1, \ldots, 9\}) \]

④ 대각선 \(d_{11}, d_{22}, d_{33}, \ldots\)을 비틀어 새 수 \(y = 0.e_1 e_2 e_3 \cdots\)을 제작한다.

\[\begin{split} \begin{aligned}e_k = \begin{cases} 5 & (d_{kk} \ne 5) \\ 6 & (d_{kk} = 5) \end{cases}\end{aligned} \end{split}\]

⑤ 두 가지를 검증한다.

자격. 모든 \(k\)에 대해 \(e_k \in \{5, 6\}\)이므로 \(0.555\cdots \le y \le 0.666\cdots\)이고 특히 \(0 < y < 1\)이다. 곧 \(y \in (0,1)\)이다. 또한 \(y\)의 전개에는 9만 이어지는 꼬리도 0만 이어지는 꼬리도 없으므로 \(y\)의 십진 표기는 유일하다.

탈출. 임의의 \(k\)를 잡자. \(y\)의 \(k\)번째 자리는 \(e_k\)이고 \(x_k\)의 \(k\)번째 자리는 \(d_{kk}\)인데, 제작 규칙에 의해 \(e_k \ne d_{kk}\)이다. \(y\)의 십진 표기가 유일하므로 \(y\)가 \(x_k\)와 같다면 \(y\)의 그 유일한 표기가 \(x_k\)의 표기 중 하나여야 하는데, \(x_k\)의 두 표기 중 ③에서 고정한 쪽은 \(k\)번째 자리에서 다르고 다른 쪽은 9 또는 0의 꼬리를 가져 \(y\)의 표기일 수 없다. 따라서 \(y \ne x_k\)이다. \(k\)는 임의였으므로 \(y\)는 목록의 어느 항과도 다르다.

⑥ 그러면 \(y \in (0,1)\)인데 \(y\)가 목록에 없으므로 \(g\)는 전사가 아니다. 이것은 ②의 가정과 모순이다. 따라서 그러한 전단사는 존재하지 않고, ①과 합하여 \((0,1)\)은 비가산이다. \(\blacksquare\)

이어서 \(\mathbb{R}\)도 비가산이다. \((0,1) \subseteq \mathbb{R}\)이고 \((0,1)\)이 비가산이므로 §1.7의 (P4)에 의해 \(\mathbb{R}\)이 비가산이다.

이 증명은 표 없이 산문으로 적었다. 표는 연습 단계의 장치이고, 실전의 증명은 처음부터 끝까지 이런 산문이다. 이번 주의 목표는 이 산문을 백지에서 재현하는 것이다.

관찰 — 세 예제의 같은 뼈대#

예제 2.1과 2.2는 가산을, 2.3은 비가산을 보였으므로 결론이 반대다. 그럼에도 밟은 순서는 같다. 대응표의 빈칸을 채워 보자.

걸음

예제 2.1

예제 2.2

예제 2.3

무대와 목표

\(2\mathbb{N}\), 전단사 제시

\(\mathbb{Z}\), 전단사 제시

\((0,1)\), 전단사 배제

제작물

\(f(n) = 2n\)

경우로 갈린 \(f\)

\(\underline{\quad(1)\quad}\)

검증 1

전사 — 원상 \(k\) 구성

전사 — 두 갈래로 구성

자격 — \(\underline{\quad(2)\quad}\)

검증 2

단사 — \(2n_1 = 2n_2\)

단사 — 부호로 갈래 분리

탈출 — \(\underline{\quad(3)\quad}\)

마무리

정의 1.1\(\cdot\)1.2 인용

정의 1.1\(\cdot\)1.2 인용

\(\underline{\quad(4)\quad}\)

확인 19. 표의 (1)~(4)를 채워 보자.

답

(1) 대각선을 비튼 수 \(y = 0.e_1e_2e_3\cdots\).

(2) \(y \in (0,1)\)이고 \(y\)의 십진 표기가 유일하다.

(3) 모든 \(k\)에 대해 \(y \ne x_k\).

(4) \(y\)가 목록에 없으므로 전사 가정과 모순 — 정의 1.3 인용.

확인 20. 세 예제가 공통으로 한 일을 한 문장으로 적어 보자. 그리고 가산 쪽과 비가산 쪽이 갈라지는 자리는 어디인가.

답

공통으로 한 일: 대상을 하나 제작하고 그것에 두 가지 검증을 붙였다.

갈라지는 자리: 제작물이 무엇이냐다. 가산 쪽에서는 목록을 만드는 함수를

제작하고 그 함수가 전사\(\cdot\)단사임을 검증한다. 비가산 쪽에서는 상대가 내놓은 목록을

재료로 원소 하나를 제작하고 그것이 무대 안에 있으면서 목록 밖에 있음을

검증한다. 검증이 둘이라는 것과 제작이 먼저라는 것은 양쪽이 같다.

방금 확인한 뼈대에 이름을 붙인다.

백지 암기 대상

크기 판정 답안의 서식

① 목표 번역 — “가산” 또는 “비가산”을 정의 1.1~1.3으로 풀어, 무엇을 제작하고 무엇을 배제할지 한 문장으로 적는다.

② 제작 — 가산이면 함수 \(f : \mathbb{N} \to A\)를, 비가산이면 목록을 가정한 뒤 탈출자 \(y\)를 명시한다.

③ 검증 1 — 가산이면 전사(빠짐 없음), 비가산이면 자격(\(y\)가 무대 안).

④ 검증 2 — 가산이면 단사(겹침 없음), 비가산이면 탈출(\(y\)가 목록 밖).

⑤ 마무리 — 인용한 정의의 번호를 대며 결론을 선언한다. 비가산 쪽은 모순을 명시하고 가정을 철회한다.

빈칸 사다리 — 지지대를 하나씩 빼며#

예제의 필사에서 자립으로 넘어가는 다리다. 훈련이 진행될수록 빈칸이 커진다. 베끼지 말고 빈칸만 스스로 채운다. 답은 §6에 있다 — 다 채운 뒤에 대조한다.

훈련 1 ●○○ — 수식과 절차의 빈칸#

명제. 음의 정수 전체의 집합 \(\mathbb{Z}^- = \{-1, -2, -3, \ldots\}\)은 가산무한이다.

증명. \(f : \mathbb{N} \to \mathbb{Z}^-\)를 \(f(n) = \underline{\quad(1)\quad}\)로 정의한다 (목록: \(-1, -2, -3, \ldots\)). \(n \in \mathbb{N}\)이면 이 값은 음의 정수이므로 무대에 들어간다.

(전사) 임의의 \(-m \in \mathbb{Z}^-\)을 잡자 (여기서 \(m \in \mathbb{N}\)이다). 그러면 \(f(\underline{\quad(2)\quad}) = -m\)이다.

(단사) \(f(n_1) = f(n_2)\)라 하자. 곧 \(-n_1 = -n_2\)이고, 양변에 \(-1\)을 곱하면 \(\underline{\quad(3)\quad}\)이다.

\(f\)는 전단사이므로 \(|\mathbb{Z}^-| = |\mathbb{N}|\)이고, \(\mathbb{Z}^-\)은 \(\underline{\quad(4)\quad}\)이다. \(\blacksquare\)

검산. \(f(1) = -1\), \(f(2) = \underline{\quad(5)\quad}\), \(f(3) = -3\).

훈련 2 ●●○ — 수식과 근거를 함께#

이번에는 구조 낱말과 근거 문장도 빈칸이다.

명제. 양의 홀수 전체의 집합 \(O = \{1, 3, 5, \ldots\}\)은 가산무한이다.

증명. \(f : \mathbb{N} \to O\)를 \(f(n) = \underline{\quad(1)\quad}\)로 정의한다 (목록: \(1, 3, 5, 7, \ldots\)). \(n \in \mathbb{N}\)이면 \(n \ge 1\)이므로 이 값은 1 이상이고, \(\underline{\quad(2)\quad}\)의 정의 꼴을 만족하므로 \(O\)에 들어간다.

(전사) 임의의 \(m \in O\)을 잡자. 홀수의 정의에 의해 \(m = 2k + 1\)인 정수 \(k\)가 존재하고, \(m \ge 1\)이므로 \(k \ge 0\), 곧 \(k + 1 \in \mathbb{N}\)이다. 그러면

\[ f(k+1) = 2(k+1) - 1 = \underline{\quad(3)\quad} = m \]

이다.

(단사) \(f(n_1) = f(n_2)\)라 하자. 곧 \(2n_1 - 1 = 2n_2 - 1\)이고, \(\underline{\quad(4)\quad}\)이므로 \(n_1 = n_2\)이다.

\(f\)는 \(\underline{\quad(5)\quad}\)이므로 정의 1.1에 의해 \(|O| = |\mathbb{N}|\)이고, 정의 1.2에 의해 \(O\)는 가산무한이다. \(\blacksquare\)

복기. 예제 2.1과 이 훈련을 합치면 \(2\mathbb{N}\)도 \(O\)도 각각 \(\mathbb{N}\)과 같은 크기다. 그런데 두 집합은 서로소이고 합집합이 \(\mathbb{N}\)이다. 곧 \(\mathbb{N}\)을 두 조각으로 쪼갰는데 각 조각이 \(\underline{\quad(6)\quad}\) — 유한에서는 불가능한 일이다.

훈련 3 ●●● — 뼈대만 남기고#

이번에는 §2 관찰의 서식 다섯 칸을 통째로 채운다.

명제. 십진 전개의 모든 자리가 5 또는 6인 \((0,1)\)의 원소 전체의 집합 \(D = \{0.c_1c_2c_3\cdots : \text{모든 } j \text{ 에 대해 } c_j \in \{5, 6\}\}\)은 비가산이다.

답안의 뼈대.

  • ① 목표 번역: \(\underline{\quad(1)\quad}\)

  • ② 제작: \(\underline{\quad(2)\quad}\)

  • ③ 검증 1 (자격): \(\underline{\quad(3)\quad}\)

  • ④ 검증 2 (탈출): \(\underline{\quad(4)\quad}\)

  • ⑤ 마무리: \(\underline{\quad(5)\quad}\)

(안내: 이번에는 비트는 규칙을 예제 2.3에서 그대로 가져올 수 없다. 제작한 \(y\)가 \((0,1)\)에 있기만 해서는 부족하고 \(D\) 안에 있어야 하기 때문이다. 자릿수 선택지가 5와 6 두 개뿐일 때 대각선을 비트는 규칙은 어떻게 되는가. 그리고 이 명제가 참이면 “비가산집합의 부분집합도 비가산일 수 있다”는 문제 12의 관찰이 한 사례를 더 얻는다.)

연습문제 (20문항)#

해설을 보기 전에 문제당 최소 10분 스스로 시도한다. 막히면 곧바로 풀이를 읽지 말고, 해설의 ‘접근’까지만 읽고 다시 시도한다 \(\to\) 그래도 안 되면 풀이를 읽는다.

가산 증명은 전단사(나열)를 실제로 제작하고, 비가산 증명은 대각선과 귀류를 명시한다.

이번 주의 채점 기준

답이 아니라 근거가 점수다. 크기 판정 답안에는 채점 항목이 넷이다.

① 제작물이 답안에 명시되어 있는가. “나열할 수 있다”는 제작이 아니라 주장이다.

② 가산 주장에 두 검증(전사\(\cdot\)단사)이 모두 붙어 있는가. 한쪽만 있으면 반쪽이다.

③ 비가산 주장에 자격 검증이 붙어 있는가. 탈출만 보이고 무대 소속을 빠뜨리는 답안이 가장 흔하다.

④ 인용한 부품의 출처를 댔는가. “가산끼리 합치면 가산이니까”는 출처 없이 쓰면 근거가 아니다.

난이도와 무관하게, 힌트 상자는 5분 이상 막힌 뒤에만 연다.

기본 ●○○#

1. [백지] 같은 크기의 정의, 가산무한\(\cdot\)가산\(\cdot\)비가산 구분, 대각선 논법의 골격을 쓰시오.

힌트

정의는 문장을 통째로 외우기보다 §1.3의 조각 표와 함께 외운다 — 조각을 지우면

무엇이 무너지는지를 알아 두면 잊은 조각을 복구할 수 있다. 대각선 논법은

§1.6의 다섯 걸음이고, 걸음마다 “빼면 무엇이 무너지는가”가 한 쌍으로 붙어 있다.

2. 다음이 가산인지 비가산인지 답하시오 (이유 간단히). (a) \(\mathbb{N}\) (b) 홀수 집합 (c) \(\mathbb{Q}\) (d) \(\mathbb{R}\) (e) 무리수 집합

힌트

다섯 칸 중 셋은 이미 만든 것을 인용하면 끝난다. (a)는 정의 1.2에 넣을 함수가

가장 단순한 것이고, (b)는 §3 훈련 2, (d)는 예제 2.3이다. (c)와 (e)는 이번 주의

문제로 미뤄져 있으므로 그 번호를 대며 답한다.

3. 예제 2.1(짝수 가산)을 백지 재현하시오.

힌트

§2 관찰의 서식 다섯 칸을 먼저 적고, 각 칸에 예제 2.1의 문장을 채워 넣는다.

자주 빠지는 것은 걸음 ①의 후반부 — \(2n\)이 실제로 \(2\mathbb{N}\)에 들어간다는 확인이다.

4. 빈칸 사다리 훈련 1을 백지에서 완성하시오.

힌트

목록 \(-1, -2, -3, \ldots\)의 \(n\)번째 항을 적으면 그것이 곧 \(f\)의 식이다.

전사 증명에서 임의의 원소를 “\(-m\)”이라 적어 두면 원상이 바로 보인다.

5. 예제 2.3(대각선)을 백지 재현하시오 — \(y \neq x_k\) 논증 포함.

힌트

다섯 걸음 중 가장 자주 빠지는 것은 ①(유한 배제)과 ⑤의 자격 검증이다.

그리고 \(y \ne x_k\)를 “자리가 다르니까”로 한 줄에 끝내면 안 된다 — 십진 표기가

두 개인 수의 가능성을 어떻게 닫았는지가 그 논증의 본체다(§1.6 확인 8).

6. “\(\mathbb{N}\)과 \(\{5, 6, 7, \ldots\}\)이 같은 크기”임을 전단사로 보이시오 (\(f(n) = n + 4\)).

힌트

목표는 정의 1.1이 요구하는 것 하나 — 전단사의 제시다. 전사 증명에서 임의의

\(m \ge 5\)를 잡았을 때 원상 후보 \(m - 4\)가 자연수인지 확인하는 줄을 빠뜨리지 않는다.

표준 ●●○#

7. \(3\mathbb{Z} = \{\ldots, -3, 0, 3, 6, \ldots\}\)(3의 배수)가 가산무한임을 증명하시오 (\(\mathbb{Z}\)와 전단사 \(f(n) = 3n\)).

힌트

문제가 지정한 \(f\)의 정의역은 \(\mathbb{Z}\)이지 \(\mathbb{N}\)이 아니다. 그러면 정의 1.2가

요구하는 “\(\mathbb{N}\)과의 전단사”에 곧바로 닿지 않는다. 예제 2.2가 만든 것을

어디에 이어 붙이면 되는가.

8. 두 가산무한 집합 \(A, B\)가 서로소이면 \(A \cup B\)가 가산무한임을 증명하시오 (지그재그 나열 — \(a_1, b_1, a_2, b_2, \ldots\)).

힌트

지그재그 나열을 식으로 옮기면 홀수 번째와 짝수 번째로 갈린 함수가 된다.

단사 증명에서 갈래 사이를 막아 주는 것이 무엇인지 찾는다 — 예제 2.2에서는

값의 부호였고, 여기서는 가정 중 아직 쓰지 않은 것 하나가 그 일을 한다.

9. \(\mathbb{N} \times \mathbb{N}\)이 가산무한임을 증명하시오 (대각선 나열 — \((1,1), (1,2), (2,1), (1,3), (2,2), (3,1), \ldots\); 또는 \(f(m,n) = 2^{m-1}(2n-1)\) 전단사).

힌트

대각선 나열 쪽을 고르면 “\((m,n)\)이 몇 번째인가”를 식으로 적어야 검증이 가능해진다.

\(m + n = c\)인 대각선 앞에 놓인 대각선들의 항수를 더하면 그 식이 나온다.

식 쪽을 고르면 모든 자연수가 \(2^a \times (\text{홀수})\) 꼴로 유일하게 적힌다는

사실이 전사와 단사를 동시에 준다.

10. 다음 제시된 증명을 평가하시오 (C5주차 §1.6의 증명 평가 다섯 걸음으로).

Result. \(\mathbb{R}\)은 가산이다.

제시된 증명. \(\mathbb{R}\)의 원소를 \(r_1, r_2, r_3, \ldots\)로 나열할 수 있다. 각 실수는 유일한 십진 전개를 가지므로. 따라서 가산.

힌트

C5주차 §1.6의 다섯 걸음을 순서대로 돌린다. 걸음 ①에서 이미 결론이 나오지만,

그것만 적고 끝내면 이 답안이 어디서 무너졌는지는 밝히지 못한다.

첫 문장이 증명하려는 것과 어떤 관계인지 §1.5의 표에서 확인한다.

11. \(\mathbb{Q}^+\)이 가산임을 대각선 나열(분수 격자)로 설명하시오 (기약분수만 세는 이유 포함 — 중복 제거).

힌트

격자의 점 \((p, q)\)에 분수 \(\frac pq\)를 대응시키면 문제 9가 이미 격자를 세어 놓았다.

남은 일은 그 순서를 그대로 쓰되 어떤 점을 건너뛸지 정하는 것이고, 건너뛰지

않으면 §1.5 확인 6의 겹침이 그대로 살아난다.

12. 비가산 집합의 부분집합이 가산일 수도 비가산일 수도 있음을 예로 보이시오 (\(\mathbb{R}\)의 부분집합: \(\mathbb{N}\)(가산), \((0,1)\)(비가산)).

힌트

두 예를 제시하는 것으로 끝나지만, 각 예마다 “이것이 \(\mathbb{R}\)의 부분집합이다”와

“이것이 가산이다(비가산이다)”를 각각 출처를 대며 적는다. 그리고 반대쪽 —

가산집합의 부분집합 — 에서는 왜 이런 갈림이 없는지 §1.7에서 확인해 덧붙인다.

13. \((0, 1)\)과 \(\mathbb{R}\)이 같은 크기임을 전단사로 보이시오 (\(f(x) = \tan(\pi(x - \frac12))\) 또는 \(f(x) = \frac{2x - 1}{x(1-x)}\) 등 — 구간을 실직선으로 펴는 함수).

힌트

탄젠트 쪽을 고르면 먼저 정의역이 맞는지 확인한다 — \(x \in (0,1)\)일 때

\(\pi(x - \frac12)\)가 어느 구간에 들어가는가. 전사 증명은 역함수를 실제로

구성하는 일이고, 그 역함수는 아크탄젠트로 적힌다.

14. 대각선 응용: “\(\mathbb{N}\)의 모든 부분집합의 집합 \(\mathcal{P}(\mathbb{N})\)은 비가산”임을 대각선으로 증명하시오 (칸토어 정리 — \(\mathbb{N} \to \mathcal{P}(\mathbb{N})\) 전사 없음; 1권 49주차). \(|\mathcal{P}(\mathbb{N})| > |\mathbb{N}|\).

이 문제가 처음 요구하는 것 — 전단사 대신 전사를 배제한다

지금까지의 비가산 증명은 전단사를 가정해 무너뜨렸다. 문제 14와 15는 더 약한

가정 — 전사만 있다 — 을 놓고 시작한다. 전단사는 전사이기도 하므로, 전사가

없으면 전단사도 없다. 곧 더 약한 가정에서 모순을 얻으면 더 강한 결론이 나온다.

표기도 확인해 둔다: \(\mathcal{P}(A)\)는 \(A\)의 부분집합 전체의 집합이고 “에이의

멱집합”이라 읽는다(1권 4주차 §1.7, C2주차). 원소가 집합이라는 점 때문에

\(n \in f(n)\) 같은 식이 뜻을 갖는다 — 대각선이 놓일 자리가 바로 여기다.

힌트

목록을 표로 펼치면 \(k\)행 \(j\)열 칸에 “\(j \in f(k)\)인가”를 적게 된다. 그 표의

대각선 칸은 “\(k \in f(k)\)인가”이고, 그것을 전부 뒤집은 행이 곧 제작할 집합이다.

도전 ●●●#

15. (칸토어 정리 일반) 임의의 집합 \(A\)에 대해 \(|A| < |\mathcal{P}(A)|\)임을 증명하시오 (전단사 없음 — \(A \to \mathcal{P}(A)\) 전사 \(f\)가 있다면 \(D = \{a \in A : a \notin f(a)\}\)이 상에 없음, 대각선의 추상판). \(|\mathbb{N}| < |\mathcal{P}(\mathbb{N})| < |\mathcal{P}(\mathcal{P}(\mathbb{N}))| < \cdots\).

힌트

“\(<\)”는 두 주장으로 쪼개진다: 단사가 있다는 것과 전단사가 없다는 것.

앞쪽은 한 줄로 끝나는 함수 하나면 되고, 뒤쪽이 문제 14의 논증을 \(\mathbb{N}\) 대신

임의의 \(A\)에 대해 그대로 옮긴 것이다. \(A = \emptyset\)에서도 성립하는지 검산한다.

16. (가산 합집합) 가산 개의 가산집합의 합집합이 가산임을 증명하시오 (각 집합을 행으로, 대각선 나열 — \(\mathbb{Q}\) 가산의 일반화). 선택공리가 필요함을 언급.

이 문제가 빌려 쓰는 사실 — 전사만으로 가산을 얻는다

지금까지의 가산 증명은 전단사를 만들었다. 이 문제에서는 겹침을 피하기 어려우므로

다음 사실을 인정하고 쓴다: **공집합이 아닌 \(S\)에 대해 전사 \(h : \mathbb{N} \to S\)가

있으면 \(S\)는 가산이다.** 이유는 한 줄이다 — 목록 \(h(1), h(2), \ldots\)에서 앞에 이미

나온 값과 같은 항을 건너뛰면 겹침이 사라지고, 건너뛰어도 빠짐은 생기지 않는다.

(엄밀화에는 각 항의 순번을 재배정하는 귀납이 필요하며, 그 수준의 논증은 이번 주에

인정하고 쓴다.)

힌트

집합들을 \(A_1, A_2, \ldots\)로 두고 각 \(A_i\)의 목록을 \(i\)행에 늘어놓으면 격자가

생긴다. 그러면 문제 9가 이미 격자를 세어 놓았으므로 남은 일은 두 함수를 잇는

것뿐이다. 선택공리가 필요한 자리는 계산이 아니라 “각 \(A_i\)의 목록을 하나씩 고른다”는

문장 자체다.

17. (무리수 비가산) 무리수 집합이 비가산임을 증명하시오 (귀류: 무리수가 가산이면 \(\mathbb{R} = \mathbb{Q} \cup\) 무리수가 가산+가산=가산 — \(\mathbb{R}\) 비가산과 모순).

힌트

귀류 가정 “무리수가 가산이다”는 정의 1.2에 의해 두 갈래(유한 또는 가산무한)로

갈린다. 문제 8은 가산무한 쪽만 다루므로, 유한 쪽도 한 줄로 처리해 두어야

경우가 빠지지 않는다.

18. (진단 종합) 다음 제시된 증명을 평가하시오.

Result. \((0,1)\)은 가산이다.

제시된 증명. \(0.1, 0.2, \ldots, 0.9, 0.01, 0.02, \ldots\)로 나열하면 모든 \((0,1)\)의 소수가 나온다. 따라서 가산.

힌트

문제 10과 달리 이 답안에는 제작물이 실제로 있다. 그러므로 걸음 ①만으로 끝내지

말고, 이 목록이 정확히 어떤 집합을 세는지 밝힌 뒤 그 집합과 \((0,1)\)의 차이를

구체적인 원소 하나로 지목한다. §1.5의 어느 걸음이 통째로 빠졌는지도 적는다.

19. (설계) \([0,1]\)과 \((0,1)\)이 같은 크기임을 증명하시오 (끝점 \(0, 1\)을 처리하는 전단사 — 힐베르트 호텔식 이동: \(0 \mapsto \frac12, 1 \mapsto \frac13, \frac1n \mapsto \frac1{n+2}\), 나머지 고정).

힌트

갈래가 셋인 함수이므로 단사 검증도 세 갈래 사이와 각 갈래 안을 모두 봐야 한다.

갈래 사이를 막아 주는 것은 각 갈래의 상이 서로 겹치지 않는다는 사실이고,

그것을 확인하려면 세 상을 각각 집합으로 적어 보면 된다.

20. (서술) (a) “부분이 전체와 같은 크기”(예제 2.1)가 왜 무한의 본질인지 세 문장 이내로. (b) 대각선 논법이 “어떤 나열도 빠뜨림을 만든다”로 비가산을 증명하는 구조를 예제 2.3으로 두 문장 이내 설명하시오.

힌트

(a)는 준비 운동 유형 1이 기대던 보증이 어디서 나왔고 무한에서 왜 사라지는지를

적으면 된다. (b)는 §1.2 확인 2의 비대칭이 논증의 형태를 어떻게 정했는지가

요점이다 — 하나를 제시하는 일과 전부를 배제하는 일의 차이.

백지 재현 — 복습 프로토콜#

이 과정의 한 주는 다섯 날로 나뉜다. 교안만 보는 주가 아니라 원서와 교안을 번갈아 읽는 주이므로, 백지 재현은 마지막 날에 놓인다.

요일

할 일

1일차

원서 Chartrand 11.1~11.3 통독 — 모르는 문장은 표시만 하고 통과한다

2일차

교안 §0~§2 — 개념과 예제. 확인 상자를 연필로 먼저 채운다

3일차

원서 11.1~11.3 재독 — 1일차에 표시한 문장을 해결하고, 원서 연습문제 몇 개를 직접 시도한다

4일차

교안 §3 빈칸 사다리와 §4 연습문제 20문항

5일차

백지 재현 1차(틀 카드)\(\cdot\)2차(완전 백지) + 체크리스트

1차 시도 — 틀 카드 허용. 가산 증명의 3단 서식(§1.5), 대각선 논법의 5단 서식(§1.6), 크기 판정 답안의 서식(§2 관찰)만 한 장에 적어 펴 놓고, 예제 2.2를 처음부터 끝까지 적는다. 정의와 본문은 보지 않는다.

2차 시도 — 완전 백지. 아무것도 보지 않고 수행한다.

  • 정의 1.1\(\cdot\)1.2\(\cdot\)1.3을 조각 그대로 썼다 (“전단사가 존재한다”, “유한하지도 않고”까지).

  • 가산 증명의 3단 서식을 쓰고, 걸음마다 그것을 빼면 무엇이 무너지는지 한 줄씩 적었다.

  • 대각선 논법의 5단 서식을 쓰고, 자릿수를 5와 6으로 제한하는 이유를 두 가지 다 적었다.

  • 예제 2.1을 재현했고, “진부분집합이 전체와 같은 크기”가 왜 모순이 아닌지 말했다.

  • 예제 2.2를 재현했고, 단사 증명에서 갈래 사이를 막는 줄을 손가락으로 짚었다.

  • 예제 2.3을 재현했고, \(y \ne x_k\) 논증에서 십진 표기의 유일성을 쓴 자리를 짚었다.

  • §1.7의 (P1)~(P4)를 진술하고, 각각의 증명 위치를 댔다.

  • 원서 11.1~11.3을 두 번 읽었고, 1일차에 표시한 문장이 모두 해결되었다.

막힌 지점별 처방. 막힌 지점이 무엇을 다시 볼지 알려 준다.

막힌 지점

처방

무엇을 만들어야 할지 몰라 첫 줄이 나오지 않는다

§2 관찰의 서식 걸음 ① — “가산”과 “비가산”을 정의로 두 걸음 번역하면 제작물이 정해진다

전단사를 만들었는데 검증에서 막힌다

§1.5의 3단 서식 — 전사는 원상 구성, 단사는 값이 같다는 가정에서 출발한다

경우로 갈린 함수의 단사 증명이 반쪽이 된다

예제 2.2의 넷째 줄 — 갈래 사이를 막는 근거를 먼저 찾는다

대각선 논법에서 모순이 어디서 나오는지 흐려진다

§1.6의 걸음 ⑤ — 모순은 “\(y\)가 목록에 없다”와 “목록이 전부다”의 충돌이다

대각선으로 만든 수가 무대 안에 있는지 확인하지 않는다

§1.6의 걸음 삭제 실험과 확인 8 — 자격 검증은 자릿수 제한에서 함께 나온다

비가산인데 가산 서식으로 쓰려다 막힌다

§1.2 확인 2 — 하나를 제시하는 일과 전부를 배제하는 일은 방향이 반대다

부품을 어디까지 인용해도 되는지 모르겠다

§1.7의 (P1)~(P4)와 §1.8의 근거 목록 — 출처를 대면 인용, 못 대면 증명

하나라도 실패하면 그 항목만 다시 필사하고 다음날 재시도한다.

해설#

각 해설은 접근(문제 앞에서 무엇을 생각하는가)과 풀이로 나뉜다. 막혔을 때는 접근까지만 읽고 연필을 다시 잡는다.

빈칸 사다리 — 훈련 1#

(1) \(-n\) (2) \(m\) (3) \(n_1 = n_2\) (4) 가산무한 (5) \(-2\)

※ 이 훈련의 관절은 (2)다. 전사 증명에서 임의의 원소를 어떻게 적어 두느냐가 원상을 찾는 난이도를 정한다. 음의 정수를 그냥 “\(x\)”라 적으면 원상 후보가 \(-x\)인지 확인하는 데 한 걸음이 더 들지만, “\(-m\) (단 \(m \in \mathbb{N}\))”이라 적어 두면 \(f(m) = -m\)이 곧바로 보인다. 임의의 원소를 가정이 주는 꼴 그대로 적는 것은 1권 이래의 습관이며, 여기서도 그대로 통한다.

빈칸 사다리 — 훈련 2#

(1) \(2n - 1\) (2) 홀수 (3) \(2k + 1\) (4) 양변에 1을 더하고 2로 나누면 (근거 ③) (5) 전단사 (6) 다시 \(\mathbb{N}\)과 같은 크기다

※ (3)에서 \(2(k+1) - 1 = 2k + 2 - 1 = 2k + 1\)이고 그것이 곧 \(m\)이다. 전사 증명의 계산은 “원상 후보를 넣었더니 목표 원소가 나온다”를 실제로 보이는 일이며, 후보를 제시하는 것만으로는 끝나지 않는다. (6)의 관찰이 이번 주에서 가장 유한 직관과 어긋나는 자리다. 유한집합을 두 조각으로 쪼개면 각 조각은 반드시 원래보다 작지만, \(\mathbb{N} = 2\mathbb{N} \cup O\)에서는 두 조각이 각각 \(\mathbb{N}\)과 같은 크기다. 이 현상을 뒤집어 읽으면 문제 8이 된다 — 같은 크기의 두 조각을 다시 붙여도 크기가 늘지 않는다.

빈칸 사다리 — 훈련 3#

(1) \(D\)가 유한하지 않고 \(\mathbb{N}\)에서 \(D\)로 가는 전단사도 존재하지 않음을 보인다 (정의 1.3). 곧 \(D\)가 가산이라 가정한 뒤 모순을 이끈다. (2) \(D\)가 가산이라 가정한다. 유한 배제: \(0.5666\cdots\), \(0.5566\cdots\), \(0.5556\cdots\) 처럼 5의 개수를 늘려 가면 서로 다른 원소를 무한히 많이 얻으므로 \(D\)는 유한하지 않다. 따라서 가산무한이고 목록 \(x_1, x_2, \ldots\)이 존재한다. \(x_k = 0.c_{k1}c_{k2}\cdots\) (\(c_{kj} \in \{5,6\}\))으로 펼치고, \(y = 0.e_1e_2\cdots\)을 다음으로 제작한다 — \(c_{kk} = 5\)이면 \(e_k = 6\), \(c_{kk} = 6\)이면 \(e_k = 5\). (3) 모든 \(e_k\)가 5 또는 6이므로 \(y \in D\)이다. 또한 \(y\)의 전개에는 9나 0의 꼬리가 없으므로 십진 표기가 유일하다. (4) 임의의 \(k\)에 대해 \(e_k \ne c_{kk}\)이고 두 수 모두 십진 표기가 유일하므로 \(y \ne x_k\)이다. 따라서 \(y\)는 목록의 어느 항과도 다르다. (5) \(y \in D\)인데 목록에 없으므로 목록이 \(D\)를 덮는다는 가정과 모순이다. 그러한 전단사는 존재하지 않으므로 정의 1.3에 의해 \(D\)는 비가산이다. \(\blacksquare\)

※ 예제 2.3에서 비트는 규칙은 “\(d_{kk} = 5\)이면 6, 아니면 5”였다. 여기서 그 규칙을 그대로 쓰면 \(d_{kk} = 6\)일 때 \(e_k = 5\)가 되어 우연히 맞지만, \(d_{kk}\)가 5도 6도 아닐 가능성을 열어 둔 규칙이라 \(D\) 안이라는 자격의 근거가 흐려진다. 자릿수가 두 개뿐인 무대에서는 맞바꾸기(\(5 \leftrightarrow 6\))가 정확한 규칙이다. 그리고 이 결과는 \(D \subseteq (0,1)\)이면서 \(D\)가 비가산임을 말하므로, 문제 12의 “비가산의 부분집합은 가산일 수도 비가산일 수도 있다”에 사례를 하나 더한다.

문제 1#

접근. 암기 항목을 문장으로만 외우면 일부를 잊었을 때 복구할 길이 없다. 정의는 §1.3의 조각 표와 함께 외우고, 논법은 §1.6의 걸음마다 붙은 “빼면 무엇이 무너지는가”와 함께 외운다. 그러면 남은 조각에서 잊은 조각을 재구성할 수 있다.

풀이. 같은 크기. 집합 \(A\), \(B\)에 대해 전단사 \(f : A \to B\)가 존재하면 \(A\)와 \(B\)는 같은 크기라 하고 \(|A| = |B|\)로 쓴다. 조각은 넷이다 — 무대 선언(유한\(\cdot\)무한을 가리지 않는다), 전단사(전사가 빠짐을, 단사가 겹침을 막는다), “존재한다”(하나만 제시하면 끝난다), 표기의 약속(개수를 세지 않는다).

가산무한\(\cdot\)가산\(\cdot\)비가산. \(|A| = |\mathbb{N}|\)인 \(A\)를 가산무한이라 한다. 유한집합 이거나 가산무한인 집합을 가산이라 한다. 가산이 아닌 집합 — 곧 유한하지도 않고 \(\mathbb{N}\)과의 전단사도 존재하지 않는 집합 — 을 비가산이라 한다. 유한집합은 비가산이 아니라 가산 쪽에 들어간다는 점에 주의한다.

대각선 논법의 골격. ① 유한 배제 — 서로 다른 원소를 무한히 많이 제시한다. ② 목록 가정 — 가산이라 가정하면 빠짐 없는 목록 \(x_1, x_2, \ldots\)이 존재한다. ③ 표로 펼치기 — 각 \(x_k\)를 자리별로 펼친다. ④ 대각선 비틀기 — \(k\)번째 자리를 \(x_k\)의 \(k\)번째 자리와 다르게 정해 \(y\)를 만든다. ⑤ 두 검증과 모순 — \(y\)가 무대 안에 있고(자격) 모든 \(x_k\)와 다름(탈출)을 보이면, \(y\)가 목록에 없어 ②와 모순이다.

복기. 세 항목이 서로를 떠받친다. 대각선 논법이 귀류의 꼴을 취하는 이유는 비가산의 정의가 “존재하지 않는다”라는 비존재 주장이기 때문이고, 비존재 주장의 상대는 “모든 함수”이므로 하나를 가정해 무너뜨리는 것 말고는 길이 없다.

문제 2#

접근. 다섯 칸 중 셋은 이미 만든 것을 인용하면 끝나고, 둘은 이번 주의 다른 문제로 미뤄져 있다. 각 칸마다 “어떤 함수 또는 어떤 정리가 근거인가”를 함께 적는다. 답만 적으면 채점 기준 ④(출처)에서 점수가 없다.

풀이. (a) 가산(가산무한). 항등함수 \(\mathrm{id} : \mathbb{N} \to \mathbb{N}\), \(\mathrm{id}(n) = n\)이 전단사이므로 \(|\mathbb{N}| = |\mathbb{N}|\)이고 정의 1.2에 의해 가산무한이다.

(b) 가산(가산무한). 양의 홀수 집합 \(O\)에 대해 \(f(n) = 2n - 1\)이 전단사임을 §3 훈련 2에서 확인했다. 모든 홀수(음수 포함)를 뜻한다면 \(2\mathbb{Z} + 1\)이고, \(g(n) = 2n + 1\)이 \(\mathbb{Z}\)에서 그 집합으로 가는 전단사이므로 예제 2.2와 합성해 역시 가산무한이다.

(c) 가산(가산무한). 문제 11이 \(\mathbb{Q}^+\)의 가산성을 주고, 같은 방식으로 \(\mathbb{Q}^-\)도 가산이며, \(\mathbb{Q} = \mathbb{Q}^- \cup \{0\} \cup \mathbb{Q}^+\)이므로 문제 8과 문제 16의 합집합 성질로 가산이다. 유한하지 않으므로 가산무한이다.

(d) 비가산. 예제 2.3이 \((0,1)\)의 비가산성을 주고, \((0,1) \subseteq \mathbb{R}\)이므로 §1.7의 (P4)에 의해 \(\mathbb{R}\)이 비가산이다.

(e) 비가산. 문제 17에서 증명한다 — \(\mathbb{Q}\)가 가산이므로, 무리수까지 가산이면 \(\mathbb{R}\)이 가산이 되어 (d)와 모순이다.

복기. 이 다섯 칸이 이번 주 전체의 지도다. (a)(b)(c)는 전부 \(\aleph_0\)이고 (d)(e)는 그보다 크다. 조밀함이 크기를 정하지 않는다는 것 — \(\mathbb{Q}\)는 수직선 어디에나 있지만 가산이고, 무리수는 비가산이다 — 이 이 표의 요점이다.

문제 3#

접근. 재현은 기억을 꺼내는 일이 아니라 서식을 돌리는 일이다. §2 관찰의 다섯 칸을 먼저 적고 각 칸을 채우면, 기억이 흐릿해도 빈칸이 무엇인지는 정확히 알 수 있다.

풀이. 명제는 “\(2\mathbb{N} = \{2,4,6,\ldots\}\)은 가산무한이다”이다.

\(f : \mathbb{N} \to 2\mathbb{N}\)을 \(f(n) = 2n\)으로 정의한다. \(n \in \mathbb{N}\)이면 \(2n\)은 \(2 \times (\text{자연수})\) 꼴이므로 양의 짝수이고, 값이 무대 \(2\mathbb{N}\)에 들어간다.

(전사) 임의의 \(m \in 2\mathbb{N}\)을 잡자. 짝수의 정의에 의해 \(m = 2k\)인 정수 \(k\)가 존재하고, \(m \ge 2\)이므로 \(k \ge 1\), 곧 \(k \in \mathbb{N}\)이다. 그러면 \(f(k) = 2k = m\)이다.

(단사) \(f(n_1) = f(n_2)\)라 하자. 곧 \(2n_1 = 2n_2\)이고, 양변을 2로 나누면 \(n_1 = n_2\)이다(근거 ③).

\(f\)는 전단사이므로 정의 1.1에 의해 \(|2\mathbb{N}| = |\mathbb{N}|\)이고, 정의 1.2에 의해 \(2\mathbb{N}\)은 가산무한이다. \(\blacksquare\)

채점 항목. ① \(f\)의 식과 무대 소속 확인이 함께 있는가 ② 전사에서 원상을 구성했고 그것이 \(\mathbb{N}\)에 있음을 확인했는가 ③ 단사가 “값이 같다”에서 출발했는가 ④ 마지막 줄에서 정의 1.1과 1.2를 각각 인용했는가.

검산. \(f(1) = 2\), \(f(2) = 4\), \(f(3) = 6\) — 목록이 \(2\mathbb{N}\)을 순서대로 훑는다.

문제 4#

접근. 훈련 1의 핵심은 목록을 식으로 옮기는 걸음이다. 목록 \(-1, -2, -3, \ldots\)의 \(n\)번째 항이 \(-n\)이므로 식이 곧바로 나온다. 나머지는 예제 2.1의 서식을 그대로 재사용한다.

풀이. (1) \(-n\) (2) \(m\) (3) \(n_1 = n_2\) (4) 가산무한 (5) \(-2\)

완성된 증명을 이어 붙이면 다음과 같다. \(f : \mathbb{N} \to \mathbb{Z}^-\)를 \(f(n) = -n\)으로 정의한다. \(n \in \mathbb{N}\)이면 \(n \ge 1\)이므로 \(-n \le -1\)이고, 곧 \(-n\)은 음의 정수라 무대에 들어간다. 전사 — 임의의 \(-m \in \mathbb{Z}^-\)(\(m \in \mathbb{N}\))에 대해 \(f(m) = -m\)이다. 단사 — \(-n_1 = -n_2\)의 양변에 \(-1\)을 곱하면 \(n_1 = n_2\)이다. 따라서 \(f\)는 전단사이고 \(\mathbb{Z}^-\)은 가산무한이다. \(\blacksquare\)

복기. 전사 증명에서 임의의 원소를 “\(-m\) (단 \(m \in \mathbb{N}\))”이라 적어 둔 것이 이 훈련의 요령이다. 임의의 원소를 무대의 정의가 주는 꼴 그대로 적어 두면 원상이 계산 없이 보인다 — 예제 2.1에서 짝수를 “\(2k\)”로 적어 둔 것과 같은 동작이다.

문제 5#

접근. 대각선 논법의 재현에서 가장 자주 빠지는 것은 걸음 ①(유한 배제)과 걸음 ⑤의 자격 검증이다. 두 걸음 모두 “당연해 보여서” 빠지지만, ①이 빠지면 유한집합도 비가산이 되고 ⑤가 빠지면 무대 밖의 대상을 반례로 내놓게 된다.

풀이. 명제는 “\((0,1)\)은 비가산이다”이다.

① \(\frac12, \frac13, \frac14, \ldots\)은 모두 \((0,1)\)의 원소이고 서로 다르므로 \((0,1)\)은 유한하지 않다.

② \((0,1)\)이 가산이라 가정하자. ①에 의해 가산무한이므로 전단사 \(g : \mathbb{N} \to (0,1)\)이 존재하고, \(x_k = g(k)\)로 두면 \(g\)의 전사성에 의해 목록 \(x_1, x_2, \ldots\)이 \((0,1)\)의 모든 원소를 덮는다.

③ 각 \(x_k\)의 십진 전개를 \(x_k = 0.d_{k1}d_{k2}d_{k3}\cdots\)으로 하나 고정한다 (두 표기를 갖는 수는 0이 이어지는 쪽으로 정한다).

④ \(y = 0.e_1e_2e_3\cdots\)을 다음으로 제작한다: \(d_{kk} \ne 5\)이면 \(e_k = 5\), \(d_{kk} = 5\)이면 \(e_k = 6\).

⑤ 자격 — 모든 자리가 5 또는 6이므로 \(0.555\cdots \le y \le 0.666\cdots\)이고 특히 \(y \in (0,1)\)이다. 또한 \(y\)의 전개에는 9의 꼬리도 0의 꼬리도 없으므로 \(y\)의 십진 표기는 유일하다. 탈출 — 임의의 \(k\)를 잡자. 제작 규칙에 의해 \(e_k \ne d_{kk}\)이다. 만약 \(y = x_k\)라면 \(y\)의 유일한 십진 표기가 \(x_k\)의 표기 중 하나여야 하는데, 고정한 쪽은 \(k\)번째 자리가 \(d_{kk} \ne e_k\)라 다르고, 나머지 한 표기가 있다면 그것은 9 또는 0의 꼬리를 가지므로 \(y\)의 표기일 수 없다. 따라서 \(y \ne x_k\)이다.

⑥ \(y \in (0,1)\)인데 어느 \(x_k\)와도 다르므로 \(y\)는 목록에 없다. 이것은 목록이 \((0,1)\)을 덮는다는 ②와 모순이다. 따라서 그러한 전단사는 존재하지 않고, ①과 합하여 \((0,1)\)은 비가산이다. \(\blacksquare\)

복기. 탈출 논증에서 “자리가 다르니까 수가 다르다”로 한 줄에 끝내면 안 되는 이유가 \(0.4999\cdots = 0.5\)다. 자릿수를 5와 6으로 제한하는 규칙이 그 함정을 막고 동시에 자격 검증까지 준다 — 규칙 하나가 두 검증을 함께 떠받친다.

문제 6#

접근. 목표는 정의 1.1이 요구하는 것 하나 — 전단사의 제시다. 함수가 이미 주어져 있으므로 남은 일은 두 검증이고, 전사 쪽에서 원상 후보가 정의역에 들어가는지 확인하는 줄이 채점의 핵심이다.

풀이. \(A = \{5, 6, 7, \ldots\}\)로 두고 \(f : \mathbb{N} \to A\)를 \(f(n) = n + 4\)로 정의한다. \(n \in \mathbb{N}\)이면 \(n \ge 1\)이므로 \(n + 4 \ge 5\)이고, 값이 \(A\)에 들어간다.

(전사) 임의의 \(m \in A\)을 잡자. 그러면 \(m \ge 5\)이므로 \(m - 4 \ge 1\)이고, \(m\)과 4가 정수이므로 \(m - 4\)도 정수다(근거 ②). 곧 \(m - 4 \in \mathbb{N}\)이다. 그러면 \(f(m-4) = (m-4) + 4 = m\)이다.

(단사) \(f(n_1) = f(n_2)\)라 하자. 곧 \(n_1 + 4 = n_2 + 4\)이고, 양변에서 4를 빼면 \(n_1 = n_2\)이다(근거 ③).

\(f\)는 전단사이므로 \(|A| = |\mathbb{N}|\)이다. \(\blacksquare\)

검산. \(f(1) = 5\), \(f(2) = 6\), \(f(3) = 7\) — 목록이 \(A\)를 순서대로 훑는다.

복기. \(A\)는 \(\mathbb{N}\)에서 원소 네 개를 뺀 집합인데 크기가 그대로다. 유한집합에서 원소 네 개를 빼면 반드시 작아지므로, 이것도 예제 2.1과 같은 종류의 어긋남이다. 힐베르트가 든 사고 실험으로 옮기면 손님이 네 명 늘어난 만실 숙소에서 \(n\)호실 손님을 전부 \(n+4\)호실로 옮기는 조작이 여기에 해당한다.

문제 7#

접근. 문제가 지정한 \(f(n) = 3n\)의 정의역은 \(\mathbb{Z}\)이므로 이 함수만으로는 \(|3\mathbb{Z}| = |\mathbb{Z}|\)까지만 나오고, 정의 1.2가 요구하는 \(\mathbb{N}\)과의 전단사에는 닿지 않는다. 빠진 다리는 예제 2.2가 이미 놓아 두었다 — 두 전단사를 합성하거나, 1권 48주차 문제 7의 추이성을 인용한다.

풀이. 먼저 \(f : \mathbb{Z} \to 3\mathbb{Z}\), \(f(n) = 3n\)이 전단사임을 보인다. \(n \in \mathbb{Z}\)이면 \(3n\)은 3의 배수이므로 값이 \(3\mathbb{Z}\)에 들어간다.

(전사) 임의의 \(x \in 3\mathbb{Z}\)을 잡자. 3의 배수의 정의에 의해 \(x = 3m\)인 정수 \(m\)이 존재하고, 그러면 \(f(m) = 3m = x\)이다.

(단사) \(f(n_1) = f(n_2)\)라 하자. 곧 \(3n_1 = 3n_2\)이고, 양변을 3으로 나누면 \(n_1 = n_2\)이다(근거 ③).

따라서 \(|3\mathbb{Z}| = |\mathbb{Z}|\)이다. 한편 예제 2.2에서 전단사 \(h : \mathbb{N} \to \mathbb{Z}\)를 만들었으므로, 합성 \(f \circ h : \mathbb{N} \to 3\mathbb{Z}\)은 전단사의 합성이라 전단사다(C12주차 §1.4의 합성 보존). 따라서 \(|3\mathbb{Z}| = |\mathbb{N}|\)이고 \(3\mathbb{Z}\)은 가산무한이다. \(\blacksquare\)

검산. 합성의 목록을 몇 항 계산해 본다. \(h(1) = 0\)이므로 \((f \circ h)(1) = 0\), \(h(2) = 1\)이므로 \((f \circ h)(2) = 3\), \(h(3) = -1\)이므로 \((f \circ h)(3) = -3\), \(h(4) = 2\)이므로 \((f \circ h)(4) = 6\). 목록 \(0, 3, -3, 6, -6, \ldots\)이 3의 배수를 빠짐없이 훑는다.

복기. “\(A\)와 \(B\)가 같은 크기이고 \(B\)와 \(C\)가 같은 크기이면 \(A\)와 \(C\)도 같은 크기”라는 추이성(1권 48주차 문제 7)이 이번 주 내내 쓰이는 부품이다. 그 증명의 본체가 바로 합성이 전단사를 보존한다는 사실이고, 그래서 위 풀이는 추이성을 인용하는 대신 합성을 직접 적어도 같은 점수다.

문제 8#

접근. 지그재그 나열 \(a_1, b_1, a_2, b_2, \ldots\)을 식으로 옮기면 홀수 번째와 짝수 번째로 갈린 함수가 된다. 예제 2.2가 이미 같은 모양을 다뤘으므로 서식을 그대로 가져오되, 갈래 사이의 겹침을 막는 근거만 바꾼다 — 거기서 “서로소”라는 가정이 쓰인다.

풀이. \(A\), \(B\)가 가산무한이므로 전단사 \(\alpha : \mathbb{N} \to A\)와 \(\beta : \mathbb{N} \to B\)가 존재한다. \(a_k = \alpha(k)\), \(b_k = \beta(k)\)로 둔다. \(g : \mathbb{N} \to A \cup B\)를 다음으로 정의한다.

\[\begin{split} \begin{aligned}g(n) = \begin{cases} a_k & (n = 2k - 1) \\ b_k & (n = 2k) \end{cases}\end{aligned} \end{split}\]

모든 자연수는 홀수이거나 짝수이고 둘 다는 아니므로(1권 17주차) 각 \(n\)에 값이 정확히 하나 정해지고, 값은 \(A\) 또는 \(B\)의 원소이므로 \(A \cup B\)에 들어간다.

(전사) 임의의 \(x \in A \cup B\)을 잡자. \(x \in A\)이면 \(\alpha\)가 전사이므로 \(x = a_k\)인 \(k \in \mathbb{N}\)이 존재하고 \(g(2k-1) = x\)이다. \(x \in B\)이면 마찬가지로 \(x = b_k\)인 \(k\)가 존재하고 \(g(2k) = x\)이다.

(단사) \(g(n_1) = g(n_2)\)라 하자. 세 경우로 나눈다. \(n_1\), \(n_2\)가 둘 다 홀수이면 \(n_1 = 2k_1 - 1\), \(n_2 = 2k_2 - 1\)에서 \(a_{k_1} = a_{k_2}\)이고, \(\alpha\)가 단사이므로 \(k_1 = k_2\), 따라서 \(n_1 = n_2\)이다. 둘 다 짝수인 경우도 \(\beta\)의 단사성으로 같은 결론이 나온다. 한쪽이 홀수이고 다른 쪽이 짝수이면 \(a_{k_1} = b_{k_2}\)인데, 좌변은 \(A\)의 원소이고 우변은 \(B\)의 원소이므로 이 값은 \(A \cap B\)에 속한다. 그런데 \(A\)와 \(B\)가 서로소라 \(A \cap B = \emptyset\)이므로 이 경우는 일어날 수 없다.

\(g\)는 전단사이므로 \(A \cup B\)는 가산무한이다. \(\blacksquare\)

복기. 서로소라는 가정이 쓰인 자리는 단 한 곳 — 단사 증명의 셋째 경우다. 가정이 어디서 소비되는지 짚어 두면 가정을 뺐을 때 무엇이 무너지는지도 보인다. 서로소가 아니면 겹치는 원소가 목록에 두 번 등장해 단사가 깨지며, 그때는 문제 16의 “겹치는 항을 건너뛰기”로 수리해 가산까지는 얻는다.

문제 9#

접근. 두 길 모두 정답이다. 대각선 나열 쪽은 그림이 직관적이지만 “\((m,n)\)이 몇 번째인가”를 식으로 적어야 검증이 가능해지고, \(f(m,n) = 2^{m-1}(2n-1)\) 쪽은 그림이 없는 대신 모든 자연수가 \(2^a \times (\text{홀수})\) 꼴로 유일하게 적힌다는 사실 하나가 전사와 단사를 동시에 준다.

풀이 1 (대각선 나열). \(m + n = c\)인 점들을 \(c\)번째 대각선이라 하자. \(c\)번째 대각선의 점은 \((1, c-1), (2, c-2), \ldots, (c-1, 1)\)의 \(c - 1\)개로 유한하다. 대각선을 \(c = 2, 3, 4, \ldots\) 순서로 훑고 각 대각선 안에서는 \(m\)이 작은 것부터 집는다. 그러면 \((m,n)\)의 순번은 앞선 대각선들의 항수 합에 대각선 안의 위치를 더한 값이다.

\[ \sigma(m, n) = \big(1 + 2 + \cdots + (m+n-2)\big) + m = \frac{(m+n-2)(m+n-1)}{2} + m \]

이 \(\sigma : \mathbb{N} \times \mathbb{N} \to \mathbb{N}\)이 전단사임을 본다. (전사) 임의의 \(N \in \mathbb{N}\)에 대해, \(\frac{(c-2)(c-1)}{2} < N \le \frac{(c-1)c}{2}\)인 \(c\)가 하나 정해진다(부분합이 증가하며 \(\mathbb{N}\)을 덮으므로). 그 \(c\)에 대해 \(m = N - \frac{(c-2)(c-1)}{2}\)로 두면 \(1 \le m \le c - 1\)이고 \(n = c - m \ge 1\)이다. 그러면 \(\sigma(m,n) = N\)이다. (단사) \(\sigma(m_1,n_1) = \sigma(m_2,n_2)\)라 하자. 순번이 같으면 같은 대각선 블록 안에 있어야 한다 — 서로 다른 대각선의 순번 구간은 겹치지 않기 때문이다. 따라서 \(m_1 + n_1 = m_2 + n_2\)이고, 그러면 식에서 \(m_1 = m_2\)이므로 \(n_1 = n_2\)이다.

검산. \(\sigma(1,1) = 0 + 1 = 1\), \(\sigma(1,2) = 1 + 1 = 2\), \(\sigma(2,1) = 1 + 2 = 3\), \(\sigma(1,3) = 3 + 1 = 4\), \(\sigma(2,2) = 3 + 2 = 5\), \(\sigma(3,1) = 3 + 3 = 6\) — 문제에 적힌 순서와 일치한다.

풀이 2 (지수 분해). \(f : \mathbb{N} \times \mathbb{N} \to \mathbb{N}\)을 \(f(m,n) = 2^{m-1}(2n-1)\)로 정의한다. \(m, n \in \mathbb{N}\)이면 \(2^{m-1} \ge 1\)이고 \(2n - 1 \ge 1\)이므로 값이 \(\mathbb{N}\)에 들어간다. (전사) 임의의 \(N \in \mathbb{N}\)을 잡자. \(N\)을 2로 나눌 수 있는 동안 계속 나누면 유한 번에 멈춘다(내림하는 자연수 열은 무한히 이어질 수 없다 — 1권 33주차의 최소원리). 멈춘 결과를 \(N = 2^a q\)(\(a \ge 0\), \(q\)는 홀수)라 하자. \(q\)가 홀수이므로 \(q = 2n - 1\)인 자연수 \(n = \frac{q+1}{2}\)이 있고, \(m = a + 1 \in \mathbb{N}\)으로 두면 \(f(m,n) = 2^a q = N\)이다. (단사) \(2^{m_1-1}(2n_1-1) = 2^{m_2-1}(2n_2-1)\)이라 하자. \(m_1 < m_2\)라 가정하면 양변을 \(2^{m_1-1}\)로 나누어 \(2n_1 - 1 = 2^{m_2-m_1}(2n_2-1)\)을 얻는데, 좌변은 홀수이고 우변은 \(m_2 - m_1 \ge 1\)이라 짝수이므로 모순이다. \(m_1 > m_2\)도 대칭적으로 모순이다. 따라서 \(m_1 = m_2\)이고, 그러면 \(2n_1 - 1 = 2n_2 - 1\)에서 \(n_1 = n_2\)이다.

두 풀이 어느 쪽이든 \(|\mathbb{N} \times \mathbb{N}| = |\mathbb{N}|\)이고 \(\mathbb{N} \times \mathbb{N}\)은 가산무한이다. \(\blacksquare\)

검산(풀이 2). \(f(1,1) = 1\), \(f(2,1) = 2\), \(f(1,2) = 3\), \(f(3,1) = 4\), \(f(1,3) = 5\), \(f(2,2) = 6\) — 자연수를 빠짐없이 훑는다.

복기. 이 결과가 §1.7의 (P3)이고, 문제 11과 16이 그대로 부품으로 인용한다. 격자를 셀 수 있다는 사실 하나가 유리수의 가산성과 가산 합집합의 가산성을 함께 떠받친다.

문제 10#

접근. C5주차 §1.6의 다섯 걸음을 순서대로 돌린다. 걸음 ①에서 이미 결론이 나오지만 그것만으로는 이 답안이 어디서 무너졌는지가 드러나지 않으므로, 걸음 ②~④까지 돌려 각 문장의 자격을 따로 적는다.

풀이. 판정: 틀림.

걸음 ① 명제 진위. 명제 “\(\mathbb{R}\)은 가산이다” 자체가 거짓이다. 예제 2.3이 \((0,1)\)의 비가산성을 주고 §1.7의 (P4)가 그것을 \(\mathbb{R}\)로 옮긴다. 거짓 명제에 붙은 증명은 반드시 어딘가가 틀렸으므로, 남은 걸음은 그 자리를 찾는 일이다.

걸음 ② 논리. 무너진 자리는 첫 문장이다. “\(\mathbb{R}\)의 원소를 \(r_1, r_2, r_3, \ldots\)로 나열할 수 있다”는 §1.4의 표에 따르면 “\(\mathbb{R}\)이 가산이다”와 같은 말이다. 곧 증명하려는 결론을 첫 줄에서 근거 없이 놓은 것이므로 순환이다. §1.5의 걸음 ①이 요구하는 것은 나열이 존재한다는 주장이 아니라 함수의 제시인데, 이 답안에는 제시가 없다.

걸음 ③ 가정 사용. 답안이 근거로 든 것은 “각 실수는 유일한 십진 전개를 가지므로” 하나다. 이 문장은 두 가지 이유로 첫 문장을 떠받치지 못한다. 첫째, 그 자체가 거짓이다 — \(0.4999\cdots\)과 \(0.5000\cdots\)은 같은 수의 두 표기다(§1.6). 둘째, 참이라 하더라도 표기의 유일성은 각 실수에 순번을 붙이는 일과 무관하다. 표기가 유일하다는 것은 한 수를 어떻게 적느냐의 문제이고, 나열 가능성은 수들을 \(\mathbb{N}\)과 짝지을 수 있느냐의 문제다.

걸음 ④ 양화사와 자격. “모든 원소를 나열할 수 있다”는 존재 주장인데, 그 존재를 보증하는 대상이 답안 어디에도 없다.

복기. 이 답안의 오류는 계산이 아니라 제작물의 부재다. §1.5의 표 첫 줄이 말하는 것이 정확히 이것이다 — 걸음 ①이 없으면 검증이 가리킬 대상이 없고, “나열할 수 있다”로 메우면 곧바로 순환이 된다. 반대로 문제 18의 답안에는 제작물이 실제로 있고, 그래서 무너지는 자리가 다르다. 두 답안을 나란히 놓고 읽어 두면 채점의 두 유형이 갈린다.

문제 11#

접근. 격자의 점 \((p,q)\)에 분수 \(\frac pq\)를 대응시키면 문제 9가 이미 격자를 세어 놓았으므로, 남은 일은 그 순서를 쓰되 어떤 점을 건너뛸지 정하는 것이다. 건너뛰지 않으면 §1.5 확인 6의 겹침이 그대로 살아난다.

풀이. 문제 9의 전단사 \(\sigma : \mathbb{N} \times \mathbb{N} \to \mathbb{N}\)을 가져온다. 격자점 \((p,q)\)를 \(\sigma\)가 정한 순서 \((1,1), (1,2), (2,1), (1,3), (2,2), (3,1), \ldots\)로 훑으면서, \(p\)와 \(q\)의 최대공약수가 1인 점만 채택하고 나머지는 건너뛴다. 채택된 점 \((p,q)\)에 유리수 \(\frac pq\)를 적으면 목록이 만들어진다.

처음 열 개의 격자점에서 목록을 실제로 만들어 보면 다음과 같다. \((1,1) \to 1\), \((1,2) \to \frac12\), \((2,1) \to 2\), \((1,3) \to \frac13\), \((2,2)\)는 최대공약수가 2이므로 건너뛴다, \((3,1) \to 3\), \((1,4) \to \frac14\), \((2,3) \to \frac23\), \((3,2) \to \frac32\), \((4,1) \to 4\). 목록은 \(1, \frac12, 2, \frac13, 3, \frac14, \frac23, \frac32, 4, \ldots\)이다.

(빠짐 없음) 임의의 \(r \in \mathbb{Q}^+\)을 잡자. \(r\)은 기약분수 \(\frac pq\) (\(p, q \in \mathbb{N}\), 최대공약수 1)로 표현된다(1권 33주차). 그 \((p,q)\)는 격자의 점이므로 \(\sigma(p,q)\)번째에 등장하고, 최대공약수가 1이라 건너뛰어지지 않으므로 채택된다. 따라서 \(r\)이 목록에 등장한다. 이 걸음에는 표현의 존재만 쓰였다.

이 풀이가 빌려 쓰는 사실 — 기약분수 표현의 유일성

양의 유리수 \(r\)을 \(r = \frac pq\) (\(p, q \in \mathbb{N}\), 최대공약수 1)로 적는 방법은

많아야 하나다. 이 사실은 지금은 인정하고 쓴다. 표현이 존재한다는 것은 1권

33주차가 주지만, 유일성은 \(\frac pq = \frac{p'}{q'}\)에서 \(pq' = p'q\)를 거쳐

유클리드 보조정리를 써야 나오며, 그 보조정리가 정식으로 서는 자리는 C15주차다.

아래 겹침 없음 검증이 이 사실을 쓰는 유일한 자리다.

(겹침 없음) 채택된 두 점 \((p,q) \ne (p',q')\)이 같은 유리수를 준다고 하자. 그러면 두 기약분수 \(\frac pq\)와 \(\frac{p'}{q'}\)이 같은 값이 되는데, 위 상자의 유일성에 모순이다. 따라서 겹침이 없다.

(순번의 유한성) 각 채택 점의 순번은 \(\sigma(p,q)\) 이하이므로 유한하다.

세 줄이 모두 성립하므로 \(\mathbb{Q}^+\)은 가산이고, 무한하므로 가산무한이다. \(\blacksquare\)

기약분수만 세는 이유. 격자 전체를 그대로 세면 \((1,1), (2,2), (3,3), \ldots\)이 모두 같은 유리수 1을 주고, \((1,2), (2,4), (3,6), \ldots\)이 모두 \(\frac12\)을 준다. 그러면 같은 원소가 무한히 여러 번 등장해 대응이 단사가 아니게 되고, 정의 1.1의 조건이 깨진다. 기약 조건은 각 유리수의 대표 하나만 남겨 그 겹침을 제거한다.

복기. “격자를 셀 수 있다”(문제 9)와 “중복을 제거한다”(이 문제)의 두 걸음이 \(\mathbb{Q}\)의 가산성을 만든다. 같은 두 걸음이 문제 16에서 그대로 반복되며, 거기서는 중복 제거가 “이미 나온 값을 건너뛴다”로 일반화된다.

문제 12#

접근. 두 예를 제시하는 것으로 끝나지만, 각 예마다 부분집합임과 가산성(또는 비가산성)을 각각 출처를 대며 적어야 채점 기준 ④를 통과한다. 그리고 반대쪽 — 가산집합의 부분집합 — 에서는 왜 이런 갈림이 없는지를 덧붙이면 이 문제의 요점인 비대칭이 드러난다.

풀이. 무대는 \(\mathbb{R}\)이고, \(\mathbb{R}\)은 비가산이다(예제 2.3과 §1.7의 (P4)).

가산인 부분집합. \(\mathbb{N} \subseteq \mathbb{R}\)이고, \(\mathbb{N}\)은 항등함수가 전단사이므로 가산무한이다(문제 2(a)).

비가산인 부분집합. \((0,1) \subseteq \mathbb{R}\)이고, \((0,1)\)은 예제 2.3에 의해 비가산이다.

따라서 비가산집합의 부분집합은 가산일 수도 있고 비가산일 수도 있다. \(\blacksquare\)

반대쪽에는 갈림이 없다. \(A\)가 가산이면 그 부분집합은 언제나 가산이다 — §1.7의 (P1)이다. 곧 “부분집합”이라는 관계는 가산성을 아래로만 전달한다. 비가산성은 아래로 전달되지 않고 위로 전달된다((P4)).

복기. 이 비대칭이 문제 17의 논증을 가능하게 한다. 무리수가 비가산임을 보일 때 \(\mathbb{R}\)의 비가산성을 부분집합으로 내려 보낼 수는 없고, 대신 (P2)의 대우를 써서 합집합의 비가산성을 조각으로 나눠 보내야 한다. 어느 방향으로 성질이 흐르는지를 표로 정리해 두면 답안에서 방향을 잘못 잡는 실수가 줄어든다. §3 훈련 3의 \(D\)는 \((0,1)\)의 진부분집합이면서 비가산인 또 하나의 사례다.

문제 13#

접근. 탄젠트 쪽을 고르면 먼저 정의역이 맞는지 확인한다. \(x \in (0,1)\)일 때 \(\pi(x - \frac12)\)가 \((-\frac\pi2, \frac\pi2)\)에 들어가는지가 함수가 정의되는 조건이고, 그 구간이 정확히 탄젠트가 순증가하며 실수 전체를 덮는 구간이다. 전사 증명은 역함수를 구성하는 일이고, 그 역함수는 아크탄젠트로 적힌다.

풀이. \(f : (0,1) \to \mathbb{R}\)를 \(f(x) = \tan\big(\pi(x - \tfrac12)\big)\)로 정의한다.

(정의됨) \(x \in (0,1)\)이면 \(x - \frac12 \in (-\frac12, \frac12)\)이므로 \(\pi(x - \frac12) \in (-\frac\pi2, \frac\pi2)\)이다. 탄젠트는 이 열린 구간에서 정의되므로 \(f(x)\)가 실수로 정해진다.

이 풀이가 빌려 쓰는 사실. 탄젠트가 \((-\frac\pi2, \frac\pi2)\)에서 순증가하며 그 구간을 \(\mathbb{R}\) 전체로 보낸다는 사실, 그리고 그 역함수가 아크탄젠트라는 사실은 지금은 인정하고 쓴다. 증명에는 해석학의 준비가 더 필요하며 이 과정 밖의 주제다(§1.8 근거 ④에 등록되어 있다).

(단사) \(x \mapsto \pi(x - \frac12)\)은 기울기가 \(\pi \ne 0\)인 일차함수라 단사이고, 탄젠트는 \((-\frac\pi2, \frac\pi2)\)에서 순증가하므로 단사다. 단사의 합성은 단사이므로(C12주차 문제 8) \(f\)는 단사다.

(전사) 임의의 \(y \in \mathbb{R}\)을 잡자. \(\theta = \arctan y\)로 두면 \(\theta \in (-\frac\pi2, \frac\pi2)\)이고 \(\tan\theta = y\)이다. 이제 \(x = \frac{\theta}{\pi} + \frac12\)로 두면 \(\frac\theta\pi \in (-\frac12, \frac12)\)이므로 \(x \in (0,1)\)이고,

\[ f(x) = \tan\Big(\pi\Big(\frac{\theta}{\pi} + \frac12 - \frac12\Big)\Big) = \tan\theta = y \]

이다. 따라서 \(f\)는 전사다.

\(f\)는 전단사이므로 \(|(0,1)| = |\mathbb{R}|\)이다. \(\blacksquare\)

검산. \(f(\frac12) = \tan 0 = 0\), \(f(\frac34) = \tan\frac\pi4 = 1\), \(f(\frac14) = \tan(-\frac\pi4) = -1\). \(x\)가 0에 가까워지면 값이 아래로, 1에 가까워지면 위로 한없이 간다 — 구간의 두 끝이 직선의 두 끝으로 펴진다.

다른 함수로도 된다. \(g(x) = \frac{2x-1}{x(1-x)}\)도 같은 일을 한다. \(g(\frac12) = 0\)이고, \(x\)가 0에 가까울수록 값이 아래로 얼마든지 작아지며 1에 가까울수록 위로 얼마든지 커진다 — 이 서술도 탄젠트의 경우와 같이 지금은 인정하고 쓴다(극한의 정밀한 처리는 이 과정 밖의 주제다). 이 함수를 쓸 때도 요구되는 검증은 똑같이 둘 — 단사와 전사(원상 구성)다.

복기. 길이가 1인 구간이 무한히 긴 직선과 같은 크기다. 길이와 크기(기수)는 서로 다른 잣대이며, 전단사는 길이를 보존할 의무가 없다. 이 결과가 문제 19와 합쳐지면 \([0,1]\), \((0,1)\), \(\mathbb{R}\)이 모두 같은 크기 \(\mathfrak{c}\)임이 나온다.

문제 14#

접근. 목록을 표로 펼치면 \(k\)행 \(j\)열 칸에 “\(j \in f(k)\)인가”를 적게 되고, 그 표의 대각선 칸은 “\(k \in f(k)\)인가”다. 그 대각선을 전부 뒤집은 행이 제작할 집합 \(D\)이며, \(D\)가 어느 행과도 다르다는 것이 곧 탈출 검증이다. 이번에는 전단사가 아니라 전사만 가정해 무너뜨리므로 결론이 더 강해진다.

풀이. 먼저 \(\mathcal{P}(\mathbb{N})\)은 유한하지 않다 — \(\{1\}, \{2\}, \{3\}, \ldots\)이 서로 다른 원소를 무한히 많이 준다.

\(\mathcal{P}(\mathbb{N})\)이 가산이라 가정하자. 유한하지 않으므로 가산무한이고, 전단사 \(f : \mathbb{N} \to \mathcal{P}(\mathbb{N})\)이 존재한다. 특히 \(f\)는 전사다.

이제 다음 집합을 제작한다.

\[ D = \{n \in \mathbb{N} : n \notin f(n)\} \]

자격. \(D\)는 \(\mathbb{N}\)의 부분집합이므로 \(D \in \mathcal{P}(\mathbb{N})\)이다.

탈출. \(f\)가 전사이므로 \(D = f(m)\)인 \(m \in \mathbb{N}\)이 존재한다. 이 \(m\)에 대해 두 경우를 따진다. \(m \in D\)이면 \(D\)의 정의에 의해 \(m \notin f(m)\)인데, \(f(m) = D\)이므로 \(m \notin D\)가 되어 모순이다. \(m \notin D\)이면 \(f(m) = D\)이므로 \(m \notin f(m)\)이고, 그러면 \(D\)의 정의에 의해 \(m \in D\)가 되어 모순이다. \(m \in D\)이거나 \(m \notin D\) 둘 중 하나는 반드시 성립하는데 양쪽 모두 모순이므로, 그러한 \(m\)은 존재하지 않는다. 곧 \(D\)는 \(f\)의 상에 없다.

이것은 \(f\)가 전사라는 것과 모순이다. 따라서 그러한 전단사는 존재하지 않고, \(\mathcal{P}(\mathbb{N})\)은 비가산이다. \(\blacksquare\)

왜 이것이 대각선인가. \(f(k)\)를 0과 1의 행으로 적어 보자 — \(k\)행 \(j\)열에 \(j \in f(k)\)이면 1, 아니면 0을 적는다. 그러면 \(D\)는 대각선 칸 \((k,k)\)의 값을 전부 뒤집은 행이고, 그래서 \(k\)행과 \(k\)열에서 반드시 다르다. 예제 2.3에서 자릿수를 비튼 것과 완전히 같은 동작이며, 자릿수 대신 소속 여부가 비틀리는 대상일 뿐이다.

검산. \(f(1) = \{1,2\}\), \(f(2) = \{3\}\), \(f(3) = \{3,4\}\)인 경우를 보자. \(1 \in f(1)\)이므로 \(1 \notin D\), \(2 \notin f(2)\)이므로 \(2 \in D\), \(3 \in f(3)\)이므로 \(3 \notin D\)이다. 곧 \(D\)는 첫 세 행과 각각 첫째\(\cdot\)둘째\(\cdot\)셋째 자리에서 다르다.

복기. 이 논증은 \(\mathbb{N}\)의 성질을 하나도 쓰지 않았다 — 쓴 것은 “\(f\)가 전사”와 “\(D\)를 만들 수 있다”뿐이다. 그래서 \(\mathbb{N}\)을 임의의 집합으로 바꿔도 그대로 돌아가고, 그것이 문제 15다.

문제 15#

접근. “\(<\)”는 두 주장으로 쪼개진다 — 단사가 존재한다는 것과 전단사가 존재하지 않는다는 것. 앞쪽은 함수 하나로 끝나고, 뒤쪽이 문제 14의 논증을 \(\mathbb{N}\) 대신 임의의 \(A\)에 대해 그대로 옮긴 것이다.

풀이. 단사가 존재한다. \(g : A \to \mathcal{P}(A)\)를 \(g(a) = \{a\}\)로 정의한다. \(a \in A\)이면 \(\{a\} \subseteq A\)이므로 값이 \(\mathcal{P}(A)\)에 들어간다. \(g(a_1) = g(a_2)\)라 하면 \(\{a_1\} = \{a_2\}\)이고, 한 원소 집합의 상등은 원소의 상등이므로 \(a_1 = a_2\)이다. 따라서 \(g\)는 단사이고, 이 뜻에서 \(|A| \le |\mathcal{P}(A)|\)이다.

전사가 존재하지 않는다. 전사 \(f : A \to \mathcal{P}(A)\)가 있다고 가정하자.

\[ D = \{a \in A : a \notin f(a)\} \]

로 두면 \(D \subseteq A\)이므로 \(D \in \mathcal{P}(A)\)이다. \(f\)가 전사이므로 \(D = f(b)\)인 \(b \in A\)가 존재한다. \(b \in D\)이면 \(D\)의 정의에 의해 \(b \notin f(b) = D\)이므로 모순이고, \(b \notin D = f(b)\)이면 \(D\)의 정의의 조건을 만족하므로 \(b \in D\)가 되어 역시 모순이다. 어느 쪽이든 모순이므로 그러한 전사는 존재하지 않는다.

전단사는 특히 전사이므로 전단사도 존재하지 않는다. 따라서 \(|A| \ne |\mathcal{P}(A)|\)이고, 단사는 있으므로 \(|A| < |\mathcal{P}(A)|\)이다. \(\blacksquare\)

검산. \(A = \emptyset\)에서도 성립한다. \(\mathcal{P}(\emptyset) = \{\emptyset\}\)이므로 원소가 0개인 집합과 1개인 집합이고, \(0 < 1\)이다. \(A = \{1\}\)이면 \(\mathcal{P}(A) = \{\emptyset, \{1\}\}\)으로 \(1 < 2\)이다.

무한의 위계. \(A = \mathbb{N}\)에 적용하면 \(|\mathbb{N}| < |\mathcal{P}(\mathbb{N})|\)이고, 같은 정리를 \(\mathcal{P}(\mathbb{N})\)에 다시 적용하면 \(|\mathcal{P}(\mathbb{N})| < |\mathcal{P}(\mathcal{P}(\mathbb{N}))|\)이다. 이 조작은 끝나지 않으므로 서로 다른 무한 기수가 무한히 많다.

복기. \(D = \{a \in A : a \notin f(a)\}\)의 모양은 1권 6주차 §1.7의 러셀 역설에 나온 “자기 자신을 원소로 갖지 않는 집합들의 모임”과 같다. 두 곳 모두 “자기 자신에 대한 소속을 뒤집는다”는 한 동작이 모순을 낳으며, 칸토어의 정리에서는 그 모순이 역설이 아니라 정리로 쓰인다. 같은 동작이 어디서는 체계를 무너뜨리고 어디서는 결론을 낳는지의 차이는, 무너뜨리는 대상이 공리계인지 가정인지에 있다.

“\(<\)”의 정식 정의는 다음 주다. 이번 주에는 \(|A| < |B|\)를 “단사가 있고 전단사가 없다”의 줄임으로만 쓴다. 이 관계가 실제로 순서처럼 행동하는지 — 특히 반대칭성이 성립하는지 — 는 C14주차의 슈뢰더-번슈타인 정리가 답한다.

문제 16#

접근. 집합들을 \(A_1, A_2, \ldots\)로 두고 각 \(A_i\)의 목록을 \(i\)행에 늘어놓으면 격자가 생기고, 문제 9가 이미 격자를 세어 놓았다. 남은 일은 두 함수를 잇는 것이다. 겹침을 피하기 어려우므로 문제에 딸린 상자의 사실 — 전사만 있어도 가산 — 을 쓴다.

풀이. \(A_1, A_2, A_3, \ldots\)이 각각 가산이라 하자(공집합인 것은 합집합에 기여하지 않으므로 미리 버린다). 각 \(i\)에 대해 \(A_i\)가 가산이므로 전사 \(h_i : \mathbb{N} \to A_i\)가 존재한다 — 가산무한이면 전단사가 그대로 전사이고, 유한이면 목록을 반복해 늘여 전사를 만든다. 각 \(i\)마다 그런 \(h_i\)를 하나씩 고른다.

\(a_{ij} = h_i(j)\)로 두고 \(H : \mathbb{N} \times \mathbb{N} \to \bigcup_i A_i\)를 \(H(i,j) = a_{ij}\)로 정의한다. \(H\)는 전사다 — 임의의 \(x \in \bigcup_i A_i\)에 대해 \(x \in A_i\)인 \(i\)가 있고, \(h_i\)가 전사이므로 \(x = h_i(j) = H(i,j)\)인 \(j\)가 있다.

문제 9의 전단사 \(\sigma : \mathbb{N} \times \mathbb{N} \to \mathbb{N}\)의 역함수 \(\sigma^{-1}\)은 전단사이므로(C12주차 §1.5), 합성 \(H \circ \sigma^{-1} : \mathbb{N} \to \bigcup_i A_i\)은 전사와 전단사의 합성이라 전사다. 곧 \(\bigcup_i A_i\) 위로 가는 전사가 \(\mathbb{N}\)에서 존재한다.

문제에 딸린 상자의 사실에 의해, \(\mathbb{N}\)에서 어떤 집합 위로 가는 전사가 있으면 그 집합은 가산이다. 따라서 \(\bigcup_i A_i\)은 가산이다. \(\blacksquare\)

선택공리가 필요한 자리. 계산이 아니라 “각 \(i\)마다 \(h_i\)를 하나씩 고른다”는 문장 자체다. 각 \(A_i\)에 대해 전사가 존재한다는 것과, 모든 \(i\)에 대한 전사를 동시에 하나씩 골라 놓은 목록 \((h_1, h_2, \ldots)\)이 존재한다는 것은 다른 주장이며, 뒤쪽을 보증하는 것이 가산 선택 공리다. 지금은 인정하고 쓴다 — 이 공리를 다루는 것은 이 과정 밖의 주제다.

\(\mathbb{Q}\)의 가산성 재유도. 각 \(q \in \mathbb{N}\)에 대해 \(A_q = \{\frac pq : p \in \mathbb{Z}\}\)로 두면 \(p \mapsto \frac pq\)가 \(\mathbb{Z}\)에서 \(A_q\)로 가는 전단사이므로 \(A_q\)는 가산이다. 그리고 \(\mathbb{Q} = \bigcup_{q} A_q\)이므로 이 정리에 의해 \(\mathbb{Q}\)가 가산이다. 문제 11의 격자 논증과 결론이 같고, 이쪽은 중복 제거를 상자의 사실에 맡긴다는 점이 다르다.

복기. 이 정리가 §1.7 (P2)의 후반부이고, 문제 17이 그 대우를 쓴다. “셀 수 있는 것을 셀 수 있는 만큼 모아도 셀 수 있다”는 문장이 \(\mathbb{N}\)의 크기가 갖는 안정성이며, 그럼에도 \(\mathbb{R}\)은 그 방식으로 도달되지 않는다.

문제 17#

접근. 귀류 가정 “무리수가 가산이다”는 정의 1.2에 의해 두 갈래(유한 또는 가산무한)로 갈린다. 문제 8은 가산무한 쪽만 다루므로 유한 쪽도 한 줄로 처리해 두어야 경우가 빠지지 않는다.

풀이. 무리수 전체를 \(I = \mathbb{R} - \mathbb{Q}\)로 쓴다.

\(I\)가 가산이라 가정하자. \(\mathbb{Q}\)는 가산이다(문제 11과 문제 2(c)). 그리고 \(\mathbb{Q}\)와 \(I\)는 서로소이고 \(\mathbb{R} = \mathbb{Q} \cup I\)이다.

경우 1: \(I\)가 가산무한. \(\mathbb{Q}\)도 가산무한이고 두 집합이 서로소이므로, 문제 8에 의해 \(\mathbb{Q} \cup I = \mathbb{R}\)이 가산무한이다.

경우 2: \(I\)가 유한. 유한집합의 목록을 \(\mathbb{Q}\)의 목록 앞에 붙이면 \(\mathbb{R}\)의 목록이 된다 — 빠짐이 없고(두 집합의 원소가 모두 등장한다) 겹침도 없다(서로소이고 각 목록에 겹침이 없다). 따라서 \(\mathbb{R}\)이 가산이다.

두 경우 모두 \(\mathbb{R}\)이 가산이라는 결론이 나온다. 그런데 \(\mathbb{R}\)은 비가산이다(예제 2.3과 §1.7의 (P4)). 모순이다.

따라서 \(I\)는 가산이 아니다. \(I\)가 유한하지 않음은 위 경우 2가 이미 배제했으므로 (유한이면 모순이 나왔다), 정의 1.3에 의해 \(I\)는 비가산이다. \(\blacksquare\)

같은 결론을 (P2)의 대우로. §1.7 확인 9에서 확인한 대우를 쓰면 한 줄로 끝난다 — \(\mathbb{R} = \mathbb{Q} \cup I\)가 비가산이고 \(\mathbb{Q}\)가 가산이므로, 둘 중 적어도 하나가 비가산이어야 한다는 조건을 만족하는 것은 \(I\)뿐이다.

복기. \(\mathbb{Q}\)와 \(I\)가 함께 \(\mathbb{R}\)을 이루는데 한쪽은 가산이고 다른 쪽은 비가산이다. 곧 \(\mathbb{R}\)의 비가산성을 떠받치는 것은 전부 무리수 쪽이다. 유리수는 수직선 어디에나 조밀하게 깔려 있으면서도 크기로는 무리수에 비해 “거의 없는” 셈이며, 조밀함과 크기가 서로 다른 잣대라는 사실이 여기서 가장 선명하게 드러난다.

문제 18#

접근. 문제 10과 달리 이 답안에는 제작물이 실제로 있다. 그러므로 걸음 ①만으로 끝내지 말고, 이 목록이 정확히 어떤 집합을 세는지 밝힌 뒤 그 집합과 \((0,1)\)의 차이를 구체적인 원소 하나로 지목한다. §1.5의 어느 걸음이 통째로 빠졌는지도 적는다.

풀이. 판정: 틀림.

걸음 ① 명제 진위. 명제 “\((0,1)\)은 가산이다”가 거짓이다(예제 2.3).

빠진 걸음. §1.5의 걸음 ② — 빠짐 없음(전사)의 검증 — 이 통째로 없다. 답안은 “모든 \((0,1)\)의 소수가 나온다”고 주장만 하고 임의의 원소에 대해 순번을 구성하지 않았다.

이 목록이 실제로 세는 집합. 제시된 나열은 소수점 아래 1자리까지 적히는 수 아홉 개, 2자리까지 적히는 수, 3자리까지 적히는 수, … 순서로 훑는다. 곧 이 목록에 등장하는 수는 어떤 자연수 \(k\)에 대해 소수점 아래 \(k\)자리에서 끝나는 수 — 유한소수뿐이다. 유한소수 전체는 \(\{\frac{m}{10^k} : k \in \mathbb{N}, 1 \le m < 10^k\}\)이고, 각 \(k\)마다 유한개이므로 문제 16에 의해 가산이다. 따라서 이 목록은 (게다가 2자리 구간이 \(0.10 = 0.1\)처럼 앞 구간의 수를 다시 내놓아 겹침까지 있으므로 걸음 ③도 통과하지 못하지만, 그 겹침은 문제 16의 상자 사실로 수리할 수 있다) 결정적으로 세는 대상이 다르다 — 그것이 세는 집합은 \((0,1)\)이 아니라 유한소수 전체다.

빠진 원소를 지목한다. \(\frac13 = 0.333\cdots \in (0,1)\)은 이 목록에 없다. 만약 있다면 어떤 \(k\)에 대해 소수점 아래 \(k\)자리에서 끝나야 하는데, \(\frac13 = \frac{m}{10^k}\)이면 \(10^k = 3m\)이 되어 좌변은 3으로 나누어떨어지지 않고 우변은 나누어떨어지므로 모순이다. 무리수 \(\frac{\sqrt2}{2} = 0.7071\cdots\)도 같은 이유로 없다 — 유한소수는 모두 유리수이기 때문이다.

복기. 문제 10의 답안은 제작물이 아예 없어 순환이었고, 이 답안은 제작물이 있으나 그것이 덮는 범위를 검증하지 않았다. 두 답안을 나란히 놓으면 §1.5 표의 첫 두 줄이 각각 어떤 실패로 나타나는지가 보인다. 그리고 이 답안은 “규칙이 그럴듯하면 통과시킨다”는 채점 습관이 왜 위험한지도 보여 준다 — 계산은 한 줄도 틀리지 않았고 목록의 규칙 자체는 잘 정의되어 있다.

문제 19#

접근. 갈래가 셋인 함수이므로 단사 검증도 세 갈래 사이와 각 갈래 안을 모두 봐야 한다. 갈래 사이를 막아 주는 것은 각 갈래의 상이 서로 겹치지 않는다는 사실이고, 그것을 확인하려면 세 상을 각각 집합으로 적어 보면 된다.

풀이. \(f : [0,1] \to (0,1)\)을 다음으로 정의한다.

\[\begin{split} \begin{aligned}f(x) = \begin{cases} \dfrac12 & (x = 0) \\[4pt] \dfrac13 & (x = 1) \\[4pt] \dfrac{1}{n+2} & \big(x = \tfrac1n,\ n \ge 2\big) \\[4pt] x & (\text{그 밖의 } x) \end{cases}\end{aligned} \end{split}\]

(정의됨과 무대 소속) 네 갈래는 서로 겹치지 않고 \([0,1]\) 전체를 덮으므로 각 \(x\)에 값이 정확히 하나 정해진다. 값은 \(\frac12\), \(\frac13\), \(\frac{1}{n+2}\) (\(n \ge 2\)이므로 \(\frac14\) 이하), 그리고 \(0\)과 \(1\)과 \(\frac1n\) 꼴을 제외한 \(x\)인데, 그런 \(x\)는 \([0,1]\)에 있으면서 끝점이 아니므로 \((0,1)\)에 있다. 따라서 모든 값이 \((0,1)\)에 들어간다.

(단사) 세 상을 적어 본다. 첫 두 갈래의 상은 \(\{\frac12, \frac13\}\)이고, 셋째 갈래의 상은 \(\{\frac14, \frac15, \frac16, \ldots\}\)이며, 넷째 갈래의 상은 넷째 갈래의 정의역 자신 — 곧 \(\frac1n\) 꼴이 아닌 \((0,1)\)의 원소들 — 이다. 세 상은 서로소다 (\(\{\frac12, \frac13\}\)의 원소는 모두 \(\frac13\) 이상이고 \(\{\frac14, \frac15, \ldots\}\)의 원소는 모두 \(\frac14\) 이하이므로 앞의 두 상이 갈리고, 넷째 갈래의 상만 \(\frac1n\) 꼴이 아니므로 그것이 앞의 둘과 갈린다). 그러므로 서로 다른 갈래의 값이 같아질 수 없다. 갈래 안에서는 — 첫 두 갈래는 값이 \(\frac12 \ne \frac13\)으로 서로 다르고, 셋째 갈래는 \(\frac{1}{n_1+2} = \frac{1}{n_2+2}\)에서 \(n_1 = n_2\)가 나오며, 넷째 갈래는 항등이라 단사다. 따라서 \(f\)는 단사다.

(전사) 임의의 \(y \in (0,1)\)을 잡자. \(y = \frac12\)이면 \(y = f(0)\)이다. \(y = \frac13\)이면 \(y = f(1)\)이다. \(y = \frac1m\)이고 \(m \ge 4\)이면 \(m - 2 \ge 2\)이므로 \(y = f\big(\frac{1}{m-2}\big)\)이다. 그 밖의 \(y\)는 \(\frac1n\) 꼴이 아니므로 넷째 갈래에서 \(f(y) = y\)이다. (\((0,1)\)에는 \(\frac11 = 1\)이 없으므로 \(\frac1n\) 꼴인 \(y\)는 \(m \ge 2\)뿐이고, 위 세 경우가 그것을 모두 덮는다.)

\(f\)는 전단사이므로 \(|[0,1]| = |(0,1)|\)이다. \(\blacksquare\)

검산. \(f(0) = \frac12\), \(f(1) = \frac13\), \(f(\frac12) = \frac14\), \(f(\frac13) = \frac15\), \(f(\frac14) = \frac16\). 값들이 \(\frac12, \frac13, \frac14, \frac15, \frac16, \ldots\)을 겹침 없이 채운다 — 원래 \(\frac12\)과 \(\frac13\)이 있던 자리에 끝점 두 개가 들어가고, 밀린 값들이 두 칸씩 뒤로 간다.

복기. 두 점을 끼워 넣기 위해 수열 하나를 골라 두 칸씩 미는 조작이 힐베르트가 든 사고 실험 그대로다. 이 조작이 가능한 이유는 \(\{\frac1n\}\)이 가산무한이라 “두 칸 밀어도 여전히 자기 자신과 같은 크기”이기 때문이며, 그것이 예제 2.1과 문제 6에서 본 성질이다. 다음 주 C14주차의 슈뢰더-번슈타인 정리를 쓰면 이 전단사를 직접 만들지 않고도 같은 결론을 얻는다 — 양쪽으로 단사만 있으면 되고, \([0,1] \to (0,1)\)의 단사는 \(x \mapsto \frac{x+1}{3}\)처럼 훨씬 쉽게 잡힌다.

문제 20#

접근. (a)는 준비 운동 유형 1이 기대던 보증이 어디서 나왔고 무한에서 왜 사라지는지를 적으면 된다. (b)는 §1.2 확인 2의 비대칭이 논증의 형태를 어떻게 정했는지가 요점이다 — 하나를 제시하는 일과 전부를 배제하는 일의 차이.

풀이 (a). (예시 답안) 유한집합에서 “진부분집합은 전체보다 작다”가 성립하는 것은 세기가 끝나 개수라는 수가 남고 그 두 수를 비교할 수 있기 때문인데, 무한집합에서는 그 수가 없으므로 이 보증이 사라진다. 예제 2.1이 보인 대로 \(2\mathbb{N}\)은 \(\mathbb{N}\)의 진부분집합이면서 전단사 \(n \mapsto 2n\)으로 \(\mathbb{N}\)과 같은 크기이며, 이것은 모순이 아니라 크기의 잣대를 짝짓기로 바꾼 결과다. 데데킨트는 이 성질 — 자신의 진부분집합과 같은 크기임 — 을 무한집합의 정의로 삼았고, 그러면 “부분이 전체와 같은 크기”는 무한의 예외가 아니라 무한의 뜻 자체가 된다.

풀이 (b). (예시 답안) 비가산은 “전단사가 하나도 없다”는 비존재 주장이므로 목록 하나를 반박하는 것으로는 끝나지 않고 모든 목록을 상대해야 하는데, 대각선 논법은 임의의 목록 하나를 가정한 뒤 그 목록 자체를 재료로 목록에 없는 원소를 만들어 그 요구를 채운다. 예제 2.3에서 목록 \(x_1, x_2, \ldots\)의 \(k\)번째 수의 \(k\)번째 자리를 비틀어 만든 \(y\)는 \((0,1)\) 안에 있으면서 모든 \(x_k\)와 \(k\)번째 자리에서 다르므로, 어떤 목록을 가져와도 그 목록이 빠뜨린 원소가 존재한다는 결론이 나온다.

채점 항목. (a)에서는 “유한의 보증이 어디서 나오는가”와 “무한에서 왜 사라지는가”가 둘 다 있어야 한다. 결론만 적고 근거를 빠뜨리면 준비 운동 유형 2와 같은 답이 된다. (b)에서는 “목록을 재료로 삼는다”는 자기 참조의 구조가 드러나야 한다. 대각선을 비틀었다는 사실만 적으면 왜 그것이 모든 목록을 처리하는지가 빠진다.

다음 주 예고 (C14): Chartrand 11.4~11.5 — 기수 비교와 슈뢰더-번슈타인 정리. 이번 주에 \(|A| < |\mathcal{P}(A)|\)를 “단사가 있고 전단사가 없다”의 줄임으로만 썼고, 그 관계가 순서처럼 행동하는지는 미뤄 두었다. 다음 주에 \(|A| \le |B|\)를 단사의 존재로 정식 정의하고, 슈뢰더-번슈타인 정리 — \(|A| \le |B|\)이고 \(|B| \le |A|\)이면 \(|A| = |B|\) — 로 그 관계의 반대칭성을 확보한다. 그러면 문제 19에서 갈래 넷으로 공들여 만든 전단사를 양쪽 단사 두 개로 대신할 수 있다. 원서 11.4~11.5를 통독하고 온다.