49주차 — 칸토어의 대각선 논법: 비가산 무한

이 주의 길잡이

핵심 문장: 어떤 목록을 내밀어도, 대각선을 비틀면 그 목록에 없는 실수가 만들어진다.

이 주의 위치: 50주 과정의 49주차. 48주차에서 넓혀 온 “가산인 무한”에 바깥이 있음을 증명하고, 무한의 등급이 끝없이 올라간다는 것까지 본다.

원서 대응: BoP(Book of Proof) 14.2 후반(Uncountable Sets), 14.3(Comparing Cardinalities) — 병행자 참고용. 원서 없이 읽을 수 있다.

이번 주 목표

1. 비가산의 정의를 백지에 쓰고, 그것이 왜 비존재 명제인지 설명할 수 있다.

2. 대각선 논법으로 \((0, 1)\)이 비가산임을 백지에서 처음부터 끝까지 증명할 수 있다.

3. 따름 결과 세 가지를 유도할 수 있다: \(\mathbb{R}\) 비가산, 무리수 비가산, 칸토어의 정리 \(|A| \neq |\mathcal{P}(A)|\).

4. 연속체 가설을 통해 “증명도 반증도 불가능함이 증명된” 네 번째 상태를 29주차의 세 상태에 더한다.

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

준비 운동 (48주차 복습)

1. 가산 무한의 정의를 백지에 쓰고, 그것을 “목록화”로 바꿔 읽으시오.

2. 지난주에 만든 세 개의 목록 — \(\mathbb{Z}\), \(\mathbb{Q}\), \(\mathbb{N} \times \mathbb{N}\) — 의 아이디어를 각각 한 마디로 쓰시오.

3. “모든 무한집합은 가산이다”가 아직 증명되지 않은 \(\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)\)을 밀어붙여 보자.

시도 — 목록을 직접 만들어 보기

“소수 자릿수가 짧은 것부터 늘어놓자:

\(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의 격자 행진을 흉내 내려 해도 마찬가지다 — 격자의 좌표가 되어 줄 두 정수가 무리수에는 없다.

확인 1. “목록을 만들려는 시도가 실패했다”는 사실은 “\((0,1)\)의 목록은

존재하지 않는다”의 증명인가. 아니라면 무엇이 더 필요한가.

답

증명이 아니다. 실패는 “이 방법으로는 안 되더라”일 뿐이고, 29주차의 세 상태로는

미해결에 해당한다 — 다른 누군가가 더 영리한 목록을 들고 올 가능성이 남아

있다. “존재하지 않는다”를 보이려면 임의의 목록 하나를 가정해 놓고, 그것이

어떤 목록이든 반드시 실패함을 보여야 한다. 비존재 명제를 가정 자리로 옮겨

다루는 기법이 21주차의 귀류법이다.

이 주 전체의 기준

이번 주에 증명할 것은 “아직 목록을 못 만들었다”가 아니라

“목록은 존재할 수 없다”이다. 대상은 특정 목록 하나가 아니라 목록 전부다.

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)\)	?	이번 주에 판정한다

확인 2. 빈칸 (1)(2)를 채우고, 넷째 행의 “?”를 “없다”로 확정하려면

무엇을 보여야 하는지 한 문장으로 적어 보자.

답

(1) 지그재그 목록 \(0,\ 1,\ -1,\ 2,\ -2,\ \dots\) (2) 양의 유리수를 분모\(\cdot\)분자의

좌표로 삼은 격자 행진(48주차 예제 2.3)에 음수와 0을 끼우는 지그재그 결합을 더한

것(48주차 문제 15), 약분으로 겹치는 값은 건너뛴다.

넷째 행을 “없다”로 확정하려면, 누가 어떤 목록을 가져와도 그 목록이 \((0,1)\)의

원소 하나를 빠뜨림을 보여야 한다. “아직 못 만들었다”와 “만들 수 없다”는

다른 문장이다.

넷째 행처럼 판정되는 집합에 이름을 붙인다. 정의 자체에 새로운 것은 없다 — 표의 넷째 행이 무엇을 뜻하는지를 문장으로 굳혔을 뿐이다.

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

집합 \(A\)가 가산이 아닐 때 — 곧 \(A\)가 유한하지도 않고, \(\mathbb{N}\)에서 \(A\)로의 전단사도 존재하지 않을 때 — \(A\)를 비가산(uncountable)이라 한다.

이 문장은 “에이는 유한하지 않고, 엔에서 에이로 가는 전단사도 존재하지 않는다”로 읽는다. 읽는 법까지가 정의다. 48주차 정의 48.2에서 “가산 = 유한이거나 가산 무한”이라 했으므로, 비가산은 그 두 가능성을 모두 부정한 것이다.

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

이 한 문장은 네 조각으로 되어 있고, 조각마다 증명에서 맡는 역할이 다르다.

조각	하는 일	증명에서의 역할
“집합 \(A\)가”	판정 대상의 선언	이 정의는 \(A\) 하나를 심사하는 기준이다
“유한하지도 않고”	유한 배제	이 조각이 빠지면 정의가 무너진다 (아래 실험)
“\(\mathbb{N}\)에서 \(A\)로의 전단사도”	반박할 상대의 지정	상대는 하나의 목록이다 — 그것이 실패하는 원소를 만들면 된다
“존재하지 않을 때”	비존재 요구	하나를 제시해서 끝낼 수 없다. 전부가 실패함을 보여야 한다 — 21주차 귀류법의 신호

