# 49주차 — 칸토어의 대각선 논법: 비가산 무한 :::{admonition} 이 주의 길잡이 :class: keybox **핵심 문장**: 어떤 목록을 내밀어도, 대각선을 비틀면 그 목록에 없는 실수가 만들어진다. **이 주의 위치**: 50주 과정의 49주차. 48주차에서 넓혀 온 "가산인 무한"에 바깥이 있음을 증명하고, 무한의 등급이 끝없이 올라간다는 것까지 본다. **원서 대응**: BoP(Book of Proof) 14.2 후반(Uncountable Sets), 14.3(Comparing Cardinalities) — 병행자 참고용. 원서 없이 읽을 수 있다. ::: ## 이번 주 목표 1. **비가산**의 정의를 백지에 쓰고, 그것이 왜 비존재 명제인지 설명할 수 있다. 1. **대각선 논법**으로 $(0, 1)$이 비가산임을 백지에서 처음부터 끝까지 증명할 수 있다. 1. 따름 결과 세 가지를 유도할 수 있다: $\mathbb{R}$ 비가산, **무리수 비가산**, 칸토어의 정리 $|A| \neq |\mathcal{P}(A)|$. 1. 연속체 가설을 통해 "증명도 반증도 불가능함이 증명된" 네 번째 상태를 29주차의 세 상태에 더한다. 본문 곳곳의 **확인** 상자는 연필로 먼저 답하는 자리다. 바로 아래의 **답** 상자는 (웹에서는 접혀 있다) 스스로 답한 뒤에 열어 대조한다. ## 준비 운동 (48주차 복습) 1. 가산 무한의 정의를 백지에 쓰고, 그것을 "목록화"로 바꿔 읽으시오. 1. 지난주에 만든 세 개의 목록 — $\mathbb{Z}$, $\mathbb{Q}$, $\mathbb{N} \times \mathbb{N}$ — 의 아이디어를 각각 한 마디로 쓰시오. 1. "모든 무한집합은 가산이다"가 아직 증명되지 않은 $\forall$ 명제인 이유를 쓰시오. (29$\cdot$48주차) ### 자주 나오는 세 가지 답 — 3번 문항 방금 쓴 답은 대개 다음 세 유형 중 하나다. 셋 다 옳은 부분이 있고, 셋 다 이번 주에 메울 정확한 간격이 있다. - **유형 1 — 사례 일반화.** "$\mathbb{Z}$도 $\mathbb{Q}$도 가산이었으니 다른 무한집합도 그럴 것이다"라고 적는다. 관찰한 세 사례에 대해서는 옳다. 문제는 무한집합이 무한히 많다는 것이다 — 확인하지 않은 나머지 전부는 무엇이 보장하는가. 1주차 문제 18에서 39개의 사례가 성립하고도 명제가 거짓이었던 것과 같은 자리다. - **유형 2 — 조밀함을 크기로.** "$\mathbb{R}$은 $\mathbb{Q}$보다 훨씬 빽빽하므로 더 클 것이다"라고 적는다. $\mathbb{R}$이 더 크다는 결론은 이번 주에 실제로 증명된다. 문제는 근거다 — $\mathbb{Q}$ 자신이 두 유리수 사이 어디에나 또 하나가 있을 만큼 빽빽한데도 가산이었다(15주차 문제 17, 48주차 예제 2.3의 격자 행진에 지그재그 결합을 더한 48주차 문제 15). 조밀함은 크기의 증거가 되지 못한다. 이 추론을 문제 18에서 정면으로 해부한다. - **유형 3 — 백지.** "모든 무한이 가산"이 참인지 거짓인지, 무엇을 보여야 판정이 끝나는지 몰라 아무것도 적지 못했다. 판정에 필요한 것이 무엇인지는 §1.2에서 정의로 확정하고, 그 판정을 실제로 수행하는 절차는 §2에서 만든다. ## 개념 — 목록 밖의 원소 ### 1 목록 만들기로 밀어붙이면 어디서 막히는가 이번 주의 상대는 구간 $(0, 1)$이다. 48주차의 도구는 하나뿐이었다 — 빠짐없고 겹침 없는 목록을 실제로 만들어 보이는 것. 그 도구로 $(0,1)$을 밀어붙여 보자. :::{admonition} 시도 — 목록을 직접 만들어 보기 :class: quotebox "소수 자릿수가 짧은 것부터 늘어놓자: $0.1,\ 0.2,\ \dots,\ 0.9,\ 0.01,\ 0.02,\ \dots,\ 0.99,\ 0.001,\ \dots$ 이렇게 하면 $(0,1)$의 실수가 전부 언젠가 나온다 — " ::: 여기서 멈춘다. 이 목록에 오르는 것은 소수점 아래가 언젠가 끝나는 수뿐이고, $\frac13 = 0.333\cdots$은 영원히 차례가 오지 않는다. 48주차 예제 2.3의 격자 행진을 흉내 내려 해도 마찬가지다 — 격자의 좌표가 되어 줄 두 정수가 무리수에는 없다. :::{container} quotebox **확인 1.** "목록을 만들려는 시도가 실패했다"는 사실은 "$(0,1)$의 목록은 존재하지 않는다"의 증명인가. 아니라면 무엇이 더 필요한가. ::: :::{admonition} 답 :class: quotebox dropdown 증명이 아니다. 실패는 "이 방법으로는 안 되더라"일 뿐이고, 29주차의 세 상태로는 **미해결**에 해당한다 — 다른 누군가가 더 영리한 목록을 들고 올 가능성이 남아 있다. "존재하지 않는다"를 보이려면 **임의의** 목록 하나를 가정해 놓고, 그것이 어떤 목록이든 반드시 실패함을 보여야 한다. 비존재 명제를 가정 자리로 옮겨 다루는 기법이 21주차의 귀류법이다. ::: :::{admonition} 이 주 전체의 기준 :class: quotebox 이번 주에 증명할 것은 "아직 목록을 못 만들었다"가 아니라 "목록은 존재할 수 없다"이다. 대상은 특정 목록 하나가 아니라 목록 전부다. ::: ### 2 목록이 없는 무한집합에 이름 붙이기 지금까지 판정이 끝난 집합들을 한 표에 모아 보자. 셋째 열의 빈칸을 채운다. | **집합** | **빠짐없는 목록이 있는가** | **목록의 아이디어** | |---|---|---| | $\mathbb{N}$ | 있다 | 항등함수 $f(n) = n$ | | $\mathbb{Z}$ | 있다 | $\underline{\quad(1)\quad}$ (48주차 예제 2.2) | | $\mathbb{Q}$ | 있다 | $\underline{\quad(2)\quad}$ (48주차 예제 2.3과 문제 15) | | $(0,1)$ | ? | 이번 주에 판정한다 | :::{container} quotebox **확인 2.** 빈칸 (1)(2)를 채우고, 넷째 행의 "?"를 "없다"로 확정하려면 무엇을 보여야 하는지 한 문장으로 적어 보자. ::: :::{admonition} 답 :class: quotebox dropdown (1) 지그재그 목록 $0,\ 1,\ -1,\ 2,\ -2,\ \dots$ (2) 양의 유리수를 분모$\cdot$분자의 좌표로 삼은 격자 행진(48주차 예제 2.3)에 음수와 0을 끼우는 지그재그 결합을 더한 것(48주차 문제 15), 약분으로 겹치는 값은 건너뛴다. 넷째 행을 "없다"로 확정하려면, 누가 어떤 목록을 가져와도 그 목록이 $(0,1)$의 원소 하나를 빠뜨림을 보여야 한다. "아직 못 만들었다"와 "만들 수 없다"는 다른 문장이다. ::: 넷째 행처럼 판정되는 집합에 이름을 붙인다. 정의 자체에 새로운 것은 없다 — 표의 넷째 행이 무엇을 뜻하는지를 문장으로 굳혔을 뿐이다. ### 정의 49.1 — 비가산 (uncountable) [백지 암기 대상] :::{container} quotebox 집합 $A$가 **가산이 아닐 때** — 곧 $A$가 유한하지도 않고, $\mathbb{N}$에서 $A$로의 전단사도 **존재하지 않을 때** — $A$를 **비가산**(uncountable)이라 한다. ::: 이 문장은 "에이는 유한하지 않고, 엔에서 에이로 가는 전단사도 존재하지 않는다"로 읽는다. 읽는 법까지가 정의다. 48주차 정의 48.2에서 "가산 = 유한이거나 가산 무한"이라 했으므로, 비가산은 그 두 가능성을 모두 부정한 것이다. ### 3 정의 해부 — 조각마다 하는 일 이 한 문장은 네 조각으로 되어 있고, 조각마다 증명에서 맡는 역할이 다르다. | **조각** | **하는 일** | **증명에서의 역할** | |---|---|---| | "집합 $A$가" | 판정 대상의 선언 | 이 정의는 $A$ 하나를 심사하는 기준이다 | | "유한하지도 않고" | 유한 배제 | 이 조각이 빠지면 정의가 무너진다 (아래 실험) | | "$\mathbb{N}$에서 $A$로의 전단사도" | 반박할 상대의 지정 | 상대는 하나의 목록이다 — 그것이 실패하는 원소를 만들면 된다 | | "존재하지 않을 때" | **비존재** 요구 | 하나를 제시해서 끝낼 수 없다. 전부가 실패함을 보여야 한다 — 21주차 귀류법의 신호 | **조각 삭제 실험.** 둘째 조각 "유한하지도 않고"를 지워 보자. 그러면 $\{1, 2, 3\}$은 $\mathbb{N}$과의 전단사가 없으므로 — 원소 개수가 다르니 당연히 없다 — 비가산이 된다. :::{container} quotebox **확인 3.** "유한하지도 않고"라는 조각을 지우는 순간 정확히 무엇이 무너지는가. ($\{1,2,3\}$만의 문제인지, 빈집합 $\emptyset$과 $\{a\}$는 어떤지 함께 생각해 보자.) ::: :::{admonition} 답 :class: quotebox dropdown **모든** 유한집합이 비가산이 된다 ($\emptyset$도, $\{a\}$도 $\mathbb{N}$과 대등하지 않다). 그러면 "비가산"이라는 말이 $\{1,2,3\}$과 $\mathbb{R}$을 **구별하지 못한다** — 무한의 등급을 재려고 만든 말이 가장 작은 집합까지 끌어안아 버린다. 정의의 조각 하나하나가 이런 붕괴를 막는 조건이다. ::: **"존재하지 않는다"는 방향에 따라 다르게 작동한다.** 48주차 정의 48.1의 "존재한다"와 정확히 반대다. | **상황** | **"존재하지 않는다"가 하는 일** | |---|---| | 목표가 "$A$는 가산" | 목록 **하나**를 만들어 제시하면 끝난다 (48주차의 모든 증명) | | 목표가 "$A$는 비가산" | 목록을 하나도 만들 수 없음을 보여야 한다 — 임의의 목록을 받아 실패시킨다 | :::{container} quotebox **확인 4.** "$(0,1)$은 비가산"을 증명하려는 두 답안이 있다. 각각 무엇이 부족한가. (가) "$0.1, 0.2, \dots$로 목록을 만들어 봤는데 $\frac13$이 빠졌다. 그러므로 비가산이다." (나) "$(0,1)$의 원소는 무한히 많다. 그러므로 비가산이다." ::: :::{admonition} 답 :class: quotebox dropdown (가) 목록 **하나**가 실패한 것뿐이다. 위 표의 둘째 행이 요구하는 것은 임의의 목록에 대한 실패이고, 특정 목록의 실패는 그 목록이 서툴렀다는 뜻일 수도 있다. (나) 무한하다는 것은 정의 49.1의 첫째 조건일 뿐이다. $\mathbb{Q}$도 무한하지만 가산이다(48주차 문제 15) — 무한은 비가산의 필요조건이지 충분조건이 아니다 (8주차의 구분). ::: ### 4 목록을 표로 펼치면 — 대각선이 보인다 임의의 목록을 어떻게 실패시킬 것인가. 목록이 손에 있다고 치고, 각 항의 십진 전개를 가로로 늘어놓아 무한 숫자표를 만들어 보자. 아래 네 항이 어떤 목록의 처음 네 개라고 하자. 마지막 열을 채운다. | **$n$** | **$r_n$** | **1번째 자리** | **2번째 자리** | **3번째 자리** | **4번째 자리** | **대각선 성분** | |---|---|---|---|---|---|---| | 1 | $0.6183\cdots$ | 6 | 1 | 8 | 3 | $\underline{\quad(1)\quad}$ | | 2 | $0.2570\cdots$ | 2 | 5 | 7 | 0 | $\underline{\quad(2)\quad}$ | | 3 | $0.9412\cdots$ | 9 | 4 | 1 | 2 | $\underline{\quad(3)\quad}$ | | 4 | $0.3348\cdots$ | 3 | 3 | 4 | 8 | $\underline{\quad(4)\quad}$ | 여기서 "대각선 성분"이란 $n$번째 수의 $n$번째 자리, 곧 표의 왼쪽 위에서 오른쪽 아래로 내려가며 뽑은 숫자를 말한다. :::{container} quotebox **확인 5.** 빈칸 (1)~(4)를 채워 보자. ::: :::{admonition} 답 :class: quotebox dropdown (1) 6 (2) 5 (3) 1 (4) 8. 첫 행에서는 첫째 자리, 둘째 행에서는 둘째 자리를 뽑았다 — 행 번호와 열 번호를 같게 맞춘 것이 전부다. ::: 이제 새 수 $c = 0.c_1c_2c_3c_4\cdots$를 만든다. 규칙은 하나 — **$c_n$은 위에서 뽑은 $n$번째 대각선 성분과 다른 숫자로 고른다.** 예를 들어 $c = 0.5555\cdots$이 아니라, (1)~(4)를 피해서 $c_1 \neq 6$, $c_2 \neq 5$, $c_3 \neq 1$, $c_4 \neq 8$이 되도록 고른다. :::{container} quotebox **확인 6.** 이렇게 만든 $c$가 $r_1, r_2, r_3, r_4$ 중 어느 것과도 같지 않다. 그 이유를 $n$을 써서 한 문장으로 적어 보자. ::: :::{admonition} 답 :class: quotebox dropdown 각 $n$에 대해 $c$와 $r_n$은 $n$번째 소수 자리에서 다르기 때문이다 — $c_n$을 고를 때 바로 그 자리를 피해서 골랐다. $r_1$과는 첫째 자리에서, $r_2$와는 둘째 자리에서, … 이런 식으로 **목록의 모든 항과 각각 다른 자리에서** 어긋난다. 이 관찰이 이번 주 증명의 전부다. §2에서 여기에 이름을 붙인다. ::: ### 5 십진 표기의 안전장치 — 왜 4와 5만 쓰는가 확인 6의 논증에는 아직 구멍이 하나 있다. "한 자리라도 다르면 다른 수다"를 근거 없이 썼다. :::{container} quotebox **확인 7.** $0.4999\cdots$과 $0.5000\cdots$은 소수 자리가 첫째부터 전부 다르다. 두 수는 다른 수인가. 46주차 문제 14의 결과로 판정해 보자. ::: :::{admonition} 답 :class: quotebox dropdown 같은 수다. 46주차 문제 14에서 $0.999\cdots = 1$을 급수의 극한으로 판결했고, 양변을 10으로 나누면 $0.0999\cdots = 0.1$이므로 $0.4999\cdots = 0.4 + 0.1 = 0.5$이다. 따라서 "자리가 다르면 다른 수"는 무조건 성립하지 않는다 — 하나의 수가 두 개의 십진 표기를 갖는 경우가 있다. ::: 두 표기를 갖는 수는 한 종류뿐이다: 어느 자리 이후로 **9만 이어지는** 표기와 같은 수의 **0만 이어지는** 표기가 짝을 이룬다($0.4999\cdots$과 $0.5000\cdots$). 그 밖의 실수는 십진 표기가 유일하다. (이 사실은 지금은 증명 없이 인정하고 쓴다 — 증명에는 급수 수렴에 관한 준비가 더 필요하며 이 과정 밖의 주제다.) :::{container} quotebox **확인 8.** 제작하는 수 $b$의 각 자리를 4와 5 중에서만 고르기로 하면, 위 함정이 어떻게 차단되는가. 그리고 그 규칙이 덤으로 보장해 주는 것은 무엇인가. ::: :::{admonition} 답 :class: quotebox dropdown $b$의 전개에는 9만 이어지는 꼬리도, 0만 이어지는 꼬리도 없다 — 모든 자리가 4 아니면 5이기 때문이다. 그러므로 $b$는 두 표기를 갖는 수가 아니고, $b$의 십진 표기는 유일하다. 덤으로 $0.444\cdots \le b \le 0.555\cdots$이므로 $b$는 0보다 크고 1보다 작다 — 곧 $b \in (0,1)$이라는 소속 확인이 같은 규칙에서 함께 나온다. ::: ### 6 근거 목록 갱신 — 칸은 그대로 네 개 1주차 §1.6에서 세운 근거 ①~④가 이번 주에 다음처럼 갱신된다. 칸의 개수는 늘지 않는다 — ① 칸에 정의가 하나 추가되고, ④ 칸에 이번 주의 결과들이 얹힐 뿐이다. | **근거** | **이번 주의 내용** | **이번 주에는 이렇게 쓴다** | |---|---|---| | ① 정의 | **정의 49.1(비가산)**, 48주차 정의 48.1(대등)$\cdot$48.2(가산) | "비가산" $\leftrightarrow$ "빠짐없는 목록이 존재하지 않는다" 사이를 번역한다 | | ② 닫힘성 | 새로 추가되는 것 없음 | $b_n$이 늘 한 자리 숫자임을 별도 설명 없이 쓴다 | | ③ 등식의 성질 | 새로 추가되는 것 없음 | 십진 전개를 급수로 바꿔 적는다(문제 16) | | ④ 이미 증명한 명제 | 48주차 예제 2.1~2.3, 48주차 문제 12$\cdot$14$\cdot$15, **배중률**(26주차 §1.4 — 증명 없이 인정하고 쓰는 원리), 이번 주 예제 2.1~2.3과 문제 8 | 문제 8이 예제 2.1을 부품으로 $\mathbb{R}$의 비가산성을 얻고(문제 8의 증명은 §4에 있다 — 예제 2.2는 결과만 앞당겨 쓴다), 예제 2.3이 배중률로 두 경우가 전체를 덮음을 말한다 | 목록 밖의 것은 이번 주에도 근거가 되지 않는다. 특히 "$\mathbb{R}$이 더 빽빽하니까"는 목록에 없다 — 그 인상을 근거로 쓰면 무엇이 무너지는지는 문제 18에서 해부한다. :::{container} quotebox **확인 9.** 어떤 증명에 다음 세 문장이 나왔다. 각각 허용되는가. 허용된다면 몇 번 근거인가. (가) "$\mathbb{Q}$는 가산이므로" (나) "$\mathbb{R}$은 수직선을 빈틈없이 채우므로 비가산이다" (다) "정의에 의해 $(0,1)$이 가산이면 빠짐없는 목록이 존재한다" ::: :::{admonition} 답 :class: quotebox dropdown (가) 허용 — 근거 ④. 48주차 문제 15에서 증명된 명제다. (나) 불허 — 목록 밖이다. "빈틈없이 채운다"는 관찰은 $\mathbb{Q}$에도 어느 정도 해당하며(15주차 문제 17), $\mathbb{Q}$는 가산이다. 반례가 있는 추론 형식은 근거가 되지 못한다. (다) 허용 — 근거 ①. 다만 정의 48.2의 "가산"에는 유한인 경우도 들어 있으므로, 목록을 꺼내려면 "무한집합인 $(0,1)$이 가산이면"까지 적어야 한다 — 유한하지 않아야 가산 무한이 되고, 가산 무한이라야 목록 $r_1, r_2, r_3, \dots$이 나온다. :::