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

## 예제 — 대각선 논법을 함께 만들기

완성된 증명을 먼저 보이지 않는다. §1.4에서 관찰한 것을 재료로, 백지에서 한 줄씩 만든다. 각 단계에서 확인 상자의 빈칸을 연필로 먼저 채운 뒤 답을 연다.

### 예제 2.1 — 대각선 논법 (칸토어, 1891)

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

**설계 — 쓰기 전에 정하는 것.** 정의 49.1이 요구하는 조각 둘 가운데 첫째(유한하지 않다)를 먼저 확인해 두고, 가정이 주는 것(출발점)과 만들어야 할 것(도착점)을 정의로 번역한다. 결론이 비존재 명제이므로 귀류법을 쓴다 (21주차) — 그러면 부정한 결론이 가정 자리로 내려온다.

|  | **말** | **번역** |
|---|---|---|
| 먼저 확인할 것 | $(0,1)$은 유한하지 않다 | $\frac12, \frac13, \frac14, \dots$이 서로 다른 원소로 들어 있다 |
| 가정 (귀류로 놓는 것) | $(0,1)$은 가산이다 | 유한하지 않으므로 가산 무한이고, 곧 $(0,1)$의 빠짐없는 목록 $r_1, r_2, r_3, \dots$이 존재한다 |
| 목표 (만들 것) | 모순 | $\underline{\quad(?)\quad}$ |

:::{container} quotebox
**확인 10.** 목표 칸의 빈칸을 채워 보자. 귀류법에서 도착점은 서로 어긋나는 두

문장이다. 위 가정과 어긋나게 하려면 무엇을 **제작**해야 하는가.
:::

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

$(0,1)$에 속하면서 목록에 없는 원소 $b$ 하나. 가정은 "목록에 빠짐이 없다"이므로,

그 목록이 빠뜨린 원소를 하나만 실제로 제시하면 두 문장이 정면으로 충돌한다.

출발점(목록 하나)과 도착점(목록 밖 원소 하나)이 정해졌다. 그 사이가 제작이다.
:::

**1단계 — 유한하지 않음을 확인하고 귀류 가정을 쓴다.** 정의 49.1은 조각 둘을 요구한다 — 유한하지 않다, 그리고 전단사가 없다. 첫 조각은 한 줄로 끝나고 둘째 조각이 이번 주의 본론이다. 둘째 조각의 첫 문장은 창작이 아니라 정해진 문형이다 — 21주차의 오프닝을 그대로 쓴다.

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

(가) "$(0,1)$은 $\underline{\qquad}$을 서로 다른 원소로 포함하므로 유한하지 않다."

(나) "모순을 이끌어내기 위해 $(0,1)$이 $\underline{\quad}$이라고 가정하자.

유한하지 않으므로 $\underline{\qquad}$이고, 따라서 $\underline{\qquad}$이 존재한다."
:::

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

(가) $\frac12, \frac13, \frac14, \dots$ — 서로 다른 원소가 무한히 많다.

(나) "모순을 이끌어내기 위해 $(0,1)$이 **가산**이라고 가정하자. 유한하지 않으므로

**가산 무한**이고, 따라서 $(0,1)$의 원소를 빠짐없이 늘어놓은

**목록 $r_1, r_2, r_3, \dots$**이 존재한다."

가운데 문장을 건너뛰면 목록이 나오지 않는다. 정의 48.2의 "가산"은 유한인 경우도

품고 있고, $\mathbb{N}$으로 첨자가 붙은 무한 목록은 가산 무한일 때만 나오기

때문이다 — §1.3의 조각 삭제 실험에서 "유한하지도 않고"가 빠지면 정의가 무너진다고

한 그 조각이 여기서 실제로 일한다.

그리고 "빠짐없이"가 나중에 무너뜨릴 문장이다. 이 낱말을 적어 두지 않으면

마지막 줄에서 무엇과 충돌하는지가 흐려진다.
:::

**2단계 — 목록을 무한 숫자표로 편다.** 목록은 아직 수의 나열일 뿐이고, 대각선을 뽑으려면 각 항의 자릿수가 이름을 가져야 한다.

:::{container} quotebox
**확인 12.** 다음 문장을 완성해 보자:

"각 $r_n$을 십진 전개로 쓰자: $r_n = 0.\,d_{n1}\,d_{n2}\,d_{n3}\cdots$

(여기서 $d_{nk}$는 $\underline{\qquad}$이다)."
:::

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

$d_{nk}$는 **$r_n$의 $k$번째 소수 자리 숫자**다. 목록이 $n$행 $k$열에 $d_{nk}$가

놓인 무한 숫자표가 된다.
:::

:::{admonition} 표기 — $d_{nk}$
:class: quotebox

첨자가 둘인 기호다. "디 엔 케이"로 읽고, 앞 첨자가 행 번호(몇 번째 수인가),

뒤 첨자가 열 번호(그 수의 몇 번째 자리인가)를 뜻한다. 대각선 성분은 두 첨자가

같은 $d_{nn}$이다.
:::

**3단계 — 대각선을 비틀어 $b$를 제작한다.** §1.4의 관찰을 규칙으로 굳히되, §1.5에서 정한 안전장치(4와 5만 쓰기)를 함께 넣는다.

:::{container} quotebox
**확인 13.** 제작 규칙의 빈칸을 채워 보자.

$b = 0.\,b_1\,b_2\,b_3\cdots$을 다음과 같이 정한다:

$b_n = 5$ ($d_{nn} \neq \underline{\quad}$일 때), $b_n = 4$ ($d_{nn} = \underline{\quad}$일 때).

이 규칙이 보장하는 것을 한 문장으로 덧붙여 보자.
:::

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

두 빈칸 모두 $5$다. 곧 대각선 성분이 5가 아니면 5를 쓰고, 5이면 4를 쓴다.

이 규칙이 보장하는 것: 모든 $n$에 대해 $b_n \neq d_{nn}$이다. 규칙이 보는 것은

표 전체가 아니라 **대각선 성분 $d_{nn}$ 하나**뿐이라는 점이 중요하다 — 그래서

어떤 표가 와도 규칙을 적용할 수 있다.
:::

**4단계 — $b$가 무대 안에 있는지 확인한다.** 제작한 것이 $(0,1)$ 밖으로 떨어지면 모순이 되지 않는다. 이 확인은 형식적 절차가 아니라 논법의 필수 단계다 (빠뜨렸을 때 무슨 일이 생기는지는 문제 9에서 본다).

:::{container} quotebox
**확인 14.** 4와 5만 쓴다는 규칙에서 두 가지가 따라 나온다. 각각 무엇인가.
:::

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

① $0.444\cdots \le b \le 0.555\cdots$이므로 $b \in (0,1)$이다 — 무대 안에 있다.

② $b$의 전개에는 9만 이어지는 꼬리도 0만 이어지는 꼬리도 없으므로 $b$의 십진

표기는 유일하다 — §1.5의 안전장치가 여기서 쓰인다.
:::

**5단계 — $b$가 목록의 모든 항과 다름을 보인다.** 여기가 논증의 심부다.

:::{container} quotebox
**확인 15.** 다음 문장을 완성해 보자:

"임의의 $n$에 대해 $b \neq r_n$이다. 만약 $b = r_n$이라면, $b$의 표기가

$\underline{\qquad}$하므로 표의 $n$행에 적힌 전개가 곧 $b$의 전개여야 한다.

그런데 $\underline{\qquad}$이므로 두 전개는 $n$번째 자리에서 다르다 — 모순이다."
:::

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

첫째 빈칸: **유일**. 둘째 빈칸: **$b_n \neq d_{nn}$**.

정리하면 — $b$는 두 표기를 갖는 수가 아니므로, $b = r_n$이라면 $r_n$의 전개

$0.d_{n1}d_{n2}\cdots$가 $b$의 전개 $0.b_1b_2\cdots$와 자리마다 같아야 한다.

그런데 $n$번째 자리에서 $b_n \neq d_{nn}$이다. 따라서 $b \neq r_n$이다.

4단계의 표기 유일성이 여기서 정확히 소비된다.
:::

**6단계 — 모순을 선언한다.**

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

"따라서 $b \in (0,1)$인데 목록의 어느 항과도 같지 않다 — 목록이

$\underline{\qquad}$이라는 가정과 모순이다. 그러므로 $(0,1)$은

$\underline{\quad}$이다. $\blacksquare$"
:::

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

첫째 빈칸: **빠짐없다**. 둘째 빈칸: **비가산**.

(1단계에서 $(0,1)$이 유한하지 않음을 이미 확인해 두었으므로, 목록의 비존재가

나오는 이 자리에서 정의 49.1의 두 조각이 모두 채워진다.)
:::

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

| 증명의 한 줄 | 왜 이 줄을 쓰는가? |
|---|---|
| $(0,1)$은 $\frac12, \frac13, \frac14, \dots$을 서로 다른 원소로 포함하므로 유한하지 않다. 모순을 이끌어내기 위해 $(0,1)$이 가산이라고 가정하자. 유한하지 않으므로 가산 무한이고, 따라서 빠짐없는 목록 $r_1, r_2, r_3, \dots$이 존재한다. | 정의 49.1의 첫 조각(유한하지 않다)을 먼저 처리하고, 둘째 조각을 귀류법으로 친다(21주차). 가운데 문장이 없으면 "가산"에서 목록이 나오지 않는다 — 정의 48.2의 가산에는 유한도 들어 있다. "빠짐없음"은 마지막 줄에서 무너뜨릴 문장이므로 여기에 적어 둔다. |
| 각 $r_n$을 십진 전개로 쓰자: $r_n = 0.\,d_{n1}\,d_{n2}\,d_{n3}\cdots$ ($d_{nk}$는 $r_n$의 $k$번째 소수 자리). | 목록을 무한 숫자표로 바꾼다 — $n$행 $k$열에 $d_{nk}$. 자릿수에 이름이 생겨야 대각선을 뽑을 수 있다. |
| 새 실수 $b = 0.\,b_1\,b_2\,b_3\cdots$을 다음 규칙으로 제작한다: $d_{nn} \neq 5$이면 $b_n = 5$, $d_{nn} = 5$이면 $b_n = 4$. | 대각선 성분 $d_{nn}$ 하나만 보고 그것과 다르게 고른다 — 새 대상을 규칙으로 정의하는 줄이므로 근거를 붙일 자리가 아니다. 규칙이 표 전체를 보지 않으므로 어떤 목록에도 그대로 적용된다. |
| $b$는 4와 5만으로 이루어지므로 $0.444\cdots \le b \le 0.555\cdots$이고, 따라서 $b \in (0,1)$이다. 또 9로만 이어지는 꼬리도 0으로만 이어지는 꼬리도 없으므로 $b$의 십진 표기는 유일하다. | 제작물의 소속 확인(근거 ①)과 표기 유일성 확보. 이 줄이 빠지면 다음 줄과 마지막 줄이 함께 무너진다. |
| 임의의 $n$에 대해 $b \neq r_n$이다: $b = r_n$이라면 표기의 유일성에 의해 $n$행의 전개가 곧 $b$의 전개여야 하는데, $n$번째 자리에서 $b_n \neq d_{nn}$이다. | 목록의 **모든** 항과 각각 다른 자리에서 어긋난다. 앞 줄에서 확보한 유일성이 여기서 쓰인다. |
| 따라서 $b \in (0,1)$인데 목록에 없다 — "빠짐없는 목록"이라는 가정과 모순이다. 곧 $(0,1)$의 빠짐없는 목록은 존재하지 않는다. 첫 줄에서 $(0,1)$이 유한하지 않음도 확인했으므로 정의 49.1의 두 조각이 모두 채워진다 — $(0,1)$은 비가산이다. $\blacksquare$ | 귀류 종결. 특정 목록이 아니라 **임의의** 목록이 실패한다는 점이 이 논법의 요점이다. 정의 49.1이 조각 둘을 요구하므로 결론 줄에서 둘을 나란히 짚는다. |

