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

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}\)

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

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

답

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

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

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

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

확인 11. 두 문장을 완성해 보자.

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

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

유한하지 않으므로 \(\underline{\qquad}\)이고, 따라서 \(\underline{\qquad}\)이 존재한다.”

답

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

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

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

**목록 \(r_1, r_2, r_3, \dots\)**이 존재한다.”

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

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

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

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

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

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

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

확인 12. 다음 문장을 완성해 보자:

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

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

답

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

놓인 무한 숫자표가 된다.

표기 — \(d_{nk}\)

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

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

같은 \(d_{nn}\)이다.

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

확인 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}\)일 때).

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

답

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

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

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

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

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

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

답

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

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

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

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

확인 15. 다음 문장을 완성해 보자:

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

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

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

답

첫째 빈칸: 유일. 둘째 빈칸: \(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단계 — 모순을 선언한다.

확인 16. 마지막 문장을 완성해 보자:

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

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

\(\underline{\quad}\)이다. \(\blacksquare\)”

답

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

(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\)) 다르다. 전혀 다른 표를 넣어도 모든 줄이 똑같이 작동한다.

확인 17. 이 증명이 처리하는 목록은 어느 쪽인가.

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

답

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

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

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

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

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

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

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

표기 — \(\mathbb{I}\)

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

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

\(\mathbb{Q} \cup \mathbb{I} = \mathbb{R}\)이다.

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

확인 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}\)

답

가정: \(\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\)거짓 표가 있다.

확인 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\)인가”를 묻는다.

답

존재. / 판정: “\(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\)

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

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

“\(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의 같은 뼈대#

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

확인 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)\)

답

(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이 된다.

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

백지 암기 대상

대각선 논법의 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\) 그래도 안 되면 풀이를 읽는다.

이번 주의 채점 기준

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

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

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

비가산”이 만점이다.

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

“임의의 목록”과 “\(b\)가 무대 안에 있다”.

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

기본 ●○○#

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

힌트

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

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

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

힌트

각 \(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\)

힌트

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

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

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

힌트

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

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

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

힌트

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

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

표기 유일)이 들어간다.

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

힌트

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

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

표준 ●●○#

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

힌트

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

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

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

힌트

원명제를 직접 치려 하면 “\(C\)의 목록이 없다”를 보여야 해서 다룰 대상이 없다.

대우로 뒤집으면 가정 자리에 “\(C\)의 목록”이라는 손에 잡히는 대상이 생긴다

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

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

힌트

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

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

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

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

힌트

훈련 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의 넣음/뺌 목록의 무한판이다)

힌트

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

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

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

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

힌트

빠뜨리기 쉬운 두 문장이 있다: “\(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})\) 비가산”의 두 증명(대각선 직접 / 칸토어 정리)을 비교하시오.

힌트

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

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

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

힌트

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

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

도전 ●●●#

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

“탈출자 \(b\)를 목록 맨 앞에 추가해 새 목록 \(b, r_1, r_2, \dots\)을 만들면 되지 않나? 그러면 \(b\)도 목록에 있으니 모순이 사라진다.”

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

힌트

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

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

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

“\(b\)는 소수 전개가 무한히 길어서 실수가 아니라 ‘완성되지 않은 과정’이다. 그러므로 증명이 무효다.”

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

이 문제가 빌려 쓰는 사실

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

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

힌트

무한 소수 \(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}\), 나머지는 그대로)이 전단사가 되는 이유를 점검하시오.

힌트

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

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

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

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

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

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

힌트

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

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

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

새 낱말 — 독립 (independence)

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

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

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

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

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

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

힌트

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

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{split} \begin{aligned}x_n = \begin{cases} 1 & (n \in X) \\ 0 & (n \notin X) \end{cases}\end{aligned} \end{split}\]

로 둔다. 각 \(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)로 다시 나온다.