# C14주차 — 기수 비교와 슈뢰더-번슈타인 정리

:::{admonition} 이 주의 길잡이
:class: keybox

**핵심 문장**: "$|A| \le |B|$"는 단사 하나의 존재를 뜻하고, **슈뢰더-번슈타인 정리**는 양쪽으로 단사가 있으면 전단사가 있음을 보장한다. 그러므로 같은 크기를 보이는 일이 전단사 하나를 만드는 일에서 단사 두 개를 만드는 일로 바뀐다.

**이 주의 위치**: 2학기 20주 과정의 C14주차. C13주차가 "같은 크기"를 전단사의 존재로 정의했고, 이번 주는 "크지 않다"를 단사의 존재로 정의해 두 기수 사이에 부등호를 놓는다. C13주차 문제 19와 1권 49주차 문제 17에서 갈래 규칙으로 공들여 만든 전단사가 여기서는 단사 두 개로 대체된다. 1권 49주차와 C13주차가 "단사는 있고 전단사는 없다"의 줄임으로만 쓰던 기호 $<$가 여기서 정식 정의를 얻는다.

**원서 대응**: Chartrand 11.4~11.5 (Comparing Cardinalities / The Schröder-Bernstein Theorem). 1일차에 이 두 절을 통독한 상태로 이 교안에 온다.
:::

## 이번 주 목표

1. **기수 비교** $|A| \le |B|$를 단사의 존재로 정의하고, 정의의 조각마다 무엇이 무너지는지 설명한다.
1. 이 관계가 반사적이고 추이적임을 증명하고, 남은 성질인 반대칭이 무한에서 왜 정리가 되어야 하는지 밝힌다.
1. **슈뢰더-번슈타인 정리**를 진술하고, CSB 활용의 3단 서식을 백지에 재현한다.
1. 전단사를 직접 만들지 않고 $|(0,1)| = |[0,1]|$, $|\mathbb{N}| = |\mathbb{N} \times \mathbb{N}|$, $|\mathbb{R}| = |\mathbb{R}^2|$를 증명한다.
1. 무한 기수의 산술을 부품 목록으로 정리하고, 연속체 가설이 어떤 종류의 물음인지 구분한다.

본문 곳곳의 **확인** 상자는 연필로 먼저 답하는 자리다. 바로 아래의 **답** 상자는 (웹에서는 접혀 있다) 스스로 답한 뒤에 열어 대조한다.

:::{admonition} 표기 — § 와 난이도 표시
:class: quotebox

§는 "절"이라고 읽는다. §1.3은 이 주차의 1.3 절을, §6은 6절 전체를 가리킨다.

다른 주차를 가리킬 때는 "C13주차 §1.6"처럼 주차를 앞에 적는다.

연습문제는 기본 1~6번, 표준 7~14번, 도전 15~20번이고, 빈칸 사다리는 훈련 1에서

3으로 갈수록 지지대가 줄어든다.
:::

## 준비 운동 (C13주차 복습)

지난주까지의 도구를 손에 올려 둔다. 셋 다 이번 주 답안에서 그대로 쓴다.

1. C13주차 정의 1.1을 진술하시오 — 무엇이 하나 존재하면 $|A| = |B|$인가.
1. C12주차 §1.3의 단사 증명 서식을 쓰시오 — 어떤 문장으로 시작해 어떤 문장으로 끝나는가.
1. C13주차 문제 19($[0,1]$과 $(0,1)$이 같은 크기)의 전단사를 백지에 재현하시오. 규칙이 몇 갈래로 갈렸는지 세어 둔다.

이어서 진단 문제 하나를 풀어 보자. 풀지 못해도 된다 — 이번 주가 무엇을 메우는지 가늠하기 위한 기록이다.

1. (진단) 직선 $\mathbb{R}$과 평면 $\mathbb{R}^2$ 중 어느 쪽이 더 큰가. 근거와 함께 답하시오.

답을 노트에 적어 둔다. §5의 백지 재현 뒤에 이 기록을 다시 본다.

### 자주 나오는 세 가지 답

방금 쓴 답은 대개 다음 세 유형 중 하나다. 셋 다 자연스러운 출발점이고, 셋 다 이번 주에 메울 정확한 간격이 있다.

- **유형 1 — 평면이 더 크다.** "직선은 평면 안에 통째로 들어가므로 평면이 더 크다."

전반부의 관찰은 정확하다 — $x \mapsto (x, 0)$이 실제로 $\mathbb{R}$을 $\mathbb{R}^2$ 안에 겹침 없이 심는다. 이번 주는 그 관찰에 $|\mathbb{R}| \le |\mathbb{R}^2|$라는 이름을 준다. 빠진 것은 후반부다 — "안에 들어간다"에서 "더 작다"로 넘어가려면 **반대 방향의 단사가 없음**을 따로 보여야 하는데 그 확인이 없다. 실제로 반대 방향의 단사는 존재하며(그 재료가 §1.1의 자리 엮기이고 완성은 예제 2.3이다), 결론은 뒤집힌다.