**이 여섯 줄이 "모든" 목록을 처리하는 이유.** §1.4의 표를 넣어 읽어 보자. 대각선 성분이 $6, 5, 1, 8$이므로 규칙이 만드는 것은 $b = 0.5455\cdots$이고, $b$는 $r_1$과 첫째 자리에서($5 \neq 6$), $r_2$와 둘째 자리에서($4 \neq 5$), $r_3$과 셋째 자리에서($5 \neq 1$), $r_4$와 넷째 자리에서($5 \neq 8$) 다르다. 전혀 다른 표를 넣어도 모든 줄이 똑같이 작동한다.

:::{container} quotebox
**확인 17.** 이 증명이 처리하는 목록은 어느 쪽인가.

(가) 방금 넣어 본 표 하나  (나) 아무 목록이나 전부
:::

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

(나). 증명의 어느 줄도 $d_{nk}$가 특정 숫자라는 사실을 쓰지 않았기 때문이다 —

쓴 것은 "$d_{nn}$이 5인지 아닌지"뿐이고, 그 두 경우 모두에 규칙이 답을 준다.

그래서 이 증명 한 번이 무한히 많은 목록을 한꺼번에 반박한다. §1.1의 시도가

메우지 못하던 간격이 여기서 메워진다.
:::

**[주의]  자주 하는 실수: 소속 확인 생략.** 4단계의 "$b \in (0,1)$"을 빼고 쓰는 경우가 많다. 제작물이 무대 밖으로 떨어지면 "목록이 빠뜨렸다"는 말 자체가 성립하지 않는다 — 애초에 담을 의무가 없는 것을 안 담은 것이기 때문이다. 이 생략이 실제로 증명을 무효로 만드는 상황을 문제 9에서 다룬다.

### 예제 2.2 — 무리수는 비가산

**명제.** 무리수 전체의 집합 $\mathbb{I} = \mathbb{R} - \mathbb{Q}$는 비가산이다.

:::{admonition} 표기 — $\mathbb{I}$
:class: quotebox

무리수 전체의 모임을 $\mathbb{I}$로 쓴다. "아이"로 읽고, $\mathbb{R}$에서

$\mathbb{Q}$를 뺀 차집합(5주차)이라는 뜻이다. $\mathbb{Q} \cap \mathbb{I} = \emptyset$이고

$\mathbb{Q} \cup \mathbb{I} = \mathbb{R}$이다.
:::

이번에는 설계만 함께 하고, 본문은 완성본으로 본다. 이 증명에는 대각선이 나오지 않는다 — 이미 증명된 결과 세 개를 조립하는 근거 ④의 증명이다.

:::{container} quotebox
**확인 18.** 설계표를 채워 보자.

가정 (귀류로 놓는 것): $\mathbb{I}$가 $\underline{\quad}$이다.

손에 있는 부품 세 개: ① $\mathbb{Q}$는 $\underline{\quad}$ (48주차 문제 15)

② 서로소인 두 **가산 무한** 집합의 합집합은 $\underline{\quad}$ (48주차 문제 14)

③ $\mathbb{R}$는 $\underline{\quad}$ (예제 2.1과 문제 8 — 문제 8은 §4에서 증명한다)

충돌 지점: $\underline{\qquad}$
:::

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

가정: $\mathbb{I}$가 **가산**이다.

부품: ① **가산** ② **가산 무한** ③ **비가산**.

충돌 지점: ①과 ②로부터 $\mathbb{R} = \mathbb{Q} \cup \mathbb{I}$가 가산이라는 결론이

나오는데, ③은 그 부정이다. 두 문장이 정면으로 어긋난다.

한 가지 손질이 필요하다 — ②가 요구하는 것은 두 집합이 **가산 무한**인 것인데,

가정한 "$\mathbb{I}$가 가산"에는 정의 48.2에 따라 "$\mathbb{I}$가 유한"인 경우도

들어 있다. 그래서 증명이 경우 둘로 갈라진다.

설계표가 완성되는 순간 증명의 줄 수까지 정해진다 — 부품 세 개를 순서대로 놓고

충돌을 선언하면 끝난다.
:::

| 증명의 한 줄 | 왜 이 줄을 쓰는가? |
|---|---|
| 모순을 이끌어내기 위해 $\mathbb{I}$가 가산이라고 가정하자. | 귀류 오프닝. 결론이 "비가산"이라는 비존재 명제이므로 부정해 가정 자리로 내린다. |
| $\mathbb{Q}$는 가산이고(48주차 문제 15), $\mathbb{N} \subseteq \mathbb{Q}$이므로 유한하지 않다 — 곧 $\mathbb{Q}$는 가산 무한이다. 또 $\mathbb{Q} \cap \mathbb{I} = \emptyset$이다. | 부품 ①을 꺼내되, 부품 ②가 요구하는 형태(가산 무한)까지 맞춘다. 서로소 조건도 같은 줄에서 확인한다. |
| $\mathbb{I}$가 가산 무한인 경우: 서로소인 두 가산 무한 집합의 합집합은 가산 무한이므로(48주차 문제 14), $\mathbb{R} = \mathbb{Q} \cup \mathbb{I}$는 가산이다. | 부품 ②를 적용한다(근거 ④). 두 목록을 교대로 엮으면 합집합의 목록이 된다. 인용한 명제의 조건을 그대로 옮겨 적는다. |
| $\mathbb{I}$가 유한인 경우: $\mathbb{Q}$의 목록 앞에 그 유한 개를 덧붙이면 $\mathbb{R}$의 목록이 되므로, 이 경우에도 $\mathbb{R}$은 가산이다. | 가정한 "가산"에 함께 들어 있는 나머지 경우다. 48주차 문제 14가 덮지 않으므로 여기서 직접 처리한다. |
| 그러나 $(0,1) \subseteq \mathbb{R}$이고 $(0,1)$은 비가산이므로(예제 2.1), 문제 8에 의해 $\mathbb{R}$은 비가산이다. | 부품 ③. 예제 2.1의 결과를 $\mathbb{R}$까지 끌어올린다. 문제 8은 §4에서 증명한다 — 지금은 결과만 앞당겨 쓴다. |
| 두 경우 모두에서 "$\mathbb{R}$은 가산"이 나왔고, 이는 바로 앞 줄과 모순이다. 따라서 $\mathbb{I}$는 비가산이다. $\blacksquare$ | 귀류 종결. 부정한 가정이 무너졌으므로 원래 결론이 남는다. |

**왜 경우가 둘로 갈라지는가.** 48주차 문제 14가 다루는 것은 두 집합이 **가산 무한**일 때다. 그런데 귀류로 놓은 "$\mathbb{I}$가 가산"에는 정의 48.2에 따라 "$\mathbb{I}$가 유한"인 경우도 들어 있다. 인용한 명제가 덮지 않는 경우를 남겨 두면 증명이 성립하지 않으므로, 그 경우를 표 안에서 한 행으로 따로 처리했다. 인용문의 조건을 그대로 옮겨 적으면 이런 누락이 눈에 띈다.

**관찰.** 유리수는 목록 한 줄로 다 담기고, 무리수는 어떤 목록으로도 담기지 않는다. 21주차 예제 2.2에서 $\sqrt2$ 하나를 증명하는 데 한 주가 걸렸는데, 이번 주의 결과는 무리수 쪽이 유리수 쪽보다 큰 등급이라는 것이다. 그러면서도 유리수는 수직선 어디에나 조밀하다(15주차 문제 17) — 조밀함과 크기가 별개라는 §0 유형 2의 지적이 여기서 확정된다.

### 예제 2.3 — 칸토어의 정리

**명제.** 임의의 집합 $A$에 대해, $A$에서 $\mathcal{P}(A)$로의 전사는 존재하지 않는다. (따라서 $|A| \neq |\mathcal{P}(A)|$이다.)

이번에는 설계부터 스스로 해 보자. 대각선을 뽑을 숫자표가 없는 대신, "$x$가 $f(x)$에 속하는가"라는 참$\cdot$거짓 표가 있다.

:::{container} quotebox
**확인 19.** 설계표를 채워 보자.

가정 (귀류로 놓는 것): 전사 $f : A \to \mathcal{P}(A)$가 $\underline{\quad}$한다.

대각선 성분에 해당하는 것: 각 $x \in A$에 대한 판정 "$\underline{\qquad}$"

비틀기: 그 판정을 뒤집어 만든 집합 $B = \{x \in A : \underline{\qquad}\}$

소속 확인: $B \in \underline{\qquad}$

충돌: $f(a) = B$인 $a$를 소환한 뒤 "$a \in B$인가"를 묻는다.
:::

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

존재. / 판정: "$x \in f(x)$인가". / $B = \{x \in A : x \notin f(x)\}$. /

$B \subseteq A$이므로 $B \in \mathcal{P}(A)$.

예제 2.1에서 $n$번째 수의 $n$번째 자리를 뒤집었듯이, 여기서는 $x$번째 집합의

$x$에 대한 소속 여부를 뒤집는다. 뒤집는 대상이 숫자에서 참$\cdot$거짓으로 바뀌었을

뿐이다.
:::

**증명.** 전사 $f : A \to \mathcal{P}(A)$가 존재한다고 가정하자. 집합

$$
B = \{x \in A : x \notin f(x)\}
$$

을 만든다. $B \subseteq A$이므로 $B \in \mathcal{P}(A)$이고, $f$가 전사이므로 $f(a) = B$인 $a \in A$가 존재한다. 이제 "$a \in B$인가"를 묻는다.

$a \in B$라고 하자. $B$의 조건에 의해 $a \notin f(a)$인데, $f(a) = B$이므로 $a \notin B$이다 — 모순이다. 반대로 $a \notin B$라고 하자. $f(a) = B$이므로 $a \notin f(a)$이고, 이는 $B$의 조건 그 자체이므로 $a \in B$이다 — 역시 모순이다. $a \in B$와 $a \notin B$ 중 하나는 반드시 참인데(배중률, 26주차 §1.4 — 근거 ④로 인정하고 쓰는 원리) 어느 쪽도 불가능하다. 따라서 전사 $f$는 존재하지 않는다. $\blacksquare$

이번 증명은 표 없이 산문으로 적었다. 표는 연습 단계의 장치이고, 실전의 증명은 처음부터 끝까지 이런 산문이다.

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

