C14주차 — 기수 비교와 슈뢰더-번슈타인 정리

C14주차 — 기수 비교와 슈뢰더-번슈타인 정리#

이 주의 길잡이

핵심 문장: “\(|A| \le |B|\)”는 단사 하나의 존재를 뜻하고, 슈뢰더-번슈타인 정리는 양쪽으로 단사가 있으면 전단사가 있음을 보장한다. 그러므로 같은 크기를 보이는 일이 전단사 하나를 만드는 일에서 단사 두 개를 만드는 일로 바뀐다.

이 주의 위치: 2학기 20주 과정의 C14주차. C13주차가 “같은 크기”를 전단사의 존재로 정의했고, 이번 주는 “크지 않다”를 단사의 존재로 정의해 두 기수 사이에 부등호를 놓는다. C13주차 문제 19와 1권 49주차 문제 17에서 갈래 규칙으로 공들여 만든 전단사가 여기서는 단사 두 개로 대체된다. 1권 49주차와 C13주차가 “단사는 있고 전단사는 없다”의 줄임으로만 쓰던 기호 \(<\)가 여기서 정식 정의를 얻는다.

원서 대응: Chartrand 11.4~11.5 (Comparing Cardinalities / The Schröder-Bernstein Theorem). 1일차에 이 두 절을 통독한 상태로 이 교안에 온다.

이번 주 목표#

  1. 기수 비교 \(|A| \le |B|\)를 단사의 존재로 정의하고, 정의의 조각마다 무엇이 무너지는지 설명한다.

  2. 이 관계가 반사적이고 추이적임을 증명하고, 남은 성질인 반대칭이 무한에서 왜 정리가 되어야 하는지 밝힌다.

  3. 슈뢰더-번슈타인 정리를 진술하고, CSB 활용의 3단 서식을 백지에 재현한다.

  4. 전단사를 직접 만들지 않고 \(|(0,1)| = |[0,1]|\), \(|\mathbb{N}| = |\mathbb{N} \times \mathbb{N}|\), \(|\mathbb{R}| = |\mathbb{R}^2|\)를 증명한다.

  5. 무한 기수의 산술을 부품 목록으로 정리하고, 연속체 가설이 어떤 종류의 물음인지 구분한다.

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

표기 — § 와 난이도 표시

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

다른 주차를 가리킬 때는 “C13주차 §1.6”처럼 주차를 앞에 적는다.

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

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

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

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

  1. C13주차 정의 1.1을 진술하시오 — 무엇이 하나 존재하면 \(|A| = |B|\)인가.

  2. C12주차 §1.3의 단사 증명 서식을 쓰시오 — 어떤 문장으로 시작해 어떤 문장으로 끝나는가.

  3. C13주차 문제 19(\([0,1]\)과 \((0,1)\)이 같은 크기)의 전단사를 백지에 재현하시오. 규칙이 몇 갈래로 갈렸는지 세어 둔다.

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

  1. (진단) 직선 \(\mathbb{R}\)과 평면 \(\mathbb{R}^2\) 중 어느 쪽이 더 큰가. 근거와 함께 답하시오.

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

자주 나오는 세 가지 답#

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

  • 유형 1 — 평면이 더 크다. “직선은 평면 안에 통째로 들어가므로 평면이 더 크다.”

전반부의 관찰은 정확하다 — \(x \mapsto (x, 0)\)이 실제로 \(\mathbb{R}\)을 \(\mathbb{R}^2\) 안에 겹침 없이 심는다. 이번 주는 그 관찰에 \(|\mathbb{R}| \le |\mathbb{R}^2|\)라는 이름을 준다. 빠진 것은 후반부다 — “안에 들어간다”에서 “더 작다”로 넘어가려면 반대 방향의 단사가 없음을 따로 보여야 하는데 그 확인이 없다. 실제로 반대 방향의 단사는 존재하며(그 재료가 §1.1의 자리 엮기이고 완성은 예제 2.3이다), 결론은 뒤집힌다.

  • 유형 2 — 둘 다 비가산이므로 같다. 결론은 이번 주의 정답과 일치한다. 그러나