- **유형 2 — 둘 다 비가산이므로 같다.** 결론은 이번 주의 정답과 일치한다. 그러나

같은 근거로 $|\mathcal{P}(\mathbb{R})| = |\mathbb{R}|$도 나오는데, C13주차 문제 15의 칸토어 정리가 그것을 반증한다. 참인 결론과 거짓인 결론을 함께 낳는 문장은 근거가 아니다. 비가산은 하나의 크기가 아니라 "$\aleph_0$이 아니다"라는 뜻일 뿐이며, 비가산끼리를 갈라내는 잣대가 §1.2에서 만들어진다.

- **유형 3 — 전단사를 만들 수 없어 답하지 못했다.** C13주차의 도구로 답하려면

$\mathbb{R}$과 $\mathbb{R}^2$ 사이의 전단사를 실제로 제작하거나 그런 것이 하나도 없음을 보여야 하는데, 둘 다 만만치 않다. 그 판단은 정확하다. 이번 주가 하는 일이 정확히 그 제작을 우회하는 길을 내는 것이고, 길이 나면 이 물음의 답은 네 줄로 끝난다.

## 개념 — 부등호를 놓는 법

### 1 전단사를 직접 만들려 하면 어디서 막히는가

새 도구를 꺼내기 전에, 지금 가진 도구 — 전단사의 직접 제작 — 만으로 준비 운동 4번을 밀어붙여 본다. C13주차 문제 13이 $|\mathbb{R}| = |(0,1)|$을 주므로 무대를 정사각형 $(0,1)^2$과 구간 $(0,1)$로 옮겨 놓고 시작한다.

:::{admonition} 시도 — 자리를 번갈아 엮어 전단사 만들기
:class: quotebox

물음: $(0,1)^2$과 $(0,1)$이 같은 크기인가.

"$x = 0.a_1a_2a_3\cdots$, $y = 0.b_1b_2b_3\cdots$의 자리를 번갈아 엮어

$h(x, y) = 0.a_1b_1a_2b_2a_3b_3\cdots$으로 정의하자.

서로 다른 쌍은 서로 다른 자리열을 주므로 겹침이 없다.

이제 빠짐이 없음을 보이면 $h$가 전단사이므로 … "
:::

여기서 멈춘다. 다음 줄이 나오지 않는다.

:::{container} quotebox
**확인 1.** 위 시도에서 $z = 0.190909\cdots$을 값으로 갖는 쌍 $(x, y)$를 실제로 찾아보자. 홀수 자리와 짝수 자리를 각각 모으면 무엇이 나오는가.
:::

:::{admonition} 답
:class: quotebox dropdown

홀수 자리를 모으면 $x = 0.1000\cdots = 0.1$이고, 짝수 자리를 모으면

$y = 0.999\cdots$이다. 그런데 $0.999\cdots$는 $1$과 같은 수이고 $1 \notin (0,1)$이므로,

이 $z$를 값으로 갖는 쌍이 무대 안에 없다. 곧 $h$는 **전사가 아니다.**

(C13주차 §1.6에서 십진 표기가 두 개인 수는 9의 꼬리 또는 0의 꼬리를 갖는

경우뿐임을 인정하고 썼다. 이번 주에도 각 실수의 십진 전개는 9의 꼬리가 없는

쪽으로 하나 고정한다. 그 약속 아래에서 $0.999\cdots$은 $(0,1)$ 원소의 전개로

등장하지 않는다.)

막힌 이유는 계산 실수가 아니다. 겹침 없음은 한 줄로 확보했는데 **빠짐 없음이

확보되지 않았고**, 빠뜨린 자리를 메우려면 대응 규칙을 처음부터 다시 설계해야 한다.
:::

:::{admonition} 이 주 전체의 기준
:class: quotebox

겹침 없음은 만들기 쉽고, 빠짐 없음은 만들기 어렵다.

그러므로 쉬운 쪽 둘로 어려운 쪽 하나를 대신할 수 있는지 묻는다.

그 물음에 답하는 것이 슈뢰더-번슈타인 정리다.
:::

### 2 사례를 모아 보기 — 무엇이 쉽고 무엇이 어려운가

네 쌍의 집합을 놓고 양쪽 방향의 단사와 전단사를 각각 떠올려 보자. 넷째 열은 "쉽다" 또는 "어렵다"로 채운다.

