# C13주차 — 기수: 가산과 비가산

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

**핵심 문장**: 무한집합의 크기는 세어서 비교할 수 없으므로 **짝짓기**로 비교한다. 빠짐도 겹침도 없는 짝짓기(전단사)가 하나라도 있으면 같은 크기이고, 그런 짝짓기가 **하나도 없음**을 보여야 다른 크기다. 이 잣대로 재면 $\mathbb{N}$, $\mathbb{Z}$, $\mathbb{Q}$는 같은 크기이고 $\mathbb{R}$은 그보다 크다.

**이 주의 위치**: 2학기 20주 과정의 C13주차. C12주차가 세운 단사$\cdot$전사$\cdot$전단사가 여기서 **크기를 재는 도구**로 그대로 재사용된다. 1권 48주차(가산 무한)와 49주차(대각선 논법)에서 다룬 내용이 Chartrand의 기수 언어로 다시 조직되고, 흩어져 있던 개별 논증이 **가산성 보존 성질**이라는 목록으로 묶인다. 다음 주 C14주차는 여기서 세운 "같은 크기"에 "$\le$"를 더해 기수 비교를 만든다.

**원서 대응**: Chartrand 11.1~11.3 (Cardinalities of Sets). 1일차에 이 세 절을 통독한 상태로 이 교안에 온다.
:::

## 이번 주 목표

1. **같은 크기**(numerically equivalent, $|A| = |B|$)를 전단사의 존재로 정의하고, 그 정의의 조각마다 무엇이 무너지는지 설명한다.
1. **가산무한**(denumerable)$\cdot$**가산**(countable)$\cdot$**비가산**(uncountable)을 구분하고, 가산 증명의 3단 서식을 백지에 재현한다.
1. $\mathbb{Z}$와 $\mathbb{Q}$가 가산임을 나열 규칙의 제작과 두 검증으로 증명한다.
1. **대각선 논법**으로 $(0,1)$이 비가산임을 증명하고, 그 논법이 왜 귀류법의 꼴을 취할 수밖에 없는지 밝힌다.

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

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

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

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

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

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

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

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

1. C12주차 §1.3의 단사$\cdot$전사 증명 서식을 쓰시오 — 단사는 "$f(a_1) = f(a_2)$라 하자"로 시작하고, 전사는 "임의의 $b$를 잡자"로 시작한다.
1. C12주차 예제 2.1($f(x) = 2x - 3$이 전단사)을 백지에 재현하시오.
1. C12주차 §1.5의 핵심 정리 1.5 "$f$가 역함수를 가진다 $\iff$ $f$가 전단사이다"를 진술하시오.

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

1. (진단) 자연수 전체 $\mathbb{N}$과 양의 짝수 전체 $2\mathbb{N} = \{2, 4, 6, \ldots\}$ 중

어느 쪽이 더 큰가. 근거와 함께 답하시오.

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

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

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

- **유형 1 — 부분이므로 작다.** "$2\mathbb{N}$은 $\mathbb{N}$의 일부이므로 $\mathbb{N}$이

더 크다." 유한집합에서는 이 추론이 보증된다 — 1권 41주차가 "유한집합에서 크기가 같은 부분집합은 전체 자신이다"를 인정하고 쓴 사실로 놓았고, 그것이 곧 "진부분집합은 전체와 크기가 같을 수 없다"이다. 문제는 그 보증이 **유한성에서 나온다**는 것이고, 무한집합에는 그 보증이 없다. 빠진 것은 결론이 아니라 근거이며, §1.2에서 이 추론이 실제로 무너지는 사례를 본다.

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

근거가 "무한이니까"라면 같은 근거로 $\mathbb{R}$도 $\mathbb{N}$과 같은 크기가 되는데, §1.6이 그것을 반증한다. 곧 이 근거는 참인 결론과 거짓인 결론을 함께 낳으므로 근거가 아니다. 필요한 것은 무한들끼리도 갈라내는 잣대이며, §1.2가 그 잣대다.

- **유형 3 — 답할 수 없다고 판단했다.** "크기"라는 말의 뜻이 무한집합에 대해

정해져 있지 않으므로 답할 수 없다고 적었다면, 그 판단이 정확하다. 이번 주가 하는 일이 정확히 그 뜻을 정하는 것이고, 뜻이 정해지는 순간 이 물음에는 한 줄의 답이 나온다.

