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

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

예제 — 대등 증명을 함께 만들기#

완성된 증명을 먼저 보이지 않는다. 백지에서 시작해 한 줄씩 만들되, 각 단계에서 확인 상자의 빈칸을 연필로 먼저 채운 뒤 답을 연다.

예제 2.1 — 부분과 전체: \(|\mathbb{N}| = |E|\)#

명제. \(E = \{2, 4, 6, \dots\}\)에 대해 \(|\mathbb{N}| = |E|\)이다.

설계 — 쓰기 전에 정하는 두 가지. 가정이 주는 것(출발점)과 만들 것(도착점)을 정의 48.1로 번역해 먼저 적는다.

말

수식 번역

가정 (주어진 것)

두 집합 \(\mathbb{N}\), \(E\)가 무엇인지

\(E\)의 원소는 \(2k\) (\(k \in \mathbb{N}\)) 꼴 — 짝수의 정의

목표 (만들 것)

\(\vert \mathbb{N} \vert = \vert E \vert\)

\(\underline{\quad(?)\quad}\)를 하나 제시하고 검증한다

확인 8. 목표 칸의 빈칸을 채워 보자. 그리고 이 문제에서 가정이 주는 정보가

사실상 없는 이유를 한 문장으로 적어 보자.

답

목표: **전단사 \(f : \mathbb{N} \to E\)**를 하나 제시하고 단사와 전사를 각각 검증한다.

가정 쪽이 비어 있는 이유는 명제에 “~이면”이 없기 때문이다 — 조건 명제가 아니라

존재 주장이므로, 26주차의 서식대로 할 일은 증인의 제작과 검증뿐이다.

1단계 — 규칙을 정한다. 무엇을 무엇에 짝지을지 정한다. §1.2의 표에서 이미 후보가 나왔다: \(n\)에게 \(2n\)을 준다.

확인 9. 첫 문장을 완성해 보자:

“\(f : \mathbb{N} \to E\)를 \(f(n) = \underline{\quad}\)로 정의하자.”

이 규칙의 출력이 정말 \(E\) 안에 있는지도 한 줄로 확인해 보자.

답

\(f(n) = 2n\). 출력 확인: \(n \in \mathbb{N}\)이면 \(2n\)은 양의 짝수이므로 \(2n \in E\)이다.

이 확인이 빠지면 공역 밖으로 나가는 규칙이 되어(40주차) 아래의 검증이 무의미해진다.