"$A$에서 $B$로의 단사는 존재하지만 전단사는 존재하지 않는다"를 줄여 쓴 것이다.

$A$와 $\mathcal{P}(A)$의 경우 단사는 $x \mapsto \{x\}$가 있고 전단사는 위 정리로

배제되므로 $|A| < |\mathcal{P}(A)|$이다. 이 부등호를 반복하면

$|\mathbb{N}| < |\mathcal{P}(\mathbb{N})| < |\mathcal{P}(\mathcal{P}(\mathbb{N}))| < \cdots$ —

무한의 등급이 끝없이 올라간다.
:::

**관찰.** 집합 $B$의 자기 참조 구조는 6주차 §1.7 러셀의 역설($\{X : X \notin X\}$)과 같다. 러셀에서는 집합 개념 자체의 위기였던 것이, $A$와 $f$라는 울타리 안에서는 "전사가 없다"는 정리가 된다. 같은 구조가 무대에 따라 역설도 되고 정리도 된다.

### 관찰 — 예제 2.1과 2.3의 같은 뼈대

두 증명은 소재가 전혀 다르다. 한쪽은 실수의 소수 자리, 다른 쪽은 원소의 소속 여부다. 그런데 단계가 같다. 대응표의 빈칸을 채워 보자.

:::{container} quotebox
**확인 20.** 다음 대응표의 빈칸 (1)(2)(3)을 채워 보자.

① 빠짐없음의 가정: 예제 2.1은 목록 $r_1, r_2, \dots$ / 예제 2.3은 전사 $f$

② 대각선 성분: 예제 2.1은 $d_{nn}$ / 예제 2.3은 $\underline{\quad(1)\quad}$

③ 비틀기: 예제 2.1은 $b_n \neq d_{nn}$ / 예제 2.3은 $\underline{\quad(2)\quad}$

④ 소속 확인: 예제 2.1은 $b \in (0,1)$ / 예제 2.3은 $\underline{\quad(3)\quad}$

⑤ 모든 항과 결별: 예제 2.1은 모든 $n$에서 $b \neq r_n$ / 예제 2.3은 모든 $x$에서 $B \neq f(x)$
:::

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

(1) 판정 "$x \in f(x)$인가"  (2) $x \in B \iff x \notin f(x)$

(3) $B \in \mathcal{P}(A)$

다섯 단계가 한 칸도 어긋나지 않는다. 예제 2.1의 숫자표에서 행을 $x$, 열을 $x$로

두고 성분을 "소속 여부"로 바꾸면 예제 2.3이 된다.
:::

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

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

**대각선 논법의 5단계 틀**

① 빠짐없음을 가정한다 $\to$ ② 대각선 성분을 지정한다 $\to$ ③ 그것과 다르게 비틀어 새 원소를 제작한다 $\to$ ④ 제작물이 무대 안에 있음을 확인한다 $\to$ ⑤ 모든 항과 다름을 보이고 ①과 충돌시킨다
:::

이 다섯 칸에 들어가기 전에 한 줄이 더 필요하다 — 다루는 집합이 유한하지 않다는 확인이다. 정의 49.1이 조각 둘을 요구하고, ①의 "가산"에서 $\mathbb{N}$으로 첨자가 붙은 무한 목록이 나오려면 그 한 줄이 먼저 있어야 하기 때문이다(예제 2.1의 1단계).

예제 2.2는 이 틀이 아니다 — 이미 증명된 결과 세 개를 조립하는 근거 ④의 증명이다. 이번 주의 **새** 증명 틀은 이 둘이고, 여기에 앞서 배운 두 서식이 함께 쓰인다 — 대우(19주차, 문제 8)와 전단사 제시(48주차 정의 48.1의 서식, 문제 11$\cdot$17). 문제 7~14가 이 넷을 번갈아 요구한다.

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

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

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

가정된 목록의 첫 네 실수가 다음과 같다 (굵은 숫자가 대각선 성분 $d_{nn}$이다):

$$
r_1 = 0.\mathbf{3}1415\cdots,\quad r_2 = 0.2\mathbf{7}182\cdots,\quad r_3 = 0.14\mathbf{1}42\cdots,\quad r_4 = 0.999\mathbf{5}9\cdots
$$

예제 2.1의 규칙($d_{nn} \neq 5$이면 5, $d_{nn} = 5$이면 4)으로 $b$의 첫 네 자리를 만들면:

$$
b_1 = \underline{\quad(1)\quad},\quad b_2 = \underline{\quad(2)\quad},\quad b_3 = \underline{\quad(3)\quad},\quad b_4 = \underline{\quad(4)\quad}
$$

그리고 $b = 0.b_1b_2b_3b_4\cdots$가 $r_3$과 다른 이유: $\underline{\quad(5)\quad}$번째 소수 자리가 다르기 때문이다.

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

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

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

**증명.** $(0,1)$은 $\frac12, \frac13, \frac14, \dots$을 서로 다른 원소로 포함하므로 $\underline{\quad(1)\quad}$. 모순을 이끌어내기 위해 $(0,1)$이 $\underline{\quad(2)\quad}$이라고 가정하자. 유한하지 않으므로 $\underline{\quad(3)\quad}$이고, 따라서 빠짐없는 목록 $r_1, r_2, \dots$이 존재한다. 각 $r_n$을 십진 전개 $r_n = 0.\,d_{n1}d_{n2}d_{n3}\cdots$로 쓰자. 새 실수 $b = 0.\,b_1b_2b_3\cdots$을 $d_{nn} \neq 5$이면 $b_n = \underline{\quad(4)\quad}$, $d_{nn} = 5$이면 $b_n = \underline{\quad(5)\quad}$으로 제작한다.

$b$는 4와 5만으로 이루어지므로 $\underline{\quad(6)\quad}$이고(무대 안에 있다), $\underline{\quad(7)\quad}$로 이어지는 꼬리가 없으므로 $b$의 십진 표기는 유일하다. 임의의 $n$에 대해 $b = r_n$이라면 표기의 유일성에 의해 두 전개가 자리마다 같아야 하는데 $\underline{\quad(8)\quad}$이므로, $b \neq r_n$이다.

따라서 $b \in (0,1)$인데 목록에 없다 — $\underline{\quad(9)\quad}$이라는 가정과 모순이다. 빠짐없는 목록이 존재할 수 없고 $(0,1)$이 유한하지도 않으므로, 정의 49.1에 의해 $(0,1)$은 비가산이다. $\blacksquare$

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

이번에는 5단계 틀의 각 칸을 통째로 채운다. 소재가 실수에서 0$\cdot$1 수열로 바뀐다.

**명제.** 0과 1로만 이루어진 무한 수열 전체의 집합 $S$는 비가산이다.

**증명의 뼈대.**

- ① 빠짐없음의 가정: $\underline{\quad(1)\quad}$
- ② 대각선 성분의 지정: $\underline{\quad(2)\quad}$
- ③ 비틀기와 제작: $\underline{\quad(3)\quad}$
- ④ 소속 확인: $\underline{\quad(4)\quad}$
- ⑤ 모든 항과 결별, 그리고 모순: $\underline{\quad(5)\quad}$

(이 훈련이 문제 10의 예행연습이다. 십진 표기의 이중성이 없으므로 ④가 훨씬 짧아진다.)

## 연습문제 (20문항)

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

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

답이 아니라 **근거**가 점수다. "$(0,1)$은 비가산이다(맞음)"는 0점이고,

"$(0,1)$이 유한하지 않음을 확인하고, 임의의 목록을 가정하고, 대각선을 비튼 $b$를

제작하고, $b \in (0,1)$을 확인하고, 모든 $n$에서 $b \neq r_n$을 보였으므로

비가산"이 만점이다.

특히 두 문구가 빠지면 감점이 아니라 증명이 성립하지 않는다 —

"**임의의** 목록"과 "$b$가 **무대 안에** 있다".

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

### 기본 ●○○

**1.** [백지] 비가산의 정의와 대각선 논법의 구도(목록 가정 $\to$ 대각선 비틀기 $\to$ 탈출자 $\to$ 모순)를 쓰시오.

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

정의는 §1.2, 구도는 §2 관찰의 5단계 틀이다. 정의에서는 "유한하지도 않고"와

"존재하지 않는다" 두 조각을, 구도에서는 "임의의"라는 낱말을 빠뜨리지 않는다.
:::

**2.** 빈칸 훈련(§3 훈련 1)을 백지에서 완성하시오.

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

각 $r_n$에서 뽑을 자리는 하나뿐이다 — 행 번호와 같은 열. 뽑은 숫자가 5인지

아닌지만 보고 4 또는 5를 적는다.
:::

**3.** 다음 목록(첫 5항)에 대해 대각선 규칙으로 $b$의 첫 다섯 자리를 제작하시오: $r_1 = 0.50000\cdots$, $r_2 = 0.12345\cdots$, $r_3 = 0.33333\cdots$, $r_4 = 0.98765\cdots$, $r_5 = 0.11115\cdots$

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

먼저 대각선 성분 다섯 개를 따로 적는다: $r_1$의 1번째, $r_2$의 2번째, …

그다음 각각에 규칙을 적용한다. 5가 나온 자리에서만 4가 된다.
:::

**4.** "$0.4999\cdots = 0.5$" 문제가 대각선 논법을 위협하는 시나리오를 설명하고, "4와 5만 사용" 규칙이 그것을 차단하는 이유를 쓰시오.

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

논법의 어느 줄이 "자리가 다르면 다른 수"를 쓰고 있는지 먼저 찾는다(예제 2.1의

다섯째 줄). 그 줄이 성립하지 않으면 결론이 어떻게 새어 나가는지 적는다.
:::

**5.** 예제 2.1을 백지에 재현하시오 (이번 주의 핵심 임무).

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

5단계 틀을 먼저 세로로 적어 놓고, 그 위에 "유한하지 않다" 한 줄을 얹은 뒤 칸을

채운다. 네 번째 칸(소속 확인)이 가장 자주 빠진다 — 그 칸에 두 문장(무대 안,

표기 유일)이 들어간다.
:::

**6.** 가산과 비가산 분류: $\mathbb{N}$, $\mathbb{Z}$, $\mathbb{Q}$, $(0,1)$, $\mathbb{R}$, 무리수, 짝수 — 각각 어느 쪽인지, 근거(주차$\cdot$정리)를 한 마디씩.

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

가산 쪽 넷은 전부 48주차에서 목록을 만들었고, 비가산 쪽 셋은 전부 이번 주

예제와 문제 8에서 나온다. 근거 없이 분류만 적으면 채점 기준상 0점이다.
:::

### 표준 ●●○

**7.** 예제 2.2(무리수 비가산)를 백지에 재현하시오.

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

대각선을 다시 그리려 하지 않는다. 이 증명은 부품 세 개(48주차 문제 15,

48주차 문제 14, 이번 주 문제 8)를 순서대로 놓는 것이 전부다.
:::

**8.** "비가산 집합을 포함하는 집합은 비가산" — 즉 $B \subseteq C$이고 $B$가 비가산이면 $C$도 비가산 — 임을 증명하시오. (힌트: 대우를 쓴다. $C$가 가산이면 그 목록에서 $B$의 원소만 남긴 부분 목록이 $B$를 목록화한다) 그리고 이것으로 $\mathbb{R}$의 비가산성을 $(0,1)$에서 유도하시오.

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