## 개념 — 세기를 짝짓기로 바꾸기

### 1 유한의 세기로 밀어붙이면 어디서 막히는가

새 잣대를 꺼내기 전에, 지금 가진 도구 — 원소의 개수를 세어 비교하는 방식 — 만으로 준비 운동 4번을 밀어붙여 본다.

:::{admonition} 시도 — 개수를 세어 비교하기
:class: quotebox

물음: $\mathbb{N}$과 $2\mathbb{N}$ 중 어느 쪽이 더 큰가.

"$\mathbb{N}$의 원소 개수를 $N$이라 하자. 짝수는 자연수 두 개마다 하나씩이므로

$2\mathbb{N}$의 원소 개수는 $N/2$이다. $N/2 < N$이므로 … "
:::

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

:::{container} quotebox
**확인 1.** 멈춘 자리에서 실제로 존재하지 않는 것은 무엇인가. 위 시도의 어느 낱말이 근거 없이 쓰였는지 하나만 지목해 보자.
:::

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

"$\mathbb{N}$의 원소 개수 $N$"이라는 **수**가 존재하지 않는다. 유한집합에서는 세기가

언젠가 끝나 자연수 하나를 남기지만, $\mathbb{N}$에서는 세기가 끝나지 않으므로

$N$이라고 적은 것은 이름만 있고 대상이 없다.

그러면 다음 줄의 "$N/2 < N$"도 무너진다 — 이 부등식은 근거 ③(등식$\cdot$부등식의

성질)인데, 근거 ③은 좌우가 **수**일 때만 적용된다. "두 개마다 하나씩"이라는 말도

마찬가지로 유한한 세기에서만 뜻이 있다.

곧 막힌 이유는 계산 실수가 아니라 **개수라는 경유지가 없다**는 것이다.
:::

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

무한집합의 크기는 개수를 거쳐 비교할 수 없다.

개수를 거치지 않고 두 집합을 직접 비교하는 방법이 **짝짓기**다.

유한에서도 실제로 한 일은 짝짓기였다 — 개수는 그 결과의 요약일 뿐이다.
:::

### 2 사례를 모아 보기 — 짝짓기가 성공하는가

짝짓기 규칙을 하나씩 놓고, 그 규칙에 빠짐과 겹침이 있는지 적어 보자. "빠짐"은 오른쪽 집합의 어떤 원소도 짝을 못 받은 경우, "겹침"은 왼쪽의 서로 다른 두 원소가 같은 짝을 받은 경우다.

| **두 집합** | **짝짓기 규칙** | **빠짐** | **겹침** | **판정** |
|---|---|---|---|---|
| $\{1,2,3\}$ 과 $\{a,b,c\}$ | $1 \mapsto a$, $2 \mapsto b$, $3 \mapsto c$ | 없다 | 없다 | 같은 크기 |
| $\{1,2,3\}$ 과 $\{a,b,c,d\}$ | $1 \mapsto a$, $2 \mapsto b$, $3 \mapsto c$ | $d$가 빠진다 | 없다 | 이 규칙은 실패 |
| $\mathbb{N}$ 과 $2\mathbb{N}$ | $n \mapsto 2n$ | $\underline{\quad(1)\quad}$ | $\underline{\quad(2)\quad}$ | $\underline{\quad(3)\quad}$ |
| $\mathbb{N}$ 과 $\mathbb{N}$ | $n \mapsto 2n$ | $1, 3, 5, \ldots$이 빠진다 | 없다 | 이 규칙은 실패 |

:::{container} quotebox
**확인 2.** 표의 (1)(2)(3)을 채워 보자. 그리고 넷째 행이 "$\mathbb{N}$과 $\mathbb{N}$은 크기가 다르다"의 근거가 되지 **않는** 이유를 한 문장으로 적어 보자.
:::

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

(1) 빠짐이 없다 — 임의의 양의 짝수는 $2m$ 꼴이고 그것은 $m$의 짝이다.

(2) 겹침이 없다 — $2n_1 = 2n_2$이면 양변을 2로 나누어 $n_1 = n_2$이다(근거 ③).

(3) 같은 크기.

넷째 행이 근거가 되지 않는 이유: **한 규칙이 실패했을 뿐이고, 다른 규칙이 성공할