같은 근거로 \(|\mathcal{P}(\mathbb{R})| = |\mathbb{R}|\)도 나오는데, C13주차 문제 15의 칸토어 정리가 그것을 반증한다. 참인 결론과 거짓인 결론을 함께 낳는 문장은 근거가 아니다. 비가산은 하나의 크기가 아니라 “\(\aleph_0\)이 아니다”라는 뜻일 뿐이며, 비가산끼리를 갈라내는 잣대가 §1.2에서 만들어진다.

  • 유형 3 — 전단사를 만들 수 없어 답하지 못했다. C13주차의 도구로 답하려면

\(\mathbb{R}\)과 \(\mathbb{R}^2\) 사이의 전단사를 실제로 제작하거나 그런 것이 하나도 없음을 보여야 하는데, 둘 다 만만치 않다. 그 판단은 정확하다. 이번 주가 하는 일이 정확히 그 제작을 우회하는 길을 내는 것이고, 길이 나면 이 물음의 답은 네 줄로 끝난다.

개념 — 부등호를 놓는 법#

1 전단사를 직접 만들려 하면 어디서 막히는가#

새 도구를 꺼내기 전에, 지금 가진 도구 — 전단사의 직접 제작 — 만으로 준비 운동 4번을 밀어붙여 본다. C13주차 문제 13이 \(|\mathbb{R}| = |(0,1)|\)을 주므로 무대를 정사각형 \((0,1)^2\)과 구간 \((0,1)\)로 옮겨 놓고 시작한다.

시도 — 자리를 번갈아 엮어 전단사 만들기

물음: \((0,1)^2\)과 \((0,1)\)이 같은 크기인가.

“\(x = 0.a_1a_2a_3\cdots\), \(y = 0.b_1b_2b_3\cdots\)의 자리를 번갈아 엮어

\(h(x, y) = 0.a_1b_1a_2b_2a_3b_3\cdots\)으로 정의하자.

서로 다른 쌍은 서로 다른 자리열을 주므로 겹침이 없다.

이제 빠짐이 없음을 보이면 \(h\)가 전단사이므로 … “

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

확인 1. 위 시도에서 \(z = 0.190909\cdots\)을 값으로 갖는 쌍 \((x, y)\)를 실제로 찾아보자. 홀수 자리와 짝수 자리를 각각 모으면 무엇이 나오는가.

답

홀수 자리를 모으면 \(x = 0.1000\cdots = 0.1\)이고, 짝수 자리를 모으면

\(y = 0.999\cdots\)이다. 그런데 \(0.999\cdots\)는 \(1\)과 같은 수이고 \(1 \notin (0,1)\)이므로,

이 \(z\)를 값으로 갖는 쌍이 무대 안에 없다. 곧 \(h\)는 전사가 아니다.

(C13주차 §1.6에서 십진 표기가 두 개인 수는 9의 꼬리 또는 0의 꼬리를 갖는

경우뿐임을 인정하고 썼다. 이번 주에도 각 실수의 십진 전개는 9의 꼬리가 없는

쪽으로 하나 고정한다. 그 약속 아래에서 \(0.999\cdots\)은 \((0,1)\) 원소의 전개로

등장하지 않는다.)

막힌 이유는 계산 실수가 아니다. 겹침 없음은 한 줄로 확보했는데 **빠짐 없음이

확보되지 않았고**, 빠뜨린 자리를 메우려면 대응 규칙을 처음부터 다시 설계해야 한다.

이 주 전체의 기준

겹침 없음은 만들기 쉽고, 빠짐 없음은 만들기 어렵다.

그러므로 쉬운 쪽 둘로 어려운 쪽 하나를 대신할 수 있는지 묻는다.

그 물음에 답하는 것이 슈뢰더-번슈타인 정리다.

2 사례를 모아 보기 — 무엇이 쉽고 무엇이 어려운가#

네 쌍의 집합을 놓고 양쪽 방향의 단사와 전단사를 각각 떠올려 보자. 넷째 열은 “쉽다” 또는 “어렵다”로 채운다.

두 집합 \(A\), \(B\)

단사 \(A \to B\)

단사 \(B \to A\)

전단사를 직접 만들기

\(\mathbb{N}\), \(2\mathbb{N}\)

\(n \mapsto 2n\)

\(m \mapsto m\)

쉽다 — 둘째 열의 함수가 이미 전단사다 (C13주차 예제 2.1)

\((0,1)\), \([0,1]\)

\(x \mapsto x\)

\(x \mapsto \frac{x+1}{3}\)

\(\underline{\quad(1)\quad}\)

\(\mathbb{N}\), \(\mathbb{N} \times \mathbb{N}\)