원명제를 직접 치려 하면 "$C$의 목록이 없다"를 보여야 해서 다룰 대상이 없다.

대우로 뒤집으면 가정 자리에 "$C$의 목록"이라는 손에 잡히는 대상이 생긴다

(19주차의 판단 기준). 건너뛰기 기술은 48주차 예제 2.3에서 이미 썼다.
:::

**9.** 대각선 논법이 "$\mathbb{Q} \cap (0,1)$에는 왜 적용되지 않는가?" — 유리수 목록(48주차)에 대각선 비틀기를 시도하면 어디서 무너지는지 설명하시오. (힌트: 제작된 $b$가 반드시 유리수인가?)

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

5단계 틀을 하나씩 대입해 보면 ①②③은 그대로 통과하고 ⑤의 앞부분도 성립한다.

무너지는 칸은 하나뿐이다.

예제 2.1의 "**[주의]**  자주 하는 실수" 상자가 이 문제의 예고였다.
:::

**10.** 0과 1로 된 무한 수열 전체의 집합 $S$ (예: $010110\cdots$)가 비가산임을 대각선 논법으로 증명하시오 (비틀기 규칙: $0 \leftrightarrow 1$ — 십진 표기의 함정도 없다).

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

훈련 3에서 뼈대를 세웠다. 비틀기 규칙은 한 줄로 적을 수 있다: $b_n = 1 - d_{nn}$.

두 수열이 같다는 것은 모든 자리가 같다는 뜻임을 마지막 줄에서 명시한다.
:::

**11.** 문제 10의 $S$와 $\mathcal{P}(\mathbb{N})$이 대등함을 논증하시오. (힌트: 부분집합 $X \subseteq \mathbb{N}$ $\leftrightarrow$ "소속 표시 수열"($n$번째 자리 = $n \in X$이면 1) — 12주차 문제 13$\cdot$31주차 예제 2.3의 넣음/뺌 목록의 무한판이다)

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

대등의 정의(48주차 정의 48.1)는 전단사 하나를 제시하고 단사$\cdot$전사를 각각

검증하라고 요구한다. 대응 자체는 힌트에 다 나와 있으므로, 점수는 두 검증에

있다. 전사 검증에서는 주어진 수열로부터 부분집합을 되돌려 만든다.
:::

**12.** 예제 2.3(칸토어의 정리)을 백지에 재현하시오.

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

빠뜨리기 쉬운 두 문장이 있다: "$B \subseteq A$이므로 $B \in \mathcal{P}(A)$"(소속

확인)와 "전사이므로 $f(a) = B$인 $a$가 존재한다"(원상 소환). 이 둘이 없으면

마지막 질문 "$a \in B$인가"를 던질 수 없다.
:::

**13.** 칸토어의 정리에서 $A = \mathbb{N}$으로 놓으면 무엇이 따라 나오는가 — 문제 10$\cdot$11과 연결해 "$\mathcal{P}(\mathbb{N})$ 비가산"의 두 증명(대각선 직접 / 칸토어 정리)을 비교하시오.

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

전단사는 전사이기도 하다. 전사가 없으면 전단사도 없다 — 이 한 줄이 정리에서

비가산으로 가는 다리다. 유한이 아님도 함께 확인해야 정의 49.1이 채워진다.
:::

**14.** (역사 문제) 다음 주장을 판정하시오: "무한은 다 같은 무한이다." — 이번 주의 어느 정리가 이것을 반증하며, 반증의 반례 쌍은 무엇인가?

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

"모든 무한집합 쌍은 대등하다"라는 $\forall$ 명제로 먼저 번역한다(10주차).

$\forall$ 명제의 반증에 필요한 것은 조합 하나다 — 이번 주에는 집합 두 개.
:::

### 도전 ●●●

**15.** 대각선 논법의 다음 오해를 교정하시오.

:::{container} quotebox
"탈출자 $b$를 목록 맨 앞에 추가해 새 목록 $b, r_1, r_2, \dots$을 만들면 되지 않나? 그러면 $b$도 목록에 있으니 모순이 사라진다."

(새 목록에 대각선 논법을 다시 적용하면? — "임의의 목록"이라는 $\forall$의 힘(10주차)으로 설명하시오.)
:::

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

새로 만든 것도 하나의 목록이다. 그 목록의 대각선 성분을 적어 보면 무슨 일이

생기는가. 이 오해는 증명된 명제의 $\forall$을 $\exists$로 읽은 데서 온다.
:::

**16.** 대각선 논법의 또 다른 오해를 교정하시오.

:::{container} quotebox
"$b$는 소수 전개가 무한히 길어서 실수가 아니라 '완성되지 않은 과정'이다. 그러므로 증명이 무효다."

(46주차 문제 14($0.999\cdots = 1$)의 정신으로: 무한 소수 전개란 무엇의 극한인가? $b$가 어엿한 실수인 이유를 급수의 언어로 쓰시오.)
:::

:::{admonition} 이 문제가 빌려 쓰는 사실
:class: quotebox

위로 유계인 증가 수열은 수렴한다(단조수렴정리). 46주차 §1에서 인정하고 쓴

사실이며, 완비성 공리에서 나온다 — 이 과정에서는 증명 없이 인정하고 쓴다.
:::

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

무한 소수 $0.b_1b_2b_3\cdots$의 정의를 46주차 §1의 급수 정의로 되돌려 적는다.

그다음 부분합 수열이 증가하는지, 무엇으로 위에서 막히는지를 확인한다.
:::

**17.** $(0, 1)$과 $[0, 1]$이 대등함을 다음 아이디어로 논증하시오: 가산 부분 $\left\{\frac12, \frac13, \frac14, \dots\right\}$ 안에서 힐베르트 호텔식 이동($\frac12 \mapsto \frac14$처럼 두 칸씩 밀어 $0, 1$을 끼워 넣기 — 구체적으로 $0 \mapsto \frac12$, $1 \mapsto \frac13$, $\frac1n \mapsto \frac1{n+2}$, 나머지는 그대로)이 전단사가 되는 이유를 점검하시오.

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

움직이는 원소와 제자리에 있는 원소를 두 무리로 나눈다. 검증할 것은 세 가지다:

움직이는 것끼리 겹치지 않는가, 움직인 것이 제자리 원소와 충돌하지 않는가,

$(0,1)$의 모든 원소가 어딘가에서 오는가. 48주차 문제 12의 정밀판이다.
:::

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

:::{container} quotebox
"$\mathbb{R}$이 비가산임을 보인다: $\mathbb{R}$은 무한하고, 48주차에서 본 가산 집합들($\mathbb{Z}, \mathbb{Q}$)과 달리 훨씬 빽빽하므로 목록화가 불가능하다. $\blacksquare$"

("빽빽함(조밀함)"이 크기의 증거가 되지 못하는 이유 — $\mathbb{Q}$가 바로 그 반례다 — 를 짚고, 올바른 증명이 갖춰야 할 것을 적으시오.)
:::

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

답안이 쓴 추론 형식을 한 문장으로 뽑아낸다: "빽빽하면 목록화 불가". 이 형식에

반례가 있는지 48주차의 결과에서 찾는다. §0의 유형 2가 같은 지점이었다.
:::

**19.** (읽을거리 + 서술) **연속체 가설**: "$|\mathbb{N}|$과 $|\mathbb{R}|$ 사이의 크기는 없다"는 칸토어의 추측은, 괴델(1940)과 코언(1963)에 의해 "표준 공리계(ZFC)로는 증명도 반증도 불가능"함이 밝혀졌다. 29주차의 "참/거짓/미해결" 3분류에 이 네 번째 상태("독립")를 추가해, 네 상태를 각각 한 문장으로 정리하시오.

:::{admonition} 새 낱말 — 독립 (independence)
:class: quotebox

어떤 명제가 주어진 공리계에서 **독립**이라는 것은, 그 공리계로부터 명제를

증명할 수도 없고 부정을 증명할 수도 없음이 **증명되었다**는 뜻이다.

미해결과 다르다 — 미해결은 아직 아무도 못 한 상태이고, 독립은 아무도 못 한다는

것 자체가 확정된 결과다. 6주차 §1.7에서 시작된 "공리로 관리되는 수학"의

귀결이며, 정식 취급은 대학 집합론으로 이월한다.
:::

**20.** (서술) 세 인류 유산 — √2 무리수(21주차), 소수 무한(21주차), 대각선 논법(이번 주) — 의 공통 구조를 분석하시오: 각각 무엇을 가정하고("전부 담았다"류의 가정), 무엇을 제작해("가정을 배반하는 증인") 무너뜨리는가. 그리고 "귀류법 + 제작"이 왜 무한을 다룰 때 되풀이해 쓰이는 절차인지 세 문장 이내로.

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

세 증명의 첫 문장과 제작물만 뽑아 표로 나란히 놓으면 구조가 드러난다.

21주차 예제 2.2$\cdot$2.3의 첫 문장을 각각 확인하고 오는 것이 출발점이다.
:::

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

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

**1차 시도 (4일차) — 틀 카드 허용.** 5단계 틀(§2 관찰)과 근거 목록(§1.6)만 펴 놓고, 예제 2.1을 처음부터 끝까지 적는다. 정의와 본문은 보지 않는다.

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

- [ ] 정의 49.1을 "유한하지도 않고 … 존재하지 않는다"까지 조각 그대로 썼다.
- [ ] 예제 2.1을 표 없이 백지에 재현했다 — 4/5 규칙과 그 이유(표기 유일성) 포함.
- [ ] 재현한 증명에서 5단계 틀의 각 칸을 손가락으로 짚을 수 있다.
- [ ] 예제 2.2의 세 부품($\mathbb{Q}$ 가산 무한, 서로소인 두 가산 무한의 합집합, $\mathbb{R}$ 비가산)을 근거와 함께 짚고, $\mathbb{I}$가 유한인 경우를 따로 처리했다.
- [ ] 예제 2.3의 집합 $B$를 쓰고, 6주차 러셀의 역설과의 관계를 한 문장으로 설명했다.
- [ ] 두 오해(문제 15$\cdot$16)의 교정을 재현했다.
- [ ] "무한에도 등급이 있다"를 반례 쌍($\mathbb{N}$과 $\mathbb{R}$)으로 설명했다.

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

| **막힌 지점** | **처방** |
|---|---|
| 첫 문장이 나오지 않는다 | 예제 2.1의 1단계 — 귀류 가정의 문형은 정해져 있다 |
| 제작 규칙을 세우지 못한다 | §1.4의 숫자표 — 보는 것은 $d_{nn}$ 하나뿐이다 |
| 왜 4와 5인지 설명하지 못한다 | §1.5 — 이중 표기의 발생 조건과 그 차단 |
| $b \in (0,1)$ 확인을 빠뜨린다 | 예제 2.1의 4단계와 문제 9 — 소속 확인이 빠지면 무엇이 무너지는가 |
| "목록을 고치면 되지 않나"가 남는다 | 문제 15 — 증명된 것은 $\forall$ 목록에 대한 절차다 |
| 칸토어 정리의 $B$가 떠오르지 않는다 | §2 관찰의 대응표 — $B$는 대각선의 집합판이다 |

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

