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

## 예제 — 대등 증명을 함께 만들기

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

### 예제 2.1 — 부분과 전체: $|\mathbb{N}| = |E|$

**명제.** $E = \{2, 4, 6, \dots\}$에 대해 $|\mathbb{N}| = |E|$이다.

**설계 — 쓰기 전에 정하는 두 가지.** 가정이 주는 것(출발점)과 만들 것(도착점)을 정의 48.1로 번역해 먼저 적는다.

|  | **말** | **수식 번역** |
|---|---|---|
| 가정 (주어진 것) | 두 집합 $\mathbb{N}$, $E$가 무엇인지 | $E$의 원소는 $2k$ ($k \in \mathbb{N}$) 꼴 — 짝수의 정의 |
| 목표 (만들 것) | $\vert \mathbb{N} \vert = \vert E \vert$ | $\underline{\quad(?)\quad}$를 하나 제시하고 검증한다 |

:::{container} quotebox
**확인 8.** 목표 칸의 빈칸을 채워 보자. 그리고 이 문제에서 가정이 주는 정보가

사실상 없는 이유를 한 문장으로 적어 보자.
:::

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

목표: **전단사 $f : \mathbb{N} \to E$**를 하나 제시하고 단사와 전사를 각각 검증한다.

가정 쪽이 비어 있는 이유는 명제에 "~이면"이 없기 때문이다 — 조건 명제가 아니라

존재 주장이므로, 26주차의 서식대로 할 일은 증인의 제작과 검증뿐이다.
:::

**1단계 — 규칙을 정한다.** 무엇을 무엇에 짝지을지 정한다. §1.2의 표에서 이미 후보가 나왔다: $n$에게 $2n$을 준다.

:::{container} quotebox
**확인 9.** 첫 문장을 완성해 보자:

"$f : \mathbb{N} \to E$를 $f(n) = \underline{\quad}$로 정의하자."

이 규칙의 출력이 정말 $E$ 안에 있는지도 한 줄로 확인해 보자.
:::

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

$f(n) = 2n$. 출력 확인: $n \in \mathbb{N}$이면 $2n$은 양의 짝수이므로 $2n \in E$이다.

이 확인이 빠지면 공역 밖으로 나가는 규칙이 되어(40주차) 아래의 검증이 무의미해진다.
:::

**2단계 — 단사를 검증한다.** 41주차의 서식은 "$f(a) = f(a')$이라 하고 $a = a'$을 이끈다"이다.

:::{container} quotebox
**확인 10.** 둘째 문장을 완성해 보자:

"(단사) $f(a) = f(a')$이라 하자. 그러면 $\underline{\quad} = \underline{\quad}$이고,

양변을 2로 나누면 $\underline{\quad}$이다."
:::

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

$2a = 2a'$이고 양변을 2로 나누면 $a = a'$이다(근거 ③) — 같은 짝을 받았다면 애초에

같은 수였다는 뜻이고, §1.2의 조건 ①이다.
:::

**3단계 — 전사를 검증한다.** 41주차의 서식은 "공역의 임의의 원소 $m$을 잡고 $f(k) = m$인 정의역 원소 $k$를 제작한다"이다.

:::{container} quotebox
**확인 11.** 셋째 문장을 완성해 보자:

"(전사) $m \in E$라 하자. $m$은 양의 짝수이므로 $m = \underline{\quad}$인

$k \in \mathbb{N}$가 존재하고, 이 $k$에 대해 $f(k) = \underline{\quad}$이다."

여기서 $k$가 자연수임을 보장하는 것은 무엇인가.
:::

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

$m = 2k$인 $k \in \mathbb{N}$가 존재하고 $f(k) = 2k = m$이다. $k$가 자연수인 것은 $E$의

원소가 "양의 짝수"이기 때문이다 — 짝수의 정의(근거 ①)가 정수성을, "양"이 $k \ge 1$을

준다. 증인 $k$를 제시하는 이 한 줄이 전사 증명의 전부다.
:::

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

:::{container} quotebox
**확인 12.** 마지막 문장을 완성해 보자:

"따라서 $f$는 $\underline{\quad}$이고, 정의 48.1에 의해 $\underline{\quad}$이다. $\blacksquare$"
:::

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

"따라서 $f$는 **전단사**이고, 정의 48.1에 의해 $|\mathbb{N}| = |E|$이다. $\blacksquare$" —

단사와 전사를 각각 확인한 뒤 그 존재를 정의에 넘겨 결론을 얻는다.
:::

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

