# 48주차 — 집합의 크기: 가산 무한

:::{admonition} 이 주의 길잡이
:class: keybox

**핵심 문장**: 센다는 것은 짝짓는 것이다 — 무한에서도.

**이 주의 위치**: 50주 과정의 48주차. 41~43주차에서 만든 전단사$\cdot$합성$\cdot$역함수가 무한집합의 크기를 재는 자로 승격되고, 다음 주가 "가산이 아닌 무한"을 보일 때 쓸 대조군이 여기서 만들어진다.

**원서 대응**: BoP(Book of Proof) 14.1 (Sets with Equal Cardinalities), 14.2 (Countable and Uncountable Sets) — 병행자 참고용. 원서 없이 읽을 수 있다.
:::

## 이번 주 목표

1. 대등($|A| = |B|$)의 **정의**를 백지에 쓰고, 그것이 유한 세기의 올바른 일반화인 이유를 설명할 수 있다.
1. **부분이 전체와 대등**해지는 현상($|\mathbb{N}| = |E|$)을 정의로 증명하고, 유한 직관의 어느 정리가 무한에서 성립하지 않는지 지목할 수 있다.
1. $|\mathbb{N}| = |\mathbb{Z}|$(지그재그)와 $\mathbb{Q}$의 가산성(격자 행진)을 목록 제작의 서식으로 쓸 수 있다.
1. 가산의 정의를 익히고, 합집합$\cdot$곱집합 같은 연산 뒤에도 가산이 유지되는지를 목록으로 판정할 수 있다.

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

## 준비 운동 (41~43주차 복습)

이번 주가 쓰는 부품은 전부 9부(함수)에서 만들어졌다. 다섯 문항으로 그 부품을 꺼내 둔다.

1. 전단사의 정의를 백지에 쓰시오 — 단사와 전사 각각의 조건을 수식으로 적으시오. (41주차)
1. 41주차 문제 16의 함수 $f : \mathbb{N} \to \mathbb{Z}$의 규칙을 쓰고, $f(1), \dots, f(6)$을 계산하시오.
1. 전단사 $f : A \to B$와 $g : B \to C$의 합성 $g \circ f$가 다시 전단사임은 어느 주차의 어느 문제가 증명했는가. (42주차)
1. 전단사의 역함수가 존재함을 보장하는 정리를 진술하고, 그 역함수가 **다시 전단사**임은 어느 주차의 어느 문제가 주는지 쓰시오. (43주차)
1. 양의 짝수 전체 $E = \{2, 4, 6, \dots\}$와 자연수 전체 $\mathbb{N}$ 중 어느 쪽 원소가 더 많은가. 이유와 함께 한 문장으로 쓰시오.

### 자주 나오는 세 가지 답 — 5번 문항

방금 쓴 답은 대개 다음 세 유형 중 하나다. 셋 다 옳은 부분이 있고, 셋 다 이번 주에 메울 정확한 간격이 있다.

- **유형 1 — 절반이다.** "$E$는 $\mathbb{N}$에서 홀수를 뺀 것이므로 절반이다."

유한한 구간에서는 옳다 — $1$부터 $100$까지에서 짝수는 정확히 50개다. 빠진 것은 판정 기준이다. "많다$\cdot$적다$\cdot$같다"를 무엇으로 판정하는지가 아직 정해지지 않았고, $\mathbb{N}$ 전체에는 "100까지"라는 잘라 세는 절차가 없다.

- **유형 2 — 둘 다 무한이므로 같다.** 결론은 이번 주에 참으로 판명된다. 문제는

근거다. 근거가 "둘 다 무한이니까"뿐이라면 다음 주에 그 근거가 무너진다 — 둘 다 무한이면서 크기가 다른 두 집합이 존재한다는 것이 49주차의 내용이다.

- **유형 3 — 비교할 수 없다.** "무한은 셀 수 없으므로 개수를 물을 수 없다." 세는

**절차**가 불가능한 것은 옳다. 간격은 "세지 않고 비교하는 방법"이 있다는 것이고, §1.1에서 그 방법이 이미 유한 세기 안에 숨어 있었음을 본다.

## 개념 — 크기를 재는 자

### 1 유한의 방법으로 무한을 재려 하면 어디서 막히는가

이미 아는 두 가지 방법 — 세기, 그리고 포함 관계 — 으로 준비 운동 5번을 밀어붙여 보자.