수 있기 때문이다.** 실제로 $n \mapsto n$이 성공한다.

이 비대칭이 이번 주의 두 임무를 갈라 놓는다. 같은 크기를 보이려면 성공하는 규칙

**하나**를 제시하면 되고, 다른 크기를 보이려면 **모든** 규칙이 실패함을 보여야 한다.

뒤쪽이 §1.6의 형태를 정한다.
:::

이 관찰에 정식 이름과 기호를 붙인다. 식 자체에 새로운 것은 없다 — 표에서 한 판정을 C12주차의 낱말로 옮겨 적었을 뿐이다. "빠짐 없음"이 전사이고 "겹침 없음"이 단사이므로, 두 조건을 함께 갖춘 규칙은 곧 전단사다.

### 정의 1.1 — 같은 크기 (numerically equivalent) [백지 암기 대상]

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

$A$와 $B$는 **같은 크기**라 하고 $|A| = |B|$로 쓴다.
:::

:::{admonition} 표기 — $|A| = |B|$
:class: quotebox

"$|A| = |B|$"는 "에이와 비는 같은 크기이다"로 읽는다. 유한집합에서 $|A|$는 원소의

개수라는 수였고(1권 12주차), 그때의 등식과 이 표기는 같은 판정을 준다.

다만 $A$가 무한일 때 이번 주가 뜻을 정한 것은 $|A| = |B|$라는 **관계 전체**이지

좌변 하나가 아니다. 무한집합 하나에 붙는 기수 기호는 아래 §1.4에서 따로 도입한다.
:::

**1권에서 하던 일이 여기서 이름을 얻는 자리.** 1권 48주차 정의 48.1이 같은 내용을 **대등**(equinumerous)이라는 이름으로 세웠다. 이번 주에 새로 생기는 것은 이름이 아니라 **묶음**이다 — 1권에서 문제마다 따로 만들던 나열 논증들이 §1.7에서 "가산성 보존 성질"이라는 한 목록으로 묶이고, 그 목록이 §2와 §4의 증명에서 재증명 없이 인용되는 부품이 된다.

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

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

| **조각** | **하는 일** | **판정에서의 역할** |
|---|---|---|
| "집합 $A$, $B$에 대해" | 무대의 선언 | 유한과 무한을 가리지 않는다 — 같은 기준을 두 세계에 쓴다 |
| "$A$에서 $B$로의 전단사 $f$가" | 짝짓기 규칙 제공 | 제작할 대상. 전사가 빠짐을, 단사가 겹침을 막는다 |
| "존재하면" | 요구 조건의 명시 | 그런 $f$를 **하나만** 제시하면 끝난다 — 모든 함수를 검사할 필요가 없다 |
| "$\vert A\vert = \vert B\vert$로 쓴다" | 표기의 약속 | 개수를 세지 않고 두 집합 사이의 관계만 기록한다 |

**조각 삭제 실험 (가) — "전사"를 지우면.** 둘째 조각에서 전사를 지우고 단사만 요구해 보자. $f : \{1,2,3\} \to \{a,b,c,d\}$를 $1 \mapsto a$, $2 \mapsto b$, $3 \mapsto c$로 두면 이 $f$는 단사이므로 $|\{1,2,3\}| = |\{a,b,c,d\}|$가 된다. 원소가 세 개인 집합과 네 개인 집합이 같은 크기가 되어 유한에서 이미 무너진다.

**조각 삭제 실험 (나) — "단사"를 지우면.** 전사만 요구하면 $f : \{a,b,c,d\} \to \{1,2,3\}$을 $a, b \mapsto 1$, $c \mapsto 2$, $d \mapsto 3$으로 두어 다시 4와 3이 같아진다.

**조각 삭제 실험 (다) — "존재하면"을 "모든 함수가 전단사이면"으로 바꾸면.** $\mathbb{N}$에서 $\mathbb{N}$으로 가는 함수 중에는 전단사가 아닌 것이 얼마든지 있다 ($n \mapsto 1$이 그렇다). 이 조건을 요구하면 $|\mathbb{N}| = |\mathbb{N}|$조차 성립하지 않는다.

:::{container} quotebox
**확인 3.** 실험 (다)에서 무너진 것을 한 문장으로 적어 보자. 그리고 §1.2 확인 2에서 확인한 비대칭이 이 실험과 어떻게 이어지는지 한 줄로 적어 보자.
:::

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