| **두 집합 $A$, $B$** | **단사 $A \to B$** | **단사 $B \to A$** | **전단사를 직접 만들기** |
|---|---|---|---|
| $\mathbb{N}$, $2\mathbb{N}$ | $n \mapsto 2n$ | $m \mapsto m$ | 쉽다 — 둘째 열의 함수가 이미 전단사다 (C13주차 예제 2.1) |
| $(0,1)$, $[0,1]$ | $x \mapsto x$ | $x \mapsto \frac{x+1}{3}$ | $\underline{\quad(1)\quad}$ |
| $\mathbb{N}$, $\mathbb{N} \times \mathbb{N}$ | $n \mapsto (n, 1)$ | $(m, n) \mapsto 2^m 3^n$ | $\underline{\quad(2)\quad}$ |
| $(0,1)^2$, $(0,1)$ | 자리 엮기 | $x \mapsto (x, \tfrac12)$ | $\underline{\quad(3)\quad}$ |

:::{container} quotebox
**확인 2.** 표의 (1)(2)(3)을 "쉽다" 또는 "어렵다"로 채우고 근거를 한 줄씩 적어 보자. 그리고 둘째$\cdot$셋째 열 여덟 칸에 공통된 것을 한 문장으로 적어 보자.
:::

:::{admonition} 답
:class: quotebox dropdown

(1) 어렵다 — C13주차 문제 19가 이 전단사를 만들었고, 규칙이 네 갈래로 갈렸다.

(2) 어렵다 — C13주차 문제 9의 대각선 나열은 "$(m,n)$이 몇 번째인가"를 식으로

적어야 검증이 가능했다.

(3) 어렵다 — §1.1의 시도가 실패했다.

여덟 칸의 공통점: **전부 한 줄짜리 식이고, 확인할 것이 겹침 없음 하나뿐이다.**

값이 무대에 들어가는지와 겹치지 않는지만 보면 되고, 무대를 덮는지는 묻지 않는다.
:::

이 관찰에 정식 이름과 기호를 붙인다. 식 자체에 새로운 것은 없다 — C13주차 정의 1.1이 요구하던 두 조건 가운데 **빠짐 없음(전사)만 지운 것**이다.

### 정의 1.1 — 기수 비교 (comparing cardinalities) [백지 암기 대상]

:::{container} quotebox
집합 $A$, $B$에 대해, $A$에서 $B$로의 **단사 $f : A \to B$가 존재하면**

$|A| \le |B|$로 쓴다.
:::

이 문장은 "에이의 기수는 비의 기수보다 크지 않다. 곧 에이에서 비로 가는 단사가 존재한다"로 읽는다. 읽는 법까지가 정의다.

:::{admonition} 표기 — $\le$ 의 좌우는 수가 아니다
:class: quotebox

$|A| \le |B|$의 좌우에 놓인 것은 집합의 기수이지 수가 아니다. 그러므로

$|B| - |A|$나 $|B| / |A|$ 같은 식은 뜻이 없고, 이 주차의 어느 답안에도 등장하지

않는다. 쓸 수 있는 것은 $\le$, $<$, $=$ 세 관계와 정의 1.1이 붙여 준 뜻뿐이다.

$A$가 유한집합일 때는 $|A|$가 원소의 개수라는 수를 뜻하기도 하지만, 무한집합의

$|A|$는 그 뜻을 갖지 않는다(C13주차 §1.1).
:::

### 정의 1.2 — 진부등호 $|A| < |B|$ (strict inequality of cardinalities) [백지 암기 대상]

:::{container} quotebox
$|A| \le |B|$이고 $|A| \ne |B|$일 때 $|A| < |B|$로 쓴다.

여기서 $|A| \ne |B|$는 "$A$에서 $B$로의 전단사가 **존재하지 않는다**"는 뜻이다

(C13주차 정의 1.1).
:::

정의 1.2를 쓰려면 두 가지를 각각 해야 한다 — 단사 하나를 **제시**하고, 전단사가 하나도 없음을 **배제**한다. 앞쪽은 한 줄이고 뒤쪽은 대개 대각선 논법이 필요하다. C13주차 §1.2 확인 2의 비대칭이 여기서도 그대로 작동한다.

### 3 정의 해부 — 조각마다 하는 일

정의 1.1은 세 조각으로 되어 있고, 조각마다 판정에서 맡는 역할이 다르다.

| **조각** | **하는 일** | **판정에서의 역할** |
|---|---|---|
| "단사" | 겹침 없음만 요구한다 | 전사 의무를 지운다 — 이 지움이 §1.1의 막힘이 풀리는 자리다 |
| "$f : A \to B$" | 방향을 고정한다 | 정의역 쪽이 "크지 않은" 쪽이다. 방향을 뒤집으면 반대 부등호가 된다 |
| "존재하면" | 하나면 충분하다 | 함수 하나를 제시하면 판정이 끝난다. 거꾸로, 실패한 함수 하나는 $\le$의 반증이 되지 않는다 |