:::{admonition} 시도 1 — 세어서 비교하기
:class: quotebox

문제: $\mathbb{N}$과 $E = \{2, 4, 6, \dots\}$ 중 어느 쪽 원소가 많은가.

"$\mathbb{N}$의 원소를 센다. $1, 2, 3, \dots$ 마지막 수에 도달하면 그 수가 개수다.

그런데 $\mathbb{N}$에는 마지막 수가 없다. 따라서 … "
:::

여기서 멈춘다. 세기라는 절차는 끝나야 답을 내놓는데, 이 절차는 끝나지 않는다.

:::{admonition} 시도 2 — 포함 관계로 비교하기
:class: quotebox

"$E \subsetneq \mathbb{N}$이므로 $E$가 더 작다." 그런데 같은 기준으로 $\mathbb{N}$과

$\mathbb{Z}^- = \{-1, -2, -3, \dots\}$를 비교하려 하면 — 어느 쪽도 다른 쪽을 포함하지

않으므로 — 판정 자체가 나오지 않는다.
:::

포함 관계는 한쪽이 다른 쪽 안에 들어 있을 때만 말을 하고, 그렇지 않은 두 집합에는 아무 말도 하지 않는다. $\{1,2,3\}$과 $\{a,b,c\}$도 서로 포함하지 않지만 유한에서는 세기가 대신 답을 주었기에 이 한계가 드러나지 않았을 뿐이다. 무한에서는 둘 다 막힌다.

:::{container} quotebox
**확인 1.** 그렇다면 $\{1,2,3\}$과 $\{a,b,c\}$의 개수가 같다고 판정할 때,

수를 세지 않고도 할 수 있는 일은 무엇인가. 한 구절로 적어 보자.
:::

:::{admonition} 답
:class: quotebox dropdown

$1 \leftrightarrow a$, $2 \leftrightarrow b$, $3 \leftrightarrow c$로 **짝짓는다**.

양쪽 모두 남는 원소가 없으면 개수가 같다고 판정한다. "세 개"라고 세는 행위 자체가

$\{1, 2, 3\}$과 짝을 짓는 일이었다 — 세기는 짝짓기의 한 종류였고,

짝짓기에는 "마지막 수"가 필요하지 않다.
:::

:::{admonition} 이 주 전체의 기준
:class: quotebox

크기 비교가 증명이 되려면 개념이 **함수**가 되어야 한다.

두 집합 사이의 짝짓기를 함수로 적어 주는 것이 이번 주의 정의다.
:::

### 2 짝짓기로 — 정의를 만들어 보기

구체 사례부터 채워 보자. 각 행에서 주어진 규칙으로 짝을 지었을 때 짝 없이 남는 원소가 있는지 확인하고, 개수가 같은지 판정한다.

| **두 집합** | **짝짓는 규칙** | **짝 없이 남는 원소** | **판정** |
|---|---|---|---|
| $\{1,2,3\}$ / $\{a,b,c\}$ | $n \leftrightarrow$ $n$번째 문자 | 없음 | 개수 같음 |
| $\{1,2,3\}$ / $\{a,b,c,d\}$ | $n \leftrightarrow$ $n$번째 문자 | $\underline{\quad(1)\quad}$ | $\underline{\quad(2)\quad}$ |
| $\mathbb{N}$ / $E$ | $n \leftrightarrow 2n$ | $\underline{\quad(3)\quad}$ | $\underline{\quad(4)\quad}$ |
| $\mathbb{N}$ / $\{5,6,7,\dots\}$ | $n \leftrightarrow n+4$ | $\underline{\quad(5)\quad}$ | $\underline{\quad(6)\quad}$ |

:::{container} quotebox
**확인 2.** 빈칸 (1)~(6)을 채우고, 짝짓기 규칙이 "개수가 같다"를 보증하려면

어떤 조건 **두 가지**를 만족해야 하는지 적어 보자.
:::

:::{admonition} 답
:class: quotebox dropdown

(1) $d$  (2) 이 규칙으로는 개수 같음을 보증하지 못한다(세어 보면 실제로 개수 다름)

(3) 없음  (4) 개수 같음  (5) 없음  (6) 개수 같음.

(3)의 확인: $E$의 원소는 전부 $2k$ 꼴이고 그 짝은 $k$다. (5)의 확인: $m \ge 5$이므로 $m - 4 \in \mathbb{N}$이다.