2단계 — 단사를 검증한다. 41주차의 서식은 “\(f(a) = f(a')\)이라 하고 \(a = a'\)을 이끈다”이다.

확인 10. 둘째 문장을 완성해 보자:

“(단사) \(f(a) = f(a')\)이라 하자. 그러면 \(\underline{\quad} = \underline{\quad}\)이고,

양변을 2로 나누면 \(\underline{\quad}\)이다.”

답

\(2a = 2a'\)이고 양변을 2로 나누면 \(a = a'\)이다(근거 ③) — 같은 짝을 받았다면 애초에

같은 수였다는 뜻이고, §1.2의 조건 ①이다.

3단계 — 전사를 검증한다. 41주차의 서식은 “공역의 임의의 원소 \(m\)을 잡고 \(f(k) = m\)인 정의역 원소 \(k\)를 제작한다”이다.

확인 11. 셋째 문장을 완성해 보자:

“(전사) \(m \in E\)라 하자. \(m\)은 양의 짝수이므로 \(m = \underline{\quad}\)인

\(k \in \mathbb{N}\)가 존재하고, 이 \(k\)에 대해 \(f(k) = \underline{\quad}\)이다.”

여기서 \(k\)가 자연수임을 보장하는 것은 무엇인가.

답

\(m = 2k\)인 \(k \in \mathbb{N}\)가 존재하고 \(f(k) = 2k = m\)이다. \(k\)가 자연수인 것은 \(E\)의

원소가 “양의 짝수”이기 때문이다 — 짝수의 정의(근거 ①)가 정수성을, “양”이 \(k \ge 1\)을

준다. 증인 \(k\)를 제시하는 이 한 줄이 전사 증명의 전부다.

4단계 — 결론을 선언한다.

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

“따라서 \(f\)는 \(\underline{\quad}\)이고, 정의 48.1에 의해 \(\underline{\quad}\)이다. \(\blacksquare\)”

답

“따라서 \(f\)는 전단사이고, 정의 48.1에 의해 \(|\mathbb{N}| = |E|\)이다. \(\blacksquare\)” —

단사와 전사를 각각 확인한 뒤 그 존재를 정의에 넘겨 결론을 얻는다.

완성본. 방금 만든 문장을 이어 붙이면 아래 왼쪽 열이 된다. 손으로 베껴 쓰면서 각 줄 옆의 “왜?”에 스스로 답해 본다.

증명의 한 줄

왜 이 줄을 쓰는가?

\(f : \mathbb{N} \to E\)를 \(f(n) = 2n\)으로 정의하자. \(n \in \mathbb{N}\)이면 \(2n\)은 양의 짝수이므로 \(f\)의 값은 \(E\) 안에 있다.

대등 증명은 증인(전단사) 제작이다(26주차 존재 서식). 규칙을 세우고 공역 안에 머무는지부터 확인한다.

(단사) \(f(a) = f(a')\)이라 하자. 그러면 \(2a = 2a'\)이므로 \(a = a'\)이다.

41주차 단사 서식. 등식의 성질(근거 ③)만으로 닫힌다.

(전사) \(m \in E\)라 하자. \(m\)은 양의 짝수이므로 \(m = 2k\)인 \(k \in \mathbb{N}\)가 존재하고, \(f(k) = 2k = m\)이다.

41주차 전사 서식. 증인 \(k\)를 짝수의 정의(근거 ①)에서 꺼내 제시한다.

따라서 \(f\)는 전단사이고, 정의 48.1에 의해 \(\vert \mathbb{N} \vert = \vert E \vert\)이다. \(\blacksquare\)

정의 충족을 선언하며 마무리한다.

이 네 줄이 무한 개의 짝을 처리하는 이유. \(n\) 자리에 구체적인 수를 넣어 읽어 보자. \(n = 7\)이면 짝은 14이고 \(m = 138\)이면 증인은 \(k = 69\)다 — 어느 값을 넣어도 그대로 성립한다.

확인 13. 이 증명에서 \(n\)과 \(k\)에 대해 실제로 사용된 정보는 무엇인가.

(가) 구체적인 값 (나) “자연수이다”라는 자격뿐

답

(나). 어느 줄도 \(n\)이나 \(k\)가 특정 수라는 사실을 쓰지 않았고 쓴 것은 자격뿐이다.

그래서 네 줄짜리 증명 하나가 무한히 많은 짝을 한 번에 확정한다. 준비 운동 유형 1이

“절반”이라고 답할 때 빠져 있던 것이 이 짝짓기다 — 짝이 하나도 남지 않는다.

예제 2.2 — \(|\mathbb{N}| = |\mathbb{Z}|\)#

명제. \(|\mathbb{N}| = |\mathbb{Z}|\)이다.

이번에는 설계만 함께 하고 본문은 완성본으로 본다. 쓸 함수는 41주차 문제 16의 것이다.

\[\begin{split} \begin{aligned}f(n) = \begin{cases} \frac{n}{2} & (n \text{ 짝수}) \\ -\frac{n-1}{2} & (n \text{ 홀수}) \end{cases}\end{aligned} \end{split}\]

확인 14. 번역표를 채워 보자.

목표: \(|\mathbb{N}| = |\mathbb{Z}|\) \(\to\) \(\underline{\quad}\)를 제시하고 \(\underline{\quad}\)와 \(\underline{\quad}\)를 검증한다.

그리고 \(f(1), \dots, f(6)\)을 계산해 출력이 \(\mathbb{Z}\)를 훑는 순서를 확인해 보자.

답

전단사 \(f : \mathbb{N} \to \mathbb{Z}\)를 제시하고 단사와 전사를 검증한다.

\(f(1) = 0\), \(f(2) = 1\), \(f(3) = -1\), \(f(4) = 2\), \(f(5) = -2\), \(f(6) = 3\) — 출력이 \(0\)에서

양쪽으로 번갈아 퍼진다. 양방향으로 무한한 \(\mathbb{Z}\)를 한 방향으로 무한한 줄로

다시 세우는 것이 이 함수의 전부다.

확인 15. 단사 검증에서 첫 관문은 “\(f(a) = f(a')\)이면 \(a\)와 \(a'\)의 홀짝이 같다”이다.

이것을 무엇으로 보이는가.

답

부호로 보인다. \(n\)이 짝수면 \(f(n) = \frac n2 > 0\), 홀수면 \(f(n) = -\frac{n-1}{2} \le 0\)

이므로 두 값 범위가 겹치지 않는다. 따라서 \(f(a) = f(a')\)이면 홀짝이 같고, 홀짝이

같으면 같은 식을 쓰므로 그 뒤는 등식 계산이다.

완성본.

증명의 한 줄

왜 이 줄을 쓰는가?

\(f : \mathbb{N} \to \mathbb{Z}\)를 위 규칙으로 정의하자. 짝수 입력은 양의 정수를, 홀수 입력은 0 이하의 정수를 내놓으므로 값은 \(\mathbb{Z}\) 안에 있다.

규칙 제시와 공역 확인. 두 갈래 규칙이므로 각 갈래의 출력 범위를 따로 본다.

(단사) \(f(a) = f(a')\)이라 하자. 짝수 입력의 값은 양수, 홀수 입력의 값은 0 이하이므로 \(a\)와 \(a'\)은 홀짝이 같다.

케이스가 섞이는 것을 먼저 차단한다 — 부호가 그 차단벽이다.

둘 다 짝수면 \(\frac a2 = \frac{a'}2\)에서 \(a = a'\)이고, 둘 다 홀수면 \(-\frac{a-1}2 = -\frac{a'-1}2\)에서 \(a = a'\)이다.

같은 갈래 안에서는 등식 계산만 남는다(근거 ③).

(전사) \(m \in \mathbb{Z}\)라 하자. \(m > 0\)이면 \(k = 2m\)이 짝수이고 \(f(k) = m\)이다. \(m \le 0\)이면 \(k = 1 - 2m\)이 홀수이고 \(f(k) = -\frac{(1-2m)-1}{2} = m\)이다.

증인 제작. 목표값의 부호에 따라 어느 갈래에서 증인을 꺼낼지가 정해진다.

따라서 \(f\)는 전단사이고 \(\vert \mathbb{N} \vert = \vert \mathbb{Z} \vert\)이다. \(\blacksquare\)

정의 48.1 충족 선언.

목록으로 적으면 \(0, 1, -1, 2, -2, 3, -3, \dots\)이고, 이 목록이 문제 6과 15의 재료가 된다.

예제 2.3 — 격자 행진: \(\mathbb{Q}^+\)는 가산 무한#

명제. 양의 유리수 전체 \(\mathbb{Q}^+\)는 가산 무한이다.

이번에는 설계부터 스스로 해 보자. \(\mathbb{Q}^+\)에는 \(f(n) = 2n\) 같은 간단한 수식이 보이지 않으므로 §1.5의 목록 판정표를 쓴다.

확인 16. 목록으로 증명하려 한다. 무엇을 만들고 무엇을 확인해야 하는가.

§1.5의 표를 보고 세 줄로 적어 보자.

답

만들 것: \(\mathbb{Q}^+\)의 원소를 한 줄로 늘어놓는 순서. 확인할 것: ① 모든 양의

유리수가 등장한다(빠짐 없음) ② 같은 유리수가 두 번 등장하지 않는다(겹침 없음)

③ 각 원소의 등장 순번이 유한하다.

행진의 설계. \((p, q)\) 칸에 분수 \(\frac pq\)를 적은 격자를 생각한다 (\(p, q \in \mathbb{N}\)). 모든 양의 유리수는 기약분수 꼴로 이 격자 어딘가에 등장한다. 이 격자를 한 줄로 훑어야 하는데, 가로줄을 하나씩 훑는 방식은 첫 줄이 끝나지 않아 둘째 줄에 도달하지 못한다. \(p + q\)가 일정한 대각선은 유한하므로 대각선을 \(p+q = 2, 3, 4, \dots\) 순으로 훑는다.

\(p+q\)

그 대각선의 칸

적힌 분수

2

\((1,1)\)

\(\frac11\)

3

\((1,2), (2,1)\)

\(\frac12, \frac21\)

4

\((1,3), (2,2), (3,1)\)

\(\frac13, \frac22, \frac31\)

5

\((1,4), (2,3), (3,2), (4,1)\)

\(\frac14, \frac23, \frac32, \frac41\)

확인 17. 위 순서를 그대로 목록으로 삼으면 세 조건 중 어느 것이 깨지는가.

구체적인 예를 하나 들어 보자.

답

② 겹침 없음이 깨진다. \(\frac22\)는 \(\frac11\)과 같은 유리수인데 두 번째로 다시 등장한다.

유리수는 분수들의 동치류이고(37주차 예제 2.3), 격자는 그 동치류의 대표를 여러 번

적어 두었기 때문이다. 처방은 하나 — 이미 목록에 나온 값이면 건너뛴다.

논증. 격자의 \((p, q)\) 칸에 \(\frac pq\)를 적고, 대각선을 \(p+q = 2, 3, 4, \dots\) 순으로 행진하며 각 대각선 안에서는 \(p\)가 작은 칸부터 방문하되 이미 목록에 나온 값은 건너뛴다. 이렇게 만든 목록을 \(r_1, r_2, r_3, \dots\)이라 하자. 빠짐이 없다: 임의의 양의 유리수는 어떤 칸 \((p,q)\)에 적혀 있고 그 칸은 \(p+q\)번째 대각선에 있으므로 유한 단계 안에 방문된다. 겹침이 없다: 같은 값이 다시 나오면 건너뛰기 규칙이 배제한다. 순번이 유한하다: 각 대각선의 칸 수가 유한하므로 \((p,q)\) 이전에 방문되는 칸의 총수도 유한하다. 따라서 \(n \mapsto r_n\)은 \(\mathbb{N}\)에서 \(\mathbb{Q}^+\)로의 전단사이고 \(\mathbb{Q}^+\)는 가산 무한이다. \(\blacksquare\)

이번 논증은 표 없이 산문으로 적었다. 표는 연습 단계의 장치이고, 실전의 증명은 이런 산문이다.

유리수는 수직선에 조밀하게 깔려 있는데도(15주차 문제 17) \(\mathbb{N}\)과 대등하다. 조밀함과 크기는 서로 다른 개념이고, 이 사실은 다음 주에 “빽빽하니까 목록이 불가능하다”는 논증을 반박하는 데 그대로 쓰인다.

음수와 0까지 포함한 \(\mathbb{Q}\) 전체는 이 목록 \(r_1, r_2, \dots\)을 재료로 문제 15에서 완성한다.

관찰 — 세 증명의 같은 뼈대#

예제 2.1, 2.2, 2.3은 소재가 다르지만 뼈대가 같다. 대응표의 빈칸을 채워 보자.

확인 18. 각 예제에서 다음 세 단계에 해당하는 부분을 찾아 보자.

① 규칙 제시: 예제 2.1은 \(f(n) = 2n\), 예제 2.3은 \(\underline{\qquad}\)

② 겹침 없음: 예제 2.1은 단사 검증, 예제 2.3은 \(\underline{\qquad}\)

③ 빠짐 없음: 예제 2.1은 전사 검증, 예제 2.3은 \(\underline{\qquad}\)

답

① 대각선을 \(p+q\) 순으로 행진하며 이미 나온 값은 건너뛰는 순서 ② 건너뛰기 규칙

③ 임의의 칸이 유한 단계 안에 방문된다는 확인.

예제 2.2도 같다 — ① 두 갈래 규칙 ② 부호로 케이스를 가른 뒤의 등식 계산

③ 부호별 증인 제작. 세 증명 모두 정확히 이 세 걸음이다.

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

백지 암기 대상

대등 증명의 3단계 틀

① 짝짓기 규칙(함수 또는 목록의 순서)을 제시하고 값이 공역 안에 있는지 확인한다 \(\to\) ② 겹침 없음(단사)을 검증한다 \(\to\) ③ 빠짐 없음(전사)을 검증하고 정의 48.1로 결론을 선언한다

이 틀은 다음 주에 “이 틀을 만족하는 목록이 존재할 수 없는 집합”을 만날 때 기준선이 된다.

빈칸 사다리 — 지지대를 하나씩 빼며#

필사에서 자립으로 넘어가는 다리다. 훈련이 진행될수록 빈칸이 커진다. 베끼지 말고 빈칸만 스스로 채운다. 답은 해설(§6)에 있다 — 다 채운 뒤에 대조한다.

훈련 1 ●○○ — 수식 빈칸#

명제. \(O = \{1, 3, 5, \dots\}\)(양의 홀수 전체)에 대해 \(|\mathbb{N}| = |O|\)이다.

증명. \(f : \mathbb{N} \to O\)를 \(f(n) = \underline{\quad(1)\quad}\)로 정의하자. \(n \ge 1\)이므로 \(f(n) \ge 1\)이고 \(f(n)\)은 홀수이므로 값은 \(O\) 안에 있다. (단사) \(f(a) = f(a')\)이면 \(2a - 1 = 2a' - 1\)이고, 양변에 1을 더한 뒤 2로 나누면 \(\underline{\quad(2)\quad}\)이다. (전사) \(m \in O\)라 하자. \(m\)은 양의 홀수이므로 \(m = 2k - 1\)인 \(k \in \mathbb{N}\)가 존재하고(\(k = \frac{m+1}{2}\)), \(f(k) = \underline{\quad(3)\quad}\)이다. 따라서 \(f\)는 전단사이고 \(|\mathbb{N}| = |O|\)이다. \(\blacksquare\)

훈련 2 ●●○ — 수식과 근거를 함께#

이번에는 구조 낱말과 근거 문장도 빈칸이다.

명제. \(M = \{0, -1, -2, -3, \dots\}\)에 대해 \(|\mathbb{N}| = |M|\)이다.

증명. \(f : \mathbb{N} \to M\)을 \(f(n) = \underline{\quad(1)\quad}\)로 정의하자. \(n \ge 1\)이므로 \(f(n) \le 0\)이고, 따라서 값은 \(M\) 안에 있다. (단사) \(f(a) = f(a')\)이라 하자. 그러면 \(\underline{\quad(2)\quad}\)이고, \(\underline{\quad(3)\quad}\)에 의해 \(a = a'\)이다. (전사) \(m \in M\)이라 하자. \(k = \underline{\quad(4)\quad}\)로 두면 \(m \le 0\)이므로 \(k \ge 1\), 곧 \(k \in \mathbb{N}\)이고 \(f(k) = \underline{\quad(5)\quad}\)이다. 따라서 \(f\)는 \(\underline{\quad(6)\quad}\)이고, \(\underline{\quad(7)\quad}\)에 의해 \(|\mathbb{N}| = |M|\)이다. \(\blacksquare\)

훈련 3 ●●● — 뼈대만 남기고#

이번에는 3단계 틀의 각 칸을 통째로 채운다.

명제. \(|E| = |O|\)이다 (\(E\)는 양의 짝수 전체, \(O\)는 양의 홀수 전체).

증명의 뼈대.

  • ① 규칙 제시와 공역 확인: \(\underline{\quad(1)\quad}\)

  • ② 겹침 없음(단사): \(\underline{\quad(2)\quad}\)

  • ③ 빠짐 없음(전사)과 결론: \(\underline{\quad(3)\quad}\)

(직접 전단사를 만드는 길과 예제 2.1\(\cdot\)훈련 1을 추이성으로 잇는 길이 모두 있다. 이 훈련이 문제 8(이미 놓인 두 다리를 추이성으로 잇기)의 예행연습이다.)

연습문제 (20문항)#

해설을 보기 전에 문제당 최소 10분 스스로 시도한다. 막히면 곧바로 풀이를 읽지 말고 해설의 ‘접근’까지만 읽고 다시 시도한다 \(\to\) 그래도 안 되면 풀이를 읽는다. 증명 문제는 3단계 틀(§2 관찰)의 세 칸을 먼저 적고 시작한다.

이번 주의 채점 기준

답이 아니라 근거가 점수다. “\(|\mathbb{N}| = |E|\)이다(맞음)”는 0점이고,

“\(f(n) = 2n\)이 전단사이므로 정의 48.1에 의해 대등하다 — 단사는 …, 전사는 …”이 만점이다.

목록으로 논증할 때는 빠짐 없음과 겹침 없음을 각각 한 줄로 적는다.

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

기본 ●○○#

1. [백지] 대등(\(|A| = |B|\))과 가산의 정의를 쓰고, “가산 무한 = 목록화 가능”의 뜻을 한 문장으로 덧붙이시오.

힌트

정의 두 개를 조각까지 그대로 쓴다 — “전단사가 존재한다”, “유한이거나 가산 무한”.

마지막 문장은 §1.5 판정표의 세 줄을 압축한 것이다.

2. \(|\{1, 2, 3\}| = |\{a, b, c\}|\)를 정의대로 증명하시오 (전단사 하나 제시 + 검증 — 유한도 같은 서식).

힌트

유한집합이라고 서식이 달라지지 않는다. 짝짓기를 순서쌍 목록으로 적은 뒤 함수 조건\(\cdot\)단사\(\cdot\)전사를 한 줄씩 확인한다.

3. 빈칸 훈련(\(|\mathbb{N}| = |O|\))을 백지에서 완성하시오.

힌트

규칙은 \(2n - 1\)이다. 전사 검증에서 증인 \(k = \frac{m+1}{2}\)가 자연수인 이유를 한 줄로

적는다 — \(m\)이 홀수라는 가정이 거기서 일한다.

4. 예제 2.1(\(|\mathbb{N}| = |E|\))을 백지에 재현하시오.

힌트

네 줄이다 — 규칙 제시와 공역 확인 / 단사 / 전사 / 결론. 전사 줄에서 증인 \(k\)가

어디서 나오는지(짝수의 정의)를 빼먹지 않는다.

5. \(|\mathbb{N}| = |\{5, 6, 7, 8, \dots\}|\)임을 증명하시오 (\(f(n) = n + 4\)).

힌트

전사 검증에서 \(m \ge 5\)라는 조건이 증인 \(m - 4\)를 자연수로 만든다. 그 한 줄이 핵심이다.

6. 예제 2.2(\(|\mathbb{N}| = |\mathbb{Z}|\))의 목록 첫 10항을 쓰고, \(f(11), f(12)\)를 계산하시오.

힌트

홀수 입력과 짝수 입력에 서로 다른 식을 쓴다(11은 홀수, 12는 짝수). 계산한 뒤에는

목록의 11번째\(\cdot\)12번째 자리와 일치하는지 대조한다.

표준 ●●○#

7. 대등이 동치관계처럼 행동함을 정리하시오: 반사\(\cdot\)대칭\(\cdot\)추이 각각의 증인(항등\(\cdot\)역함수\(\cdot\)합성)과 근거 주차를 명시하며 증명하시오.

8. \(|\mathbb{Z}| = |E|\)임을 두 가지 방법으로 논하시오: (a) 직접 전단사 구성 없이 — 추이성(문제 7)으로 \(|\mathbb{Z}| = |\mathbb{N}| = |E|\) 연결 (b) 42주차 문제 15의 합성 릴레이 인용.

힌트

(a)는 예제 2.2에 대칭성을 먼저 적용해 방향을 \(\mathbb{Z} \to \mathbb{N}\)으로 돌리는 것이 첫

걸음이다. (b)는 그 두 다리를 실제로 합성해 하나의 명시적 함수를 적는다.

새 무대 — 실수 구간

문제 9와 10은 정의역과 공역이 \(\mathbb{N}\)이나 \(\mathbb{Z}\)가 아니라 실수 구간이다.

서식은 바뀌지 않는다 — 단사는 여전히 “\(f(a) = f(a')\)에서 \(a = a'\)”, 전사는 여전히

“증인 제작”이고, 달라지는 것은 검증의 재료가 등식 계산에서 부등식 계산으로

바뀐다는 점뿐이다. 증인을 만든 뒤 그것이 정의역 구간 안에 있는지 부등식으로

확인하는 줄이 하나 더 붙는다.

9. \((0, 1)\)과 \((0, 2)\)가 대등함을 증명하시오 (\(f(x) = 2x\) — 단사\(\cdot\)전사 검증. 길이가 두 배인 구간과 크기가 같다).

10. \((0, 1)\)과 \((3, 7)\)이 대등함을 증명하시오 (일차함수 \(f(x) = 4x + 3\) 설계 — 치역 확인 포함).

힌트

계수 4와 상수 3의 출처를 먼저 확인한다 — 폭이 1에서 4로 늘어나므로 4배, 시작점이

0에서 3으로 옮겨 가므로 \(+3\)이다. 전사 증인은 이 식을 \(x\)에 대해 푼 것이다.

11. 예제 2.3의 격자 행진에서 처음 10개의 목록 항(건너뛰기 반영)을 나열하시오.

힌트

대각선을 \(p+q = 2, 3, 4, 5, 6\)까지 차례로 적은 뒤 이미 나온 값과 같은 것을 지운다.

\(\frac22\)가 첫 번째 건너뛰기다.

12. (힐베르트 호텔 1) 만실인 무한 호텔(\(n\)호실 손님 \(n\))에 새 손님 1명이 왔다. 전원 이동 규칙과, 그 규칙이 “모두 방을 가지고, 한 방에 한 명”임을 — 즉 \(\mathbb{N} \to \{2, 3, 4, \dots\}\) 전단사임을 — 증명하시오.

힌트

“한 방에 한 명”이 단사, “모두 방을 가진다”가 전사로 번역된다. 규칙을 정한 뒤에는 문제 5와 같은 계산이다.

13. (힐베르트 호텔 2) 이번엔 무한 버스(손님이 \(\mathbb{N}\)만큼)가 도착했다. 기존 손님과 새 손님 전원을 수용하는 규칙(기존 \(\to\) 짝수 방, 새 손님 \(\to\) 홀수 방)을 설계하고 정당화하시오.

힌트

두 규칙은 이미 증명한 것들이다 — 예제 2.1과 훈련 1. 남은 일은 짝수 방과 홀수 방이

서로소이고 합치면 전체라는 확인이다(17주차의 분할).

14. 두 가산 무한 집합 \(A = \{a_1, a_2, \dots\}\), \(B = \{b_1, b_2, \dots\}\)가 서로소이면 \(A \cup B\)도 가산 무한임을 교대 목록(\(a_1, b_1, a_2, b_2, \dots\))으로 논증하시오.

힌트

교대 목록에 번호를 붙여 식으로 적는다: \(c_{2k-1} = a_k\), \(c_{2k} = b_k\). 그 다음은

§1.5 판정표의 세 줄을 각각 확인한다 — “서로소”가 어느 줄에서 일하는지 지목한다.

도전 ●●●#

15. \(\mathbb{Q}\) 전체(음수\(\cdot\)0 포함)가 가산임을 논증하시오. (예제 2.3의 \(\mathbb{Q}^+\) 목록 \(r_1, r_2, \dots\)과 지그재그 결합: \(0, r_1, -r_1, r_2, -r_2, \dots\) — 빠짐\(\cdot\)겹침 점검)

힌트

새 목록의 항에 번호를 붙인다: 1번은 0, \(2k\)번은 \(r_k\), \(2k+1\)번은 \(-r_k\). 임의의

유리수가 0\(\cdot\)양수\(\cdot\)음수 중 정확히 하나라는 것이 빠짐\(\cdot\)겹침 확인의 뼈대다.

16. \(|\mathbb{N} \times \mathbb{N}| = |\mathbb{N}|\)임을 격자 행진으로 논증하시오 (이번엔 건너뛰기가 필요 없다 — 왜 \(\mathbb{Q}^+\) 때와 다른지 한 문장 포함).

힌트

격자의 칸에 무엇이 적혀 있는지를 비교한다. 예제 2.3에서는 서로 다른 칸에 같은 값이

올 수 있었지만, 이번에는 칸 자체가 원소다.

17. \((-1, 1)\)과 \(\mathbb{R}\)가 대등함을 다음 함수로 논하시오: \(f(x) = \dfrac{x}{1 - |x|}\). (a) \(f(0), f(\frac12), f(-\frac12), f(0.9)\)를 계산해 감을 잡고, (b) \(g(y) = \dfrac{y}{1 + |y|}\)가 역함수 후보임을 \(g(f(x)) = x\) 계산(케이스: \(x \ge 0\))으로 확인하시오 — 유한한 구간과 실수 전체가 같은 크기.

힌트

(b)에서 \(|f(x)|\)를 없애는 것이 첫 관문이다. \(x \ge 0\)이면 \(1 - x > 0\)이므로 \(f(x) \ge 0\),

따라서 \(|f(x)| = f(x)\)다. 그 다음은 분모를 통분해 정리하는 계산뿐이다.

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

“짝수 집합 \(E\)는 \(\mathbb{N}\)의 진부분집합이므로 \(|E| < |\mathbb{N}|\)이다 — 부분은 전체보다 작기 때문이다.”

(유한 직관의 어느 정리(41주차 문제 17)가 무한에서 무너졌는가? 예제 2.1과 대조하라.)

이 문제가 빌려 쓰는 사실 — 무한 번의 선택

문제 19의 논증은 “원소를 하나 뽑고, 또 하나 뽑고, …”를 무한히 반복한다.

이 반복을 한꺼번에 정당화하려면 선택공리라는 별도의 공리가 필요하다.

이 과정에서는 그 공리를 증명 없이 인정하고 쓴다 — 엄밀한 정당화는 대학

집합론으로 이월한다. 문제에서 요구하는 것은 “왜 멈추지 않는가”와

“왜 얻어진 집합이 가산 무한인가” 두 가지의 논증이다.

19. “무한집합은 반드시 가산 무한 부분집합을 가진다”를 다음 스케치로 논증하시오: 무한집합 \(A\)에서 원소 \(a_1\)을 뽑고, 남은 것(여전히 무한 — 왜?)에서 \(a_2\)를 뽑고, … 이 과정이 멈추지 않는 이유와, 얻어진 \(\{a_1, a_2, \dots\}\)가 가산 무한인 이유를 쓰시오. (엄밀화에는 선택공리가 필요 — “고르기를 무한 번”의 정당화는 대학 집합론으로 이월한다는 논평 포함)

힌트

“멈추지 않는다”를 직접 보이려 하면 막힌다. 뒤집는다 — 어느 단계에서 멈춘다면 남은

집합이 공집합이고 그러면 \(A\)가 유한하므로(정의 48.3) 가정에 어긋난다.

20. (서술) (a) “센다 = 짝짓는다”가 유한 세기의 본질이며 무한으로 일반화되는 유일한 길인 이유를 세 문장 이내로. (b) 유한 직관과 어긋나는 이번 주의 두 결과(부분=전체, 조밀한 \(\mathbb{Q}\)가 가산)를 보고도 “그럼 모든 무한은 가산”이라고 결론지으면 안 되는 이유 — 29주차의 언어로 — 를 한 문장으로 (다음 주 예고).

백지 재현 — 복습 프로토콜#

권장 일정 — 1~3일차: §0~§4 학습과 연습문제 / 4일차: 1차 재현 / 5일차: 완전 백지 재현. 한 번에 완전 백지로 가지 않는다.

1차 시도 (4일차) — 틀 카드 허용. 3단계 틀(§2 관찰)\(\cdot\)근거 목록(§1.7)\(\cdot\)목록 판정표(§1.5)만 펴 놓고 예제 2.1과 2.2를 끝까지 적는다. 정의와 본문은 보지 않는다.

2차 시도 (5일차) — 완전 백지. 아무것도 보지 않고 수행한다:

  • 정의 48.1과 48.2를 조각 그대로 썼다 (“전단사가 존재한다”, “유한이거나 가산 무한”).

  • \(|\mathbb{N}| = |E|\)와 \(|\mathbb{N}| = |\mathbb{Z}|\)를 전단사 서식으로 재현했다.

  • 격자 행진의 순서와 건너뛰기 규칙을 그림으로 그리고, 왜 건너뛰기가 필요한지 말했다.

  • 힐베르트 호텔 두 경우(+1명, +무한 버스)의 이동 규칙을 함수로 적었다.

  • 대등의 반사\(\cdot\)대칭\(\cdot\)추이가 각각 어느 주차의 부품을 쓰는지 말했다.

  • \(\mathbb{Q}\)가 조밀한데도 가산이라는 사실이 왜 모순이 아닌지 한 문장으로 답했다.

막힌 지점별 처방. 막힌 지점이 무엇을 다시 볼지 알려 준다.

막힌 지점

처방

무엇을 만들어야 하는지 모르겠다

예제 2.1의 설계 — 목표를 “전단사 하나 제시”로 번역한다

함수는 적었는데 다음이 나오지 않는다

§2 관찰의 3단계 틀 — ② 겹침 없음 ③ 빠짐 없음의 순서

전사 검증에서 증인이 안 나온다

예제 2.1의 3단계 — 목표값 \(m\)을 정의로 풀어 증인을 꺼낸다

목록 논증을 어디까지 써야 할지 모르겠다

§1.5의 판정표 — 세 줄을 각각 한 문장씩 쓴다

케이스가 섞여 단사 증명이 막힌다

예제 2.2의 둘째 줄 — 부호로 케이스를 먼저 가른다

진부분집합인데 대등하다는 것이 받아들여지지 않는다

§1.6과 확인 6 — 유한에서만 참인 문장을 지목한다

하나라도 실패하면 그 항목만 다시 필사하고 다음날 재시도한다.

해설#

각 해설은 접근(문제 앞에서 무엇을 생각하는가)과 풀이로 나뉜다. 막혔을 때는 접근까지만 읽고 연필을 다시 잡는다.

빈칸 사다리 — 훈련 1#

(1) \(2n - 1\) (2) \(a = a'\) (3) \(2k - 1 = m\)

※ (3)에서 증인 \(k\)가 자연수임을 보장하는 것은 \(m\)이 양의 홀수라는 조건이다 — \(m = 2k-1 \ge 1\)에서 \(k \ge 1\)이 나오고, 이 확인이 빠지면 전사 증명이 닫히지 않는다.

빈칸 사다리 — 훈련 2#

(1) \(1 - n\) (2) \(1 - a = 1 - a'\) (3) 등식의 성질 (근거 ③ — 양변에서 1을 빼고 부호를 바꾼다) (4) \(1 - m\) (5) \(1 - (1 - m) = m\) (6) 전단사 (7) 정의 48.1

※ 규칙 \(f(n) = 1-n\)은 \(1 \mapsto 0\), \(2 \mapsto -1\), \(3 \mapsto -2\)로 간다. 증인이 \(k = 1-m\)인 이유는 \(m = 1-k\)를 \(k\)에 대해 푼 것이기 때문이다 — 전사 증인은 목표 등식을 정의역 문자에 대해 푼 결과라는 규칙이 여기서도 작동한다.

빈칸 사다리 — 훈련 3#

(1) \(f : E \to O\)를 \(f(m) = m - 1\)로 정의하자. \(m\)이 양의 짝수이면 \(m \ge 2\)이므로 \(m - 1 \ge 1\)이고 \(m-1\)은 홀수이므로 값은 \(O\) 안에 있다. (2) \(f(a) = f(a')\)이라 하자. 그러면 \(a - 1 = a' - 1\)이고 양변에 1을 더하면 \(a = a'\)이다(근거 ③). (3) \(t \in O\)라 하자. \(k = t+1\)로 두면 \(k\)는 2 이상의 짝수, 곧 \(k \in E\)이고 \(f(k) = t\)이다. 따라서 \(f\)는 전단사이고 정의 48.1에 의해 \(|E| = |O|\)이다. \(\blacksquare\)

※ 다른 길: 예제 2.1과 훈련 1에 대칭성\(\cdot\)추이성(문제 7)을 이어 \(|E| = |\mathbb{N}| = |O|\)로 끝내도 된다. 직접 구성은 명시적 함수를 얻고, 추이 논법은 줄 수가 적다.

문제 1#

접근. 이번 주의 [백지 암기 대상]은 정의 두 개다. 통째로 외우기보다 §1.3의 조각별 역할과 함께 재구성한다.

풀이. 대등: 집합 \(A\), \(B\)에 대해 전단사 \(f : A \to B\)가 존재하면 \(A\)와 \(B\)는 대등하다고 하고 \(|A| = |B|\)로 쓴다. 가산: \(|A| = |\mathbb{N}|\)인 집합을 가산 무한이라 하고, 유한집합이거나 가산 무한인 집합을 가산이라 한다(가산이 아니면 비가산). 목록화의 뜻: 전단사 \(f : \mathbb{N} \to A\)가 있다는 것은 \(f(1), f(2), f(3), \dots\)이 \(A\)의 원소를 빠짐없이(전사) 겹침 없이(단사) 훑고 모든 원소가 유한한 자리에 등장한다는 뜻이다.

복기. 자가 채점의 기준은 조각이다 — “존재한다”를 빠뜨리면 무엇을 제작해야 하는지가 사라지고, “유한집합이거나”를 빠뜨리면 유한집합이 가산에서 빠져 다음 주 정의 49.1(비가산)이 유한집합까지 비가산으로 분류하게 된다.

문제 2#

접근. 유한집합이라고 서식이 달라지지 않는다. 새 정의가 옛 세기와 같은 답을 주는지 확인하는 문제이기도 하다.

풀이. \(f : \{1,2,3\} \to \{a,b,c\}\)를 \(f = \{(1,a), (2,b), (3,c)\}\)로 정의하자. 함수 조건: 정의역의 세 원소 각각에 값이 정확히 하나씩 배정되어 있다. 단사: 세 출력 \(a, b, c\)가 서로 다르므로 \(f(x) = f(y)\)인 서로 다른 \(x, y\)가 없다. 전사: 공역의 원소 \(a, b, c\) 각각에 원상 \(1, 2, 3\)이 존재한다. 따라서 \(f\)는 전단사이고, 정의 48.1에 의해 \(|\{1,2,3\}| = |\{a,b,c\}|\)이다. \(\blacksquare\)

복기. 정의를 넓힐 때 옛 영역에서 결론이 바뀌지 않는지 검사하는 것이 표준 절차이고, 이 검사가 통과하지 못하면 §1.3의 삭제 실험처럼 정의를 고쳐야 한다.

문제 3#

접근. 3단계 틀 그대로다. 규칙은 \(2n-1\)이고, 어려운 곳은 전사의 증인이 자연수임을 보이는 한 줄이다.

풀이. \(f : \mathbb{N} \to O\)를 \(f(n) = 2n - 1\)로 정의하자. \(n \ge 1\)이므로 \(f(n) = 2n - 1 \ge 1\)이고 \(2n-1\)은 홀수이므로 값은 \(O\) 안에 있다. (단사) \(f(a) = f(a')\)이라 하자. \(2a - 1 = 2a' - 1\)이므로 양변에 1을 더하면 \(2a = 2a'\), 2로 나누면 \(a = a'\)이다. (전사) \(m \in O\)라 하자. \(m\)은 양의 홀수이므로 \(m = 2k - 1\)인 정수 \(k\)가 존재하고, \(m \ge 1\)에서 \(k = \frac{m+1}{2} \ge 1\)이므로 \(k \in \mathbb{N}\)이다. 이 \(k\)에 대해 \(f(k) = 2k - 1 = m\)이다. 따라서 \(f\)는 전단사이고 \(|\mathbb{N}| = |O|\)이다. \(\blacksquare\)

검산. \(f(1) = 1\), \(f(2) = 3\), \(f(3) = 5\) — 목록 \(1, 3, 5, \dots\)가 \(O\)를 순서대로 훑는다.

문제 4#

접근. 예제 2.1의 네 줄을 재현한다. 채점 항목은 규칙 제시\(\cdot\)공역 확인\(\cdot\)단사\(\cdot\)전사이고, 전사에서 증인 \(k\)의 출처(짝수의 정의)를 적었는지가 갈림길이다.

풀이. \(f : \mathbb{N} \to E\)를 \(f(n) = 2n\)으로 정의하자. \(n \in \mathbb{N}\)이면 \(2n\)은 양의 짝수이므로 \(f(n) \in E\)이다. (단사) \(f(a) = f(a')\)이라 하자. \(2a = 2a'\)이므로 양변을 2로 나누면 \(a = a'\)이다. (전사) \(m \in E\)라 하자. \(m\)은 양의 짝수이므로 짝수의 정의에 의해 \(m = 2k\)인 정수 \(k\)가 존재하고, \(m \ge 2\)에서 \(k \ge 1\)이므로 \(k \in \mathbb{N}\)이다. 이 \(k\)에 대해 \(f(k) = 2k = m\)이다. 따라서 \(f\)는 전단사이고, 정의 48.1에 의해 \(|\mathbb{N}| = |E|\)이다. \(\blacksquare\)

복기. \(E\)가 \(\mathbb{N}\)의 진부분집합이라는 사실은 이 증명의 어느 줄에도 쓰이지 않았다 — 정의 48.1이 포함 관계를 묻지 않기 때문이고, 문제 18의 결함이 이 지점의 오해다.

문제 5#

접근. 규칙이 주어져 있으므로 할 일은 검증뿐이다. 전사에서 \(m \ge 5\)가 증인 \(m-4\)를 자연수로 만든다.

풀이. \(f : \mathbb{N} \to \{5,6,7,\dots\}\)를 \(f(n) = n + 4\)로 정의하자. \(n \ge 1\)이면 \(n + 4 \ge 5\)이므로 값은 공역 안에 있다. (단사) \(f(a) = f(a')\)이라 하자. \(a + 4 = a' + 4\)이므로 양변에서 4를 빼면 \(a = a'\)이다. (전사) \(m \in \{5,6,7,\dots\}\)이라 하자. \(k = m - 4\)로 두면 \(m \ge 5\)이므로 \(k \ge 1\), 곧 \(k \in \mathbb{N}\)이고 \(f(k) = (m-4) + 4 = m\)이다. 따라서 \(f\)는 전단사이고 \(|\mathbb{N}| = |\{5,6,7,\dots\}|\)이다. \(\blacksquare\)

복기. 이 함수는 문제 12의 이동 규칙 \(n \mapsto n+1\)을 네 칸으로 늘린 것이다. “밀기”는 단사이면서 전사가 아닌 표준 예이며, 공역을 밀린 자리에 맞춰 자르면 전단사가 된다.

문제 6#

접근. 목록은 \(f(1)\)부터 차례로 쓰면 나온다. 개별 값은 입력의 홀짝을 먼저 판정한 뒤 해당하는 식에 대입한다 — 갈래를 잘못 고르는 것이 가장 흔한 오류다.

풀이. \(f(1) = -\frac{1-1}{2} = 0\), \(f(2) = \frac22 = 1\), \(f(3) = -\frac{3-1}{2} = -1\), \(f(4) = 2\), \(f(5) = -2\), \(f(6) = 3\), \(f(7) = -3\), \(f(8) = 4\), \(f(9) = -4\), \(f(10) = 5\). 따라서 첫 10항은

\[ 0,\ 1,\ -1,\ 2,\ -2,\ 3,\ -3,\ 4,\ -4,\ 5 \]

이다. 11은 홀수이므로 \(f(11) = -\frac{11-1}{2} = -5\), 12는 짝수이므로 \(f(12) = \frac{12}{2} = 6\)이다.

검산. 홀수 번째 자리에는 0 이하가, 짝수 번째 자리에는 양수가 와야 한다. 11번째가 \(-5\), 12번째가 \(6\)으로 그 규칙에 맞는다.

문제 7#

접근. 세 성질에 세 부품이 대응한다. 성질마다 “받는 전단사”와 “제시할 전단사”를 구분해 적으면 두 줄씩으로 끝난다.

풀이. (반사) 항등함수 \(\mathrm{id}_A(x) = x\)는 전단사다(단사: \(x = x'\)이면 그대로 \(x = x'\). 전사: 임의의 \(y \in A\)의 원상은 \(y\) 자신). 따라서 정의 48.1에 의해 \(|A| = |A|\)이다. (대칭) \(|A| = |B|\)라 하자. 전단사 \(f : A \to B\)가 존재하고, 43주차 핵심 정리에 의해 역함수 \(f^{-1} : B \to A\)가 존재한다. 43주차 문제 14에 의해 \((f^{-1})^{-1} = f\)이므로 \(f^{-1}\)의 역관계는 함수이고, 핵심 정리를 이번에는 \(f^{-1}\)에 적용하면 \(f^{-1}\)도 전단사다. 따라서 \(|B| = |A|\)이다. (추이) \(|A| = |B|\)이고 \(|B| = |C|\)라 하자. 전단사 \(f : A \to B\)와 \(g : B \to C\)가 존재하고, 42주차 문제 15에 의해 \(g \circ f : A \to C\)는 전단사다. 따라서 \(|A| = |C|\)이다. \(\blacksquare\)

복기. 세 증명 모두 “가정의 존재 주장에서 함수를 받아, 목표에 맞는 함수를 만들어 제시한다”는 같은 구조이며, 새로 계산한 것은 한 줄도 없고 9부의 결과들(43주차 핵심 정리와 문제 14, 42주차 문제 15)을 인용했을 뿐이다. 다만 이 세 성질을 “동치관계”라 부르지 않는 이유는 §1.4에 적었다.

문제 8#

접근. 이미 놓인 다리 두 개를 잇는다. (a)는 추이성을 쓰고, (b)는 그 증명 안의 합성을 실제로 적어 명시적 함수를 얻는다.

풀이. (a) 예제 2.2에서 \(|\mathbb{N}| = |\mathbb{Z}|\)이고 문제 7의 대칭성에 의해 \(|\mathbb{Z}| = |\mathbb{N}|\)이다. 예제 2.1에서 \(|\mathbb{N}| = |E|\)이므로, 문제 7의 추이성을 두 등식에 적용하면 \(|\mathbb{Z}| = |E|\)를 얻는다. \(\blacksquare\) (b) 명시적 함수를 만든다. 예제 2.2의 지그재그 \(f : \mathbb{N} \to \mathbb{Z}\)는 전단사이고 43주차 핵심 정리에 의해 \(f^{-1} : \mathbb{Z} \to \mathbb{N}\)이 존재하며 문제 7의 대칭 증명대로 \(f^{-1}\)도 전단사다. 예제 2.1의 \(h : \mathbb{N} \to E\), \(h(n) = 2n\)도 전단사다. 42주차 문제 15에 의해 \(h \circ f^{-1} : \mathbb{Z} \to E\)가 전단사이므로 \(|\mathbb{Z}| = |E|\)이다. \(f^{-1}\)의 식은 \(f(k) = m\)을 \(k\)에 대해 푼 것이다. \(m > 0\)이면 \(2m\)이 짝수이고 \(f(2m) = \frac{2m}{2} = m\)이므로 \(f^{-1}(m) = 2m\)이고, 따라서 \((h \circ f^{-1})(m) = h(2m) = 4m\)이다. \(m \le 0\)이면 \(1 - 2m\)이 홀수이고 \(f(1-2m) = -\frac{(1-2m)-1}{2} = m\)이므로 \(f^{-1}(m) = 1 - 2m\)이고, 따라서 \((h \circ f^{-1})(m) = h(1-2m) = 2 - 4m\)이다. \(\blacksquare\)

검산. (b)의 규칙으로 \(m = 1 \mapsto 4\), \(m = 0 \mapsto 2\), \(m = -1 \mapsto 6\), \(m = 2 \mapsto 8\) — 전부 양의 짝수이고 서로 다르다.

복기. (a)와 (b)는 같은 증명의 추상판과 구체판이다 — 추이성의 증명이 곧 합성이므로, 추이성을 인용하는 순간 이미 합성 함수를 만든 것이다.

문제 9#

접근. 무대가 실수 구간으로 바뀌었을 뿐 서식은 같다. 전사 증인은 \(y = 2x\)를 \(x\)에 대해 푼 \(\frac y2\)이고, 그 증인이 \((0,1)\) 안에 있는지를 부등식으로 확인하는 줄이 붙는다.

풀이. \(f : (0,1) \to (0,2)\)를 \(f(x) = 2x\)로 정의하자. \(0 < x < 1\)이면 \(0 < 2x < 2\)이므로 값은 \((0,2)\) 안에 있다. (단사) \(f(a) = f(a')\)이라 하자. \(2a = 2a'\)이므로 양변을 2로 나누면 \(a = a'\)이다. (전사) \(y \in (0,2)\)라 하자. \(x = \frac y2\)로 두면 \(0 < y < 2\)에서 \(0 < x < 1\)이므로 \(x \in (0,1)\)이고, \(f(x) = 2 \cdot \frac y2 = y\)이다. 따라서 \(f\)는 전단사이고 \(|(0,1)| = |(0,2)|\)이다. \(\blacksquare\)

복기. 길이 1인 구간과 길이 2인 구간이 대등하다는 것은 길이가 크기의 판정 기준이 아니라는 뜻이다 — §1.1에서 포함 관계가 기준이 되지 못했던 것과 같은 관찰이다.

문제 10#

접근. 계수를 먼저 설계한다 — 폭 1을 4로 늘리므로 기울기 4, 시작점 0을 3으로 옮기므로 상수항 3이다. 설계가 끝나면 검증은 문제 9와 같다.

풀이. \(f : (0,1) \to (3,7)\)을 \(f(x) = 4x + 3\)으로 정의하자. \(0 < x < 1\)이면 \(0 < 4x < 4\)이므로 \(3 < 4x + 3 < 7\), 곧 값은 \((3,7)\) 안에 있다. (단사) \(f(a) = f(a')\)이라 하자. \(4a + 3 = 4a' + 3\)이므로 양변에서 3을 빼고 4로 나누면 \(a = a'\)이다. (전사) \(y \in (3,7)\)이라 하자. \(x = \frac{y-3}{4}\)로 두면 \(3 < y < 7\)에서 \(0 < y - 3 < 4\), 따라서 \(0 < x < 1\)이므로 \(x \in (0,1)\)이고 \(f(x) = 4 \cdot \frac{y-3}{4} + 3 = (y - 3) + 3 = y\)이다. 따라서 \(f\)는 전단사이고 \(|(0,1)| = |(3,7)|\)이다. \(\blacksquare\)

복기. 같은 설계로 임의의 두 열린구간 \((a,b)\), \((c,d)\)가 대등함을 얻는다 — \(f(x) = c + \frac{d-c}{b-a}(x-a)\)로 두면 된다. 기울기가 두 폭의 비이고, \(x = a\)에서 값이 \(c\)가 되도록 평행이동한 것이다. 이 사실이 문제 17로 확장된다.

문제 11#

접근. 대각선을 순서대로 적고 이미 나온 값과 같은 항을 지운다. \(p+q = 6\)까지 적으면 10항이 채워진다.

풀이. 대각선별로 적으면 \(p+q = 2\): \(\frac11\) / \(p+q = 3\): \(\frac12\), \(\frac21 = 2\) / \(p+q = 4\): \(\frac13\), \(\frac22\)(이미 나온 \(\frac11\)과 같으므로 건너뜀), \(\frac31 = 3\) / \(p+q = 5\): \(\frac14\), \(\frac23\), \(\frac32\), \(\frac41 = 4\) / \(p+q = 6\): \(\frac15\), 이하 \(\frac24, \frac33, \frac42\)는 각각 \(\frac12, \frac11, 2\)와 같으므로 건너뜀. 따라서 처음 10개의 목록 항은

\[ \tfrac11,\ \tfrac12,\ 2,\ \tfrac13,\ 3,\ \tfrac14,\ \tfrac23,\ \tfrac32,\ 4,\ \tfrac15 \]

이다.

검산. 열 항을 소수로 바꾸면 \(1, 0.5, 2, 0.333\dots, 3, 0.25, 0.666\dots, 1.5, 4, 0.2\)로 중복이 없다.

복기. 목록의 항을 기약 대표로 적는 것은 37주차에서 유리수를 동치류로 정의하고 대표원을 골랐던 절차이며, 건너뛰기는 “대표가 이미 등장했는가”를 묻는 절차다.

문제 12#

접근. 말로 된 규칙을 함수로 번역하는 것이 첫 걸음이다 — “한 방에 한 명”이 단사, “모두 방을 가진다”가 전사다. 번역이 끝나면 문제 5와 같은 계산이다.

풀이. 이동 규칙: \(n\)호실 손님을 \(n+1\)호실로 옮긴다. 이를 함수로 적으면 \(f : \mathbb{N} \to \{2,3,4,\dots\}\), \(f(n) = n + 1\)이다. \(n \ge 1\)이면 \(n + 1 \ge 2\)이므로 값은 공역 안에 있다. (단사 — 한 방에 한 명) \(f(a) = f(a')\)이라 하자. \(a + 1 = a' + 1\)이므로 \(a = a'\)이고, 서로 다른 두 손님이 같은 방을 배정받는 일이 없다. (전사 — 2호실부터 빈방 없음) \(m \ge 2\)라 하자. \(k = m - 1\)로 두면 \(k \ge 1\)이므로 \(k \in \mathbb{N}\)이고 \(f(k) = m\)이다. 따라서 \(f\)는 전단사이고 기존 손님 전원이 \(\{2,3,4,\dots\}\)에 한 명씩 들어간다. 1호실은 어느 손님의 배정지도 아니므로 비어 있고, 새 손님이 그 방에 들어간다. \(\blacksquare\)

복기. 만실인데 자리가 나는 이유는 \(g : \mathbb{N} \to \mathbb{N}\), \(g(n) = n+1\)이 단사이면서 전사가 아니기 때문이다 — 유한집합에 그런 함수가 없음은 41주차 문제 17이 증명했고, 이 문제와 문제 18은 같은 사실의 앞뒷면이다.

문제 13#

접근. 두 규칙을 이미 증명한 전단사(예제 2.1과 훈련 1)로 고른 뒤, 두 목적지가 겹치지 않고 합치면 전체가 됨을 확인한다.

풀이. 규칙: 기존 손님 \(n\)을 \(2n\)호실로, 새 손님 \(k\)를 \(2k - 1\)호실로 보낸다. ① 기존 손님 배정 \(h : \mathbb{N} \to E\), \(h(n) = 2n\)은 예제 2.1에 의해 전단사다 — 짝수 방이 빠짐없이 겹침없이 채워진다. ② 새 손님 배정 \(g : \mathbb{N} \to O\), \(g(k) = 2k - 1\)은 훈련 1에 의해 전단사다 — 홀수 방이 빠짐없이 겹침없이 채워진다. ③ 모든 자연수는 짝수이거나 홀수이고 둘 다일 수는 없으므로 \(E \cap O = \emptyset\), \(E \cup O = \mathbb{N}\) — 곧 \(\{E, O\}\)는 방 전체의 분할이다(17주차). ①②③에 의해 두 무리가 서로 다른 방을 받고, 어느 손님도 방을 못 받지 않으며, 방 전체가 정확히 채워진다. \(\blacksquare\)

복기. 짝\(\cdot\)홀로 가르는 이 기술이 문제 14의 교대 목록과 같다 — 방 번호가 목록의 순번 자리이고, 두 무리가 홀수 자리와 짝수 자리를 나눠 갖는다.

문제 14#

접근. 교대 목록에 번호를 붙여 식으로 적는 것이 시작이고, 그 다음은 §1.5 판정표의 세 줄을 확인한다. “서로소”는 겹침 없음의 세 번째 경우에서 일한다.

풀이. 목록을 \(c_1 = a_1\), \(c_2 = b_1\), \(c_3 = a_2\), \(c_4 = b_2, \dots\)로 정의한다. 식으로 적으면 \(c_{2k-1} = a_k\), \(c_{2k} = b_k\) (\(k \in \mathbb{N}\))이다. (빠짐 없음) \(A \cup B\)의 임의의 원소는 \(A\)의 원소이거나 \(B\)의 원소다. \(A\)의 원소이면 어떤 \(k\)에 대해 \(a_k\)이고 \(2k-1\)번째 자리에 있다. \(B\)의 원소이면 어떤 \(k\)에 대해 \(b_k\)이고 \(2k\)번째 자리에 있다. (겹침 없음) 서로 다른 두 자리의 항이 같다고 하자. 두 자리가 모두 홀수면 \(a_k = a_{k'}\)인데 \(A\)의 목록에는 중복이 없으므로 \(k = k'\), 곧 같은 자리다. 두 자리가 모두 짝수면 같은 이유로 같은 자리다. 한 자리가 홀수이고 다른 자리가 짝수면 \(a_k = b_{k'}\)이 되어 그 원소가 \(A \cap B\)에 속하는데 \(A \cap B = \emptyset\)이므로 불가능하다. (순번 유한) \(a_k\)의 순번은 \(2k-1\), \(b_k\)의 순번은 \(2k\)로 모두 유한한 자연수다. 따라서 \(n \mapsto c_n\)은 \(\mathbb{N}\)에서 \(A \cup B\)로의 전단사이고, \(A \cup B\)는 가산 무한이다. \(\blacksquare\)

복기. 서로소가 아니면 겹침 없음의 세 번째 경우가 깨지고, 처방은 예제 2.3과 같다 — 이미 나온 값이면 건너뛴다. 이 결과는 다음 주 “무리수가 비가산”에서 인용된다.

문제 15#

접근. \(\mathbb{Q}\)를 \(\{0\}\), \(\mathbb{Q}^+\), 음의 유리수로 나누고 예제 2.3의 목록을 재료로 지그재그로 엮는다 — 예제 2.2의 목록 구조를 유리수판으로 옮기는 셈이다.

풀이. 예제 2.3의 목록을 \(r_1, r_2, r_3, \dots\)이라 하자 — \(\mathbb{Q}^+\)의 빠짐\(\cdot\)겹침 없는 목록이다. 새 목록을

\[ 0,\ r_1,\ -r_1,\ r_2,\ -r_2,\ r_3,\ -r_3,\ \dots \]

로 정의한다. 순번으로 적으면 1번은 \(0\), \(2k\)번은 \(r_k\), \(2k+1\)번은 \(-r_k\)이다. (빠짐 없음) 임의의 유리수 \(q\)는 \(q = 0\), \(q > 0\), \(q < 0\) 중 정확히 하나다. \(q = 0\)이면 1번 자리에 있다. \(q > 0\)이면 어떤 \(k\)에 대해 \(q = r_k\)이고 \(2k\)번 자리에 있다. \(q < 0\)이면 \(-q \in \mathbb{Q}^+\)이므로 어떤 \(k\)에 대해 \(-q = r_k\)이고 \(q = -r_k\)는 \(2k+1\)번 자리에 있다. (겹침 없음) 세 구역 \(\{0\}\), \(\mathbb{Q}^+\), 음의 유리수 전체는 서로소이므로 구역이 다르면 값이 같을 수 없고, 같은 구역 안에서는 원 목록에 중복이 없다. (순번 유한) 모든 항의 순번이 \(1\), \(2k\), \(2k+1\) 꼴로 유한하다. 따라서 \(\mathbb{Q}\)는 가산 무한이고, 특히 가산이다. \(\blacksquare\)

복기. 이 논증은 “이미 만든 목록 두세 개를 하나로 엮는다”는 기술이다 — 문제 14가 두 개를, 여기서는 세 개를 엮었고, 유한 개의 가산 목록은 언제나 이렇게 엮인다. 조밀한 \(\mathbb{Q}\)가 가산이라는 이 결과가 다음 주 “무리수가 비가산”의 재료가 된다.

문제 16#

접근. 격자는 같지만 칸에 적힌 것이 다르다. 예제 2.3에서는 칸에 분수라는 값이 적혀 있어 서로 다른 칸이 같은 값을 가질 수 있었고, 이번에는 칸 \((p,q)\) 자체가 원소다.

풀이. \(\mathbb{N} \times \mathbb{N}\)의 원소 \((p,q)\)를 격자의 \((p,q)\) 칸에 놓고, 대각선을 \(p+q = 2, 3, 4, \dots\) 순으로, 각 대각선 안에서는 \(p\)가 작은 것부터 방문하는 목록을 만든다. (빠짐 없음) 임의의 \((p,q)\)는 \(p + q\)번째 대각선에 있고 그 대각선은 유한 단계 안에 방문되므로 목록에 등장한다. (겹침 없음) 서로 다른 두 칸은 서로 다른 순서쌍이다. \((1,2)\)와 \((2,4)\)는 분수로 보면 같은 값이지만 순서쌍으로는 다르므로 두 칸이 같은 원소를 담는 일이 없다. 따라서 건너뛰기가 아예 필요하지 않다 — 이것이 \(\mathbb{Q}^+\) 때와 다른 점이다. (순번 유한) \(p+q = s\)인 대각선의 칸은 \(s-1\)개이므로 \((p,q)\) 이전에 방문되는 칸의 수는 유한하다. 따라서 목록은 \(\mathbb{N}\)과 \(\mathbb{N} \times \mathbb{N}\) 사이의 전단사를 주고, \(|\mathbb{N} \times \mathbb{N}| = |\mathbb{N}|\)이다. \(\blacksquare\)

검산. 처음 여섯 항 \((1,1), (1,2), (2,1), (1,3), (2,2), (3,1)\)은 모두 서로 다르다. \((2,2)\)를 건너뛰지 않는 것이 예제 2.3과의 차이다.

복기. 예제 2.3을 이 결과의 따름으로 얻으려는 길도 있다 — \(\mathbb{Q}^+\)의 원소마다 기약분수 \((p,q)\)를 대응시키면 \(\mathbb{Q}^+\)가 \(\mathbb{N} \times \mathbb{N}\)의 부분집합과 대등해진다. 여기에 “가산집합의 무한 부분집합도 가산”이라는 사실을 더하면 예제 2.3이 따름으로 나오는데, 그 사실은 이 과정에서 증명하지 않았다. 그래서 예제 2.3은 직접 목록을 만들어 증명했다.

문제 17#

접근. (a)는 값을 넣어 구간의 끝으로 갈수록 출력이 커지는 모양을 확인하는 계산이다. (b)의 관문은 \(|f(x)|\)를 없애는 것이고, \(x \ge 0\)이면 \(f(x) \ge 0\)임을 확인하면 벗겨진다.

풀이. (a) \(f(0) = \frac{0}{1-0} = 0\), \(f(\frac12) = \frac{1/2}{1/2} = 1\), \(f(-\frac12) = \frac{-1/2}{1/2} = -1\), \(f(0.9) = \frac{0.9}{0.1} = 9\). 입력이 구간의 끝 \(\pm 1\)에 가까워질수록 분모가 0에 가까워지므로 출력의 절댓값이 한없이 커진다 — 유한한 구간이 실수 전체로 펴진다는 뜻이다. (b) \(x \ge 0\)이라 하자. \(0 \le x < 1\)이므로 \(1 - x > 0\)이고 \(f(x) = \frac{x}{1-x} \ge 0\)이다. 따라서 \(|f(x)| = f(x)\)이고,

\[ g(f(x)) = \frac{f(x)}{1 + f(x)} = \frac{\frac{x}{1-x}}{1 + \frac{x}{1-x}} = \frac{\frac{x}{1-x}}{\frac{(1-x) + x}{1-x}} = \frac{\frac{x}{1-x}}{\frac{1}{1-x}} = x \]

이다. \(x < 0\)인 경우도 같은 계산이다: \(|x| = -x\)이므로 \(f(x) = \frac{x}{1+x}\)이고 \(1 + x > 0\)이므로 \(f(x) < 0\), 곧 \(|f(x)| = -f(x)\)이다. 그러면

\[ g(f(x)) = \frac{f(x)}{1 - f(x)} = \frac{\frac{x}{1+x}}{1 - \frac{x}{1+x}} = \frac{\frac{x}{1+x}}{\frac{(1+x) - x}{1+x}} = x \]

이다. 두 경우를 합치면 모든 \(x \in (-1,1)\)에 대해 \(g(f(x)) = x\)이다.

반대 방향도 같은 서식으로 적는다. 먼저 임의의 \(y \in \mathbb{R}\)에 대해 \(|g(y)| = \frac{|y|}{1 + |y|} < 1\)이므로 \(g(y) \in (-1,1)\)이고, 따라서 \(f(g(y))\)가 정의된다. \(y \ge 0\)이면 \(|y| = y\)이므로 \(g(y) = \frac{y}{1+y} \ge 0\)이고 \(|g(y)| = g(y)\)이므로

\[ f(g(y)) = \frac{g(y)}{1 - g(y)} = \frac{\frac{y}{1+y}}{1 - \frac{y}{1+y}} = \frac{\frac{y}{1+y}}{\frac{(1+y) - y}{1+y}} = \frac{\frac{y}{1+y}}{\frac{1}{1+y}} = y \]

이다. \(y < 0\)이면 \(|y| = -y\)이므로 \(g(y) = \frac{y}{1-y}\)이고, \(1 - y > 0\)이므로 \(g(y) < 0\), 곧 \(|g(y)| = -g(y)\)이다. 그러면

\[ f(g(y)) = \frac{g(y)}{1 + g(y)} = \frac{\frac{y}{1-y}}{1 + \frac{y}{1-y}} = \frac{\frac{y}{1-y}}{\frac{(1-y) + y}{1-y}} = \frac{\frac{y}{1-y}}{\frac{1}{1-y}} = y \]

이다. 두 경우를 합치면 모든 \(y \in \mathbb{R}\)에 대해 \(f(g(y)) = y\)이다. 양쪽 합성이 항등함수이므로 \(f\)는 전단사이고(43주차), \(|(-1,1)| = |\mathbb{R}|\)이다. \(\blacksquare\)

검산. \(x = \frac12\)에서 \(f(x) = 1\)이고 \(g(1) = \frac{1}{1+1} = \frac12\) ✓. \(x = 0.9\)에서 \(f(x) = 9\)이고 \(g(9) = \frac{9}{10} = 0.9\) ✓.

복기. 문제 9\(\cdot\)10의 “임의의 두 열린구간이 대등”과 여기의 “열린구간과 \(\mathbb{R}\)가 대등”을 추이성으로 이으면 임의의 열린구간이 \(\mathbb{R}\)와 대등하다. 이 결과는 다음 주에 \((0,1)\)의 비가산성에서 \(\mathbb{R}\)의 비가산성으로 넘어갈 때 다리가 된다.

문제 18#

접근. 주장은 “부분은 전체보다 작다”는 정리를 인용하고 있다. 그 정리가 어느 무대에서 증명되었는지 확인하고 무대 밖에서 쓰였음을 지목하는 것이 결함 지적의 형식이다.

풀이. 결함은 “부분은 전체보다 작다”를 무한집합에 적용한 데 있다. 이 문장은 유한집합의 성질이다 — 그 뿌리는 41주차 도전 절이 “이 절이 빌려 쓰는 사실 ②”로 증명 없이 인정하고 쓴 문장, 곧 “유한집합에서 크기가 같은 부분집합은 전체 자신이다”이고, 41주차 문제 17은 그 사실을 써서 “\(|A| = |B| = n\)인 유한집합에서 단사이면 전사”를 세기로 증명했다. 진부분집합 \(B \subsetneq A\)와 전단사 \(f : A \to B\)가 있다면, 같은 \(f\)를 \(A \to A\)로 보아 단사이지만 치역이 \(B \subsetneq A\)라 전사가 아니므로 문제 17에 어긋난다 — 유한에서 “진부분집합은 전체와 대등하지 않다”는 이렇게 나온다. 두 근거 모두 “원소를 세어 \(n\)과 비교한다”는 절차에 기대고 있고, 무한집합에는 그 절차가 없으므로 증명이 옮겨 가지 않는다. 실제로 무한에서는 결론이 거짓이다. 예제 2.1에서 \(f(n) = 2n\)이 \(\mathbb{N}\)에서 \(E\)로의 전단사임을 증명했고 정의 48.1에 의해 \(|E| = |\mathbb{N}|\)이므로, \(E \subsetneq \mathbb{N}\)이면서 대등하다. 덧붙이면 진부분집합과 대등하다는 이 성질이야말로 무한집합을 유한집합과 가르는 기준으로 쓰이므로(데데킨트), 주장이 근거로 삼은 문장은 사실 무한집합의 반대 신호였다.

복기. 결함 지적의 형식은 세 줄이다 — ① 근거로 삼은 문장 지목 ② 그 문장이 참인 무대 확인 ③ 무대 밖의 반례 제시. 41주차의 인정 사실 ②와 그것을 쓴 문제 17이 ②를, 예제 2.1이 ③을 담당한다.

문제 19#

접근. “멈추지 않는다”를 직접 보이려 하면 막히므로 뒤집는다 — 어느 단계에서 멈춘다면 남은 집합이 공집합이고 그러면 \(A\)가 유한이라는 결론이 나와 가정과 어긋난다. 뽑힌 원소들이 서로 다르다는 것은 뽑는 절차가 보장한다.

풀이. \(A\)를 무한집합이라 하자. \(A \ne \emptyset\)이므로(\(\emptyset\)은 정의 48.3에 의해 유한이다) 원소 \(a_1\)을 뽑을 수 있다. \(k\)개를 뽑았다고 하고 \(A - \{a_1, \dots, a_k\}\)를 보자. 이 집합이 공집합이면 \(A = \{a_1, \dots, a_k\}\), 곧 \(|A| = |\{1,\dots,k\}|\)이므로 정의 48.3에 의해 \(A\)가 유한이 되어 가정에 어긋난다. 따라서 \(a_{k+1}\)을 뽑을 수 있고, 뽑기는 어느 단계에서도 멈추지 않는다. 뽑힌 원소들은 서로 다르다 — \(a_{k+1}\)은 \(a_1, \dots, a_k\)를 제거한 집합에서 뽑았기 때문이다. 따라서 \(n \mapsto a_n\)은 \(\mathbb{N}\)에서 \(\{a_1, a_2, \dots\}\)로의 함수이며, 단사(서로 다른 원소를 뽑았으므로)이고 전사(공역의 원소가 전부 어떤 \(a_n\)이므로)다. 곧 \(\{a_1, a_2, \dots\}\)는 \(A\)의 가산 무한 부분집합이다. \(\blacksquare\)

논평. 이 논증은 “뽑기”를 무한 번 수행한다. 각 단계의 뽑기는 정당하지만, 무한히 많은 뽑기를 한꺼번에 확정하려면 선택공리가 필요하다 — 이 과정에서는 그 공리를 증명 없이 인정하고 쓰고, 정식 논의는 대학 집합론으로 이월한다.

복기. 결과의 뜻은 “가산 무한이 가장 작은 무한”이라는 것이다 — 어떤 무한집합도 가산 무한 부분집합을 품는다. 다음 주에 “가산보다 큰 무한이 있다”가 증명되면 등급이 생긴다.

문제 20#

접근. (a)는 확인 1에서 관찰한 것 — 세기 자체가 짝짓기였다 — 을 문장으로 정리한다. (b)는 29주차의 반증 언어를 쓴다: 예시가 쌓여도 전칭 명제의 증명이 되지 않는다.

풀이. (예시 답안) (a) “다섯 개”라고 세는 행위는 대상들을 \(1, 2, 3, 4, 5\)와 하나씩 짝짓는 일이므로, 유한 세기의 본질은 수가 아니라 전단사다. 무한집합에는 “마지막 수”가 없어 세는 절차를 끝낼 수 없지만 짝짓기는 여전히 가능하므로, 전단사의 존재를 크기 같음의 정의로 삼는 것이 절차에 의존하지 않는 유일한 일반화이며, 이 정의는 유한에서 기존 세기와 같은 답을 준다(문제 2). (b) \(E\), \(\mathbb{Z}\), \(\mathbb{Q}\), \(\mathbb{N} \times \mathbb{N}\)이 모두 가산이라는 것은 사례의 축적일 뿐이고, “모든 무한집합은 가산이다”라는 전칭 명제는 반례 하나로 무너지는 형태이므로(29주차) 사례만으로는 증명이 되지 않는다.

복기. (b)의 형태는 1주차 문제 18과 같다 — 그때는 39개의 사례가 성립하고 40번째에서 무너졌고, 이번에는 네 개의 큰 사례가 성립하다 다음 주 \(\mathbb{R}\)에서 무너진다.

다음 주 예고: 칸토어의 대각선 논법으로 “\((0,1)\)의 모든 목록에는 반드시 빠진 수가 있다”를 증명한다. 이번 주의 3단계 틀이 그대로 기준선이 된다 — 목록을 만드는 대신, 어떤 목록도 §1.5 판정표의 첫 줄(빠짐 없음)을 만족할 수 없음을 보이는 귀류법이다.