:::{container} quotebox
**확인 3.** $|A| \le |B|$를 보이려고 한다. 만들어야 하는 것은 $A \to B$ 단사인가, $B \to A$ 단사인가. 헷갈리지 않을 기억 장치를 한 문장으로 만들어 보자.
:::

:::{admonition} 답
:class: quotebox dropdown

$A \to B$ 단사다. 기억 장치: **작은 쪽이 큰 쪽 안으로 들어간다** — 들어가는 쪽이

정의역이므로, 부등호에서 왼쪽에 적힌 집합이 정의역이다.

방향을 뒤집으면 전혀 다른 주장이 된다. $\mathbb{N} \to \mathbb{R}$ 단사는 쉽게

만들어지지만 $\mathbb{R} \to \mathbb{N}$ 단사는 존재하지 않는다(문제 2 (c)).
:::

**조각 삭제 실험 — "단사"를 지우면.** 첫째 조각을 지우고 "함수 $f : A \to B$가 존재하면 $|A| \le |B|$"로 두어 보자. 비어 있지 않은 두 집합 $A$, $B$에 대해 $b_0 \in B$를 하나 고정하고 모든 $a$를 $b_0$으로 보내는 상수함수를 잡으면 그것이 언제나 함수이므로, 어떤 두 집합에 대해서도 부등호가 성립한다.

:::{container} quotebox
**확인 4.** "단사"를 지우는 순간 정확히 무엇이 무너지는가. $A = \mathbb{R}$, $B = \mathbb{N}$으로 놓고 확인해 보자.
:::

:::{admonition} 답
:class: quotebox dropdown

상수함수 $f(x) = 1$이 $\mathbb{R} \to \mathbb{N}$ 함수이므로 $|\mathbb{R}| \le |\mathbb{N}|$이

되고, 같은 방식으로 $|\mathbb{N}| \le |\mathbb{R}|$도 되어 두 부등호가 동시에 성립한다.

그러면 §1.5의 정리를 붙이는 순간 $|\mathbb{R}| = |\mathbb{N}|$이 나오는데, 이것은

C13주차 예제 2.3과 정면으로 어긋난다.

곧 **모든 집합 쌍에 대해 부등호가 성립해 $\le$가 아무것도 구별하지 못한다.**

겹침 없음이라는 조각 하나가 이 붕괴를 막는 유일한 조건이다.
:::

:::{admonition} 표기 — 포함사상 $A \hookrightarrow B$
:class: quotebox

$A \subseteq B$일 때 $x \mapsto x$로 정의되는 단사를 **포함사상**이라 하고, 이 함수를

$A \hookrightarrow B$로 쓴다. "에이를 비 안으로 심는 포함사상"이라고 읽는다.

화살표에 갈고리를 단 것이 "겹침 없이 심는다"는 표시다. 이 기호는 함수 하나의

이름이므로, 답안에서는 $A \hookrightarrow B$라고 적은 뒤에도 식 $x \mapsto x$와

무대 확인 $A \subseteq B$를 그대로 적는다.
:::

### 4 순서처럼 행동하는가 — 두 성질은 이미 손에 있다

$\le$라는 기호를 빌려 썼으니 이 관계가 실제로 순서처럼 행동하는지 확인해야 한다. S7주차 문제 16에서 실수의 $\le$가 반대칭적임을 삼분법으로 확인했고, C11주차 문제 18에서 반사$\cdot$추이$\cdot$반대칭을 갖춘 관계를 부분순서라 불렀다. 세 성질을 차례로 본다.

:::{container} quotebox
**확인 5.** 다음 두 성질을 각각 한 줄로 증명해 보자.

(가) 반사: 임의의 집합 $A$에 대해 $|A| \le |A|$이다.

(나) 추이: $|A| \le |B|$이고 $|B| \le |C|$이면 $|A| \le |C|$이다.
:::

:::{admonition} 답
:class: quotebox dropdown

(가) 항등함수 $\mathrm{id}_A : A \to A$, $\mathrm{id}_A(a) = a$를 잡는다.

$\mathrm{id}_A(a_1) = \mathrm{id}_A(a_2)$이면 곧 $a_1 = a_2$이므로 단사이고,

정의 1.1에 의해 $|A| \le |A|$이다.

(나) 가정에서 단사 $f : A \to B$와 단사 $g : B \to C$를 받는다. C12주차 문제 8

(합성의 단사 보존)에 의해 $g \circ f : A \to C$가 단사이므로, 정의 1.1에 의해

$|A| \le |C|$이다. (이 논증을 부품 인용 없이 처음부터 적는 것이 문제 9다.)
:::