\(n \mapsto (n, 1)\)

\((m, n) \mapsto 2^m 3^n\)

\(\underline{\quad(2)\quad}\)

\((0,1)^2\), \((0,1)\)

자리 엮기

\(x \mapsto (x, \tfrac12)\)

\(\underline{\quad(3)\quad}\)

확인 2. 표의 (1)(2)(3)을 “쉽다” 또는 “어렵다”로 채우고 근거를 한 줄씩 적어 보자. 그리고 둘째\(\cdot\)셋째 열 여덟 칸에 공통된 것을 한 문장으로 적어 보자.

답

(1) 어렵다 — C13주차 문제 19가 이 전단사를 만들었고, 규칙이 네 갈래로 갈렸다.

(2) 어렵다 — C13주차 문제 9의 대각선 나열은 “\((m,n)\)이 몇 번째인가”를 식으로

적어야 검증이 가능했다.

(3) 어렵다 — §1.1의 시도가 실패했다.

여덟 칸의 공통점: 전부 한 줄짜리 식이고, 확인할 것이 겹침 없음 하나뿐이다.

값이 무대에 들어가는지와 겹치지 않는지만 보면 되고, 무대를 덮는지는 묻지 않는다.

이 관찰에 정식 이름과 기호를 붙인다. 식 자체에 새로운 것은 없다 — C13주차 정의 1.1이 요구하던 두 조건 가운데 빠짐 없음(전사)만 지운 것이다.

정의 1.1 — 기수 비교 (comparing cardinalities) [백지 암기 대상]#

집합 \(A\), \(B\)에 대해, \(A\)에서 \(B\)로의 단사 \(f : A \to B\)가 존재하면

\(|A| \le |B|\)로 쓴다.

이 문장은 “에이의 기수는 비의 기수보다 크지 않다. 곧 에이에서 비로 가는 단사가 존재한다”로 읽는다. 읽는 법까지가 정의다.

표기 — \(\le\) 의 좌우는 수가 아니다

\(|A| \le |B|\)의 좌우에 놓인 것은 집합의 기수이지 수가 아니다. 그러므로

\(|B| - |A|\)나 \(|B| / |A|\) 같은 식은 뜻이 없고, 이 주차의 어느 답안에도 등장하지

않는다. 쓸 수 있는 것은 \(\le\), \(<\), \(=\) 세 관계와 정의 1.1이 붙여 준 뜻뿐이다.

\(A\)가 유한집합일 때는 \(|A|\)가 원소의 개수라는 수를 뜻하기도 하지만, 무한집합의

\(|A|\)는 그 뜻을 갖지 않는다(C13주차 §1.1).

정의 1.2 — 진부등호 \(|A| < |B|\) (strict inequality of cardinalities) [백지 암기 대상]#

\(|A| \le |B|\)이고 \(|A| \ne |B|\)일 때 \(|A| < |B|\)로 쓴다.

여기서 \(|A| \ne |B|\)는 “\(A\)에서 \(B\)로의 전단사가 존재하지 않는다”는 뜻이다

(C13주차 정의 1.1).

정의 1.2를 쓰려면 두 가지를 각각 해야 한다 — 단사 하나를 제시하고, 전단사가 하나도 없음을 배제한다. 앞쪽은 한 줄이고 뒤쪽은 대개 대각선 논법이 필요하다. C13주차 §1.2 확인 2의 비대칭이 여기서도 그대로 작동한다.

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

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

조각

하는 일

판정에서의 역할

“단사”

겹침 없음만 요구한다

전사 의무를 지운다 — 이 지움이 §1.1의 막힘이 풀리는 자리다

“\(f : A \to B\)”

방향을 고정한다

정의역 쪽이 “크지 않은” 쪽이다. 방향을 뒤집으면 반대 부등호가 된다

“존재하면”

하나면 충분하다

함수 하나를 제시하면 판정이 끝난다. 거꾸로, 실패한 함수 하나는 \(\le\)의 반증이 되지 않는다

확인 3. \(|A| \le |B|\)를 보이려고 한다. 만들어야 하는 것은 \(A \to B\) 단사인가, \(B \to A\) 단사인가. 헷갈리지 않을 기억 장치를 한 문장으로 만들어 보자.

답

\(A \to B\) 단사다. 기억 장치: 작은 쪽이 큰 쪽 안으로 들어간다 — 들어가는 쪽이