두 조건은 ① 서로 다른 것끼리는 서로 다른 짝을 갖는다 ② 상대편에 짝이 없는 원소가

남지 않는다. ①은 **단사**, ②는 **전사**의 조건이고, 둘을 합치면 전단사 하나다.

규칙 하나가 실패했다고 곧바로 "개수 다름"인 것은 아니다 — 유한에서는 세기가 그

결론을 따로 보증하고, 무한에서는 이 추론이 무너진다(§1.6, 문제 18).
:::

이 관찰에 정식 이름과 기호를 붙인다. 식 자체에 새로운 것은 없다 — 방금 표에서 한 판정을 문장으로 굳혔을 뿐이다.

### 정의 48.1 — 대등 (equinumerous) [백지 암기 대상]

:::{container} quotebox
집합 $A$, $B$에 대해, $A$에서 $B$로의 **전단사 $f : A \to B$가 존재**하면

$A$와 $B$는 **대등**하다고 하고, $|A| = |B|$로 쓴다.
:::

:::{admonition} 표기 — $|A| = |B|$
:class: quotebox

"$|A| = |B|$"는 "$A$와 $B$는 대등하다"로 읽는다. 유한집합에서는 $|A|$가 원소의

개수라는 수였고(12~13주차), 그때의 등식과 이 표기는 같은 결론을 준다(문제 2).

다만 $A$가 무한일 때 $|A|$ 자체에 어떤 수를 붙이지는 않는다 — 이번 주에 뜻이

정해진 것은 $|A| = |B|$라는 **관계 전체**이지, 좌변 하나가 아니다.
:::

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

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

| **조각** | **하는 일** | **증명(판정)에서의 역할** |
|---|---|---|
| "집합 $A$, $B$에 대해" | 무대의 선언 | 유한$\cdot$무한을 가리지 않는다 — 같은 기준을 두 세계에 쓴다 |
| "$A$에서 $B$로의 전단사 $f$가" | 짝짓기 규칙 제공 | 제작할 대상. 단사가 겹침을, 전사가 빠짐을 막는다 |
| "존재하면" | 요구 조건의 명시 | 그런 $f$를 **하나만** 제시하면 끝난다 — 모든 함수를 검사할 필요가 없다 |
| "$\vert A \vert = \vert B \vert$로 쓴다" | 표기의 약속 | 개수를 세지 않고 두 집합 사이의 관계만 기록한다 |

**조각 삭제 실험.** 둘째 조각의 "전단사"에서 조건을 하나씩 지워 보자.

- **전사를 지우면**(단사만 요구): $f(1)=a$, $f(2)=b$, $f(3)=c$인 $f : \{1,2,3\} \to \{a,b,c,d\}$가

단사이므로 $|\{1,2,3\}| = |\{a,b,c,d\}|$가 된다 — 3과 4가 같아진다.

- **단사를 지우면**(전사만 요구): $a, b \mapsto 1$, $c \mapsto 2$, $d \mapsto 3$인

$f : \{a,b,c,d\} \to \{1,2,3\}$이 전사이므로 다시 4와 3이 같아진다.

:::{container} quotebox
**확인 3.** 두 실험에서 붕괴한 것을 각각 한 문장으로 적어 보자.

그리고 두 조건 중 하나만으로는 왜 부족한지 표 §1.2의 두 조건과 대응시켜 보자.
:::

:::{admonition} 답
:class: quotebox dropdown

전사를 지우면 "짝 없이 남는 원소"($d$)가 있어도 같다고 판정된다 — §1.2의 조건 ②가 사라진다.

단사를 지우면 "둘이 한 짝을 나눠 갖는" 상황이 허용된다 — 조건 ①이 사라진다.

어느 쪽이든 유한집합에서 이미 3과 4를 같다고 말하게 되므로 새 정의가 옛 세기와

어긋난다. 두 조건이 함께 있어야 정의가 무너지지 않는다.
:::

### 4 부품 재취업 — 대등의 세 성질

대등은 새로 만든 관계지만, 그 성질을 증명할 부품은 이미 전부 있다.