**원소가 두 개 이상인 집합은 자기 자신과 같은 크기가 아니게 된다**(공집합과

한원소집합만 살아남는다 — 이 둘에서는 자기 자신으로 가는 함수가 각각 공함수와

항등함수 하나뿐이고 둘 다 전단사이므로 바뀐 조건도 통과한다). 원소가 둘 이상이면

상수함수가 언제나 있어 조건이 깨진다. 곧 반사성이 무너지고, 크기라는 말이 뜻을 잃는다.

비대칭과의 연결: "존재한다"의 부정은 "모든 것에 대해 아니다"이므로, $|A| \ne |B|$를

주장하는 쪽이 **모든 함수를 상대해야 하는** 쪽이 된다. 실험 (다)는 그 부담을 잘못

옮겨 놓으면 무엇이 벌어지는지를 보여 준다. §1.6의 증명이 귀류법의 꼴을 취하는

이유도 같다 — 상대가 "모든 함수"일 때는 하나를 가정해 놓고 무너뜨리는 것이

유일한 접근이다.
:::

### 4 나열 — 가산과 비가산의 이름

정의 1.1에서 $B = \mathbb{N}$인 특별한 경우를 본다. 전단사 $f : \mathbb{N} \to A$가 있으면 그 출력을 $f(1), f(2), f(3), \ldots$ 순서로 늘어놓을 수 있고, 그러면 $A$의 원소가 한 줄로 늘어선 **목록**이 생긴다.

### 정의 1.2 — 가산 (countable) [백지 암기 대상]

:::{container} quotebox
$|A| = |\mathbb{N}|$인 집합 $A$를 **가산무한**(denumerable, countably infinite)이라 한다.

유한집합이거나 가산무한인 집합을 **가산**(countable)이라 한다.
:::

### 정의 1.3 — 비가산 (uncountable) [백지 암기 대상]

:::{container} quotebox
집합 $A$가 가산이 아닐 때 — 곧 $A$가 유한하지도 않고 $\mathbb{N}$에서 $A$로의

전단사도 **존재하지 않을 때** — $A$를 **비가산**(uncountable)이라 한다.
:::

정의 1.3은 "에이는 유한하지 않고, 엔에서 에이로 가는 전단사도 존재하지 않는다"로 읽는다. 읽는 법까지가 정의다. 1권 48주차 정의 48.2와 49주차 정의 49.1이 같은 내용을 세웠다.

목록의 그림이 곧 가산무한의 실전 판정 기준이다. 이번 주의 증명 대부분은 전단사를 수식으로 적는 대신 목록을 만들어 아래 세 줄을 확인하는 방식으로 진행된다.

| **목록이 만족해야 할 것** | **함수의 성질** | **목록에서 보이는 현상** |
|---|---|---|
| $A$의 모든 원소가 등장한다 | 전사 | 빠짐 없음 |
| 같은 원소가 두 번 등장하지 않는다 | 단사 | 겹침 없음 |
| 각 원소의 등장 순번이 유한하다 | 정의역이 $\mathbb{N}$ | 몇 번째인지 말할 수 있음 |

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

$|\mathbb{N}|$을 $\aleph_0$로 쓰고 "알레프 영"이라고 읽는다. $\aleph$는 히브리

문자이고 아래 첨자 0은 이것이 가장 작은 무한 기수임을 가리킨다. $|\mathbb{R}|$은

$\mathfrak{c}$로 쓰고 "연속체"(continuum)라고 읽는다. 이 두 기호는 이번 주에

**이름표로만** 쓴다 — 두 기호 사이의 대소를 다루는 정식 도구는 다음 주 C14주차의

기수 비교다. 답안에서는 "$A$는 가산무한이다"라고 적어도 같은 점수다.
:::

:::{container} quotebox
**확인 4.** 다음 세 문장 각각이 정의 1.2$\cdot$1.3에 비추어 옳은지 판정하고, 옳지 않은 것은 어디서 어긋나는지 적어 보자.

(가) 무한집합은 가산이거나 비가산이다.

(나) 유한집합은 비가산이다.

(다) 비가산집합은 무한집합이다.
:::

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

옳은 것은 (가)와 (다) 둘이다.

(가) 옳다 — 무한집합은 정의 1.2의 "유한집합" 갈래에서 빠지므로, 가산무한이거나