남은 것은 **반대칭**이다 — "$|A| \le |B|$이고 $|B| \le |A|$이면 $|A| = |B|$인가." 유한집합에서는 이 물음이 어렵지 않다. 원소의 개수라는 **수** $m$, $n$이 있고 $m \le n$과 $n \le m$에서 $m = n$을 얻는 데 쓰는 것이 실수 $\le$의 반대칭성 (S7주차 문제 16)이기 때문이다. 무한집합에는 경유할 그 수가 없다(C13주차 §1.1).

:::{container} quotebox
**확인 6.** 무한집합에서 반대칭을 보이려면 결국 무엇을 만들어야 하는가. 가정과 결론을 정의 1.1과 C13주차 정의 1.1로 각각 풀어서 답해 보자.
:::

:::{admonition} 답
:class: quotebox dropdown

가정이 주는 것은 단사 $f : A \to B$와 단사 $g : B \to A$ 두 개다(정의 1.1).

결론이 요구하는 것은 전단사 $h : A \to B$ 하나다(C13주차 정의 1.1).

곧 반대칭은 **단사 두 개를 재료로 전단사 하나를 제작하라**는 요구이며,

유한집합처럼 개수를 세어 우회할 길이 없다. 이 제작이 언제나 가능하다는 것이

다음 절의 정리이고, 그 제작 절차가 정리의 증명이다.
:::

### 5 슈뢰더-번슈타인 정리

§1.4가 남긴 물음은 하나다 — 서로 반대 방향의 단사 두 개를 재료로 전단사 하나를 제작할 수 있는가. 이 절은 그 제작이 언제나 가능하다는 것을 정리로 세운다. 그 보장이 서면 §1.2 표에서 "어렵다"로 채운 칸들이 둘째$\cdot$셋째 열의 한 줄짜리 식 두 개로 대체되고, 이번 주 답안의 마지막 줄은 거의 전부 이 정리의 인용이 된다.

### 정리 1.3 — 칸토어-슈뢰더-번슈타인 (Cantor-Schröder-Bernstein, CSB) [백지 암기 대상]

:::{container} quotebox
단사 $f : A \to B$와 단사 $g : B \to A$가 모두 존재하면, 전단사 $h : A \to B$가

존재한다. 곧 $|A| \le |B|$이고 $|B| \le |A|$이면 $|A| = |B|$이다.
:::

정리 1.3을 §1.4의 두 성질과 합치면 기수의 $\le$가 반사$\cdot$추이$\cdot$반대칭을 모두 갖춘다. C11주차 문제 18의 낱말로 말하면 이 관계는 부분순서처럼 행동하고, 유한집합에서 개수를 세어 얻던 세 성질이 무한 기수에서도 그대로 성립한다.

**증명은 이 과정에서 인정하고 쓴다.** 다만 무엇을 인정하는지는 알아 두어야 하므로 제작의 얼개만 적는다. 각 $a \in A$에서 출발해 $g^{-1}$과 $f^{-1}$을 번갈아 거슬러 올라가는 사슬을 만든다 — $a$가 $g$의 상에 있으면 $g^{-1}(a) \in B$로 한 칸 올라가고, 그것이 다시 $f$의 상에 있으면 또 한 칸 올라간다. 사슬은 셋 중 하나로 끝난다: $A$ 쪽에서 더 올라갈 수 없게 되거나, $B$ 쪽에서 더 올라갈 수 없게 되거나, 영원히 올라간다. 그러면 $h$를 이렇게 정한다 — 사슬이 $B$ 쪽에서 끝나는 $a$에는 $h(a) = g^{-1}(a)$를, 나머지 $a$에는 $h(a) = f(a)$를 준다. 이 $h$가 전단사임을 확인하는 것이 증명의 본체이고, 원서 11.5에 그 확인이 있다.

:::{container} quotebox
**확인 7.** 정리 1.3이 유한집합에서는 새로운 내용을 주지 않는 이유를 한 문장으로 적어 보자. 그리고 무한집합에서 새로운 내용이 되는 이유도 한 문장으로 적어 보자.
:::

:::{admonition} 답
:class: quotebox dropdown

유한집합에서는 $|A|$와 $|B|$가 원소의 개수라는 **수**이므로, 두 부등식에서 실수

$\le$의 반대칭성(S7주차 문제 16)으로 곧바로 개수가 같음이 나오고 전단사의 존재는

개수가 같다는 사실에서 따라온다.

무한집합에서는 경유할 수가 없으므로 두 단사에서 전단사를 실제로 제작하는 것

말고는 길이 없고, 그 제작이 언제나 가능하다는 것은 자명하지 않다.
:::

