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

내용

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

이 주의 길잡이

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

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

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

이번 주 목표#

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

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

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

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

전단사의 정의를 백지에 쓰시오 — 단사와 전사 각각의 조건을 수식으로 적으시오. (41주차)
41주차 문제 16의 함수 \(f : \mathbb{N} \to \mathbb{Z}\)의 규칙을 쓰고, \(f(1), \dots, f(6)\)을 계산하시오.
전단사 \(f : A \to B\)와 \(g : B \to C\)의 합성 \(g \circ f\)가 다시 전단사임은 어느 주차의 어느 문제가 증명했는가. (42주차)
전단사의 역함수가 존재함을 보장하는 정리를 진술하고, 그 역함수가 다시 전단사임은 어느 주차의 어느 문제가 주는지 쓰시오. (43주차)
양의 짝수 전체 \(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번을 밀어붙여 보자.

시도 1 — 세어서 비교하기

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

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

그런데 \(\mathbb{N}\)에는 마지막 수가 없다. 따라서 … “

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

시도 2 — 포함 관계로 비교하기

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

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

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

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

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

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

답

\(1 \leftrightarrow a\), \(2 \leftrightarrow b\), \(3 \leftrightarrow c\)로 짝짓는다.

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

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

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

이 주 전체의 기준

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

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

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

확인 2. 빈칸 (1)~(6)을 채우고, 짝짓기 규칙이 “개수가 같다”를 보증하려면

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

답

(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) [백지 암기 대상]#

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

\(A\)와 \(B\)는 대등하다고 하고, \(|A| = |B|\)로 쓴다.

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

“\(|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이 같아진다.

확인 3. 두 실험에서 붕괴한 것을 각각 한 문장으로 적어 보자.

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

답

전사를 지우면 “짝 없이 남는 원소”(\(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

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

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

제시할 것: \(\underline{\quad}\)” 꼴로 적어 보자.

답

받는 것: 전단사 \(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이 어떤 그림이 되는지 본다.

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

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

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

답

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

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

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

여기에 이름을 붙인다.

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

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

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

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

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

집합 \(A\)가 유한이라는 것은 \(A = \emptyset\)이거나 어떤 자연수 \(n\)에 대해

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

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

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

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

표기 — \(\mathbb{Q}^+\)와 \(\mathbb{N} \times \mathbb{N}\)

\(\mathbb{Q}^+\)는 “양의 유리수 전체”로 읽는다. \(\mathbb{N} \times \mathbb{N}\)은

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

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

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

확인 6. \(E = \{2,4,6,\dots\}\)는 \(\mathbb{N}\)의 진부분집합이다.

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

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

답

“진부분집합은 전체와 대등하지 않다”이다. 유한집합에서 이 문장을 떠받치는 것은 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이 반례다.

확인 7. 어떤 답안에 다음 세 문장이 나왔다. 각각 허용되는가.

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

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

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

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

답

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

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

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

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

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

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