| **성질** | **진술** | **필요한 부품** | **출처** |
|---|---|---|---|
| 반사 | $\vert A \vert = \vert A \vert$ | 항등함수 $\mathrm{id}_A$가 전단사 | 41~42주차 |
| 대칭 | $\vert A \vert = \vert B \vert$이면 $\vert B \vert = \vert A \vert$ | 전단사의 역함수가 존재하고 전단사 | 43주차 핵심 정리 + 문제 14 |
| 추이 | $\vert A \vert = \vert B \vert$, $\vert B \vert = \vert C \vert$이면 $\vert A \vert = \vert C \vert$ | 전단사의 합성이 전단사 | 42주차 문제 15 |

:::{container} quotebox
**확인 4.** 추이 성질을 증명하려 한다. 가정에서 받는 것은 무엇이고,

목표를 위해 제시해야 하는 것은 무엇인가. "받는 것: $\underline{\quad}$ /

제시할 것: $\underline{\quad}$" 꼴로 적어 보자.
:::

:::{admonition} 답
:class: quotebox dropdown

받는 것: 전단사 $f : A \to B$와 $g : B \to C$ (정의 48.1의 "존재한다"를 가정 쪽에서 푼 것).

제시할 것: $A$에서 $C$로의 전단사 하나 — 곧 $g \circ f$이고, 그것이 전단사임은

42주차 문제 15가 이미 증명했다. 완전한 증명은 문제 7에서 쓴다.
:::

대등은 이 세 성질을 갖지만 36~37주차의 "동치관계"라고 부르지는 않는다 — 그 관계가 놓일 무대가 "모든 집합의 모임"이어야 하는데, 그 모임을 집합으로 다루면 6주차 §1.7의 러셀의 역설이 발생한다. 그래서 "동치관계처럼 행동한다"까지만 말한다.

### 5 목록화 — 가산의 정의

$B = \mathbb{N}$인 특별한 경우에 정의 48.1이 어떤 그림이 되는지 본다.

:::{container} quotebox
**확인 5.** 전단사 $f : \mathbb{N} \to A$가 있다고 하자. 이 함수의 출력을

$f(1), f(2), f(3), \dots$ 순서로 늘어놓으면 무엇이 생기는가.

그리고 단사와 전사는 그 줄에서 각각 어떤 현상으로 보이는가.
:::

:::{admonition} 답
:class: quotebox dropdown

$A$의 원소를 한 줄로 늘어놓은 **목록**이 생긴다. 전사이므로 어느 원소도 빠지지 않고

(빠짐 없음), 단사이므로 같은 원소가 두 번 나오지 않는다(겹침 없음). 정의역이

$\mathbb{N}$이므로 모든 원소는 유한한 번째 자리에 등장한다 — "몇 번째"가 확정된다.
:::

여기에 이름을 붙인다.

### 정의 48.2 — 가산 (countable) [백지 암기 대상]

:::{container} quotebox
$|A| = |\mathbb{N}|$인 집합 $A$를 **가산 무한**(countably infinite)이라 한다.

유한집합이거나 가산 무한인 집합을 **가산**(countable)이라 하고,

가산이 아닌 집합을 **비가산**(uncountable)이라 한다.
:::

### 정의 48.3 — 유한과 무한 (finite / infinite)

:::{container} quotebox
집합 $A$가 **유한**이라는 것은 $A = \emptyset$이거나 어떤 자연수 $n$에 대해

$|A| = |\{1, 2, \dots, n\}|$이라는 뜻이다. 유한이 아닌 집합을 **무한**이라 한다.
:::

정의 48.3이 실제로 일하는 곳은 문제 19다.

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

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

:::{admonition} 표기 — $\mathbb{Q}^+$와 $\mathbb{N} \times \mathbb{N}$
:class: quotebox

$\mathbb{Q}^+$는 "양의 유리수 전체"로 읽는다. $\mathbb{N} \times \mathbb{N}$은

6주차의 데카르트 곱이고 "자연수 순서쌍 전체"로 읽는다 — 원소는 $(p, q)$ 꼴이다.
:::

### 6 부분이 전체와 대등해지는 현상

41주차 문제 17은 유한집합에서 "단사이면 전사"임을 세기로 증명했고, 같은 문제 뒷부분에서 $f(n) = 2n$이 $\mathbb{N}$ 위에서는 단사이지만 전사가 아님을 확인했다. 두 사실을 나란히 놓으면 이번 주의 현상이 나온다.

:::{container} quotebox
**확인 6.** $E = \{2,4,6,\dots\}$는 $\mathbb{N}$의 진부분집합이다.

그런데 $f(n) = 2n$을 $f : \mathbb{N} \to E$로 보면 전단사다(예제 2.1).

