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

이 주의 길잡이

핵심 문장: 무한집합의 크기는 세어서 비교할 수 없으므로 짝짓기로 비교한다. 빠짐도 겹침도 없는 짝짓기(전단사)가 하나라도 있으면 같은 크기이고, 그런 짝짓기가 하나도 없음을 보여야 다른 크기다. 이 잣대로 재면 \(\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|\))를 전단사의 존재로 정의하고, 그 정의의 조각마다 무엇이 무너지는지 설명한다.

2. 가산무한(denumerable)\(\cdot\)가산(countable)\(\cdot\)비가산(uncountable)을 구분하고, 가산 증명의 3단 서식을 백지에 재현한다.

3. \(\mathbb{Z}\)와 \(\mathbb{Q}\)가 가산임을 나열 규칙의 제작과 두 검증으로 증명한다.

4. 대각선 논법으로 \((0,1)\)이 비가산임을 증명하고, 그 논법이 왜 귀류법의 꼴을 취할 수밖에 없는지 밝힌다.

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

표기 — § 와 난이도 표시

§는 “절”이라고 읽는다. §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\)를 잡자”로 시작한다.

2. C12주차 예제 2.1(\(f(x) = 2x - 3\)이 전단사)을 백지에 재현하시오.

3. 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번을 밀어붙여 본다.

시도 — 개수를 세어 비교하기

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

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

\(2\mathbb{N}\)의 원소 개수는 \(N/2\)이다. \(N/2 < N\)이므로 … “

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

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

답

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

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

\(N\)이라고 적은 것은 이름만 있고 대상이 없다.

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

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

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

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

이 주 전체의 기준

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

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

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

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\)이 빠진다	없다	이 규칙은 실패

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

답

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

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

(3) 같은 크기.

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

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

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

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

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

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

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

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

\(A\)와 \(B\)는 같은 크기라 하고 \(|A| = |B|\)로 쓴다.

표기 — \(|A| = |B|\)

“\(|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}|\)조차 성립하지 않는다.

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

답

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

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

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

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

비대칭과의 연결: “존재한다”의 부정은 “모든 것에 대해 아니다”이므로, \(|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) [백지 암기 대상]

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

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

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

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

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

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

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

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

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

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

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

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

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

기수 비교다. 답안에서는 “\(A\)는 가산무한이다”라고 적어도 같은 점수다.

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

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

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

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

답

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

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

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

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

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

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

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

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

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

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

백지 암기 대상

가산 증명의 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의 분수 격자가 이 함정을 실제로 갖고 있다

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

삭제 실험 — 규칙만 제작한 답안

명제: 구간 \((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)\)은 가산무한이다.”

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

답

계산은 한 줄도 틀리지 않았다. \(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).

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

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

답

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

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

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

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

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

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

6 절차 해부 — 대각선 논법

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

백지 암기 대상

대각선 논법의 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\)만 피할 수 있다
⑤ 두 검증	제작물이 무대 안에 있고 실제로 탈출함을 보인다	무대 밖의 대상을 반례로 제출하거나, 다르다는 주장이 검증 없이 남는다

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

삭제 실험 — 탈출만 검증한 답안

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

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

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

따라서 \(y\)가 목록에 없어 모순이다.”

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

답

검증되지 않은 것은 “\(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도 아니기만 하면 어느 쌍이든 된다).

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

답

첫째 함정(자리 넘침) 차단: 규칙이 “\(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에 의해”처럼 출처를 밝힌다.

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

답

참이고, (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이 반례다.

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

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

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

(다) “\(2n_1 = 2n_2\)이므로 \(n_1 = n_2\)이다.”

답

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

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

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

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

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