그렇지 않거나 둘 중 하나다. 그렇지 않은 쪽이 곧 비가산이다.

(나) 어긋난다 — 정의 1.2가 유한집합을 **가산**에 넣었으므로 유한집합은 비가산이

아니다. "셀 수 없다"는 일상 표현에 끌리면 이 자리를 놓치기 쉽다.

(다) 옳다 — 정의 1.3의 첫 조각이 "유한하지도 않고"이므로 비가산이면 무한이다.

이 조각을 지우면 어떤 유한집합도 $\mathbb{N}$과 전단사가 없다는 이유로 비가산이 되어,

비가산이라는 말이 "무한히 크다"는 뜻을 잃는다.
:::

### 5 절차 해부 — 가산 증명의 3단 서식

가산임을 보이는 답안은 언제나 같은 세 걸음이다.

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

**가산 증명의 3단 서식**

집합 $A$가 가산무한임을 보이려면 —

① **규칙 제작** — 함수 $f : \mathbb{N} \to A$를 식이나 목록으로 명시한다. 식이 경우로 갈리면 각 경우에서 값이 실제로 $A$에 들어가는지 함께 밝힌다.

② **빠짐 없음(전사)** — 임의의 $a \in A$를 잡고 $f(n) = a$인 $n$을 **구성**한다.

③ **겹침 없음(단사)** — $f(n_1) = f(n_2)$라 하고 $n_1 = n_2$를 유도한다.
:::

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

| **걸음** | **하는 일** | **이 걸음을 빼면 무엇이 무너지는가** |
|---|---|---|
| ① 규칙 제작 | 검증할 대상을 무대에 올린다 | 검증이 가리킬 것이 없다. "나열할 수 있다"로 메우면 곧바로 순환이 된다 — 문제 10의 답안이 정확히 이것이다 |
| ② 빠짐 없음 | 목록이 $A$ 전체를 덮음을 보인다 | $A$의 일부만 세고 $A$ 전체를 셌다고 주장하게 된다 — 문제 18의 답안이 이것이다 |
| ③ 겹침 없음 | 각 원소가 한 번만 등장함을 보인다 | 같은 원소를 여러 번 세는 목록이 통과한다 — 문제 11의 분수 격자가 이 함정을 실제로 갖고 있다 |

**걸음 삭제 실험 — ②를 빼면.** 빠짐 검증 의무를 지우면 다음 답안이 합법이 된다.

:::{admonition} 삭제 실험 — 규칙만 제작한 답안
:class: quotebox

명제: 구간 $(0,1)$은 가산무한이다.

"$f : \mathbb{N} \to (0,1)$을 $f(n) = \dfrac{1}{n+1}$로 정의한다.

$n_1 \ne n_2$이면 $\dfrac{1}{n_1+1} \ne \dfrac{1}{n_2+1}$이므로 단사이다.

따라서 $(0,1)$은 가산무한이다."
:::

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

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

계산은 한 줄도 틀리지 않았다. $f$는 실제로 단사이고 값도 모두 $(0,1)$ 안에 있다.

잘못된 것은 **걸음 ②가 통째로 빠졌다**는 것이다. 걸음 ②를 수행하려면 임의의

$a \in (0,1)$에 대해 $\frac{1}{n+1} = a$인 자연수 $n$을 구성해야 하는데,

$n = \frac1a - 1$이 자연수라는 보장이 없다 — $a = \frac13$이면 $n = 2$,

$a = \frac16$이면 $n = 5$로 성공하지만, $a = 0.7$이면 $n = \frac{3}{7}$이라

자연수가 아니어서 실패한다. 실제로 이 목록은 $(0,1)$의 원소 대부분을 빠뜨리며, 명제 자체가 거짓이다(§1.6).

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

:::{container} quotebox
**확인 6.** 걸음 ③을 빼면 무엇이 무너지는가. $\mathbb{Q}^+$의 원소를 $\frac pq$ 꼴로 격자에 늘어놓고 훑는 목록에서 실제로 일어나는 일을 예로 들어 보자.
:::

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

같은 원소가 여러 번 등장하는 목록이 통과한다. 격자를 그냥 훑으면

$\frac11, \frac12, \frac21, \frac13, \frac22, \frac31, \ldots$이 나오는데 $\frac22$는