## 해설

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

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

(1) $5$  (2) $5$  (3) $5$  (4) $4$  (5) $3$

※ 대각선 성분은 차례로 $d_{11} = 3$, $d_{22} = 7$, $d_{33} = 1$, $d_{44} = 5$이다. 앞의 셋은 5가 아니므로 5를 적고, 넷째만 5이므로 4를 적는다. (5)의 이유: $b_3 = 5$이고 $r_3$의 셋째 자리는 1이므로 셋째 자리에서 어긋난다.

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

(1) 유한하지 않다  (2) 가산  (3) 가산 무한  (4) $5$  (5) $4$ (6) $0.444\cdots \le b \le 0.555\cdots$, 곧 $b \in (0,1)$  (7) 9만, 또는 0만 (8) $n$번째 자리에서 $b_n \neq d_{nn}$  (9) 빠짐없는 목록

※ (6)과 (7)이 한 규칙("4와 5만 쓴다")에서 함께 나온다는 점이 이 증명의 설계 요령이다. 한 줄에 두 가지 의무를 동시에 처리한다. (1)~(3)의 세 칸도 하나로 묶여 있다 — 정의 48.2의 "가산"에는 유한인 경우가 들어 있으므로, (1)이 없으면 (3)으로 넘어갈 수 없고 목록도 나오지 않는다.

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

(1) $S$는 "$n$번째 항만 1이고 나머지는 0"인 수열들을 서로 다른 원소로 무한히 포함하므로 유한하지 않다. 모순을 이끌어내기 위해 $S$가 가산이라고 가정하자. 유한하지 않으므로 $S$는 가산 무한이고, 따라서 빠짐없는 목록 $s_1, s_2, s_3, \dots$이 존재한다. (2) $s_n$의 $k$번째 항을 $d_{nk} \in \{0, 1\}$이라 쓰고, 대각선 성분을 $d_{nn}$으로 둔다. (3) 새 수열 $b = (b_n)$을 $b_n = 1 - d_{nn}$으로 제작한다 (0이면 1, 1이면 0). (4) 각 $b_n$이 0 또는 1이므로 $b$는 0$\cdot$1 수열이다 — 곧 $b \in S$이다. (5) 임의의 $n$에 대해 $b$와 $s_n$은 $n$번째 항이 다르고, 두 수열이 같다는 것은 모든 항이 같다는 뜻이므로 $b \neq s_n$이다. 따라서 $b \in S$인데 목록에 없다 — 가정과 모순이다. 빠짐없는 목록이 존재할 수 없고 (1)에서 $S$가 유한하지 않음도 확인했으므로, 정의 49.1에 의해 $S$는 비가산이다. $\blacksquare$

※ 실수판의 ④가 두 문장(무대 안, 표기 유일)이었던 데 비해 여기서는 한 문장으로 끝난다. 다루는 대상이 수가 아니라 수열 자체여서 이중 표기가 발생할 여지가 없기 때문이다.

### 문제 1

**접근.** 두 가지를 나누어 쓴다 — 정의(§1.2)와 구도(§2 관찰). 정의에서는 조각을 빠뜨리지 않는 것이, 구도에서는 "임의의"라는 낱말이 채점 포인트다. 특정 목록 하나를 반박한 것은 증명이 아니기 때문이다.

**풀이.** (예시 답안) **정의.** 집합 $A$가 유한하지도 않고 $\mathbb{N}$에서 $A$로의 전단사도 존재하지 않을 때, $A$를 비가산이라 한다. 두 조각이 모두 필요하다 — "유한하지도 않고"를 빼면 $\{1,2,3\}$까지 비가산이 되고, "존재하지 않는다"는 목록 하나를 제시해 끝낼 수 없다는 뜻이므로 귀류법을 요구한다. **구도(5단계).** ① 대상이 유한하지 않음을 확인한 뒤, **임의의** 빠짐없는 목록 $r_1, r_2, \dots$이 존재한다고 가정한다(유한하지 않아야 "가산"에서 무한 목록이 나온다). ② 각 항의 십진 전개를 표로 펴고 대각선 성분 $d_{nn}$을 지정한다. ③ 모든 $n$에서 $b_n \neq d_{nn}$이 되도록 새 원소 $b$를 제작한다. ④ $b$가 무대 안에 있음을 확인한다($b \in (0,1)$, 표기 유일). ⑤ 모든 $n$에서 $b \neq r_n$이므로 $b$는 목록 밖이고, 이는 "빠짐없다"는 ①과 모순이다.

**복기.** 정의를 쓸 때는 조각별 역할(§1.3의 표)을 떠올리면 통째 암기가 실패해도 재구성할 수 있다. 구도를 쓸 때는 ④를 잊기 쉬우므로 다섯 칸을 먼저 세로로 적어 놓고 채운다.

### 문제 2

**접근.** 각 $r_n$에서 볼 자리는 하나뿐이다 — 행 번호와 같은 열. 다섯째 빈칸은 계산이 아니라 이유를 묻는 것이므로 "$b$가 $r_3$과 어느 자리에서 어긋나는가"를 답해야 한다.

**풀이.** 대각선 성분은 $d_{11} = 3$, $d_{22} = 7$, $d_{33} = 1$, $d_{44} = 5$이다. 규칙을 적용하면 (1) $b_1 = 5$ ($3 \neq 5$이므로), (2) $b_2 = 5$ ($7 \neq 5$이므로), (3) $b_3 = 5$ ($1 \neq 5$이므로), (4) $b_4 = 4$ ($d_{44} = 5$이므로). 곧 $b = 0.5554\cdots$이다. (5) $3$ — $b$의 셋째 자리는 5이고 $r_3 = 0.141\cdots$의 셋째 자리는 1이므로 셋째 소수 자리에서 다르다.

**검산.** 각 $n$에서 $b_n$과 $d_{nn}$을 나란히 놓으면 $5 \neq 3$, $5 \neq 7$, $5 \neq 1$, $4 \neq 5$ — 네 자리 모두 어긋난다.

### 문제 3

**접근.** 먼저 대각선 성분 다섯 개를 뽑아 따로 적는다. 자리를 세다 헷갈리기 쉬우므로 각 수의 자릿수를 손가락으로 세어 $n$번째를 확정한 뒤 규칙을 적용한다.

**풀이.** 대각선 성분: $d_{11} = 5$ ($r_1 = 0.\mathbf{5}0000\cdots$), $d_{22} = 2$ ($r_2 = 0.1\mathbf{2}345\cdots$), $d_{33} = 3$ ($r_3 = 0.33\mathbf{3}33\cdots$), $d_{44} = 6$ ($r_4 = 0.987\mathbf{6}5\cdots$), $d_{55} = 5$ ($r_5 = 0.1111\mathbf{5}\cdots$). 규칙을 적용하면 $b_1 = 4$ ($d_{11} = 5$이므로), $b_2 = 5$, $b_3 = 5$, $b_4 = 5$, $b_5 = 4$ ($d_{55} = 5$이므로). 곧

$$
b = 0.45554\cdots
$$

**검산.** $b$와 각 $r_n$을 $n$번째 자리에서 비교하면 $4 \neq 5$, $5 \neq 2$, $5 \neq 3$, $5 \neq 6$, $4 \neq 5$ — 다섯 항 모두와 어긋난다. 또 자리가 전부 4 또는 5이므로 $b \in (0,1)$이고 표기도 유일하다.

### 문제 4

**접근.** 논법의 어느 줄이 "자리가 다르면 다른 수"를 쓰고 있는지 먼저 찾는다 — 예제 2.1의 다섯째 줄이다. 그 줄이 무너지는 유일한 경우가 이중 표기이므로, 위협의 정체는 "자리가 다른데 같은 수"가 생길 가능성이다.

**풀이.** **위협.** 대각선 논법의 마지막 단계는 "$b$와 $r_n$이 $n$번째 자리에서 다르므로 $b \neq r_n$"이고, 이 추론은 십진 표기의 유일성을 전제한다. 그런데 $0.4999\cdots = 0.5000\cdots$처럼 같은 수가 두 표기를 갖는 경우가 있으므로, 표기가 다른데도 같은 수일 수 있다. 그러면 제작한 $b$가 어떤 $r_n$과 표기만 다르고 실제로는 같은 수일 가능성이 남아 "$b$는 목록 밖"이라는 결론이 새어 나간다. **차단.** 두 표기를 갖는 수는 반드시 한쪽이 어느 자리 이후 9만 이어지고 다른 쪽이 0만 이어지는 쌍이다. $b$는 모든 자리가 4 또는 5이므로 9로만 이어지는 꼬리도, 0으로만 이어지는 꼬리도 없다. 따라서 $b$는 두 표기를 갖는 수가 아니고 $b$의 십진 표기는 유일하다. 그러므로 $b = r_n$이라면 $r_n$의 전개가 곧 $b$의 전개여야 하는데 $n$번째 자리에서 다르므로, $b \neq r_n$이 안전하게 성립한다.

**복기.** 증명 안의 안전장치는 대개 이런 모양이다 — 일반적으로는 성립하지 않는 추론을, 제작물을 특별하게 만들어 그 범위 안에서만 성립하게 한다.

### 문제 5

**접근.** 5단계 틀을 세로로 적고 그 위에 "유한하지 않다" 한 줄을 얹은 뒤 칸을 채운다. 맨 위 줄이 있어야 ①의 "가산"에서 무한 목록이 나오고, 정의 49.1의 첫 조각도 함께 채워진다. ①에 "빠짐없는", ④에 두 문장(무대 안, 표기 유일), ⑤에 "임의의 $n$에 대해"가 들어가야 한다. 이 넷 중 하나라도 빠지면 증명이 성립하지 않는다.

**풀이.** $(0,1)$은 $\frac12, \frac13, \frac14, \dots$을 서로 다른 원소로 포함하므로 유한하지 않다. 모순을 이끌어내기 위해 $(0,1)$이 가산이라고 가정하자. 유한하지 않으므로 $(0,1)$은 가산 무한이고, 따라서 빠짐없는 목록 $r_1, r_2, r_3, \dots$이 존재한다. 각 $r_n$을 십진 전개로 $r_n = 0.\,d_{n1}d_{n2}d_{n3}\cdots$라 쓴다($d_{nk}$는 $r_n$의 $k$번째 소수 자리). 새 실수 $b = 0.\,b_1b_2b_3\cdots$을 다음 규칙으로 제작한다: $d_{nn} \neq 5$이면 $b_n = 5$, $d_{nn} = 5$이면 $b_n = 4$. $b$는 4와 5만으로 이루어지므로 $0.444\cdots \le b \le 0.555\cdots$이고 따라서 $b \in (0,1)$이다. 또 9로만 이어지는 꼬리도 0으로만 이어지는 꼬리도 없으므로 $b$의 십진 표기는 유일하다. 임의의 $n$에 대해 $b \neq r_n$이다: 만약 $b = r_n$이라면 표기의 유일성에 의해 $0.d_{n1}d_{n2}\cdots$가 곧 $b$의 전개여야 하는데, 제작 규칙에 의해 $b_n \neq d_{nn}$이므로 $n$번째 자리가 다르다. 따라서 $b \in (0,1)$인데 목록의 어느 항과도 같지 않다 — 목록이 빠짐없다는 가정과 모순이다. 곧 $(0,1)$의 빠짐없는 목록은 존재하지 않는다. 첫 줄에서 $(0,1)$이 유한하지 않음도 확인했으므로 정의 49.1의 두 조각이 모두 채워진다 — $(0,1)$은 비가산이다. $\blacksquare$