정의역이므로, 부등호에서 왼쪽에 적힌 집합이 정의역이다.

방향을 뒤집으면 전혀 다른 주장이 된다. \(\mathbb{N} \to \mathbb{R}\) 단사는 쉽게

만들어지지만 \(\mathbb{R} \to \mathbb{N}\) 단사는 존재하지 않는다(문제 2 (c)).

조각 삭제 실험 — “단사”를 지우면. 첫째 조각을 지우고 “함수 \(f : A \to B\)가 존재하면 \(|A| \le |B|\)”로 두어 보자. 비어 있지 않은 두 집합 \(A\), \(B\)에 대해 \(b_0 \in B\)를 하나 고정하고 모든 \(a\)를 \(b_0\)으로 보내는 상수함수를 잡으면 그것이 언제나 함수이므로, 어떤 두 집합에 대해서도 부등호가 성립한다.

확인 4. “단사”를 지우는 순간 정확히 무엇이 무너지는가. \(A = \mathbb{R}\), \(B = \mathbb{N}\)으로 놓고 확인해 보자.

답

상수함수 \(f(x) = 1\)이 \(\mathbb{R} \to \mathbb{N}\) 함수이므로 \(|\mathbb{R}| \le |\mathbb{N}|\)이

되고, 같은 방식으로 \(|\mathbb{N}| \le |\mathbb{R}|\)도 되어 두 부등호가 동시에 성립한다.

그러면 §1.5의 정리를 붙이는 순간 \(|\mathbb{R}| = |\mathbb{N}|\)이 나오는데, 이것은

C13주차 예제 2.3과 정면으로 어긋난다.

곧 모든 집합 쌍에 대해 부등호가 성립해 \(\le\)가 아무것도 구별하지 못한다.

겹침 없음이라는 조각 하나가 이 붕괴를 막는 유일한 조건이다.

표기 — 포함사상 \(A \hookrightarrow B\)

\(A \subseteq B\)일 때 \(x \mapsto x\)로 정의되는 단사를 포함사상이라 하고, 이 함수를

\(A \hookrightarrow B\)로 쓴다. “에이를 비 안으로 심는 포함사상”이라고 읽는다.

화살표에 갈고리를 단 것이 “겹침 없이 심는다”는 표시다. 이 기호는 함수 하나의

이름이므로, 답안에서는 \(A \hookrightarrow B\)라고 적은 뒤에도 식 \(x \mapsto x\)와

무대 확인 \(A \subseteq B\)를 그대로 적는다.

4 순서처럼 행동하는가 — 두 성질은 이미 손에 있다#

\(\le\)라는 기호를 빌려 썼으니 이 관계가 실제로 순서처럼 행동하는지 확인해야 한다. S7주차 문제 16에서 실수의 \(\le\)가 반대칭적임을 삼분법으로 확인했고, C11주차 문제 18에서 반사\(\cdot\)추이\(\cdot\)반대칭을 갖춘 관계를 부분순서라 불렀다. 세 성질을 차례로 본다.

확인 5. 다음 두 성질을 각각 한 줄로 증명해 보자.

(가) 반사: 임의의 집합 \(A\)에 대해 \(|A| \le |A|\)이다.

(나) 추이: \(|A| \le |B|\)이고 \(|B| \le |C|\)이면 \(|A| \le |C|\)이다.

답

(가) 항등함수 \(\mathrm{id}_A : A \to A\), \(\mathrm{id}_A(a) = a\)를 잡는다.

\(\mathrm{id}_A(a_1) = \mathrm{id}_A(a_2)\)이면 곧 \(a_1 = a_2\)이므로 단사이고,

정의 1.1에 의해 \(|A| \le |A|\)이다.

(나) 가정에서 단사 \(f : A \to B\)와 단사 \(g : B \to C\)를 받는다. C12주차 문제 8

(합성의 단사 보존)에 의해 \(g \circ f : A \to C\)가 단사이므로, 정의 1.1에 의해

\(|A| \le |C|\)이다. (이 논증을 부품 인용 없이 처음부터 적는 것이 문제 9다.)

남은 것은 반대칭이다 — “\(|A| \le |B|\)이고 \(|B| \le |A|\)이면 \(|A| = |B|\)인가.” 유한집합에서는 이 물음이 어렵지 않다. 원소의 개수라는 수 \(m\), \(n\)이 있고 \(m \le n\)과 \(n \le m\)에서 \(m = n\)을 얻는 데 쓰는 것이 실수 \(\le\)의 반대칭성 (S7주차 문제 16)이기 때문이다. 무한집합에는 경유할 그 수가 없다(C13주차 §1.1).