**이 정리가 하는 일.** 정리 1.3은 증명의 우회로를 낸다. $|A| = |B|$의 증명이 "전단사 하나 제작"에서 "단사 두 개 제작"으로 바뀌고, §1.2 표에서 확인한 대로 단사 쪽은 한 줄짜리 식으로 끝나는 경우가 많다. C13주차 문제 19가 네 갈래로 만든 전단사를 이번 주 예제 2.1이 두 줄로 대신하는 것이 그 첫 사례다.

### 6 절차 해부 — CSB 활용의 3단 서식

:::{admonition} 백지 암기 대상
:class: keybox

**CSB 활용의 3단 서식**

$|A| = |B|$를 정리 1.3으로 증명하려면 —

① **단사 $f : A \to B$ 제작** — 식을 명시하고, 값이 $B$에 들어감을 확인한 뒤 단사임을 증명한다. 이로써 $|A| \le |B|$.

② **단사 $g : B \to A$ 제작** — 같은 요령으로 반대 방향. 이로써 $|B| \le |A|$.

③ **정리 1.3 인용** — 두 부등식에 CSB를 적용해 $|A| = |B|$를 선언한다.

각 단사는 전사일 필요가 없다. 겹치지만 않으면 된다.
:::

세 걸음이 각각 다른 일을 한다. 하나를 빼면 무엇이 무너지는지가 그 걸음의 존재 이유다.

| **걸음** | **하는 일** | **이 걸음을 빼면 무엇이 무너지는가** |
|---|---|---|
| ① 단사 $f$ | $A$를 $B$ 안에 겹침 없이 심는다 | 한쪽 부등식이 없으면 상등이 나오지 않는다 — $\vert\mathbb{N}\vert \le \vert\mathbb{R}\vert$만으로는 아무 결론도 얻지 못한다 |
| ② 단사 $g$ | $B$를 $A$ 안에 겹침 없이 심는다 | 같은 이유로 반쪽이다. 아래 삭제 실험의 답안이 정확히 이 결함을 갖는다 |
| ③ 정리 인용 | 두 부등식을 상등으로 승격한다 | 전단사의 존재를 주장할 근거가 없다. 두 부등식만으로는 C13주차 정의 1.1의 조건이 채워지지 않는다 |
| (각 걸음 안) 단사 검증 | 겹침 없음을 실제로 보인다 | 뭉개는 대응이 통과해 거짓 결론이 나온다 — 문제 10의 답안이 이것이다 |

**걸음 삭제 실험 — ②를 빼면.** 반대쪽 단사를 만들 의무를 지우면 다음 답안이 합법이 된다.

:::{admonition} 삭제 실험 — 한쪽 단사만 만든 답안
:class: quotebox

명제: $|\mathbb{N}| = |\mathbb{R}|$.

"$f : \mathbb{N} \to \mathbb{R}$을 $f(n) = n$으로 정의한다. $f(n_1) = f(n_2)$이면

곧 $n_1 = n_2$이므로 $f$는 단사이고, 따라서 $|\mathbb{N}| \le |\mathbb{R}|$이다.

그러므로 두 집합은 같은 크기이다."
:::

:::{container} quotebox
**확인 8.** 위 답안에서 계산이 틀린 줄이 있는가. 없다면 무엇이 잘못되었는가. 빠진 걸음을 실제로 수행하려 하면 어디서 막히는가.
:::

:::{admonition} 답
:class: quotebox dropdown

계산은 한 줄도 틀리지 않았다. $f(n) = n$은 실제로 단사이고 $|\mathbb{N}| \le |\mathbb{R}|$은

참이다. 잘못된 것은 **걸음 ②가 통째로 빠졌다**는 것이고, 마지막 줄의 "그러므로"가

근거 없이 놓였다.

걸음 ②를 수행하려면 단사 $g : \mathbb{R} \to \mathbb{N}$을 만들어야 하는데,

그런 함수는 존재하지 않는다. 존재한다면 이 답안의 $f$와 함께 정리 1.3에 넣어

$|\mathbb{N}| = |\mathbb{R}|$을 얻게 되고, 그것은 C13주차 예제 2.3과 모순이기 때문이다.

곧 걸음 ②는 형식적 절차가 아니라 **명제의 진위를 가르는 걸음**이다.

이 논증 자체가 문제 2 (c)의 풀이가 된다 — 정리 1.3은 상등을 세울 때만이 아니라

단사의 비존재를 보일 때도 쓰인다.
:::

### 7 무한 기수의 산술 — 부품 목록

앞으로의 증명은 매번 밑바닥부터 시작하지 않는다. 아래 여섯 줄을 부품으로 인용하되, 인용할 때는 반드시 출처를 밝힌다.

:::{admonition} 표기 — $\aleph_0$ 와 $\mathfrak{c}$
:class: quotebox

$|\mathbb{N}|$을 $\aleph_0$로 쓰고 "알레프 영"이라고 읽는다. $|\mathbb{R}|$은