**복기.** 채점 포인트는 여섯이다: ① 유한하지 않음을 확인해 "가산"에서 무한 목록으로 넘어가는 다리를 놓았는가 ② 귀류 가정에 "빠짐없는"이 있는가 ③ 규칙이 $d_{nn}$만 보는가 ④ $b \in (0,1)$을 확인했는가 ⑤ 표기 유일성을 확보하고 실제로 사용했는가 ⑥ "임의의 $n$"이라고 적었는가. ①은 정의 49.1의 두 조각 중 첫 조각을 채우는 자리이기도 하다 — 한 줄이 두 몫을 한다.

### 문제 6

**접근.** 48주차의 결과 넷과 이번 주의 결과 셋을 배치하는 문제다. 분류만 적으면 채점 기준상 0점이므로 각 항목에 근거를 붙인다. "짝수"는 48주차 예제 2.1의 양의 짝수 전체 $E$를 가리킨다.

**풀이.**

| **집합** | **분류** | **근거** |
|---|---|---|
| $\mathbb{N}$ | 가산 | 항등함수가 전단사 — 정의 48.2 그 자체 |
| $\mathbb{Z}$ | 가산 | 지그재그 목록 $0, 1, -1, 2, -2, \dots$ (48주차 예제 2.2) |
| $\mathbb{Q}$ | 가산 | 격자 행진과 건너뛰기 (48주차 예제 2.3, 문제 15) |
| $(0,1)$ | 비가산 | 대각선 논법 (이번 주 예제 2.1) |
| $\mathbb{R}$ | 비가산 | $(0,1) \subseteq \mathbb{R}$과 문제 8 |
| 무리수 | 비가산 | 예제 2.2 — $\mathbb{Q}$ 가산과 $\mathbb{R}$ 비가산의 조립 |
| 짝수 | 가산 | $f(n) = 2n$이 전단사 (48주차 예제 2.1) |

**복기.** 가산 쪽은 전부 "목록을 하나 제시했다"로 끝나고, 비가산 쪽은 전부 "임의의 목록을 실패시켰다"로 끝난다. 두 방향의 증명 의무가 정반대라는 것이 §1.3의 방향 표에 정리되어 있다.

### 문제 7

**접근.** 대각선을 다시 그리지 않는다. 이 증명은 부품 조립형이므로 필요한 부품 세 개를 먼저 나열하고 귀류의 흐름에 순서대로 끼워 넣는다. 부품 ②가 요구하는 조건(서로소)을 확인하는 줄을 빠뜨리지 않는다.

**풀이.** 모순을 이끌어내기 위해 $\mathbb{I} = \mathbb{R} - \mathbb{Q}$가 가산이라고 가정하자. $\mathbb{Q}$는 가산이고(48주차 문제 15), $\mathbb{N} \subseteq \mathbb{Q}$이므로 유한하지 않다 — 곧 $\mathbb{Q}$는 가산 무한이다. 또 $\mathbb{Q} \cap \mathbb{I} = \emptyset$이다. $\mathbb{I}$가 가산 무한인 경우: 서로소인 두 가산 무한 집합의 합집합은 가산 무한이므로(48주차 문제 14 — 두 목록을 교대로 엮는다),

$$
\mathbb{R} = \mathbb{Q} \cup \mathbb{I}
$$

는 가산이다. $\mathbb{I}$가 유한인 경우: $\mathbb{Q}$의 목록 앞에 그 유한 개를 덧붙이면 $\mathbb{R}$의 목록이 되므로 이 경우에도 $\mathbb{R}$은 가산이다. 어느 경우에도 $\mathbb{R}$은 가산이다. 그러나 $(0,1) \subseteq \mathbb{R}$이고 $(0,1)$은 비가산이므로(예제 2.1), 문제 8에 의해 $\mathbb{R}$은 비가산이다. 가산과 비가산이 동시에 성립할 수는 없으므로 모순이다. 따라서 $\mathbb{I}$는 비가산이다. $\blacksquare$

**복기.** 48주차 문제 14는 두 집합이 가산 **무한**일 때의 결과다. 그러므로 인용하기 전에 $\mathbb{Q}$가 가산 무한임을 확인해야 하고, 가정한 "$\mathbb{I}$가 가산"에 들어 있는 "$\mathbb{I}$가 유한"인 경우를 따로 처리해야 한다. 부품 조립형 증명의 채점 포인트는 부품마다 출처를 밝혔는가, 그리고 부품이 요구하는 조건을 빠짐없이 확인했는가다.

### 문제 8

**접근.** 원명제를 직접 치려 하면 "$C$의 목록이 존재하지 않는다"를 보여야 해서 손에 잡을 대상이 없다. 대우로 뒤집으면 가정 자리에 "$C$의 목록"이라는 구체적 대상이 생긴다 — 19주차의 판단 기준("부정형 결론이면 대우를 의심한다") 그대로다.

**풀이.** 원명제 "$B$가 비가산이면 $C$도 비가산"의 대우는 "$C$가 가산이면 $B$도 가산"이다. 이 대우를 증명한다. $C$가 가산이라 하자. $C$가 유한이면 그 부분집합 $B$도 유한이므로 가산이다. $C$가 가산 무한이면 목록 $c_1, c_2, c_3, \dots$이 존재한다. 이 목록을 앞에서부터 훑으면서 $B$에 속하지 않는 항을 건너뛰고 속하는 항만 차례로 적어 새 목록을 만든다(48주차 예제 2.3에서 약분 중복을 건너뛴 것과 같은 기술). 이 부분 목록은 $B$의 원소를 빠짐없이 담고($B \subseteq C$이므로 $B$의 원소는 모두 원래 목록에 있다) 겹침도 없다(원래 목록에 겹침이 없었다). 남은 항이 무한하면 $B$는 가산 무한이고 유한하면 $B$는 유한이다 — 어느 쪽이든 $B$는 가산이다. 대우가 성립하므로 원명제도 성립한다: $B \subseteq C$이고 $B$가 비가산이면 $C$도 비가산이다. $\blacksquare$ **적용.** $(0,1) \subseteq \mathbb{R}$이고 $(0,1)$은 비가산이므로(예제 2.1), $\mathbb{R}$도 비가산이다.

**복기.** 19주차의 대우를 45주 뒤에도 그대로 쓴다. 판단 기준도 그대로다 — 결론이 "존재하지 않는다"이면 뒤집었을 때 다룰 대상이 생기는지 확인한다.

### 문제 9

**접근.** 5단계 틀을 $\mathbb{Q} \cap (0,1)$에 하나씩 대입해 본다. ①(목록 가정), ②(대각선 지정), ③(비틀기)은 그대로 통과하고, ⑤의 앞부분("모든 항과 다름")까지도 성립한다. 무너지는 곳은 ④ 소속 확인이고, ④가 무너지면 ⑤의 뒷부분(①과의 충돌)이 따라 무너진다 — 충돌하려면 제작물이 목록이 담았어야 할 대상이어야 하기 때문이다. 예제 2.1의 "**[주의]**  자주 하는 실수" 상자가 이 문제의 예고였다.

**풀이.** $\mathbb{Q} \cap (0,1)$의 목록(48주차 예제 2.3의 격자 행진에서 구간에 드는 것만 남기면 얻어진다)에 대각선 비틀기를 적용하면, 목록의 모든 항과 $n$번째 자리에서 어긋나는 실수 $b$가 실제로 만들어진다. 여기까지는 예제 2.1과 한 줄도 다르지 않다. 무너지는 곳은 4단계다. 모순이 되려면 $b$가 **$\mathbb{Q} \cap (0,1)$의 원소**여야 하는데 — 그래야 "유리수의 빠짐없는 목록"이 원소 하나를 빠뜨린 것이 된다 — 제작된 $b$는 소수 전개가 순환한다는 보장이 없으므로 유리수라는 보장이 없다(실제로는 무리수가 되는 것이 보통이다). 제작물이 무대 밖에 떨어지면, 목록이 그것을 담지 않은 것은 결함이 아니다. 애초에 담을 의무가 없기 때문이다. 그러므로 이 시도에서 얻는 결론은 "이 목록은 $(0,1)$ 전체를 담지 못한다"일 뿐이고 "$\mathbb{Q} \cap (0,1)$을 담지 못한다"가 아니다. 유리수의 가산성(48주차 문제 15)과 대각선 논법은 이렇게 충돌 없이 공존한다.

**복기.** 소속 확인은 형식적 절차가 아니라 논법이 작동하는 조건이다. 예제 2.1이 4와 5만 쓰는 규칙으로 $b \in (0,1)$을 확보한 것은 바로 이 칸을 채우기 위한 설계였다.

### 문제 10

**접근.** 예제 2.1에서 소재만 바꾼다: 십진 자리 $\to$ 0$\cdot$1 항, 비틀기 규칙 $\to$ $0 \leftrightarrow 1$. 이중 표기 문제가 없으므로 4단계가 한 문장으로 줄어든다. 마지막 줄에서 "수열의 상등 = 모든 항의 일치"를 명시한다.

**풀이.** $S$는 "$n$번째 항만 1이고 나머지는 0"인 수열들을 서로 다른 원소로 무한히 포함하므로 유한하지 않다. 모순을 이끌어내기 위해 $S$가 가산이라고 가정하자. 유한하지 않으므로 $S$는 가산 무한이고, 따라서 빠짐없는 목록 $s_1, s_2, s_3, \dots$이 존재한다. $s_n$의 $k$번째 항을 $d_{nk} \in \{0, 1\}$이라 쓴다. 새 수열 $b = (b_n)$을

$$
b_n = 1 - d_{nn}
$$

으로 제작한다 (곧 $d_{nn} = 0$이면 $b_n = 1$, $d_{nn} = 1$이면 $b_n = 0$). 각 $b_n$은 0 또는 1이므로 $b$는 0$\cdot$1 수열이고, 따라서 $b \in S$이다. 임의의 $n$에 대해 $b$와 $s_n$은 $n$번째 항이 다르다($b_n \neq d_{nn}$). 두 수열이 같다는 것은 모든 항이 일치한다는 뜻이므로 $b \neq s_n$이다. 따라서 $b \in S$인데 목록의 어느 항과도 같지 않다 — 목록이 빠짐없다는 가정과 모순이다. 곧 $S$의 빠짐없는 목록은 존재하지 않는다. 첫 줄에서 $S$가 유한하지 않음도 확인했으므로 정의 49.1의 두 조각이 모두 채워진다 — $S$는 비가산이다. $\blacksquare$