확인 6. 무한집합에서 반대칭을 보이려면 결국 무엇을 만들어야 하는가. 가정과 결론을 정의 1.1과 C13주차 정의 1.1로 각각 풀어서 답해 보자.

답

가정이 주는 것은 단사 \(f : A \to B\)와 단사 \(g : B \to A\) 두 개다(정의 1.1).

결론이 요구하는 것은 전단사 \(h : A \to B\) 하나다(C13주차 정의 1.1).

곧 반대칭은 단사 두 개를 재료로 전단사 하나를 제작하라는 요구이며,

유한집합처럼 개수를 세어 우회할 길이 없다. 이 제작이 언제나 가능하다는 것이

다음 절의 정리이고, 그 제작 절차가 정리의 증명이다.

5 슈뢰더-번슈타인 정리#

§1.4가 남긴 물음은 하나다 — 서로 반대 방향의 단사 두 개를 재료로 전단사 하나를 제작할 수 있는가. 이 절은 그 제작이 언제나 가능하다는 것을 정리로 세운다. 그 보장이 서면 §1.2 표에서 “어렵다”로 채운 칸들이 둘째\(\cdot\)셋째 열의 한 줄짜리 식 두 개로 대체되고, 이번 주 답안의 마지막 줄은 거의 전부 이 정리의 인용이 된다.

정리 1.3 — 칸토어-슈뢰더-번슈타인 (Cantor-Schröder-Bernstein, CSB) [백지 암기 대상]#

단사 \(f : A \to B\)와 단사 \(g : B \to A\)가 모두 존재하면, 전단사 \(h : A \to B\)가

존재한다. 곧 \(|A| \le |B|\)이고 \(|B| \le |A|\)이면 \(|A| = |B|\)이다.

정리 1.3을 §1.4의 두 성질과 합치면 기수의 \(\le\)가 반사\(\cdot\)추이\(\cdot\)반대칭을 모두 갖춘다. C11주차 문제 18의 낱말로 말하면 이 관계는 부분순서처럼 행동하고, 유한집합에서 개수를 세어 얻던 세 성질이 무한 기수에서도 그대로 성립한다.

증명은 이 과정에서 인정하고 쓴다. 다만 무엇을 인정하는지는 알아 두어야 하므로 제작의 얼개만 적는다. 각 \(a \in A\)에서 출발해 \(g^{-1}\)과 \(f^{-1}\)을 번갈아 거슬러 올라가는 사슬을 만든다 — \(a\)가 \(g\)의 상에 있으면 \(g^{-1}(a) \in B\)로 한 칸 올라가고, 그것이 다시 \(f\)의 상에 있으면 또 한 칸 올라간다. 사슬은 셋 중 하나로 끝난다: \(A\) 쪽에서 더 올라갈 수 없게 되거나, \(B\) 쪽에서 더 올라갈 수 없게 되거나, 영원히 올라간다. 그러면 \(h\)를 이렇게 정한다 — 사슬이 \(B\) 쪽에서 끝나는 \(a\)에는 \(h(a) = g^{-1}(a)\)를, 나머지 \(a\)에는 \(h(a) = f(a)\)를 준다. 이 \(h\)가 전단사임을 확인하는 것이 증명의 본체이고, 원서 11.5에 그 확인이 있다.

확인 7. 정리 1.3이 유한집합에서는 새로운 내용을 주지 않는 이유를 한 문장으로 적어 보자. 그리고 무한집합에서 새로운 내용이 되는 이유도 한 문장으로 적어 보자.

답

유한집합에서는 \(|A|\)와 \(|B|\)가 원소의 개수라는 수이므로, 두 부등식에서 실수

\(\le\)의 반대칭성(S7주차 문제 16)으로 곧바로 개수가 같음이 나오고 전단사의 존재는

개수가 같다는 사실에서 따라온다.

무한집합에서는 경유할 수가 없으므로 두 단사에서 전단사를 실제로 제작하는 것

말고는 길이 없고, 그 제작이 언제나 가능하다는 것은 자명하지 않다.