$\mathfrak{c}$로 쓰고 "연속체"라고 읽는다(C13주차 §1.4). 이번 주부터 두 기호

사이에 $\le$와 $<$를 놓을 수 있다 — 정의 1.1과 1.2가 그 뜻을 정했기 때문이다.

기수의 덧셈 $\kappa + \lambda$는 서로소인 두 집합의 합집합의 기수를, 곱셈

$\kappa \cdot \lambda$는 곱집합의 기수를 뜻한다. 서로소라는 조건이 덧셈 쪽에

붙는 이유는 문제 17에서 다룬다.

두 연산 모두 기수를 대표하는 집합을 골라 계산하므로, 고른 집합이 달라져도 결과가

같아야 뜻이 선다. $|X| = |X'|$이고 $|Y| = |Y'|$이면 $|X \times Y| = |X' \times Y'|$이고,

두 쌍이 각각 서로소이면 $|X \cup Y| = |X' \cup Y'|$이다. 곧 두 정의는 대표원 선택에

의존하지 않는다. 이 두 사실은 지금은 인정하고 쓴다 — 검증은 주어진 두 전단사를

좌표별로, 또는 조각별로 붙이는 일이다.
:::

| **성질** | **진술** | **출처** |
|---|---|---|
| (Q1) | $\aleph_0 + \aleph_0 = \aleph_0$ | C13주차 문제 8 (서로소인 두 가산무한의 합집합) |
| (Q2) | $\aleph_0 \cdot \aleph_0 = \aleph_0$ | C13주차 문제 9, 그리고 이번 주 예제 2.2 |
| (Q3) | $\vert(0,1)\vert = \vert[0,1]\vert = \vert\mathbb{R}\vert = \mathfrak{c}$ | 이번 주 예제 2.1과 문제 13 |
| (Q4) | $\mathfrak{c} \cdot \mathfrak{c} = \mathfrak{c}$ | 이번 주 예제 2.3과 문제 19 |
| (Q5) | $\aleph_0 < \mathfrak{c}$ | 이번 주 문제 2 (b)($\aleph_0 \le \mathfrak{c}$) + C13주차 예제 2.3($\ne$) + 이번 주 정의 1.2 |
| (Q6) | 임의의 집합 $A$에 대해 $\vert A\vert < \vert\mathcal{P}(A)\vert$ | C13주차 문제 15 (칸토어 정리) |

(Q1)~(Q4)는 유한의 산술과 어긋난다 — 유한에서는 $n \ge 2$일 때 $n + n \ne n$이고 $n \cdot n \ne n$이다. 무한 기수에서 이 등식들이 성립하는 것은 계산 규칙이 달라져서가 아니라, 좌변과 우변 사이에 전단사가 실제로 존재하기 때문이다.

**연속체 가설.** (Q5)는 $\aleph_0 < \mathfrak{c}$를 주고, 문제 15는 $\mathfrak{c} = |\mathcal{P}(\mathbb{N})|$을 준다. 두 줄을 합치면 $\aleph_0 < |\mathcal{P}(\mathbb{N})|$이며, 이것은 (Q6)을 $A = \mathbb{N}$에 적용한 결과와 같다. 그러면 $\aleph_0$과 $\mathfrak{c}$ **사이에** 다른 기수가 있는가. 이 물음이 연속체 가설이고, 괴델과 코언은 표준 공리계 ZFC 안에서 이 문장이 증명될 수도 반증될 수도 없음을 보였다. 곧 연속체 가설은 아직 답이 나오지 않은 문제가 아니라 **공리계가 결정하지 않는 문제**이며, 1권 49주차 문제 19가 이 상태를 "참$\cdot$거짓$\cdot$미해결"에 더해지는 넷째 상태로 정리해 두었다. 같은 구분이 S19주차의 공리계 논의와 이어진다.

:::{container} quotebox
**확인 9.** 다음 두 주장 각각이 위 목록의 어느 줄에서 따라오는지, 또는 따라오지 않는지 적어 보자.

(가) $|\mathbb{Z} \times \mathbb{Z}| = \aleph_0$이다.

(나) $\aleph_0$과 $\mathfrak{c}$ 사이에 다른 기수가 없다.
:::

:::{admonition} 답
:class: quotebox dropdown

(가) 따라온다. $\mathbb{Z}$가 가산무한이므로(C13주차 예제 2.2) $|\mathbb{Z}| = \aleph_0$이고,

(Q2)에 의해 $|\mathbb{Z} \times \mathbb{Z}| = \aleph_0 \cdot \aleph_0 = \aleph_0$이다.

곱집합의 기수가 대표원 선택에 의존하지 않는다는 것은 §1.7의 표기 상자에서