유한집합에서 참인 어떤 문장이 여기서 성립하지 않는가.
:::

:::{admonition} 답
:class: quotebox dropdown

"진부분집합은 전체와 대등하지 않다"이다. 유한집합에서 이 문장을 떠받치는 것은 41주차

도전 절이 "이 절이 빌려 쓰는 사실 ②"로 증명 없이 인정하고 쓴 유한성의 사실 —

유한집합에서 크기가 같은 부분집합은 전체 자신이다 — 이고, 41주차 문제 17은 바로 그

사실을 써서 "유한에서 단사이면 전사"를 얻었다. $\mathbb{N}$에서는 그 문장이 거짓이다 —

$E \subsetneq \mathbb{N}$이면서 $|E| = |\mathbb{N}|$이다. 이것은 모순이 아니라 무한집합의

성질이며, 데데킨트는 이 성질을 무한집합의 정의로 삼았다.
:::

같은 현상을 힐베르트가 든 사고 실험으로 옮기면, 방이 $\mathbb{N}$개인 만실 숙소에 손님이 한 명 더 와도 $n$호실 손님을 전부 $n+1$호실로 옮기면 1호실이 빈다. 유한한 숙소에서는 불가능한 조작이고, 무한에서 가능한 이유는 $n \mapsto n+1$이 단사이면서 전사가 아니기 때문이다. 문제 12와 13이 이 조작을 전단사 서식으로 정리하는 자리다.

### 7 근거 목록 갱신 — 이번 주에 추가되는 것

칸의 개수는 그대로 네 개다. ① 칸에 정의 세 개가 추가되고, ④ 칸에 9부의 결과들이 들어온다.

| **근거** | **내용** | **이번 주에는 이렇게 쓴다** |
|---|---|---|
| ① 정의 | 기존 정의들 + **정의 48.1, 48.2, 48.3** | "$\vert A \vert = \vert B \vert$" $\leftrightarrow$ "전단사 $A \to B$가 존재" 사이를 번역한다 |
| ② 닫힘성 | 정수$\cdot$유리수의 사칙 결과가 그 세계에 남는다 | "$m = 2k$이면 $k = \frac m2$는 정수"를 짝수의 정의로 확보한다 |
| ③ 등식의 성질 | 대입 / 전개 / 묶기 / 양변 연산 | $2a = 2a'$에서 $a = a'$을 얻는다 |
| ④ 이미 증명한 명제 | 41주차 문제 16$\cdot$17과 도전 절 인정 사실 ②, 42주차 문제 15, 43주차 핵심 정리$\cdot$문제 14, 37주차 예제 2.3, 17주차 표준 분할(짝/홀), 15주차 문제 17, 이번 주 예제 | 전단사의 합성$\cdot$역함수를 재증명 없이 인용한다 |

목록 밖의 것은 이번 주에도 근거가 되지 않는다. 특히 "둘 다 무한이니까 같다", "빽빽하니까 많다"는 근거가 아니다 — 전자는 다음 주에 반례를 만나고 후자는 예제 2.3이 반례다.

:::{container} quotebox
**확인 7.** 어떤 답안에 다음 세 문장이 나왔다. 각각 허용되는가.

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

(가) "전단사 $f : A \to B$와 $g : B \to C$가 있으므로 $g \circ f$도 전단사다"

(나) "$\mathbb{Q}$는 수직선에 빽빽하게 깔려 있으므로 $\mathbb{N}$보다 많다"

(다) "$m$이 양의 짝수이므로 $m = 2k$인 $k \in \mathbb{N}$가 존재한다"
:::

:::{admonition} 답
:class: quotebox dropdown

(가) 허용 — 근거 ④. 42주차 문제 15가 증명한 명제의 인용이다.

(나) 불허 — 목록 밖이다. "빽빽함"은 크기의 판정 기준이 아니며, 예제 2.3에서 실제로

$\mathbb{Q}$가 가산임이 증명된다.

(다) 허용 — 다만 근거 ①과 ③의 두 걸음이다. 정의 1.1(1주차, 근거 ①)이 주는 것은

$m = 2k$인 **정수** $k$까지이고, $m \ge 2$에서 $k \ge 1$(근거 ③)이 나와야 비로소

$k \in \mathbb{N}$이다. 무한을 다루는 주에도 각 줄의 근거는 1주차의 네 칸을 벗어나지 않는다.
:::