이미 나온 $\frac11$과 같은 유리수다. 그러면 이 대응은 단사가 아니므로 전단사가

아니고, 정의 1.1의 조건을 만족하지 않는다.

고치는 방법은 기약분수만 채택하는 것이며, 그 처리가 문제 11이다. 걸음 ③이

없으면 이 수리가 필요하다는 사실 자체가 답안에 드러나지 않는다.
:::

### 6 절차 해부 — 대각선 논법

§1.2 확인 2의 비대칭 때문에, 비가산 증명은 "어떤 규칙이 실패한다"로는 끝나지 않는다. **모든** 규칙이 실패함을 보여야 하고, 그것을 직접 훑을 수는 없다. 그래서 규칙이 하나 성공했다고 가정해 놓고 그 규칙 자체를 재료로 삼아 무너뜨린다.

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

**대각선 논법의 5단 서식**

집합 $A$가 비가산임을 보이려면 —

① **유한 배제** — $A$가 유한하지 않음을 밝힌다(서로 다른 원소를 무한히 많이 제시하면 된다).

② **목록 가정** — $A$가 가산이라 가정한다. ①과 합하면 가산무한이므로 전단사 $g : \mathbb{N} \to A$, 곧 빠짐 없는 목록 $x_1, x_2, x_3, \ldots$이 존재한다.

③ **표로 펼치기** — 각 $x_k$를 자리별 데이터로 펼쳐 $k$행 $j$열의 표를 만든다.

④ **대각선 비틀기** — $k$번째 자리를 $x_k$의 $k$번째 자리와 다르게 정해 새 대상 $y$를 제작한다.

⑤ **두 검증과 모순** — $y \in A$임을 검증하고(자격), 모든 $k$에 대해 $y \ne x_k$임을 검증한다(탈출). 그러면 $y$가 목록에 없으므로 ②의 "빠짐 없음"과 모순이다.
:::

| **걸음** | **하는 일** | **이 걸음을 빼면 무엇이 무너지는가** |
|---|---|---|
| ① 유한 배제 | 정의 1.3의 첫 조각을 채운다 | 유한집합도 "$\mathbb{N}$과의 전단사가 없다"는 이유로 비가산으로 판정된다 |
| ② 목록 가정 | 상대를 하나로 좁힌다 | "모든 함수"를 상대해야 하고, 무너뜨릴 구체적 대상이 없다 |
| ③ 표로 펼치기 | 비틀 자리를 만든다 | $y$를 제작할 재료가 없다 — 대각선은 표가 있어야 존재한다 |
| ④ 대각선 비틀기 | 목록 전체를 한 번에 피하는 대상을 만든다 | 원소 하나를 고르는 것으로는 특정 $x_k$만 피할 수 있다 |
| ⑤ 두 검증 | 제작물이 무대 안에 있고 실제로 탈출함을 보인다 | 무대 밖의 대상을 반례로 제출하거나, 다르다는 주장이 검증 없이 남는다 |

**걸음 삭제 실험 — ⑤의 자격 검증을 빼면.** 자격 검증 의무를 지우면 다음 답안이 합법이 된다.

:::{admonition} 삭제 실험 — 탈출만 검증한 답안
:class: quotebox

명제: $(0,1)$은 비가산이다.

"$(0,1)$이 가산이라 하고 목록 $x_1, x_2, \ldots$을 잡자. $y$를 $k$번째 자리가

$d_{kk} + 1$인 수로 정의하면 $y$는 모든 $x_k$와 $k$번째 자리에서 다르다.

따라서 $y$가 목록에 없어 모순이다."
:::

:::{container} quotebox
**확인 7.** 위 답안에서 검증되지 않은 것은 무엇인가. $d_{kk} = 9$인 자리가 하나라도 있으면 무슨 일이 벌어지는가.
:::

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

검증되지 않은 것은 "$y \in (0,1)$"이라는 **자격**이다. 그리고 이 자리는 채울 수도

없다 — $d_{kk} = 9$이면 $d_{kk} + 1 = 10$이라 십진수의 한 자리에 들어가지 않으므로,

그 규칙은 애초에 수 하나를 정의하지 못한다.

규칙을 $d_{kk} = 9$일 때 $0$을 쓰도록 고쳐도 문제가 남는다. 그러면 $y$의 전개에