이 정리가 하는 일. 정리 1.3은 증명의 우회로를 낸다. \(|A| = |B|\)의 증명이 “전단사 하나 제작”에서 “단사 두 개 제작”으로 바뀌고, §1.2 표에서 확인한 대로 단사 쪽은 한 줄짜리 식으로 끝나는 경우가 많다. C13주차 문제 19가 네 갈래로 만든 전단사를 이번 주 예제 2.1이 두 줄로 대신하는 것이 그 첫 사례다.

6 절차 해부 — CSB 활용의 3단 서식#

백지 암기 대상

CSB 활용의 3단 서식

\(|A| = |B|\)를 정리 1.3으로 증명하려면 —

① 단사 \(f : A \to B\) 제작 — 식을 명시하고, 값이 \(B\)에 들어감을 확인한 뒤 단사임을 증명한다. 이로써 \(|A| \le |B|\).

② 단사 \(g : B \to A\) 제작 — 같은 요령으로 반대 방향. 이로써 \(|B| \le |A|\).

③ 정리 1.3 인용 — 두 부등식에 CSB를 적용해 \(|A| = |B|\)를 선언한다.

각 단사는 전사일 필요가 없다. 겹치지만 않으면 된다.

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

걸음

하는 일

이 걸음을 빼면 무엇이 무너지는가

① 단사 \(f\)

\(A\)를 \(B\) 안에 겹침 없이 심는다

한쪽 부등식이 없으면 상등이 나오지 않는다 — \(\vert\mathbb{N}\vert \le \vert\mathbb{R}\vert\)만으로는 아무 결론도 얻지 못한다

② 단사 \(g\)

\(B\)를 \(A\) 안에 겹침 없이 심는다

같은 이유로 반쪽이다. 아래 삭제 실험의 답안이 정확히 이 결함을 갖는다

③ 정리 인용

두 부등식을 상등으로 승격한다

전단사의 존재를 주장할 근거가 없다. 두 부등식만으로는 C13주차 정의 1.1의 조건이 채워지지 않는다

(각 걸음 안) 단사 검증

겹침 없음을 실제로 보인다

뭉개는 대응이 통과해 거짓 결론이 나온다 — 문제 10의 답안이 이것이다

걸음 삭제 실험 — ②를 빼면. 반대쪽 단사를 만들 의무를 지우면 다음 답안이 합법이 된다.

삭제 실험 — 한쪽 단사만 만든 답안

명제: \(|\mathbb{N}| = |\mathbb{R}|\).

“\(f : \mathbb{N} \to \mathbb{R}\)을 \(f(n) = n\)으로 정의한다. \(f(n_1) = f(n_2)\)이면

곧 \(n_1 = n_2\)이므로 \(f\)는 단사이고, 따라서 \(|\mathbb{N}| \le |\mathbb{R}|\)이다.

그러므로 두 집합은 같은 크기이다.”

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

답

계산은 한 줄도 틀리지 않았다. \(f(n) = n\)은 실제로 단사이고 \(|\mathbb{N}| \le |\mathbb{R}|\)은

참이다. 잘못된 것은 걸음 ②가 통째로 빠졌다는 것이고, 마지막 줄의 “그러므로”가

근거 없이 놓였다.

걸음 ②를 수행하려면 단사 \(g : \mathbb{R} \to \mathbb{N}\)을 만들어야 하는데,

그런 함수는 존재하지 않는다. 존재한다면 이 답안의 \(f\)와 함께 정리 1.3에 넣어

\(|\mathbb{N}| = |\mathbb{R}|\)을 얻게 되고, 그것은 C13주차 예제 2.3과 모순이기 때문이다.

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

이 논증 자체가 문제 2 (c)의 풀이가 된다 — 정리 1.3은 상등을 세울 때만이 아니라

단사의 비존재를 보일 때도 쓰인다.

7 무한 기수의 산술 — 부품 목록#

앞으로의 증명은 매번 밑바닥부터 시작하지 않는다. 아래 여섯 줄을 부품으로 인용하되, 인용할 때는 반드시 출처를 밝힌다.

표기 — \(\aleph_0\) 와 \(\mathfrak{c}\)

\(|\mathbb{N}|\)을 \(\aleph_0\)로 쓰고 “알레프 영”이라고 읽는다. \(|\mathbb{R}|\)은

\(\mathfrak{c}\)로 쓰고 “연속체”라고 읽는다(C13주차 §1.4). 이번 주부터 두 기호