**복기.** 5단계 틀에서 실수 특유의 군더더기(4/5 규칙, 표기 유일성)를 걷어내면 이 증명이 남는다. 논법의 뼈대가 십진법과 무관하다는 것이 여기서 드러난다.

### 문제 11

**접근.** 대등의 정의(48주차 정의 48.1)는 전단사 하나를 제시하고 단사$\cdot$전사를 각각 검증하라고 요구한다. 대응 자체는 문제의 힌트에 나와 있으므로 점수는 두 검증에 있다. 전사 검증에서는 주어진 수열로부터 부분집합을 되돌려 만든다.

**풀이.** 대응 $\Phi : \mathcal{P}(\mathbb{N}) \to S$를 다음과 같이 정한다. 부분집합 $X \subseteq \mathbb{N}$에 수열 $\Phi(X) = (x_n)$을 배정하되

$$
\begin{aligned}x_n = \begin{cases} 1 & (n \in X) \\ 0 & (n \notin X) \end{cases}\end{aligned}
$$

로 둔다. 각 $x_n$이 0 또는 1이므로 $\Phi(X) \in S$이고, $X$가 정해지면 각 $n$의 소속 여부가 하나로 정해지므로 $\Phi$는 잘 정의된다. **(단사)** $\Phi(X) = \Phi(Y)$라 하자. 임의의 $n$에 대해 두 수열의 $n$번째 항이 같으므로 $n \in X \iff x_n = 1 \iff n \in Y$이다. 곧 $X$와 $Y$는 같은 원소를 가지므로 집합의 상등(27주차의 서식)에 의해 $X = Y$이다. **(전사)** 임의의 0$\cdot$1 수열 $(x_n) \in S$에 대해 $X = \{n \in \mathbb{N} : x_n = 1\}$이라 두면 $X \subseteq \mathbb{N}$이므로 $X \in \mathcal{P}(\mathbb{N})$이고, $\Phi(X)$의 $n$번째 항은 정의상 $n \in X$일 때 1, 아닐 때 0이므로 $(x_n)$과 일치한다. 곧 $\Phi(X) = (x_n)$이다. 따라서 $\Phi$는 전단사이고 $|\mathcal{P}(\mathbb{N})| = |S|$이다. $\blacksquare$

**복기.** 유한에서 $|\mathcal{P}(A)| = 2^n$을 증명할 때 쓴 "각 원소를 넣을지 뺄지 선택"(31주차 예제 2.3, 12주차 문제 13)의 선택 기록이 유한 길이의 0$\cdot$1 목록이었다. 이 문제는 그 목록을 무한 길이로 늘린 것이고, 대응의 아이디어가 그대로 이월된다.

### 문제 12

**접근.** 빠뜨리기 쉬운 두 문장을 먼저 확보한다: "$B \subseteq A$이므로 $B \in \mathcal{P}(A)$"(소속 확인)와 "전사이므로 $f(a) = B$인 $a$가 존재한다"(원상 소환). 이 둘이 없으면 마지막 질문 "$a \in B$인가"를 던질 대상이 없다.

**풀이.** 전사 $f : A \to \mathcal{P}(A)$가 존재한다고 가정하자. 집합

$$
B = \{x \in A : x \notin f(x)\}
$$

을 만든다. $B$는 $A$의 원소들로만 이루어지므로 $B \subseteq A$이고, 따라서 $B \in \mathcal{P}(A)$이다. $f$가 전사이므로 $f(a) = B$인 $a \in A$가 존재한다. 이제 "$a \in B$인가"를 묻는다. **$a \in B$인 경우.** $B$를 정의한 조건에 의해 $a \notin f(a)$이다. 그런데 $f(a) = B$이므로 $a \notin B$이다 — $a \in B$와 어긋난다. **$a \notin B$인 경우.** $f(a) = B$이므로 $a \notin f(a)$이다. 이는 $B$의 조건 그 자체이므로 $a \in B$이다 — $a \notin B$와 어긋난다. $a \in B$이거나 $a \notin B$ 중 하나는 반드시 성립하는데(26주차 §1.4의 배중률) 두 경우 모두 모순에 이른다. 따라서 전사 $f$는 존재하지 않는다. $\blacksquare$

**복기.** 채점 포인트는 넷이다: ① $B$의 정의에 $x \notin f(x)$가 정확히 들어갔는가 ② $B \in \mathcal{P}(A)$를 확인했는가 ③ 전사에서 $a$를 소환했는가 ④ 두 경우를 모두 처리했는가. 한쪽 경우만 쓰고 끝내면 증명이 절반이다.

### 문제 13

**접근.** 전단사는 전사이기도 하므로 "전사가 없다"에서 "전단사가 없다"가 따라 나오고, 여기에 "유한이 아니다"를 더하면 정의 49.1의 두 조건이 채워진다. 비교 부분에서는 두 증명이 실제로 같은 구조인지를 대응으로 확인한다.

**풀이.** **따라 나오는 것.** 칸토어의 정리에 $A = \mathbb{N}$을 넣으면 $\mathbb{N}$에서 $\mathcal{P}(\mathbb{N})$으로의 전사가 존재하지 않는다. 전단사는 전사이므로 전단사도 존재하지 않는다. 또 $\{1\}, \{2\}, \{3\}, \dots$이 서로 다른 원소를 무한히 주므로 $\mathcal{P}(\mathbb{N})$은 유한하지 않다. 정의 49.1의 두 조건이 모두 성립하므로 $\mathcal{P}(\mathbb{N})$은 비가산이다. **두 증명의 비교.** 길 A는 문제 10과 11이다: 0$\cdot$1 수열의 집합 $S$를 대각선으로 직접 공격해 비가산임을 얻고 $|\mathcal{P}(\mathbb{N})| = |S|$로 옮겨 온다 — 숫자표를 실제로 만드는 구체적인 길이다. 길 B는 칸토어의 정리로, 자기 참조 집합 $B$ 하나로 추상적으로 끝낸다. 두 길은 사실 같은 길이다. 문제 11의 대응 $\Phi$로 번역하면 $f(n)$은 $n$번째 0$\cdot$1 수열이고, "$n \in f(n)$인가"는 그 수열의 $n$번째 항, 곧 대각선 성분이다. $B = \{n : n \notin f(n)\}$은 그 대각선 성분을 자리마다 뒤집은 수열에 대응한다 — 문제 10의 $b_n = 1 - d_{nn}$ 그 자체다.

**복기.** 서로 달라 보이는 두 증명이 같은 것인지 확인하는 방법은 번역이다 — 한쪽의 대상을 다른 쪽의 언어로 옮겨 놓고 제작 규칙이 일치하는지 본다.

### 문제 14

**접근.** 주장을 먼저 $\forall$ 명제로 번역한다(10주차): "임의의 무한집합 $A, B$에 대해 $|A| = |B|$이다." $\forall$ 명제의 반증에 필요한 것은 반례 하나이고, 여기서는 집합 두 개로 이루어진 조합이다(29주차의 반증 서식).

**풀이.** 주장은 **거짓**이며, 반증한다. 반례 쌍: $\mathbb{N}$과 $\mathbb{R}$. 둘 다 무한집합이다. 그런데 $\mathbb{N}$은 가산이고(정의 48.2), $\mathbb{R}$은 비가산이다(예제 2.1과 문제 8). 만약 $|\mathbb{N}| = |\mathbb{R}|$이라면 $\mathbb{N}$에서 $\mathbb{R}$로의 전단사가 존재하고, 그것은 곧 $\mathbb{R}$의 빠짐없는 목록이므로 $\mathbb{R}$이 가산이 되어 비가산성과 어긋난다. 따라서 $|\mathbb{N}| \neq |\mathbb{R}|$이고 "무한은 다 같은 무한"은 무너진다. $\blacksquare$ 이것을 반증하는 정리는 대각선 논법(예제 2.1)이다. 더 나아가 칸토어의 정리(예제 2.3)는 등급이 둘이 아니라 무한히 많음을 준다: $|\mathbb{N}| < |\mathcal{P}(\mathbb{N})| < |\mathcal{P}(\mathcal{P}(\mathbb{N}))| < \cdots$.

**복기.** 반증의 완결 조건은 두 가지다 — 반례가 가정 부분(둘 다 무한집합)을 실제로 만족하는가, 결론 부분(대등하다)이 실제로 거짓인가. 둘 중 하나만 쓰면 반례 제시가 절반이다.

### 문제 15

**접근.** 오해의 정체를 먼저 짚는다. 대각선 논법은 특정 목록 하나에 대한 반박이 아니라 **임의의** 목록에 대한 절차이므로, 새로 만든 목록도 그 절차의 입력이 된다. $\forall$ 명제를 $\exists$ 명제로 읽은 데서 온 오해다(10주차).

**풀이.** **교정.** 예제 2.1이 증명한 것은 "어떤 목록 하나가 $b$를 빠뜨린다"가 아니라 "임의의 목록에 대해 그 목록이 빠뜨리는 원소를 제작할 수 있다"이다. $b$를 맨 앞에 붙인 $b, r_1, r_2, \dots$도 하나의 목록이므로 같은 절차를 그대로 다시 적용할 수 있다. 새 목록의 숫자표에서 새 대각선 성분을 뽑아 비틀면 새 탈출자 $b'$이 만들어지고, $b'$은 $b$와도 다르고 모든 $r_n$과도 다르다(각각 해당 자리에서 어긋나므로). 목록을 고치는 작업은 몇 번을 반복해도 끝나지 않는다. **오해의 계보.** 이 반박은 증명된 문장을 "$\exists$ 목록: 그 목록이 실패한다"로 읽은 것이다. 실제로 증명된 문장은 "$\forall$ 목록 $\exists$ 탈출자"이며, 양화사의 순서가 다르면 명제가 다르다(10주차의 핵심 문장). 앞에 놓인 $\forall$이 먼저 정해지므로, 목록을 무엇으로 바꾸든 그 뒤에 탈출자가 따라 나온다.

**복기.** "반례를 목록에 추가하면 되지 않나"라는 반박은 무한을 다룰 때 반복해서 등장한다. 판정 기준은 늘 같다 — 증명된 문장의 양화사 순서를 그대로 읽는다.

### 문제 16

**접근.** "무한 소수는 완성되지 않은 과정"이라는 그림을 46주차의 급수 정의로 교체한다. 무한 소수는 과정이 아니라 부분합 수열의 극한값이므로, 수렴만 확인하면 $b$는 하나의 실수로 확정된다.

**풀이.** **교정.** 무한 소수 전개 $0.b_1b_2b_3\cdots$는 "끝나지 않는 과정"이 아니라 급수

$$
\sum_{n=1}^{\infty} \frac{b_n}{10^n}
$$

의 값, 곧 부분합 수열 $S_N = \sum_{n=1}^{N} \frac{b_n}{10^n}$의 극한으로 **정의된다**(46주차 §1의 급수 정의. 46주차 문제 14에서 $0.999\cdots = 1$을 이 정의로 판결한 것과 같은 방식이다). 이 급수가 수렴함을 확인한다. $b_n \ge 0$이므로 $S_N \le S_{N+1}$이다 — 부분합 수열은 감소하지 않는다(자릿수가 0인 자리에서는 값이 그대로이므로 넓은 의미의 증가다). 이번 주에 제작한 $b$는 모든 자리가 4 또는 5여서 $b_n > 0$이므로 $S_N < S_{N+1}$이고, 부분합 수열은 좁은 의미로도 증가한다. 또 모든 $n$에 대해 $b_n \le 9$이므로