0이 무한히 이어지는 꼬리가 생길 수 있고, 그런 수는 십진 표기가 두 개라

"자리가 다르므로 수가 다르다"는 걸음 ⑤의 탈출 검증이 무너진다.

두 함정을 함께 막는 방법이 아래의 자릿수 제한이다.
:::

**십진 표기의 안전장치.** 십진 전개가 두 개인 수가 있다. 어느 자리 이후로 9만 이어지는 표기와, 같은 수의 0만 이어지는 표기가 짝을 이룬다 — $0.4999\cdots$과 $0.5000\cdots$은 같은 수다. 그 밖의 실수는 십진 표기가 유일하다. (이 사실은 지금은 인정하고 쓴다. 증명에는 급수 수렴에 관한 준비가 더 필요하며 이 과정 밖의 주제다. 1권 49주차 §1.5도 같은 처리를 했다.)

그러므로 제작하는 $y$의 각 자리를 **0도 9도 아닌 두 숫자** 중에서만 고르기로 약속한다. 이 교안은 **5와 6**을 쓴다(1권 49주차는 4와 5를 썼다 — 두 숫자가 서로 다르고 둘 다 0도 9도 아니기만 하면 어느 쌍이든 된다).

:::{container} quotebox
**확인 8.** 자릿수를 5와 6으로 제한하면 두 함정이 각각 어떻게 차단되는가. 그리고 이 제한이 덤으로 보장해 주는 것은 무엇인가.
:::

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

첫째 함정(자리 넘침) 차단: 규칙이 "$d_{kk} \ne 5$이면 5, $d_{kk} = 5$이면 6"이므로

어떤 $d_{kk}$에 대해서도 값이 정해지고 그 값은 언제나 한 자리 숫자다.

둘째 함정(이중 표기) 차단: $y$의 전개에는 9만 이어지는 꼬리도 0만 이어지는 꼬리도

없으므로 $y$의 십진 표기는 유일하다. 따라서 "$k$번째 자리가 다르다"에서

"$y \ne x_k$"로 넘어가는 걸음이 정당해진다.

덤: 모든 자리가 5 이상 6 이하이므로 $0.555\cdots \le y \le 0.666\cdots$이고,

특히 $0 < y < 1$이다 — 걸음 ⑤의 자격 검증이 같은 규칙에서 함께 나온다.
:::

### 7 가산성 보존 성질 — 부품 목록

앞으로의 증명은 매번 전단사를 새로 만들지 않는다. 아래 네 줄을 부품으로 인용한다.

| **성질** | **진술** | **증명 위치** |
|---|---|---|
| (P1) 부분집합 | $A$가 가산이고 $B \subseteq A$이면 $B$도 가산이다 | 아래 스케치 |
| (P2) 합집합 | 가산집합 두 개의 합집합은 가산이다. 가산 개의 가산집합의 합집합도 가산이다 | 서로소인 두 가산무한은 문제 8, 일반의 경우(한쪽이 유한인 경우$\cdot$서로소가 아닌 경우 포함)는 문제 16 |
| (P3) 곱 | $A$, $B$가 가산이면 $A \times B$도 가산이다 | 문제 9의 일반화 — 이번 주에는 인정하고 쓴다 |
| (P4) 포함 | 비가산집합을 부분집합으로 갖는 집합은 비가산이다 | (P1)의 대우 |

**(P1)의 스케치.** $A$가 유한이면 $B$도 유한이므로 가산이다. $A$가 가산무한이면 목록 $a_1, a_2, a_3, \ldots$이 있으므로, 그 목록에서 $B$에 속하는 항만 순서대로 남긴다. 남은 것이 유한하면 $B$는 유한이고, 무한하면 남은 순서가 그대로 $B$의 목록이 된다 — 빠짐이 없고(원래 목록이 $A$를 덮었으므로 $B$의 원소도 전부 등장한다) 겹침도 없다(원래 목록에 겹침이 없었다). 어느 쪽이든 $B$는 가산이다.

**(P4)는 (P1)의 대우다.** $B \subseteq A$이고 $B$가 비가산이라 하자. $A$가 가산이면 (P1)에 의해 $B$가 가산이 되어 모순이므로 $A$는 비가산이다. 이 한 줄이 예제 2.3의 마지막 걸음에서 $(0,1)$의 비가산성을 $\mathbb{R}$로 옮기는 데 쓰인다.