| 증명의 한 줄 | 왜 이 줄을 쓰는가? |
|---|---|
| $f : \mathbb{N} \to E$를 $f(n) = 2n$으로 정의하자. $n \in \mathbb{N}$이면 $2n$은 양의 짝수이므로 $f$의 값은 $E$ 안에 있다. | 대등 증명은 증인(전단사) 제작이다(26주차 존재 서식). 규칙을 세우고 공역 안에 머무는지부터 확인한다. |
| (단사) $f(a) = f(a')$이라 하자. 그러면 $2a = 2a'$이므로 $a = a'$이다. | 41주차 단사 서식. 등식의 성질(근거 ③)만으로 닫힌다. |
| (전사) $m \in E$라 하자. $m$은 양의 짝수이므로 $m = 2k$인 $k \in \mathbb{N}$가 존재하고, $f(k) = 2k = m$이다. | 41주차 전사 서식. 증인 $k$를 짝수의 정의(근거 ①)에서 꺼내 제시한다. |
| 따라서 $f$는 전단사이고, 정의 48.1에 의해 $\vert \mathbb{N} \vert = \vert E \vert$이다. $\blacksquare$ | 정의 충족을 선언하며 마무리한다. |

**이 네 줄이 무한 개의 짝을 처리하는 이유.** $n$ 자리에 구체적인 수를 넣어 읽어 보자. $n = 7$이면 짝은 14이고 $m = 138$이면 증인은 $k = 69$다 — 어느 값을 넣어도 그대로 성립한다.

:::{container} quotebox
**확인 13.** 이 증명에서 $n$과 $k$에 대해 실제로 사용된 정보는 무엇인가.

(가) 구체적인 값  (나) "자연수이다"라는 자격뿐
:::

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

(나). 어느 줄도 $n$이나 $k$가 특정 수라는 사실을 쓰지 않았고 쓴 것은 자격뿐이다.

그래서 네 줄짜리 증명 하나가 무한히 많은 짝을 한 번에 확정한다. 준비 운동 유형 1이

"절반"이라고 답할 때 빠져 있던 것이 이 짝짓기다 — 짝이 하나도 남지 않는다.
:::

### 예제 2.2 — $|\mathbb{N}| = |\mathbb{Z}|$

**명제.** $|\mathbb{N}| = |\mathbb{Z}|$이다.

이번에는 설계만 함께 하고 본문은 완성본으로 본다. 쓸 함수는 41주차 문제 16의 것이다.

$$
\begin{aligned}f(n) = \begin{cases} \frac{n}{2} & (n \text{ 짝수}) \\ -\frac{n-1}{2} & (n \text{ 홀수}) \end{cases}\end{aligned}
$$

:::{container} quotebox
**확인 14.** 번역표를 채워 보자.

목표: $|\mathbb{N}| = |\mathbb{Z}|$ $\to$ $\underline{\quad}$를 제시하고 $\underline{\quad}$와 $\underline{\quad}$를 검증한다.

그리고 $f(1), \dots, f(6)$을 계산해 출력이 $\mathbb{Z}$를 훑는 순서를 확인해 보자.
:::

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

전단사 $f : \mathbb{N} \to \mathbb{Z}$를 제시하고 단사와 전사를 검증한다.

$f(1) = 0$, $f(2) = 1$, $f(3) = -1$, $f(4) = 2$, $f(5) = -2$, $f(6) = 3$ — 출력이 $0$에서

양쪽으로 번갈아 퍼진다. 양방향으로 무한한 $\mathbb{Z}$를 한 방향으로 무한한 줄로

다시 세우는 것이 이 함수의 전부다.
:::

:::{container} quotebox
**확인 15.** 단사 검증에서 첫 관문은 "$f(a) = f(a')$이면 $a$와 $a'$의 홀짝이 같다"이다.

이것을 무엇으로 보이는가.
:::

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

**부호**로 보인다. $n$이 짝수면 $f(n) = \frac n2 > 0$, 홀수면 $f(n) = -\frac{n-1}{2} \le 0$

이므로 두 값 범위가 겹치지 않는다. 따라서 $f(a) = f(a')$이면 홀짝이 같고, 홀짝이

같으면 같은 식을 쓰므로 그 뒤는 등식 계산이다.
:::

**완성본.**

| 증명의 한 줄 | 왜 이 줄을 쓰는가? |
|---|---|
| $f : \mathbb{N} \to \mathbb{Z}$를 위 규칙으로 정의하자. 짝수 입력은 양의 정수를, 홀수 입력은 0 이하의 정수를 내놓으므로 값은 $\mathbb{Z}$ 안에 있다. | 규칙 제시와 공역 확인. 두 갈래 규칙이므로 각 갈래의 출력 범위를 따로 본다. |
| (단사) $f(a) = f(a')$이라 하자. 짝수 입력의 값은 양수, 홀수 입력의 값은 0 이하이므로 $a$와 $a'$은 홀짝이 같다. | 케이스가 섞이는 것을 먼저 차단한다 — 부호가 그 차단벽이다. |
| 둘 다 짝수면 $\frac a2 = \frac{a'}2$에서 $a = a'$이고, 둘 다 홀수면 $-\frac{a-1}2 = -\frac{a'-1}2$에서 $a = a'$이다. | 같은 갈래 안에서는 등식 계산만 남는다(근거 ③). |
| (전사) $m \in \mathbb{Z}$라 하자. $m > 0$이면 $k = 2m$이 짝수이고 $f(k) = m$이다. $m \le 0$이면 $k = 1 - 2m$이 홀수이고 $f(k) = -\frac{(1-2m)-1}{2} = m$이다. | 증인 제작. 목표값의 부호에 따라 어느 갈래에서 증인을 꺼낼지가 정해진다. |
| 따라서 $f$는 전단사이고 $\vert \mathbb{N} \vert = \vert \mathbb{Z} \vert$이다. $\blacksquare$ | 정의 48.1 충족 선언. |

목록으로 적으면 $0, 1, -1, 2, -2, 3, -3, \dots$이고, 이 목록이 문제 6과 15의 재료가 된다.

### 예제 2.3 — 격자 행진: $\mathbb{Q}^+$는 가산 무한

**명제.** 양의 유리수 전체 $\mathbb{Q}^+$는 가산 무한이다.

이번에는 설계부터 스스로 해 보자. $\mathbb{Q}^+$에는 $f(n) = 2n$ 같은 간단한 수식이 보이지 않으므로 §1.5의 목록 판정표를 쓴다.

:::{container} quotebox
**확인 16.** 목록으로 증명하려 한다. 무엇을 만들고 무엇을 확인해야 하는가.

§1.5의 표를 보고 세 줄로 적어 보자.
:::

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

만들 것: $\mathbb{Q}^+$의 원소를 한 줄로 늘어놓는 순서. 확인할 것: ① 모든 양의

유리수가 등장한다(빠짐 없음) ② 같은 유리수가 두 번 등장하지 않는다(겹침 없음)

③ 각 원소의 등장 순번이 유한하다.
:::

**행진의 설계.** $(p, q)$ 칸에 분수 $\frac pq$를 적은 격자를 생각한다 ($p, q \in \mathbb{N}$). 모든 양의 유리수는 기약분수 꼴로 이 격자 어딘가에 등장한다. 이 격자를 한 줄로 훑어야 하는데, 가로줄을 하나씩 훑는 방식은 첫 줄이 끝나지 않아 둘째 줄에 도달하지 못한다. $p + q$가 일정한 대각선은 유한하므로 대각선을 $p+q = 2, 3, 4, \dots$ 순으로 훑는다.

| **$p+q$** | **그 대각선의 칸** | **적힌 분수** |
|---|---|---|
| 2 | $(1,1)$ | $\frac11$ |
| 3 | $(1,2), (2,1)$ | $\frac12, \frac21$ |
| 4 | $(1,3), (2,2), (3,1)$ | $\frac13, \frac22, \frac31$ |
| 5 | $(1,4), (2,3), (3,2), (4,1)$ | $\frac14, \frac23, \frac32, \frac41$ |

:::{container} quotebox
**확인 17.** 위 순서를 그대로 목록으로 삼으면 세 조건 중 어느 것이 깨지는가.

구체적인 예를 하나 들어 보자.
:::

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

② 겹침 없음이 깨진다. $\frac22$는 $\frac11$과 같은 유리수인데 두 번째로 다시 등장한다.

유리수는 분수들의 동치류이고(37주차 예제 2.3), 격자는 그 동치류의 **대표**를 여러 번

적어 두었기 때문이다. 처방은 하나 — 이미 목록에 나온 값이면 건너뛴다.
:::

**논증.** 격자의 $(p, q)$ 칸에 $\frac pq$를 적고, 대각선을 $p+q = 2, 3, 4, \dots$ 순으로 행진하며 각 대각선 안에서는 $p$가 작은 칸부터 방문하되 **이미 목록에 나온 값은 건너뛴다**. 이렇게 만든 목록을 $r_1, r_2, r_3, \dots$이라 하자. 빠짐이 없다: 임의의 양의 유리수는 어떤 칸 $(p,q)$에 적혀 있고 그 칸은 $p+q$번째 대각선에 있으므로 유한 단계 안에 방문된다. 겹침이 없다: 같은 값이 다시 나오면 건너뛰기 규칙이 배제한다. 순번이 유한하다: 각 대각선의 칸 수가 유한하므로 $(p,q)$ 이전에 방문되는 칸의 총수도 유한하다. 따라서 $n \mapsto r_n$은 $\mathbb{N}$에서 $\mathbb{Q}^+$로의 전단사이고 $\mathbb{Q}^+$는 가산 무한이다. $\blacksquare$

이번 논증은 표 없이 산문으로 적었다. 표는 연습 단계의 장치이고, 실전의 증명은 이런 산문이다.

유리수는 수직선에 조밀하게 깔려 있는데도(15주차 문제 17) $\mathbb{N}$과 대등하다. 조밀함과 크기는 서로 다른 개념이고, 이 사실은 다음 주에 "빽빽하니까 목록이 불가능하다"는 논증을 반박하는 데 그대로 쓰인다.

음수와 0까지 포함한 $\mathbb{Q}$ 전체는 이 목록 $r_1, r_2, \dots$을 재료로 문제 15에서 완성한다.

### 관찰 — 세 증명의 같은 뼈대

예제 2.1, 2.2, 2.3은 소재가 다르지만 뼈대가 같다. 대응표의 빈칸을 채워 보자.

:::{container} quotebox
**확인 18.** 각 예제에서 다음 세 단계에 해당하는 부분을 찾아 보자.

① 규칙 제시: 예제 2.1은 $f(n) = 2n$, 예제 2.3은 $\underline{\qquad}$

② 겹침 없음: 예제 2.1은 단사 검증, 예제 2.3은 $\underline{\qquad}$

③ 빠짐 없음: 예제 2.1은 전사 검증, 예제 2.3은 $\underline{\qquad}$
:::

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

① 대각선을 $p+q$ 순으로 행진하며 이미 나온 값은 건너뛰는 순서 ② 건너뛰기 규칙

③ 임의의 칸이 유한 단계 안에 방문된다는 확인.

예제 2.2도 같다 — ① 두 갈래 규칙 ② 부호로 케이스를 가른 뒤의 등식 계산

③ 부호별 증인 제작. 세 증명 모두 정확히 이 세 걸음이다.
:::

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

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

**대등 증명의 3단계 틀**

① 짝짓기 규칙(함수 또는 목록의 순서)을 제시하고 값이 공역 안에 있는지 확인한다 $\to$ ② 겹침 없음(단사)을 검증한다 $\to$ ③ 빠짐 없음(전사)을 검증하고 정의 48.1로 결론을 선언한다
:::

이 틀은 다음 주에 "이 틀을 만족하는 목록이 존재할 수 없는 집합"을 만날 때 기준선이 된다.

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

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

### 훈련 1 ●○○ — 수식 빈칸

**명제.** $O = \{1, 3, 5, \dots\}$(양의 홀수 전체)에 대해 $|\mathbb{N}| = |O|$이다.

**증명.** $f : \mathbb{N} \to O$를 $f(n) = \underline{\quad(1)\quad}$로 정의하자. $n \ge 1$이므로 $f(n) \ge 1$이고 $f(n)$은 홀수이므로 값은 $O$ 안에 있다. (단사) $f(a) = f(a')$이면 $2a - 1 = 2a' - 1$이고, 양변에 1을 더한 뒤 2로 나누면 $\underline{\quad(2)\quad}$이다. (전사) $m \in O$라 하자. $m$은 양의 홀수이므로 $m = 2k - 1$인 $k \in \mathbb{N}$가 존재하고($k = \frac{m+1}{2}$), $f(k) = \underline{\quad(3)\quad}$이다. 따라서 $f$는 전단사이고 $|\mathbb{N}| = |O|$이다. $\blacksquare$

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

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

**명제.** $M = \{0, -1, -2, -3, \dots\}$에 대해 $|\mathbb{N}| = |M|$이다.

**증명.** $f : \mathbb{N} \to M$을 $f(n) = \underline{\quad(1)\quad}$로 정의하자. $n \ge 1$이므로 $f(n) \le 0$이고, 따라서 값은 $M$ 안에 있다. (단사) $f(a) = f(a')$이라 하자. 그러면 $\underline{\quad(2)\quad}$이고, $\underline{\quad(3)\quad}$에 의해 $a = a'$이다. (전사) $m \in M$이라 하자. $k = \underline{\quad(4)\quad}$로 두면 $m \le 0$이므로 $k \ge 1$, 곧 $k \in \mathbb{N}$이고 $f(k) = \underline{\quad(5)\quad}$이다. 따라서 $f$는 $\underline{\quad(6)\quad}$이고, $\underline{\quad(7)\quad}$에 의해 $|\mathbb{N}| = |M|$이다. $\blacksquare$

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

이번에는 3단계 틀의 각 칸을 통째로 채운다.

**명제.** $|E| = |O|$이다 ($E$는 양의 짝수 전체, $O$는 양의 홀수 전체).

**증명의 뼈대.**

- ① 규칙 제시와 공역 확인: $\underline{\quad(1)\quad}$
- ② 겹침 없음(단사): $\underline{\quad(2)\quad}$
- ③ 빠짐 없음(전사)과 결론: $\underline{\quad(3)\quad}$

(직접 전단사를 만드는 길과 예제 2.1$\cdot$훈련 1을 추이성으로 잇는 길이 모두 있다. 이 훈련이 문제 8(이미 놓인 두 다리를 추이성으로 잇기)의 예행연습이다.)

## 연습문제 (20문항)

해설을 보기 전에 문제당 최소 10분 스스로 시도한다. 막히면 곧바로 풀이를 읽지 말고 해설의 '접근'까지만 읽고 다시 시도한다 $\to$ 그래도 안 되면 풀이를 읽는다. 증명 문제는 3단계 틀(§2 관찰)의 세 칸을 먼저 적고 시작한다.

:::{admonition} 이번 주의 채점 기준
:class: quotebox

답이 아니라 **근거**가 점수다. "$|\mathbb{N}| = |E|$이다(맞음)"는 0점이고,

"$f(n) = 2n$이 전단사이므로 정의 48.1에 의해 대등하다 — 단사는 …, 전사는 …"이 만점이다.

목록으로 논증할 때는 빠짐 없음과 겹침 없음을 **각각** 한 줄로 적는다.

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

### 기본 ●○○

**1.** [백지] 대등($|A| = |B|$)과 가산의 정의를 쓰고, "가산 무한 = 목록화 가능"의 뜻을 한 문장으로 덧붙이시오.

:::{admonition} 힌트
:class: quotebox dropdown

정의 두 개를 조각까지 그대로 쓴다 — "전단사가 존재한다", "유한이거나 가산 무한".

마지막 문장은 §1.5 판정표의 세 줄을 압축한 것이다.
:::

**2.** $|\{1, 2, 3\}| = |\{a, b, c\}|$를 정의대로 증명하시오 (전단사 하나 제시 + 검증 — 유한도 같은 서식).

:::{admonition} 힌트
:class: quotebox dropdown

유한집합이라고 서식이 달라지지 않는다. 짝짓기를 순서쌍 목록으로 적은 뒤 함수 조건$\cdot$단사$\cdot$전사를 한 줄씩 확인한다.
:::

**3.** 빈칸 훈련($|\mathbb{N}| = |O|$)을 백지에서 완성하시오.

:::{admonition} 힌트
:class: quotebox dropdown

규칙은 $2n - 1$이다. 전사 검증에서 증인 $k = \frac{m+1}{2}$가 자연수인 이유를 한 줄로

적는다 — $m$이 홀수라는 가정이 거기서 일한다.
:::

**4.** 예제 2.1($|\mathbb{N}| = |E|$)을 백지에 재현하시오.

:::{admonition} 힌트
:class: quotebox dropdown

네 줄이다 — 규칙 제시와 공역 확인 / 단사 / 전사 / 결론. 전사 줄에서 증인 $k$가

어디서 나오는지(짝수의 정의)를 빼먹지 않는다.
:::

**5.** $|\mathbb{N}| = |\{5, 6, 7, 8, \dots\}|$임을 증명하시오 ($f(n) = n + 4$).

:::{admonition} 힌트
:class: quotebox dropdown

전사 검증에서 $m \ge 5$라는 조건이 증인 $m - 4$를 자연수로 만든다. 그 한 줄이 핵심이다.
:::

**6.** 예제 2.2($|\mathbb{N}| = |\mathbb{Z}|$)의 목록 첫 10항을 쓰고, $f(11), f(12)$를 계산하시오.

:::{admonition} 힌트
:class: quotebox dropdown

홀수 입력과 짝수 입력에 서로 다른 식을 쓴다(11은 홀수, 12는 짝수). 계산한 뒤에는

목록의 11번째$\cdot$12번째 자리와 일치하는지 대조한다.
:::

### 표준 ●●○

**7.** 대등이 동치관계처럼 행동함을 정리하시오: 반사$\cdot$대칭$\cdot$추이 각각의 증인(항등$\cdot$역함수$\cdot$합성)과 근거 주차를 명시하며 증명하시오.

**8.** $|\mathbb{Z}| = |E|$임을 두 가지 방법으로 논하시오: (a) 직접 전단사 구성 없이 — 추이성(문제 7)으로 $|\mathbb{Z}| = |\mathbb{N}| = |E|$ 연결 (b) 42주차 문제 15의 합성 릴레이 인용.

:::{admonition} 힌트
:class: quotebox dropdown

(a)는 예제 2.2에 대칭성을 먼저 적용해 방향을 $\mathbb{Z} \to \mathbb{N}$으로 돌리는 것이 첫

걸음이다. (b)는 그 두 다리를 실제로 합성해 하나의 명시적 함수를 적는다.
:::

:::{admonition} 새 무대 — 실수 구간
:class: quotebox

문제 9와 10은 정의역과 공역이 $\mathbb{N}$이나 $\mathbb{Z}$가 아니라 실수 구간이다.

서식은 바뀌지 않는다 — 단사는 여전히 "$f(a) = f(a')$에서 $a = a'$", 전사는 여전히

"증인 제작"이고, 달라지는 것은 검증의 재료가 등식 계산에서 **부등식 계산**으로

바뀐다는 점뿐이다. 증인을 만든 뒤 그것이 정의역 구간 안에 있는지 부등식으로

확인하는 줄이 하나 더 붙는다.
:::

**9.** $(0, 1)$과 $(0, 2)$가 대등함을 증명하시오 ($f(x) = 2x$ — 단사$\cdot$전사 검증. 길이가 두 배인 구간과 크기가 같다).

**10.** $(0, 1)$과 $(3, 7)$이 대등함을 증명하시오 (일차함수 $f(x) = 4x + 3$ 설계 — 치역 확인 포함).

:::{admonition} 힌트
:class: quotebox dropdown

계수 4와 상수 3의 출처를 먼저 확인한다 — 폭이 1에서 4로 늘어나므로 4배, 시작점이

0에서 3으로 옮겨 가므로 $+3$이다. 전사 증인은 이 식을 $x$에 대해 푼 것이다.
:::

**11.** 예제 2.3의 격자 행진에서 처음 10개의 **목록 항**(건너뛰기 반영)을 나열하시오.

:::{admonition} 힌트
:class: quotebox dropdown

대각선을 $p+q = 2, 3, 4, 5, 6$까지 차례로 적은 뒤 이미 나온 값과 같은 것을 지운다.

$\frac22$가 첫 번째 건너뛰기다.
:::

**12.** (힐베르트 호텔 1) 만실인 무한 호텔($n$호실 손님 $n$)에 새 손님 1명이 왔다. 전원 이동 규칙과, 그 규칙이 "모두 방을 가지고, 한 방에 한 명"임을 — 즉 $\mathbb{N} \to \{2, 3, 4, \dots\}$ 전단사임을 — 증명하시오.

:::{admonition} 힌트
:class: quotebox dropdown

"한 방에 한 명"이 단사, "모두 방을 가진다"가 전사로 번역된다. 규칙을 정한 뒤에는 문제 5와 같은 계산이다.
:::

**13.** (힐베르트 호텔 2) 이번엔 **무한 버스**(손님이 $\mathbb{N}$만큼)가 도착했다. 기존 손님과 새 손님 전원을 수용하는 규칙(기존 $\to$ 짝수 방, 새 손님 $\to$ 홀수 방)을 설계하고 정당화하시오.

:::{admonition} 힌트
:class: quotebox dropdown

두 규칙은 이미 증명한 것들이다 — 예제 2.1과 훈련 1. 남은 일은 짝수 방과 홀수 방이

서로소이고 합치면 전체라는 확인이다(17주차의 분할).
:::

**14.** 두 가산 무한 집합 $A = \{a_1, a_2, \dots\}$, $B = \{b_1, b_2, \dots\}$가 서로소이면 $A \cup B$도 가산 무한임을 교대 목록($a_1, b_1, a_2, b_2, \dots$)으로 논증하시오.

:::{admonition} 힌트
:class: quotebox dropdown

교대 목록에 번호를 붙여 식으로 적는다: $c_{2k-1} = a_k$, $c_{2k} = b_k$. 그 다음은

§1.5 판정표의 세 줄을 각각 확인한다 — "서로소"가 어느 줄에서 일하는지 지목한다.
:::

### 도전 ●●●

**15.** $\mathbb{Q}$ 전체(음수$\cdot$0 포함)가 가산임을 논증하시오. (예제 2.3의 $\mathbb{Q}^+$ 목록 $r_1, r_2, \dots$과 지그재그 결합: $0, r_1, -r_1, r_2, -r_2, \dots$ — 빠짐$\cdot$겹침 점검)

:::{admonition} 힌트
:class: quotebox dropdown

새 목록의 항에 번호를 붙인다: 1번은 0, $2k$번은 $r_k$, $2k+1$번은 $-r_k$. 임의의

유리수가 0$\cdot$양수$\cdot$음수 중 정확히 하나라는 것이 빠짐$\cdot$겹침 확인의 뼈대다.
:::

**16.** $|\mathbb{N} \times \mathbb{N}| = |\mathbb{N}|$임을 격자 행진으로 논증하시오 (이번엔 건너뛰기가 필요 없다 — 왜 $\mathbb{Q}^+$ 때와 다른지 한 문장 포함).

:::{admonition} 힌트
:class: quotebox dropdown

격자의 칸에 무엇이 적혀 있는지를 비교한다. 예제 2.3에서는 서로 다른 칸에 같은 값이

올 수 있었지만, 이번에는 칸 자체가 원소다.
:::

**17.** $(-1, 1)$과 $\mathbb{R}$가 대등함을 다음 함수로 논하시오: $f(x) = \dfrac{x}{1 - |x|}$. (a) $f(0), f(\frac12), f(-\frac12), f(0.9)$를 계산해 감을 잡고, (b) $g(y) = \dfrac{y}{1 + |y|}$가 역함수 후보임을 $g(f(x)) = x$ 계산(케이스: $x \ge 0$)으로 확인하시오 — **유한한 구간과 실수 전체가 같은 크기**.

:::{admonition} 힌트
:class: quotebox dropdown

(b)에서 $|f(x)|$를 없애는 것이 첫 관문이다. $x \ge 0$이면 $1 - x > 0$이므로 $f(x) \ge 0$,

따라서 $|f(x)| = f(x)$다. 그 다음은 분모를 통분해 정리하는 계산뿐이다.
:::

**18.** (진단) 다음 주장의 결함을 지적하시오.

:::{container} quotebox
"짝수 집합 $E$는 $\mathbb{N}$의 진부분집합이므로 $|E| < |\mathbb{N}|$이다 — 부분은 전체보다 작기 때문이다."

(유한 직관의 어느 정리(41주차 문제 17)가 무한에서 무너졌는가? 예제 2.1과 대조하라.)
:::

:::{admonition} 이 문제가 빌려 쓰는 사실 — 무한 번의 선택
:class: quotebox

문제 19의 논증은 "원소를 하나 뽑고, 또 하나 뽑고, …"를 무한히 반복한다.

이 반복을 한꺼번에 정당화하려면 **선택공리**라는 별도의 공리가 필요하다.

이 과정에서는 그 공리를 증명 없이 인정하고 쓴다 — 엄밀한 정당화는 대학

집합론으로 이월한다. 문제에서 요구하는 것은 "왜 멈추지 않는가"와

"왜 얻어진 집합이 가산 무한인가" 두 가지의 논증이다.
:::

**19.** "무한집합은 반드시 가산 무한 부분집합을 가진다"를 다음 스케치로 논증하시오: 무한집합 $A$에서 원소 $a_1$을 뽑고, 남은 것(여전히 무한 — 왜?)에서 $a_2$를 뽑고, … 이 과정이 멈추지 않는 이유와, 얻어진 $\{a_1, a_2, \dots\}$가 가산 무한인 이유를 쓰시오. (엄밀화에는 선택공리가 필요 — "고르기를 무한 번"의 정당화는 대학 집합론으로 이월한다는 논평 포함)

:::{admonition} 힌트
:class: quotebox dropdown

"멈추지 않는다"를 직접 보이려 하면 막힌다. 뒤집는다 — 어느 단계에서 멈춘다면 남은

집합이 공집합이고 그러면 $A$가 유한하므로(정의 48.3) 가정에 어긋난다.
:::

**20.** (서술) (a) "센다 = 짝짓는다"가 유한 세기의 본질이며 무한으로 일반화되는 유일한 길인 이유를 세 문장 이내로. (b) 유한 직관과 어긋나는 이번 주의 두 결과(부분=전체, 조밀한 $\mathbb{Q}$가 가산)를 보고도 "그럼 모든 무한은 가산"이라고 결론지으면 안 되는 이유 — 29주차의 언어로 — 를 한 문장으로 (다음 주 예고).

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

권장 일정 — 1~3일차: §0~§4 학습과 연습문제 / 4일차: 1차 재현 / 5일차: 완전 백지 재현. 한 번에 완전 백지로 가지 않는다.

**1차 시도 (4일차) — 틀 카드 허용.** 3단계 틀(§2 관찰)$\cdot$근거 목록(§1.7)$\cdot$목록 판정표(§1.5)만 펴 놓고 예제 2.1과 2.2를 끝까지 적는다. 정의와 본문은 보지 않는다.

**2차 시도 (5일차) — 완전 백지.** 아무것도 보지 않고 수행한다:

- [ ] 정의 48.1과 48.2를 조각 그대로 썼다 ("전단사가 존재한다", "유한이거나 가산 무한").
- [ ] $|\mathbb{N}| = |E|$와 $|\mathbb{N}| = |\mathbb{Z}|$를 전단사 서식으로 재현했다.
- [ ] 격자 행진의 순서와 건너뛰기 규칙을 그림으로 그리고, 왜 건너뛰기가 필요한지 말했다.
- [ ] 힐베르트 호텔 두 경우(+1명, +무한 버스)의 이동 규칙을 함수로 적었다.
- [ ] 대등의 반사$\cdot$대칭$\cdot$추이가 각각 어느 주차의 부품을 쓰는지 말했다.
- [ ] $\mathbb{Q}$가 조밀한데도 가산이라는 사실이 왜 모순이 아닌지 한 문장으로 답했다.

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

| **막힌 지점** | **처방** |
|---|---|
| 무엇을 만들어야 하는지 모르겠다 | 예제 2.1의 설계 — 목표를 "전단사 하나 제시"로 번역한다 |
| 함수는 적었는데 다음이 나오지 않는다 | §2 관찰의 3단계 틀 — ② 겹침 없음 ③ 빠짐 없음의 순서 |
| 전사 검증에서 증인이 안 나온다 | 예제 2.1의 3단계 — 목표값 $m$을 정의로 풀어 증인을 꺼낸다 |
| 목록 논증을 어디까지 써야 할지 모르겠다 | §1.5의 판정표 — 세 줄을 각각 한 문장씩 쓴다 |
| 케이스가 섞여 단사 증명이 막힌다 | 예제 2.2의 둘째 줄 — 부호로 케이스를 먼저 가른다 |
| 진부분집합인데 대등하다는 것이 받아들여지지 않는다 | §1.6과 확인 6 — 유한에서만 참인 문장을 지목한다 |

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

## 해설

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

### 빈칸 사다리 — 훈련 1

(1) $2n - 1$  (2) $a = a'$  (3) $2k - 1 = m$

※ (3)에서 증인 $k$가 자연수임을 보장하는 것은 $m$이 **양의 홀수**라는 조건이다 — $m = 2k-1 \ge 1$에서 $k \ge 1$이 나오고, 이 확인이 빠지면 전사 증명이 닫히지 않는다.

### 빈칸 사다리 — 훈련 2

(1) $1 - n$  (2) $1 - a = 1 - a'$  (3) 등식의 성질 (근거 ③ — 양변에서 1을 빼고 부호를 바꾼다) (4) $1 - m$  (5) $1 - (1 - m) = m$  (6) 전단사  (7) 정의 48.1

※ 규칙 $f(n) = 1-n$은 $1 \mapsto 0$, $2 \mapsto -1$, $3 \mapsto -2$로 간다. 증인이 $k = 1-m$인 이유는 $m = 1-k$를 $k$에 대해 푼 것이기 때문이다 — 전사 증인은 목표 등식을 정의역 문자에 대해 푼 결과라는 규칙이 여기서도 작동한다.

### 빈칸 사다리 — 훈련 3

(1) $f : E \to O$를 $f(m) = m - 1$로 정의하자. $m$이 양의 짝수이면 $m \ge 2$이므로 $m - 1 \ge 1$이고 $m-1$은 홀수이므로 값은 $O$ 안에 있다. (2) $f(a) = f(a')$이라 하자. 그러면 $a - 1 = a' - 1$이고 양변에 1을 더하면 $a = a'$이다(근거 ③). (3) $t \in O$라 하자. $k = t+1$로 두면 $k$는 2 이상의 짝수, 곧 $k \in E$이고 $f(k) = t$이다. 따라서 $f$는 전단사이고 정의 48.1에 의해 $|E| = |O|$이다. $\blacksquare$

※ 다른 길: 예제 2.1과 훈련 1에 대칭성$\cdot$추이성(문제 7)을 이어 $|E| = |\mathbb{N}| = |O|$로 끝내도 된다. 직접 구성은 명시적 함수를 얻고, 추이 논법은 줄 수가 적다.

### 문제 1

**접근.** 이번 주의 [백지 암기 대상]은 정의 두 개다. 통째로 외우기보다 §1.3의 조각별 역할과 함께 재구성한다.

**풀이.** 대등: 집합 $A$, $B$에 대해 전단사 $f : A \to B$가 존재하면 $A$와 $B$는 대등하다고 하고 $|A| = |B|$로 쓴다. 가산: $|A| = |\mathbb{N}|$인 집합을 가산 무한이라 하고, 유한집합이거나 가산 무한인 집합을 가산이라 한다(가산이 아니면 비가산). 목록화의 뜻: 전단사 $f : \mathbb{N} \to A$가 있다는 것은 $f(1), f(2), f(3), \dots$이 $A$의 원소를 빠짐없이(전사) 겹침 없이(단사) 훑고 모든 원소가 유한한 자리에 등장한다는 뜻이다.

**복기.** 자가 채점의 기준은 조각이다 — "존재한다"를 빠뜨리면 무엇을 제작해야 하는지가 사라지고, "유한집합이거나"를 빠뜨리면 유한집합이 가산에서 빠져 다음 주 정의 49.1(비가산)이 유한집합까지 비가산으로 분류하게 된다.

### 문제 2

**접근.** 유한집합이라고 서식이 달라지지 않는다. 새 정의가 옛 세기와 같은 답을 주는지 확인하는 문제이기도 하다.

**풀이.** $f : \{1,2,3\} \to \{a,b,c\}$를 $f = \{(1,a), (2,b), (3,c)\}$로 정의하자. 함수 조건: 정의역의 세 원소 각각에 값이 정확히 하나씩 배정되어 있다. 단사: 세 출력 $a, b, c$가 서로 다르므로 $f(x) = f(y)$인 서로 다른 $x, y$가 없다. 전사: 공역의 원소 $a, b, c$ 각각에 원상 $1, 2, 3$이 존재한다. 따라서 $f$는 전단사이고, 정의 48.1에 의해 $|\{1,2,3\}| = |\{a,b,c\}|$이다. $\blacksquare$

**복기.** 정의를 넓힐 때 옛 영역에서 결론이 바뀌지 않는지 검사하는 것이 표준 절차이고, 이 검사가 통과하지 못하면 §1.3의 삭제 실험처럼 정의를 고쳐야 한다.

### 문제 3

**접근.** 3단계 틀 그대로다. 규칙은 $2n-1$이고, 어려운 곳은 전사의 증인이 자연수임을 보이는 한 줄이다.

**풀이.** $f : \mathbb{N} \to O$를 $f(n) = 2n - 1$로 정의하자. $n \ge 1$이므로 $f(n) = 2n - 1 \ge 1$이고 $2n-1$은 홀수이므로 값은 $O$ 안에 있다. (단사) $f(a) = f(a')$이라 하자. $2a - 1 = 2a' - 1$이므로 양변에 1을 더하면 $2a = 2a'$, 2로 나누면 $a = a'$이다. (전사) $m \in O$라 하자. $m$은 양의 홀수이므로 $m = 2k - 1$인 정수 $k$가 존재하고, $m \ge 1$에서 $k = \frac{m+1}{2} \ge 1$이므로 $k \in \mathbb{N}$이다. 이 $k$에 대해 $f(k) = 2k - 1 = m$이다. 따라서 $f$는 전단사이고 $|\mathbb{N}| = |O|$이다. $\blacksquare$

**검산.** $f(1) = 1$, $f(2) = 3$, $f(3) = 5$ — 목록 $1, 3, 5, \dots$가 $O$를 순서대로 훑는다.

### 문제 4

**접근.** 예제 2.1의 네 줄을 재현한다. 채점 항목은 규칙 제시$\cdot$공역 확인$\cdot$단사$\cdot$전사이고, 전사에서 증인 $k$의 출처(짝수의 정의)를 적었는지가 갈림길이다.

**풀이.** $f : \mathbb{N} \to E$를 $f(n) = 2n$으로 정의하자. $n \in \mathbb{N}$이면 $2n$은 양의 짝수이므로 $f(n) \in E$이다. (단사) $f(a) = f(a')$이라 하자. $2a = 2a'$이므로 양변을 2로 나누면 $a = a'$이다. (전사) $m \in E$라 하자. $m$은 양의 짝수이므로 짝수의 정의에 의해 $m = 2k$인 정수 $k$가 존재하고, $m \ge 2$에서 $k \ge 1$이므로 $k \in \mathbb{N}$이다. 이 $k$에 대해 $f(k) = 2k = m$이다. 따라서 $f$는 전단사이고, 정의 48.1에 의해 $|\mathbb{N}| = |E|$이다. $\blacksquare$

**복기.** $E$가 $\mathbb{N}$의 진부분집합이라는 사실은 이 증명의 어느 줄에도 쓰이지 않았다 — 정의 48.1이 포함 관계를 묻지 않기 때문이고, 문제 18의 결함이 이 지점의 오해다.

### 문제 5

**접근.** 규칙이 주어져 있으므로 할 일은 검증뿐이다. 전사에서 $m \ge 5$가 증인 $m-4$를 자연수로 만든다.

**풀이.** $f : \mathbb{N} \to \{5,6,7,\dots\}$를 $f(n) = n + 4$로 정의하자. $n \ge 1$이면 $n + 4 \ge 5$이므로 값은 공역 안에 있다. (단사) $f(a) = f(a')$이라 하자. $a + 4 = a' + 4$이므로 양변에서 4를 빼면 $a = a'$이다. (전사) $m \in \{5,6,7,\dots\}$이라 하자. $k = m - 4$로 두면 $m \ge 5$이므로 $k \ge 1$, 곧 $k \in \mathbb{N}$이고 $f(k) = (m-4) + 4 = m$이다. 따라서 $f$는 전단사이고 $|\mathbb{N}| = |\{5,6,7,\dots\}|$이다. $\blacksquare$

**복기.** 이 함수는 문제 12의 이동 규칙 $n \mapsto n+1$을 네 칸으로 늘린 것이다. "밀기"는 단사이면서 전사가 아닌 표준 예이며, 공역을 밀린 자리에 맞춰 자르면 전단사가 된다.

### 문제 6

**접근.** 목록은 $f(1)$부터 차례로 쓰면 나온다. 개별 값은 입력의 홀짝을 먼저 판정한 뒤 해당하는 식에 대입한다 — 갈래를 잘못 고르는 것이 가장 흔한 오류다.

**풀이.** $f(1) = -\frac{1-1}{2} = 0$, $f(2) = \frac22 = 1$, $f(3) = -\frac{3-1}{2} = -1$, $f(4) = 2$, $f(5) = -2$, $f(6) = 3$, $f(7) = -3$, $f(8) = 4$, $f(9) = -4$, $f(10) = 5$. 따라서 첫 10항은

$$
0,\ 1,\ -1,\ 2,\ -2,\ 3,\ -3,\ 4,\ -4,\ 5
$$

이다. 11은 홀수이므로 $f(11) = -\frac{11-1}{2} = -5$, 12는 짝수이므로 $f(12) = \frac{12}{2} = 6$이다.

**검산.** 홀수 번째 자리에는 0 이하가, 짝수 번째 자리에는 양수가 와야 한다. 11번째가 $-5$, 12번째가 $6$으로 그 규칙에 맞는다.

### 문제 7

**접근.** 세 성질에 세 부품이 대응한다. 성질마다 "받는 전단사"와 "제시할 전단사"를 구분해 적으면 두 줄씩으로 끝난다.

**풀이.** (반사) 항등함수 $\mathrm{id}_A(x) = x$는 전단사다(단사: $x = x'$이면 그대로 $x = x'$. 전사: 임의의 $y \in A$의 원상은 $y$ 자신). 따라서 정의 48.1에 의해 $|A| = |A|$이다. (대칭) $|A| = |B|$라 하자. 전단사 $f : A \to B$가 존재하고, 43주차 핵심 정리에 의해 역함수 $f^{-1} : B \to A$가 존재한다. 43주차 문제 14에 의해 $(f^{-1})^{-1} = f$이므로 $f^{-1}$의 역관계는 함수이고, 핵심 정리를 이번에는 $f^{-1}$에 적용하면 $f^{-1}$도 전단사다. 따라서 $|B| = |A|$이다. (추이) $|A| = |B|$이고 $|B| = |C|$라 하자. 전단사 $f : A \to B$와 $g : B \to C$가 존재하고, 42주차 문제 15에 의해 $g \circ f : A \to C$는 전단사다. 따라서 $|A| = |C|$이다. $\blacksquare$

**복기.** 세 증명 모두 "가정의 존재 주장에서 함수를 받아, 목표에 맞는 함수를 만들어 제시한다"는 같은 구조이며, 새로 계산한 것은 한 줄도 없고 9부의 결과들(43주차 핵심 정리와 문제 14, 42주차 문제 15)을 인용했을 뿐이다. 다만 이 세 성질을 "동치관계"라 부르지 않는 이유는 §1.4에 적었다.

### 문제 8

**접근.** 이미 놓인 다리 두 개를 잇는다. (a)는 추이성을 쓰고, (b)는 그 증명 안의 합성을 실제로 적어 명시적 함수를 얻는다.

**풀이.** (a) 예제 2.2에서 $|\mathbb{N}| = |\mathbb{Z}|$이고 문제 7의 대칭성에 의해 $|\mathbb{Z}| = |\mathbb{N}|$이다. 예제 2.1에서 $|\mathbb{N}| = |E|$이므로, 문제 7의 추이성을 두 등식에 적용하면 $|\mathbb{Z}| = |E|$를 얻는다. $\blacksquare$ (b) 명시적 함수를 만든다. 예제 2.2의 지그재그 $f : \mathbb{N} \to \mathbb{Z}$는 전단사이고 43주차 핵심 정리에 의해 $f^{-1} : \mathbb{Z} \to \mathbb{N}$이 존재하며 문제 7의 대칭 증명대로 $f^{-1}$도 전단사다. 예제 2.1의 $h : \mathbb{N} \to E$, $h(n) = 2n$도 전단사다. 42주차 문제 15에 의해 $h \circ f^{-1} : \mathbb{Z} \to E$가 전단사이므로 $|\mathbb{Z}| = |E|$이다. $f^{-1}$의 식은 $f(k) = m$을 $k$에 대해 푼 것이다. $m > 0$이면 $2m$이 짝수이고 $f(2m) = \frac{2m}{2} = m$이므로 $f^{-1}(m) = 2m$이고, 따라서 $(h \circ f^{-1})(m) = h(2m) = 4m$이다. $m \le 0$이면 $1 - 2m$이 홀수이고 $f(1-2m) = -\frac{(1-2m)-1}{2} = m$이므로 $f^{-1}(m) = 1 - 2m$이고, 따라서 $(h \circ f^{-1})(m) = h(1-2m) = 2 - 4m$이다. $\blacksquare$

**검산.** (b)의 규칙으로 $m = 1 \mapsto 4$, $m = 0 \mapsto 2$, $m = -1 \mapsto 6$, $m = 2 \mapsto 8$ — 전부 양의 짝수이고 서로 다르다.

**복기.** (a)와 (b)는 같은 증명의 추상판과 구체판이다 — 추이성의 증명이 곧 합성이므로, 추이성을 인용하는 순간 이미 합성 함수를 만든 것이다.

### 문제 9

**접근.** 무대가 실수 구간으로 바뀌었을 뿐 서식은 같다. 전사 증인은 $y = 2x$를 $x$에 대해 푼 $\frac y2$이고, 그 증인이 $(0,1)$ 안에 있는지를 부등식으로 확인하는 줄이 붙는다.

**풀이.** $f : (0,1) \to (0,2)$를 $f(x) = 2x$로 정의하자. $0 < x < 1$이면 $0 < 2x < 2$이므로 값은 $(0,2)$ 안에 있다. (단사) $f(a) = f(a')$이라 하자. $2a = 2a'$이므로 양변을 2로 나누면 $a = a'$이다. (전사) $y \in (0,2)$라 하자. $x = \frac y2$로 두면 $0 < y < 2$에서 $0 < x < 1$이므로 $x \in (0,1)$이고, $f(x) = 2 \cdot \frac y2 = y$이다. 따라서 $f$는 전단사이고 $|(0,1)| = |(0,2)|$이다. $\blacksquare$

**복기.** 길이 1인 구간과 길이 2인 구간이 대등하다는 것은 길이가 크기의 판정 기준이 아니라는 뜻이다 — §1.1에서 포함 관계가 기준이 되지 못했던 것과 같은 관찰이다.

### 문제 10

**접근.** 계수를 먼저 설계한다 — 폭 1을 4로 늘리므로 기울기 4, 시작점 0을 3으로 옮기므로 상수항 3이다. 설계가 끝나면 검증은 문제 9와 같다.

**풀이.** $f : (0,1) \to (3,7)$을 $f(x) = 4x + 3$으로 정의하자. $0 < x < 1$이면 $0 < 4x < 4$이므로 $3 < 4x + 3 < 7$, 곧 값은 $(3,7)$ 안에 있다. (단사) $f(a) = f(a')$이라 하자. $4a + 3 = 4a' + 3$이므로 양변에서 3을 빼고 4로 나누면 $a = a'$이다. (전사) $y \in (3,7)$이라 하자. $x = \frac{y-3}{4}$로 두면 $3 < y < 7$에서 $0 < y - 3 < 4$, 따라서 $0 < x < 1$이므로 $x \in (0,1)$이고 $f(x) = 4 \cdot \frac{y-3}{4} + 3 = (y - 3) + 3 = y$이다. 따라서 $f$는 전단사이고 $|(0,1)| = |(3,7)|$이다. $\blacksquare$

**복기.** 같은 설계로 임의의 두 열린구간 $(a,b)$, $(c,d)$가 대등함을 얻는다 — $f(x) = c + \frac{d-c}{b-a}(x-a)$로 두면 된다. 기울기가 두 폭의 비이고, $x = a$에서 값이 $c$가 되도록 평행이동한 것이다. 이 사실이 문제 17로 확장된다.

### 문제 11

**접근.** 대각선을 순서대로 적고 이미 나온 값과 같은 항을 지운다. $p+q = 6$까지 적으면 10항이 채워진다.

**풀이.** 대각선별로 적으면 $p+q = 2$: $\frac11$ / $p+q = 3$: $\frac12$, $\frac21 = 2$ / $p+q = 4$: $\frac13$, $\frac22$(이미 나온 $\frac11$과 같으므로 건너뜀), $\frac31 = 3$ / $p+q = 5$: $\frac14$, $\frac23$, $\frac32$, $\frac41 = 4$ / $p+q = 6$: $\frac15$, 이하 $\frac24, \frac33, \frac42$는 각각 $\frac12, \frac11, 2$와 같으므로 건너뜀. 따라서 처음 10개의 목록 항은

$$
\tfrac11,\ \tfrac12,\ 2,\ \tfrac13,\ 3,\ \tfrac14,\ \tfrac23,\ \tfrac32,\ 4,\ \tfrac15
$$

이다.

**검산.** 열 항을 소수로 바꾸면 $1, 0.5, 2, 0.333\dots, 3, 0.25, 0.666\dots, 1.5, 4, 0.2$로 중복이 없다.

**복기.** 목록의 항을 기약 대표로 적는 것은 37주차에서 유리수를 동치류로 정의하고 대표원을 골랐던 절차이며, 건너뛰기는 "대표가 이미 등장했는가"를 묻는 절차다.

### 문제 12

**접근.** 말로 된 규칙을 함수로 번역하는 것이 첫 걸음이다 — "한 방에 한 명"이 단사, "모두 방을 가진다"가 전사다. 번역이 끝나면 문제 5와 같은 계산이다.

**풀이.** 이동 규칙: $n$호실 손님을 $n+1$호실로 옮긴다. 이를 함수로 적으면 $f : \mathbb{N} \to \{2,3,4,\dots\}$, $f(n) = n + 1$이다. $n \ge 1$이면 $n + 1 \ge 2$이므로 값은 공역 안에 있다. (단사 — 한 방에 한 명) $f(a) = f(a')$이라 하자. $a + 1 = a' + 1$이므로 $a = a'$이고, 서로 다른 두 손님이 같은 방을 배정받는 일이 없다. (전사 — 2호실부터 빈방 없음) $m \ge 2$라 하자. $k = m - 1$로 두면 $k \ge 1$이므로 $k \in \mathbb{N}$이고 $f(k) = m$이다. 따라서 $f$는 전단사이고 기존 손님 전원이 $\{2,3,4,\dots\}$에 한 명씩 들어간다. 1호실은 어느 손님의 배정지도 아니므로 비어 있고, 새 손님이 그 방에 들어간다. $\blacksquare$

**복기.** 만실인데 자리가 나는 이유는 $g : \mathbb{N} \to \mathbb{N}$, $g(n) = n+1$이 단사이면서 전사가 아니기 때문이다 — 유한집합에 그런 함수가 없음은 41주차 문제 17이 증명했고, 이 문제와 문제 18은 같은 사실의 앞뒷면이다.

### 문제 13

**접근.** 두 규칙을 이미 증명한 전단사(예제 2.1과 훈련 1)로 고른 뒤, 두 목적지가 겹치지 않고 합치면 전체가 됨을 확인한다.

**풀이.** 규칙: 기존 손님 $n$을 $2n$호실로, 새 손님 $k$를 $2k - 1$호실로 보낸다. ① 기존 손님 배정 $h : \mathbb{N} \to E$, $h(n) = 2n$은 예제 2.1에 의해 전단사다 — 짝수 방이 빠짐없이 겹침없이 채워진다. ② 새 손님 배정 $g : \mathbb{N} \to O$, $g(k) = 2k - 1$은 훈련 1에 의해 전단사다 — 홀수 방이 빠짐없이 겹침없이 채워진다. ③ 모든 자연수는 짝수이거나 홀수이고 둘 다일 수는 없으므로 $E \cap O = \emptyset$, $E \cup O = \mathbb{N}$ — 곧 $\{E, O\}$는 방 전체의 분할이다(17주차). ①②③에 의해 두 무리가 서로 다른 방을 받고, 어느 손님도 방을 못 받지 않으며, 방 전체가 정확히 채워진다. $\blacksquare$

**복기.** 짝$\cdot$홀로 가르는 이 기술이 문제 14의 교대 목록과 같다 — 방 번호가 목록의 순번 자리이고, 두 무리가 홀수 자리와 짝수 자리를 나눠 갖는다.

### 문제 14

**접근.** 교대 목록에 번호를 붙여 식으로 적는 것이 시작이고, 그 다음은 §1.5 판정표의 세 줄을 확인한다. "서로소"는 겹침 없음의 세 번째 경우에서 일한다.

**풀이.** 목록을 $c_1 = a_1$, $c_2 = b_1$, $c_3 = a_2$, $c_4 = b_2, \dots$로 정의한다. 식으로 적으면 $c_{2k-1} = a_k$, $c_{2k} = b_k$ ($k \in \mathbb{N}$)이다. (빠짐 없음) $A \cup B$의 임의의 원소는 $A$의 원소이거나 $B$의 원소다. $A$의 원소이면 어떤 $k$에 대해 $a_k$이고 $2k-1$번째 자리에 있다. $B$의 원소이면 어떤 $k$에 대해 $b_k$이고 $2k$번째 자리에 있다. (겹침 없음) 서로 다른 두 자리의 항이 같다고 하자. 두 자리가 모두 홀수면 $a_k = a_{k'}$인데 $A$의 목록에는 중복이 없으므로 $k = k'$, 곧 같은 자리다. 두 자리가 모두 짝수면 같은 이유로 같은 자리다. 한 자리가 홀수이고 다른 자리가 짝수면 $a_k = b_{k'}$이 되어 그 원소가 $A \cap B$에 속하는데 $A \cap B = \emptyset$이므로 불가능하다. (순번 유한) $a_k$의 순번은 $2k-1$, $b_k$의 순번은 $2k$로 모두 유한한 자연수다. 따라서 $n \mapsto c_n$은 $\mathbb{N}$에서 $A \cup B$로의 전단사이고, $A \cup B$는 가산 무한이다. $\blacksquare$

**복기.** 서로소가 아니면 겹침 없음의 세 번째 경우가 깨지고, 처방은 예제 2.3과 같다 — 이미 나온 값이면 건너뛴다. 이 결과는 다음 주 "무리수가 비가산"에서 인용된다.

### 문제 15

**접근.** $\mathbb{Q}$를 $\{0\}$, $\mathbb{Q}^+$, 음의 유리수로 나누고 예제 2.3의 목록을 재료로 지그재그로 엮는다 — 예제 2.2의 목록 구조를 유리수판으로 옮기는 셈이다.

**풀이.** 예제 2.3의 목록을 $r_1, r_2, r_3, \dots$이라 하자 — $\mathbb{Q}^+$의 빠짐$\cdot$겹침 없는 목록이다. 새 목록을

$$
0,\ r_1,\ -r_1,\ r_2,\ -r_2,\ r_3,\ -r_3,\ \dots
$$

로 정의한다. 순번으로 적으면 1번은 $0$, $2k$번은 $r_k$, $2k+1$번은 $-r_k$이다. (빠짐 없음) 임의의 유리수 $q$는 $q = 0$, $q > 0$, $q < 0$ 중 정확히 하나다. $q = 0$이면 1번 자리에 있다. $q > 0$이면 어떤 $k$에 대해 $q = r_k$이고 $2k$번 자리에 있다. $q < 0$이면 $-q \in \mathbb{Q}^+$이므로 어떤 $k$에 대해 $-q = r_k$이고 $q = -r_k$는 $2k+1$번 자리에 있다. (겹침 없음) 세 구역 $\{0\}$, $\mathbb{Q}^+$, 음의 유리수 전체는 서로소이므로 구역이 다르면 값이 같을 수 없고, 같은 구역 안에서는 원 목록에 중복이 없다. (순번 유한) 모든 항의 순번이 $1$, $2k$, $2k+1$ 꼴로 유한하다. 따라서 $\mathbb{Q}$는 가산 무한이고, 특히 가산이다. $\blacksquare$

**복기.** 이 논증은 "이미 만든 목록 두세 개를 하나로 엮는다"는 기술이다 — 문제 14가 두 개를, 여기서는 세 개를 엮었고, 유한 개의 가산 목록은 언제나 이렇게 엮인다. 조밀한 $\mathbb{Q}$가 가산이라는 이 결과가 다음 주 "무리수가 비가산"의 재료가 된다.

### 문제 16

**접근.** 격자는 같지만 칸에 적힌 것이 다르다. 예제 2.3에서는 칸에 분수라는 **값**이 적혀 있어 서로 다른 칸이 같은 값을 가질 수 있었고, 이번에는 칸 $(p,q)$ 자체가 원소다.

**풀이.** $\mathbb{N} \times \mathbb{N}$의 원소 $(p,q)$를 격자의 $(p,q)$ 칸에 놓고, 대각선을 $p+q = 2, 3, 4, \dots$ 순으로, 각 대각선 안에서는 $p$가 작은 것부터 방문하는 목록을 만든다. (빠짐 없음) 임의의 $(p,q)$는 $p + q$번째 대각선에 있고 그 대각선은 유한 단계 안에 방문되므로 목록에 등장한다. (겹침 없음) 서로 다른 두 칸은 서로 다른 순서쌍이다. $(1,2)$와 $(2,4)$는 분수로 보면 같은 값이지만 순서쌍으로는 다르므로 두 칸이 같은 원소를 담는 일이 없다. 따라서 건너뛰기가 아예 필요하지 않다 — 이것이 $\mathbb{Q}^+$ 때와 다른 점이다. (순번 유한) $p+q = s$인 대각선의 칸은 $s-1$개이므로 $(p,q)$ 이전에 방문되는 칸의 수는 유한하다. 따라서 목록은 $\mathbb{N}$과 $\mathbb{N} \times \mathbb{N}$ 사이의 전단사를 주고, $|\mathbb{N} \times \mathbb{N}| = |\mathbb{N}|$이다. $\blacksquare$

**검산.** 처음 여섯 항 $(1,1), (1,2), (2,1), (1,3), (2,2), (3,1)$은 모두 서로 다르다. $(2,2)$를 건너뛰지 않는 것이 예제 2.3과의 차이다.

**복기.** 예제 2.3을 이 결과의 따름으로 얻으려는 길도 있다 — $\mathbb{Q}^+$의 원소마다 기약분수 $(p,q)$를 대응시키면 $\mathbb{Q}^+$가 $\mathbb{N} \times \mathbb{N}$의 부분집합과 대등해진다. 여기에 "가산집합의 무한 부분집합도 가산"이라는 사실을 더하면 예제 2.3이 따름으로 나오는데, 그 사실은 이 과정에서 증명하지 않았다. 그래서 예제 2.3은 직접 목록을 만들어 증명했다.

### 문제 17

**접근.** (a)는 값을 넣어 구간의 끝으로 갈수록 출력이 커지는 모양을 확인하는 계산이다. (b)의 관문은 $|f(x)|$를 없애는 것이고, $x \ge 0$이면 $f(x) \ge 0$임을 확인하면 벗겨진다.

**풀이.** (a) $f(0) = \frac{0}{1-0} = 0$, $f(\frac12) = \frac{1/2}{1/2} = 1$, $f(-\frac12) = \frac{-1/2}{1/2} = -1$, $f(0.9) = \frac{0.9}{0.1} = 9$. 입력이 구간의 끝 $\pm 1$에 가까워질수록 분모가 0에 가까워지므로 출력의 절댓값이 한없이 커진다 — 유한한 구간이 실수 전체로 펴진다는 뜻이다. (b) $x \ge 0$이라 하자. $0 \le x < 1$이므로 $1 - x > 0$이고 $f(x) = \frac{x}{1-x} \ge 0$이다. 따라서 $|f(x)| = f(x)$이고,

$$
g(f(x)) = \frac{f(x)}{1 + f(x)} = \frac{\frac{x}{1-x}}{1 + \frac{x}{1-x}} = \frac{\frac{x}{1-x}}{\frac{(1-x) + x}{1-x}} = \frac{\frac{x}{1-x}}{\frac{1}{1-x}} = x
$$

이다. $x < 0$인 경우도 같은 계산이다: $|x| = -x$이므로 $f(x) = \frac{x}{1+x}$이고 $1 + x > 0$이므로 $f(x) < 0$, 곧 $|f(x)| = -f(x)$이다. 그러면

$$
g(f(x)) = \frac{f(x)}{1 - f(x)} = \frac{\frac{x}{1+x}}{1 - \frac{x}{1+x}} = \frac{\frac{x}{1+x}}{\frac{(1+x) - x}{1+x}} = x
$$

이다. 두 경우를 합치면 모든 $x \in (-1,1)$에 대해 $g(f(x)) = x$이다.

반대 방향도 같은 서식으로 적는다. 먼저 임의의 $y \in \mathbb{R}$에 대해 $|g(y)| = \frac{|y|}{1 + |y|} < 1$이므로 $g(y) \in (-1,1)$이고, 따라서 $f(g(y))$가 정의된다. $y \ge 0$이면 $|y| = y$이므로 $g(y) = \frac{y}{1+y} \ge 0$이고 $|g(y)| = g(y)$이므로

$$
f(g(y)) = \frac{g(y)}{1 - g(y)} = \frac{\frac{y}{1+y}}{1 - \frac{y}{1+y}} = \frac{\frac{y}{1+y}}{\frac{(1+y) - y}{1+y}} = \frac{\frac{y}{1+y}}{\frac{1}{1+y}} = y
$$

이다. $y < 0$이면 $|y| = -y$이므로 $g(y) = \frac{y}{1-y}$이고, $1 - y > 0$이므로 $g(y) < 0$, 곧 $|g(y)| = -g(y)$이다. 그러면

$$
f(g(y)) = \frac{g(y)}{1 + g(y)} = \frac{\frac{y}{1-y}}{1 + \frac{y}{1-y}} = \frac{\frac{y}{1-y}}{\frac{(1-y) + y}{1-y}} = \frac{\frac{y}{1-y}}{\frac{1}{1-y}} = y
$$

이다. 두 경우를 합치면 모든 $y \in \mathbb{R}$에 대해 $f(g(y)) = y$이다. 양쪽 합성이 항등함수이므로 $f$는 전단사이고(43주차), $|(-1,1)| = |\mathbb{R}|$이다. $\blacksquare$

**검산.** $x = \frac12$에서 $f(x) = 1$이고 $g(1) = \frac{1}{1+1} = \frac12$ ✓. $x = 0.9$에서 $f(x) = 9$이고 $g(9) = \frac{9}{10} = 0.9$ ✓.

**복기.** 문제 9$\cdot$10의 "임의의 두 열린구간이 대등"과 여기의 "열린구간과 $\mathbb{R}$가 대등"을 추이성으로 이으면 임의의 열린구간이 $\mathbb{R}$와 대등하다. 이 결과는 다음 주에 $(0,1)$의 비가산성에서 $\mathbb{R}$의 비가산성으로 넘어갈 때 다리가 된다.

### 문제 18

**접근.** 주장은 "부분은 전체보다 작다"는 정리를 인용하고 있다. 그 정리가 어느 무대에서 증명되었는지 확인하고 무대 밖에서 쓰였음을 지목하는 것이 결함 지적의 형식이다.

**풀이.** 결함은 "부분은 전체보다 작다"를 무한집합에 적용한 데 있다. 이 문장은 **유한집합의 성질**이다 — 그 뿌리는 41주차 도전 절이 "이 절이 빌려 쓰는 사실 ②"로 증명 없이 인정하고 쓴 문장, 곧 "유한집합에서 크기가 같은 부분집합은 전체 자신이다"이고, 41주차 문제 17은 그 사실을 써서 "$|A| = |B| = n$인 유한집합에서 단사이면 전사"를 세기로 증명했다. 진부분집합 $B \subsetneq A$와 전단사 $f : A \to B$가 있다면, 같은 $f$를 $A \to A$로 보아 단사이지만 치역이 $B \subsetneq A$라 전사가 아니므로 문제 17에 어긋난다 — 유한에서 "진부분집합은 전체와 대등하지 않다"는 이렇게 나온다. 두 근거 모두 "원소를 세어 $n$과 비교한다"는 절차에 기대고 있고, 무한집합에는 그 절차가 없으므로 증명이 옮겨 가지 않는다. 실제로 무한에서는 결론이 거짓이다. 예제 2.1에서 $f(n) = 2n$이 $\mathbb{N}$에서 $E$로의 전단사임을 증명했고 정의 48.1에 의해 $|E| = |\mathbb{N}|$이므로, $E \subsetneq \mathbb{N}$이면서 대등하다. 덧붙이면 진부분집합과 대등하다는 이 성질이야말로 무한집합을 유한집합과 가르는 기준으로 쓰이므로(데데킨트), 주장이 근거로 삼은 문장은 사실 무한집합의 반대 신호였다.

**복기.** 결함 지적의 형식은 세 줄이다 — ① 근거로 삼은 문장 지목 ② 그 문장이 참인 무대 확인 ③ 무대 밖의 반례 제시. 41주차의 인정 사실 ②와 그것을 쓴 문제 17이 ②를, 예제 2.1이 ③을 담당한다.

### 문제 19

**접근.** "멈추지 않는다"를 직접 보이려 하면 막히므로 뒤집는다 — 어느 단계에서 멈춘다면 남은 집합이 공집합이고 그러면 $A$가 유한이라는 결론이 나와 가정과 어긋난다. 뽑힌 원소들이 서로 다르다는 것은 뽑는 절차가 보장한다.

**풀이.** $A$를 무한집합이라 하자. $A \ne \emptyset$이므로($\emptyset$은 정의 48.3에 의해 유한이다) 원소 $a_1$을 뽑을 수 있다. $k$개를 뽑았다고 하고 $A - \{a_1, \dots, a_k\}$를 보자. 이 집합이 공집합이면 $A = \{a_1, \dots, a_k\}$, 곧 $|A| = |\{1,\dots,k\}|$이므로 정의 48.3에 의해 $A$가 유한이 되어 가정에 어긋난다. 따라서 $a_{k+1}$을 뽑을 수 있고, 뽑기는 어느 단계에서도 멈추지 않는다. 뽑힌 원소들은 서로 다르다 — $a_{k+1}$은 $a_1, \dots, a_k$를 제거한 집합에서 뽑았기 때문이다. 따라서 $n \mapsto a_n$은 $\mathbb{N}$에서 $\{a_1, a_2, \dots\}$로의 함수이며, 단사(서로 다른 원소를 뽑았으므로)이고 전사(공역의 원소가 전부 어떤 $a_n$이므로)다. 곧 $\{a_1, a_2, \dots\}$는 $A$의 가산 무한 부분집합이다. $\blacksquare$

**논평.** 이 논증은 "뽑기"를 무한 번 수행한다. 각 단계의 뽑기는 정당하지만, 무한히 많은 뽑기를 한꺼번에 확정하려면 **선택공리**가 필요하다 — 이 과정에서는 그 공리를 증명 없이 인정하고 쓰고, 정식 논의는 대학 집합론으로 이월한다.

**복기.** 결과의 뜻은 "가산 무한이 가장 작은 무한"이라는 것이다 — 어떤 무한집합도 가산 무한 부분집합을 품는다. 다음 주에 "가산보다 큰 무한이 있다"가 증명되면 등급이 생긴다.

### 문제 20

**접근.** (a)는 확인 1에서 관찰한 것 — 세기 자체가 짝짓기였다 — 을 문장으로 정리한다. (b)는 29주차의 반증 언어를 쓴다: 예시가 쌓여도 전칭 명제의 증명이 되지 않는다.

**풀이.** (예시 답안) (a) "다섯 개"라고 세는 행위는 대상들을 $1, 2, 3, 4, 5$와 하나씩 짝짓는 일이므로, 유한 세기의 본질은 수가 아니라 전단사다. 무한집합에는 "마지막 수"가 없어 세는 절차를 끝낼 수 없지만 짝짓기는 여전히 가능하므로, 전단사의 존재를 크기 같음의 정의로 삼는 것이 절차에 의존하지 않는 유일한 일반화이며, 이 정의는 유한에서 기존 세기와 같은 답을 준다(문제 2). (b) $E$, $\mathbb{Z}$, $\mathbb{Q}$, $\mathbb{N} \times \mathbb{N}$이 모두 가산이라는 것은 사례의 축적일 뿐이고, "모든 무한집합은 가산이다"라는 전칭 명제는 반례 하나로 무너지는 형태이므로(29주차) 사례만으로는 증명이 되지 않는다.

**복기.** (b)의 형태는 1주차 문제 18과 같다 — 그때는 39개의 사례가 성립하고 40번째에서 무너졌고, 이번에는 네 개의 큰 사례가 성립하다 다음 주 $\mathbb{R}$에서 무너진다.

---

**다음 주 예고:** 칸토어의 대각선 논법으로 "$(0,1)$의 모든 목록에는 반드시 빠진 수가 있다"를 증명한다. 이번 주의 3단계 틀이 그대로 기준선이 된다 — 목록을 만드는 대신, 어떤 목록도 §1.5 판정표의 첫 줄(빠짐 없음)을 만족할 수 없음을 보이는 귀류법이다.