조각 삭제 실험. 둘째 조각 “유한하지도 않고”를 지워 보자. 그러면 \(\{1, 2, 3\}\)은 \(\mathbb{N}\)과의 전단사가 없으므로 — 원소 개수가 다르니 당연히 없다 — 비가산이 된다.

확인 3. “유한하지도 않고”라는 조각을 지우는 순간 정확히 무엇이 무너지는가.

(\(\{1,2,3\}\)만의 문제인지, 빈집합 \(\emptyset\)과 \(\{a\}\)는 어떤지 함께 생각해 보자.)

답

모든 유한집합이 비가산이 된다 (\(\emptyset\)도, \(\{a\}\)도 \(\mathbb{N}\)과 대등하지

않다). 그러면 “비가산”이라는 말이 \(\{1,2,3\}\)과 \(\mathbb{R}\)을 구별하지 못한다 —

무한의 등급을 재려고 만든 말이 가장 작은 집합까지 끌어안아 버린다. 정의의 조각

하나하나가 이런 붕괴를 막는 조건이다.

“존재하지 않는다”는 방향에 따라 다르게 작동한다. 48주차 정의 48.1의 “존재한다”와 정확히 반대다.

상황	“존재하지 않는다”가 하는 일
목표가 “\(A\)는 가산”	목록 하나를 만들어 제시하면 끝난다 (48주차의 모든 증명)
목표가 “\(A\)는 비가산”	목록을 하나도 만들 수 없음을 보여야 한다 — 임의의 목록을 받아 실패시킨다

확인 4. “\((0,1)\)은 비가산”을 증명하려는 두 답안이 있다. 각각 무엇이 부족한가.

(가) “\(0.1, 0.2, \dots\)로 목록을 만들어 봤는데 \(\frac13\)이 빠졌다. 그러므로 비가산이다.”

(나) “\((0,1)\)의 원소는 무한히 많다. 그러므로 비가산이다.”

답

(가) 목록 하나가 실패한 것뿐이다. 위 표의 둘째 행이 요구하는 것은 임의의

목록에 대한 실패이고, 특정 목록의 실패는 그 목록이 서툴렀다는 뜻일 수도 있다.

(나) 무한하다는 것은 정의 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\)번째 자리, 곧 표의 왼쪽 위에서 오른쪽 아래로 내려가며 뽑은 숫자를 말한다.

확인 5. 빈칸 (1)~(4)를 채워 보자.

답

(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\)이 되도록 고른다.

확인 6. 이렇게 만든 \(c\)가 \(r_1, r_2, r_3, r_4\) 중 어느 것과도 같지 않다.

그 이유를 \(n\)을 써서 한 문장으로 적어 보자.

답

각 \(n\)에 대해 \(c\)와 \(r_n\)은 \(n\)번째 소수 자리에서 다르기 때문이다 — \(c_n\)을

고를 때 바로 그 자리를 피해서 골랐다. \(r_1\)과는 첫째 자리에서, \(r_2\)와는 둘째

자리에서, … 이런 식으로 목록의 모든 항과 각각 다른 자리에서 어긋난다.

이 관찰이 이번 주 증명의 전부다. §2에서 여기에 이름을 붙인다.

5 십진 표기의 안전장치 — 왜 4와 5만 쓰는가

확인 6의 논증에는 아직 구멍이 하나 있다. “한 자리라도 다르면 다른 수다”를 근거 없이 썼다.

확인 7. \(0.4999\cdots\)과 \(0.5000\cdots\)은 소수 자리가 첫째부터 전부 다르다.

두 수는 다른 수인가. 46주차 문제 14의 결과로 판정해 보자.

답

같은 수다. 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\)). 그 밖의 실수는 십진 표기가 유일하다. (이 사실은 지금은 증명 없이 인정하고 쓴다 — 증명에는 급수 수렴에 관한 준비가 더 필요하며 이 과정 밖의 주제다.)

확인 8. 제작하는 수 \(b\)의 각 자리를 4와 5 중에서만 고르기로 하면, 위 함정이

어떻게 차단되는가. 그리고 그 규칙이 덤으로 보장해 주는 것은 무엇인가.

답

\(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에서 해부한다.

확인 9. 어떤 증명에 다음 세 문장이 나왔다. 각각 허용되는가.

허용된다면 몇 번 근거인가.

(가) “\(\mathbb{Q}\)는 가산이므로” (나) “\(\mathbb{R}\)은 수직선을 빈틈없이 채우므로 비가산이다”

(다) “정의에 의해 \((0,1)\)이 가산이면 빠짐없는 목록이 존재한다”

답

(가) 허용 — 근거 ④. 48주차 문제 15에서 증명된 명제다.

(나) 불허 — 목록 밖이다. “빈틈없이 채운다”는 관찰은 \(\mathbb{Q}\)에도 어느 정도

해당하며(15주차 문제 17), \(\mathbb{Q}\)는 가산이다. 반례가 있는 추론 형식은 근거가

되지 못한다.

(다) 허용 — 근거 ①. 다만 정의 48.2의 “가산”에는 유한인 경우도 들어 있으므로,

목록을 꺼내려면 “무한집합인 \((0,1)\)이 가산이면”까지 적어야 한다 — 유한하지

않아야 가산 무한이 되고, 가산 무한이라야 목록 \(r_1, r_2, r_3, \dots\)이 나온다.