(P2)와 (P3)은 이번 주에 **인정하고 쓰되**, 그 핵심 경우의 증명을 문제 8$\cdot$9$\cdot$16에서 직접 만든다. 인용할 때는 "(P2)에 의해"가 아니라 "문제 8에 의해"처럼 출처를 밝힌다.

:::{container} quotebox
**확인 9.** (P1)의 대우가 (P4)임을 확인했다. (P2)의 대우도 쓸모가 있는가. "$A \cup B$가 비가산이면 $A$와 $B$ 중 적어도 하나는 비가산이다"가 참인지 판정해 보자.
:::

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

참이고, (P2)의 대우가 정확히 그 문장이다. (P2)는 "$A$ 가산이고 $B$ 가산이면

$A \cup B$ 가산"이므로, 대우는 "$A \cup B$가 가산이 아니면 $A$가 가산이 아니거나

$B$가 가산이 아니다"이다(연언의 부정은 선언 — C3주차 §1.7의 드모르간 1).

이 대우가 실제로 일하는 곳이 문제 17이다. $\mathbb{R} = \mathbb{Q} \cup I$이고

$\mathbb{R}$이 비가산인데 $\mathbb{Q}$가 가산이므로, 남은 $I$가 비가산일 수밖에 없다.
:::

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

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

| **근거** | **이번 주에 추가$\cdot$갱신되는 것** | **이번 주에는 이렇게 쓴다** |
|---|---|---|
| ① 정의 | **정의 1.1, 1.2, 1.3** | "$\vert A\vert = \vert B\vert$" $\leftrightarrow$ "전단사 $A \to B$가 존재" 사이를 번역한다 |
| ② 닫힘성 | 변화 없음 | 정수$\cdot$유리수의 사칙 결과가 그 세계에 남음을 별도 설명 없이 쓴다 |
| ③ 등식$\cdot$부등식의 성질 | 변화 없음 | $2n_1 = 2n_2$에서 $n_1 = n_2$를 얻는 것이 단사 증명의 본체다 |
| ④ 이미 증명한 명제 | 합성의 단사$\cdot$전사 보존(C12주차 §1.4, 문제 8) $\cdot$ 전단사와 역함수의 동치(C12주차 핵심 정리 1.5) $\cdot$ 대등의 반사$\cdot$대칭$\cdot$추이(1권 48주차 문제 7) $\cdot$ 모든 자연수는 짝수이거나 홀수(1권 17주차) $\cdot$ 십진 표기가 두 개인 수는 9 또는 0의 꼬리를 갖는 경우뿐(인정하고 쓴다) $\cdot$ 기약분수 표현의 유일성(인정하고 쓴다 — 존재는 1권 33주차, 유일성의 증명은 유클리드 보조정리가 서는 C15주차; 문제 11) $\cdot$ 탄젠트가 $(-\frac\pi2, \frac\pi2)$에서 순증가하며 그 구간을 $\mathbb{R}$ 전체로 보내고 그 역함수가 아크탄젠트임(인정하고 쓴다 — 이 과정 밖의 주제; 문제 13) $\cdot$ 이번 주 §1.7의 (P1)$\cdot$(P4)와 예제 | "C12주차 문제 8에 의해"처럼 출처를 대고 한 줄로 끝낸다 |

목록 밖의 것은 이번 주에도 근거가 되지 않는다. 특히 **"빽빽하니까 많다"와 "부분이니까 작다"는 근거가 아니다** — 전자는 문제 11이, 후자는 예제 2.1이 반례다.

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

(가) "$\mathbb{Q}$는 수직선에 조밀하게 깔려 있으므로 $\mathbb{N}$보다 크다."

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

(다) "$2n_1 = 2n_2$이므로 $n_1 = n_2$이다."
:::

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

(가) 불허 — 목록 밖이다. 조밀함은 크기의 판정 기준이 아니며, 문제 11에서 실제로

$\mathbb{Q}^+$가 가산임이 증명된다.

(나) 허용 — 근거 ④. C12주차 §1.4의 합성 보존 성질(단사 보존과 전사 보존)을

함께 인용한 것이고, 결론은 1권 48주차 문제 7의 추이성과 같다.

(다) 허용 — 근거 ③. 양변을 0이 아닌 수로 나누는 조작이다.
:::