$$
S_N \le \sum_{n=1}^{N} \frac{9}{10^n} = 1 - \frac{1}{10^N} < 1
$$

이어서 $S_N$은 1로 위에서 막힌다. 위로 유계인 증가 수열은 수렴하므로(단조수렴정리 — 46주차에서 인정하고 쓴 사실. 46주차의 진술이 "증가하는 수열"이므로, 위에서 확인한 좁은 의미의 증가가 그 진술을 그대로 만족시킨다) 극한이 존재하고, 그 극한값이 $b$다. 따라서 $b$는 어엿한 하나의 실수이고 증명은 유효하다. 덧붙여 $b$의 각 자리가 4 이상 5 이하이므로 $\frac49 \le b \le \frac59$이며, 이는 예제 2.1의 4단계에서 확인한 $b \in (0,1)$과 일치한다.

**검산.** 모든 자리가 4이면 $\sum \frac{4}{10^n} = \frac49 = 0.444\cdots$, 모든 자리가 5이면 $\frac59 = 0.555\cdots$ — 양 끝값이 실제로 계산된다.

**복기.** "무한 = 미완성"이라는 직관은 45주차의 $\varepsilon$-$N$ 정의가 대체한 낡은 그림이다. 무한을 다루는 문장을 만나면 그 문장의 정의가 어느 극한으로 환원되는지부터 확인한다.

### 문제 17

**접근.** 움직이는 원소와 제자리에 있는 원소를 두 무리로 나눈다. 검증할 것은 세 가지다: 움직이는 것끼리 겹치지 않는가, 움직인 것이 제자리 원소와 충돌하지 않는가, $(0,1)$의 모든 원소가 어딘가에서 오는가. 48주차 문제 12의 정밀판이다.

**풀이.** 함수 $f : [0,1] \to (0,1)$을 다음과 같이 정한다.

$$
f(0) = \tfrac12, \quad f(1) = \tfrac13, \quad f\left(\tfrac1n\right) = \tfrac{1}{n+2}\ (n \ge 2), \quad \text{그 외에는 } f(x) = x
$$

**(치역 확인)** 움직이는 원소의 상은 $\frac12, \frac13$과 $\frac{1}{n+2}$ $(n \ge 2)$, 곧 $\frac14, \frac15, \dots$이다. 제자리 원소는 $[0,1]$에서 $0, 1, \frac12, \frac13, \dots$을 뺀 것이다. 어느 쪽이든 값은 $(0,1)$ 안에 있다. **(단사)** 움직이는 원소의 집합 $\{0, 1\} \cup \{\frac12, \frac13, \frac14, \dots\}$의 상은 $\{\frac12, \frac13\} \cup \{\frac14, \frac15, \dots\} = \{\frac12, \frac13, \frac14, \dots\}$이고, 배정은 $0 \mapsto \frac12$, $1 \mapsto \frac13$, $\frac12 \mapsto \frac14$, $\frac13 \mapsto \frac15$, … 로 서로 겹치지 않는다. 제자리 원소는 $\frac1n$ 꼴이 아니므로 그 상도 $\frac1n$ 꼴이 아니고, 따라서 움직인 원소의 상과 충돌하지 않는다. 서로 다른 두 제자리 원소는 상도 서로 다르다. 그러므로 $f$는 단사다. **(전사)** $(0,1)$의 임의의 원소 $y$를 잡는다. $y$가 $\frac1n$ 꼴이 아니면 $f(y) = y$이므로 $y$ 자신이 원상이다. $y = \frac12$이면 원상은 $0$, $y = \frac13$이면 원상은 $1$이다. $y = \frac1n$ $(n \ge 4)$이면 $n - 2 \ge 2$이므로 원상은 $\frac{1}{n-2}$이다. 빠짐이 없다. 따라서 $f$는 전단사이고 $|[0,1]| = |(0,1)|$이다. $\blacksquare$

**복기.** 끝점 두 개를 끼워 넣기 위해 가산 부분만 두 칸씩 밀었다 — 48주차 문제 12에서 손님 전원을 옆방으로 옮겨 1호실을 비운 것과 같은 조작이다. 무한을 다룰 때는 유한 개의 추가를 가산 부분 안에서 흡수할 수 있다.

### 문제 18

**접근.** 답안이 쓴 추론 형식을 한 문장으로 뽑아낸다: "빽빽하면 목록화가 불가능하다". 이 형식에 반례가 있는지 48주차의 결과에서 찾는다. 반례가 있으면 그 추론은 근거가 될 수 없다 — 1주차부터의 원칙이다.

**풀이.** **결함.** 답안의 근거는 "$\mathbb{R}$이 빽빽하다(조밀하다)"뿐이다. 그런데 $\mathbb{Q}$도 어느 두 유리수 사이에 또 하나의 유리수가 있을 만큼 빽빽하고(15주차 문제 17), 그러면서도 가산이다(48주차 문제 15). 곧 "빽빽하면 목록화 불가"라는 추론 형식에는 이미 반례가 있다. 반례가 있는 형식은 근거의 자리에 설 수 없으므로, 답안은 결론이 참인데도 증명이 아니다. 또 답안은 "$\mathbb{Z}, \mathbb{Q}$와 달리"라고 적었지만 $\mathbb{Q}$는 조밀하므로 사실 관계도 어긋난다. **올바른 증명이 갖춰야 할 것.** ① 임의의 목록을 가정으로 놓을 것(특정 목록 하나가 아니라) ② 그 목록에서 실제로 빠지는 원소를 제작할 것 ③ 제작물이 $\mathbb{R}$에 속함을 확인할 것 ④ 목록의 모든 항과 다름을 보이고 "빠짐없음"과 충돌시킬 것. 예제 2.1이 $(0,1)$에 대해 이 넷을 갖추었고, 문제 8이 그것을 $\mathbb{R}$로 옮긴다.

**복기.** 인상을 근거로 쓴 답안을 판정하는 절차는 늘 같다 — 인상을 추론 형식으로 적어 내고 그 형식의 반례를 찾는다. 반례가 나오면 결론의 참$\cdot$거짓과 무관하게 답안은 증명이 아니다.

### 문제 19

**접근.** 29주차가 세운 세 상태에 네 번째를 얹는 문제다. 핵심은 셋째(미해결)와 넷째(독립)의 차이를 흐리지 않는 것이다 — 미해결은 진행 상황에 대한 서술이고, 독립은 명제와 공리계 사이의 관계에 대한 확정된 결과다.

**풀이.** (예시 답안) ① **증명됨(참).** 명제가 공리로부터 유도되었다 — 예: 소수는 무한히 많다(21주차 예제 2.3). ② **반증됨(거짓).** 명제의 부정이 증명되었다 — 예: "모든 무한집합은 가산이다"는 이번 주 예제 2.1로 반증되었다. ③ **미해결.** 아직 어느 쪽 증명도 나오지 않았다 — 예: 콜라츠 추측(29주차 문제 19), 골드바흐 추측. 이것은 명제의 상태가 아니라 진행 상황에 대한 서술이며, 내일 누군가 풀 수 있다. ④ **독립.** 주어진 공리계로는 증명도 반증도 **불가능함이 증명되었다** — 예: ZFC에서의 연속체 가설(괴델 1940, 코언 1963). 미해결과 달리 완결된 지식이며, "더 노력하면 풀린다"가 아니라 "이 공리들로는 원리적으로 결정되지 않는다"는 결론이다. ③과 ④의 차이가 이 문제의 요점이다. ④가 말해 주는 것은 어떤 공리를 채택하느냐가 수학의 내용을 바꾼다는 사실이다 — 연속체 가설을 공리로 추가한 수학과 그 부정을 추가한 수학이 둘 다 모순 없이 존재한다. 6주차 §1.7의 러셀에서 시작된 "공리로 관리되는 수학"이 도달한 지점이다.

**복기.** 명제를 만나면 "참인가 거짓인가"만 묻지 않는다. "어느 공리계에서 말하는 것인가"까지 물어야 답이 정해지는 명제가 실제로 존재한다.

### 문제 20

**접근.** 세 증명의 첫 문장과 제작물만 뽑아 표로 나란히 놓으면 구조가 드러난다. 21주차 예제 2.2$\cdot$2.3의 첫 문장을 각각 확인하고 오는 것이 출발점이다.

**풀이.** (예시 답안)

| **증명** | **"전부 담았다"는 가정** | **제작한 증인** | **무너지는 지점** |
|---|---|---|---|
| $\sqrt2$ 무리수 (21주차 예제 2.2) | $\sqrt2 = \frac ab$로 표현했고 그 분수는 기약이다 | 짝수성 하강으로 얻은, 더 약분되는 표현 | 기약이라는 가정 |
| 소수 무한 (21주차 예제 2.3) | 소수를 $p_1, \dots, p_k$로 전부 나열했다 | $p_1 p_2 \cdots p_k + 1$의 소인수 | 목록에 전부 있다는 가정 |
| 대각선 논법 (예제 2.1) | $(0,1)$의 실수를 목록으로 전부 나열했다 | 대각선을 비튼 실수 $b$ | 목록이 빠짐없다는 가정 |

**공통 구조.** 세 증명 모두 "전부 담았다"는 완결성 주장을 가정으로 받아들인 다음, 그 가정이 준 목록(또는 표현) **자체를 재료로** 삼아 목록을 배반하는 대상을 만들어 낸다. 제작물이 목록에서 나왔기 때문에 목록이 어떻게 생겼든 제작이 가능하고, 그래서 반박이 특정 목록이 아니라 모든 목록에 통한다. **왜 되풀이해 쓰이는가(세 문장).** 무한한 대상은 하나씩 확인해 셀 수 없으므로 직접적인 검사로는 "전부"에 관한 주장을 판정할 수 없다. 대신 "전부 담았다"는 주장을 가정 자리에 놓으면 유한한 문장 하나를 손에 쥐게 되고, 그 문장이 스스로를 배반하는 증인을 만들어 낸다. 곧 귀류법이 무한을 유한한 조작으로 바꾸어 주고, 제작이 그 조작의 내용을 채운다.

**복기.** 새로운 무한 대상을 만났을 때 물을 것은 하나다 — "전부 담았다"고 가정하면 그 가정 자체에서 무엇을 만들 수 있는가.

---

**다음 주 예고 (마지막 주).** 50주 전 범위의 최종 종합 평가와 수료 주간이다. 1주차의 "짝수 + 짝수 = 짝수"에서 이번 주의 대각선까지 걸어온 길을 한 장의 지도로 정리하고, 다음에 열리는 네 방향(이산수학$\cdot$선형대수$\cdot$해석학$\cdot$정수론)에서 이 과정의 무엇이 그대로 재사용되는지를 절별로 대조한다. 이번 주의 예제 2.1은 50주차 문제 19의 재현 대상이고, 문제 20의 분석은 50주차 문제 20의 (a)로 다시 나온다.