사이에 \(\le\)와 \(<\)를 놓을 수 있다 — 정의 1.1과 1.2가 그 뜻을 정했기 때문이다.

기수의 덧셈 \(\kappa + \lambda\)는 서로소인 두 집합의 합집합의 기수를, 곱셈

\(\kappa \cdot \lambda\)는 곱집합의 기수를 뜻한다. 서로소라는 조건이 덧셈 쪽에

붙는 이유는 문제 17에서 다룬다.

두 연산 모두 기수를 대표하는 집합을 골라 계산하므로, 고른 집합이 달라져도 결과가

같아야 뜻이 선다. \(|X| = |X'|\)이고 \(|Y| = |Y'|\)이면 \(|X \times Y| = |X' \times Y'|\)이고,

두 쌍이 각각 서로소이면 \(|X \cup Y| = |X' \cup Y'|\)이다. 곧 두 정의는 대표원 선택에

의존하지 않는다. 이 두 사실은 지금은 인정하고 쓴다 — 검증은 주어진 두 전단사를

좌표별로, 또는 조각별로 붙이는 일이다.

성질

진술

출처

(Q1)

\(\aleph_0 + \aleph_0 = \aleph_0\)

C13주차 문제 8 (서로소인 두 가산무한의 합집합)

(Q2)

\(\aleph_0 \cdot \aleph_0 = \aleph_0\)

C13주차 문제 9, 그리고 이번 주 예제 2.2

(Q3)

\(\vert(0,1)\vert = \vert[0,1]\vert = \vert\mathbb{R}\vert = \mathfrak{c}\)

이번 주 예제 2.1과 문제 13

(Q4)

\(\mathfrak{c} \cdot \mathfrak{c} = \mathfrak{c}\)

이번 주 예제 2.3과 문제 19

(Q5)

\(\aleph_0 < \mathfrak{c}\)

이번 주 문제 2 (b)(\(\aleph_0 \le \mathfrak{c}\)) + C13주차 예제 2.3(\(\ne\)) + 이번 주 정의 1.2

(Q6)

임의의 집합 \(A\)에 대해 \(\vert A\vert < \vert\mathcal{P}(A)\vert\)

C13주차 문제 15 (칸토어 정리)

(Q1)~(Q4)는 유한의 산술과 어긋난다 — 유한에서는 \(n \ge 2\)일 때 \(n + n \ne n\)이고 \(n \cdot n \ne n\)이다. 무한 기수에서 이 등식들이 성립하는 것은 계산 규칙이 달라져서가 아니라, 좌변과 우변 사이에 전단사가 실제로 존재하기 때문이다.

연속체 가설. (Q5)는 \(\aleph_0 < \mathfrak{c}\)를 주고, 문제 15는 \(\mathfrak{c} = |\mathcal{P}(\mathbb{N})|\)을 준다. 두 줄을 합치면 \(\aleph_0 < |\mathcal{P}(\mathbb{N})|\)이며, 이것은 (Q6)을 \(A = \mathbb{N}\)에 적용한 결과와 같다. 그러면 \(\aleph_0\)과 \(\mathfrak{c}\) 사이에 다른 기수가 있는가. 이 물음이 연속체 가설이고, 괴델과 코언은 표준 공리계 ZFC 안에서 이 문장이 증명될 수도 반증될 수도 없음을 보였다. 곧 연속체 가설은 아직 답이 나오지 않은 문제가 아니라 공리계가 결정하지 않는 문제이며, 1권 49주차 문제 19가 이 상태를 “참\(\cdot\)거짓\(\cdot\)미해결”에 더해지는 넷째 상태로 정리해 두었다. 같은 구분이 S19주차의 공리계 논의와 이어진다.

확인 9. 다음 두 주장 각각이 위 목록의 어느 줄에서 따라오는지, 또는 따라오지 않는지 적어 보자.

(가) \(|\mathbb{Z} \times \mathbb{Z}| = \aleph_0\)이다.

(나) \(\aleph_0\)과 \(\mathfrak{c}\) 사이에 다른 기수가 없다.

답

(가) 따라온다. \(\mathbb{Z}\)가 가산무한이므로(C13주차 예제 2.2) \(|\mathbb{Z}| = \aleph_0\)이고,

(Q2)에 의해 \(|\mathbb{Z} \times \mathbb{Z}| = \aleph_0 \cdot \aleph_0 = \aleph_0\)이다.