인정하고 쓰기로 한 사실이며, $\mathbb{N}$ 대신 $\mathbb{Z}$를 대표로 놓을 수 있는

근거가 그것이다.

(나) 따라오지 않는다. 이것이 연속체 가설이며 목록의 어느 줄에서도 유도되지 않는다.

답안에 근거로 쓸 수 없는 문장이라는 점이 중요하다 — 참이라고 적어도 거짓이라고

적어도 근거가 없다.
:::

### 8 이번 주에 쓸 수 있는 근거 — 목록 갱신

허용 목록은 1권 이래 네 줄이다: ① 정의 ② 닫힘성 ③ 등식$\cdot$부등식의 성질 ④ 이미 증명한 명제. 이번 주가 채우는 것은 ①과 ④다.

| **근거** | **이번 주에 추가$\cdot$갱신되는 것** | **이번 주에는 이렇게 쓴다** |
|---|---|---|
| ① 정의 | **정의 1.1, 1.2** | "$\vert A\vert \le \vert B\vert$" $\leftrightarrow$ "단사 $A \to B$가 존재" 사이를 번역한다 |
| ② 닫힘성 | 변화 없음 | 정수$\cdot$유리수$\cdot$실수의 사칙 결과가 그 세계에 남음을 별도 설명 없이 쓴다 |
| ③ 등식$\cdot$부등식의 성질 | 변화 없음 | $\frac{x_1+1}{3} = \frac{x_2+1}{3}$에서 $x_1 = x_2$를 얻는 것이 단사 증명의 본체다 |
| ④ 이미 증명한 명제 | **정리 1.3(CSB — 인정하고 쓴다, 원서 11.5)** $\cdot$ 합성의 단사 보존(C12주차 문제 8) $\cdot$ C13주차의 정의 1.1~1.3과 예제 2.1~2.3, 문제 2$\cdot$8$\cdot$9$\cdot$11$\cdot$13$\cdot$14$\cdot$15$\cdot$19 $\cdot$ 십진 표기가 두 개인 수는 9 또는 0의 꼬리를 갖는 경우뿐(인정하고 쓴다 — C13주차 §1.6) $\cdot$ 소인수분해의 유일성(인정하고 쓴다 — C15주차에서 증명한다. 이번 주에는 예제 2.2처럼 홀짝 논증으로 대신할 수도 있다) $\cdot$ 아크탄젠트가 $\mathbb{R}$에서 순증가하며 치역이 $(-\frac\pi2, \frac\pi2)$임(인정하고 쓴다 — C13주차 §1.8과 같은 처리; 문제 13) $\cdot$ 서로 다른 두 실수 사이에 유리수가 있음(인정하고 쓴다; 문제 15) $\cdot$ 기수의 덧셈$\cdot$곱셈이 대표원 선택에 의존하지 않음(인정하고 쓴다 — §1.7 표기 상자) $\cdot$ 홀수끼리의 곱은 홀수(1권 1주차 문제 8; 인수가 여럿이면 귀납으로 반복 적용한다) $\cdot$ 자연수의 비어 있지 않은 부분집합에 최소원소가 있음(1권 33주차 최소원리; 문제 12) $\cdot$ 합동과 그 곱 보존(C6주차 정의 6.2와 예제 2.2; 훈련 3 해설) | "C13주차 문제 9에 의해"처럼 출처를 대고 한 줄로 끝낸다 |

목록 밖의 것은 이번 주에도 근거가 되지 않는다. 특히 **"차원이 높으니까 크다"와 "둘 다 비가산이니까 같다"는 근거가 아니다** — 전자는 예제 2.3이, 후자는 (Q6)이 반례다.

:::{container} quotebox
**확인 10.** 어떤 답안에 다음 세 문장이 나왔다. 각각 허용되는가. 허용된다면 몇 번 근거인가.

(가) "평면은 직선보다 차원이 높으므로 $|\mathbb{R}| < |\mathbb{R}^2|$이다."

(나) "$f : A \to B$와 $g : B \to C$가 단사이므로 $g \circ f$도 단사이다."

(다) "두 단사가 있으므로 $|A| = |B|$이다."
:::

:::{admonition} 답
:class: quotebox dropdown

(가) 불허 — 목록 밖이다. 차원은 크기의 판정 기준이 아니며, 예제 2.3이 실제로

$|\mathbb{R}| = |\mathbb{R}^2|$를 증명한다.

(나) 허용 — 근거 ④. C12주차 문제 8이 출처다. 이 한 줄이 §1.4 추이성의 본체다.

(다) 허용 — 근거 ④, 정리 1.3. 다만 "두 단사"가 **서로 반대 방향**임을 답안에

명시해야 한다. 방향이 같은 단사 두 개는 정리 1.3의 가정이 아니다.
:::