곱집합의 기수가 대표원 선택에 의존하지 않는다는 것은 §1.7의 표기 상자에서

인정하고 쓰기로 한 사실이며, \(\mathbb{N}\) 대신 \(\mathbb{Z}\)를 대표로 놓을 수 있는

근거가 그것이다.

(나) 따라오지 않는다. 이것이 연속체 가설이며 목록의 어느 줄에서도 유도되지 않는다.

답안에 근거로 쓸 수 없는 문장이라는 점이 중요하다 — 참이라고 적어도 거짓이라고

적어도 근거가 없다.

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

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

근거

이번 주에 추가\(\cdot\)갱신되는 것

이번 주에는 이렇게 쓴다

① 정의

정의 1.1, 1.2

“\(\vert A\vert \le \vert B\vert\)” \(\leftrightarrow\) “단사 \(A \to B\)가 존재” 사이를 번역한다

② 닫힘성

변화 없음

정수\(\cdot\)유리수\(\cdot\)실수의 사칙 결과가 그 세계에 남음을 별도 설명 없이 쓴다

③ 등식\(\cdot\)부등식의 성질

변화 없음

\(\frac{x_1+1}{3} = \frac{x_2+1}{3}\)에서 \(x_1 = x_2\)를 얻는 것이 단사 증명의 본체다

④ 이미 증명한 명제

정리 1.3(CSB — 인정하고 쓴다, 원서 11.5) \(\cdot\) 합성의 단사 보존(C12주차 문제 8) \(\cdot\) C13주차의 정의 1.1~1.3과 예제 2.1~2.3, 문제 2\(\cdot\)8\(\cdot\)9\(\cdot\)11\(\cdot\)13\(\cdot\)14\(\cdot\)15\(\cdot\)19 \(\cdot\) 십진 표기가 두 개인 수는 9 또는 0의 꼬리를 갖는 경우뿐(인정하고 쓴다 — C13주차 §1.6) \(\cdot\) 소인수분해의 유일성(인정하고 쓴다 — C15주차에서 증명한다. 이번 주에는 예제 2.2처럼 홀짝 논증으로 대신할 수도 있다) \(\cdot\) 아크탄젠트가 \(\mathbb{R}\)에서 순증가하며 치역이 \((-\frac\pi2, \frac\pi2)\)임(인정하고 쓴다 — C13주차 §1.8과 같은 처리; 문제 13) \(\cdot\) 서로 다른 두 실수 사이에 유리수가 있음(인정하고 쓴다; 문제 15) \(\cdot\) 기수의 덧셈\(\cdot\)곱셈이 대표원 선택에 의존하지 않음(인정하고 쓴다 — §1.7 표기 상자) \(\cdot\) 홀수끼리의 곱은 홀수(1권 1주차 문제 8; 인수가 여럿이면 귀납으로 반복 적용한다) \(\cdot\) 자연수의 비어 있지 않은 부분집합에 최소원소가 있음(1권 33주차 최소원리; 문제 12) \(\cdot\) 합동과 그 곱 보존(C6주차 정의 6.2와 예제 2.2; 훈련 3 해설)

“C13주차 문제 9에 의해”처럼 출처를 대고 한 줄로 끝낸다

목록 밖의 것은 이번 주에도 근거가 되지 않는다. 특히 “차원이 높으니까 크다”와 “둘 다 비가산이니까 같다”는 근거가 아니다 — 전자는 예제 2.3이, 후자는 (Q6)이 반례다.

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

(가) “평면은 직선보다 차원이 높으므로 \(|\mathbb{R}| < |\mathbb{R}^2|\)이다.”

(나) “\(f : A \to B\)와 \(g : B \to C\)가 단사이므로 \(g \circ f\)도 단사이다.”

(다) “두 단사가 있으므로 \(|A| = |B|\)이다.”

답

(가) 불허 — 목록 밖이다. 차원은 크기의 판정 기준이 아니며, 예제 2.3이 실제로

\(|\mathbb{R}| = |\mathbb{R}^2|\)를 증명한다.

(나) 허용 — 근거 ④. C12주차 문제 8이 출처다. 이 한 줄이 §1.4 추이성의 본체다.

(다) 허용 — 근거 ④, 정리 1.3. 다만 “두 단사”가 서로 반대 방향임을 답안에

명시해야 한다. 방향이 같은 단사 두 개는 정리 1.3의 가정이 아니다.