07. Countable and Uncountable Sets

1. 기본 정의

 

    집합의 크기를 비교하는 기준은 전단사함수(Bijection)의 존재 여부다. 두 집합 사이에 전단사함수가 존재하면 크기가 같다고 정의한다. 이는 유한 집합뿐만 아니라 무한 집합에도 동일하게 적용된다.

 

무한 집합은 두 가지로 분류한다.

• Countable: 유한하거나 countably infinite한 집합
• Uncountable: countable하지 않은 집합

 

    모든 countably infinite한 집합의 크기는 ℵ0​(aleph null)로 표기한다. ℵ0​는 "가장 작은 무한의 크기"에 붙인 이름이다. ∣N∣=∣Z∣=∣N×N∣=ℵ0​.

 

---

2. Hilbert Hotel — 무한의 역설

 

    무한히 꽉 찬 호텔에 새 손님이 왔을 때 방을 만들 수 있을까? 유한한 호텔이라면 불가능하다. 방의 수가 정해져 있기 때문이다. 그러나 무한 호텔에서는 가능하다. 기존 손님을 모두 한 칸씩 옮기면 0번 방이 비기 때문이다.

 

f(n)=n+1

 

    이것이 가능한 이유는 무한 집합이 자기 자신의 진부분집합과 전단사함수가 존재할 수 있기 때문이다. 유한 집합에서는 절대 불가능한 일이다.

 

    두 개의 무한 호텔 G, J를 새 호텔 H로 합치는 것도 가능하다. G 손님은 짝수 방으로, J 손님은 홀수 방으로 보내면 된다.

fG​(n)=2n,fJ​(n)=2n+1

 

이 아이디어가 바로 다음 정리의 핵심이다.

"The union of countably many countably infinite sets is countably infinite."
셀 수 있는 개수만큼의 countably infinite한 집합들을 합쳐도 여전히 countably infinite하다.

 

---

3. Countably Infinite 집합들

 

ℤ이 Countably Infinite한 이유

 

    0→0,1→1,2→2,… 순서로 매핑하면 안 된다. 자연수를 전부 양의 정수에 써버리기 때문에 음수에 번호를 붙일 자연수가 남지 않는다. 전사함수가 되지 못하는 것이다.

 

대신 교대로 매핑한다.

f(n)=−n/2 if n is even
(n+1)/2​ if n is odd​

 

이 함수를 적용하면 f(0)=0, f(1)=1, f(2)=−1, f(3)=2, f(4)=−2, … 로 ℤ 전체를 빠짐없이 셀 수 있다.

 

ℕ × ℕ이 Countably Infinite한 이유

 

    ⟨0,0⟩,⟨0,1⟩,⟨0,2⟩,… 순서로 나열하면 안 된다. 자연수를 전부 첫 번째 원소가 0인 쌍에 써버리기 때문에 ⟨1,0⟩에 번호를 붙일 자연수가 남지 않는다. ℤ 증명에서 음수를 매핑하지 못하던 것과 정확히 같은 문제다.

 

대신 x + y 값이 작은 순서대로 나열한다.

• x + y = 0: ⟨0,0⟩
• x + y = 1: ⟨0,1⟩, ⟨1,0⟩
• x + y = 2: ⟨0,2⟩, ⟨1,1⟩, ⟨2,0⟩
• …
  이렇게 하면 어떤 순서쌍이든 반드시 유한한 번째에 등장하게 된다.

 

---

4. 𝒫(ℕ)이 Uncountable하다 — 대각선 논법

 

    P(N)이 uncountable하다는 것을 증명하려면 P(N)과 N 사이에 전단사함수가 존재하지 않는다는 것을 보여야 한다. 이를 위해 귀류법(proof by contradiction)을 사용한다.

 

특성 함수 (Characteristic Function)

 

    증명에 앞서, P(N)의 각 원소(자연수의 부분집합)를 비트 문자열로 표현할 수 있다. 집합 S의 특성 함수 X_S는 다음과 같이 정의된다.

X_S(n) = 1 if n∈S
0 if n∈/S

예) S = {1, 2, 3} → X_S =0111000000...
예) S = {0, 2, 4, ...} → X_S =1010101010...

 

증명

 

1단계. P(N)이 countable하다고 가정한다.

그러면 전단사함수 b:N→P(N)이 존재하고, 모든 부분집합을 S0​,S1​,S2​,… 로 나열할 수 있다.

 

2단계. 각 S_n의 특성 함수를 행렬로 쓴다.

	0번째 비트	1번째 비트	2번째 비트	3번째 비트	...
S_0	0	1	0	1	...
S_1	1	1	1	0	...
S_2	1	0	1	0	...
S_3	0	1	0	1	...

 

3단계. 대각선 비트를 전부 뒤집어 새로운 집합 D를 만든다.

대각선: 0, 1, 1, 1, ... → 뒤집으면 D: 1, 0, 0, 0, ...

 

4단계. D는 어떤 S_i와도 같을 수 없다.

D를 만드는 방법 자체가 S_i의 i번째 비트를 뒤집은 것이기 때문에, D와 S_i는 i번째 비트에서 반드시 다르다. 단 한 비트만 달라도 두 집합은 다른 집합이다.

 

5단계. 그러나 D∈P(N)이므로 반드시 목록에 있어야 한다. 이것이 모순이다.

따라서 원래 가정이 거짓이고, P(N)은 uncountable하다.

∣P(N)∣>∣N∣

 

---

5. Halting Problem

 

    대각선 논법은 컴퓨터 과학에도 그대로 적용된다. 프로그램 H가 있다고 가정하자. H는 프로그램 P와 입력 x를 받아서, P가 x를 입력받았을 때 언젠가 멈추는지 여부를 "halts" 또는 "no"로 출력한다.

 

이제 다음과 같은 프로그램 D를 만든다.

D(y):
    if H(y, y) == "halts":
        loop forever
    else:
        halt immediately

 

D(D)를 실행하면 어떻게 될까?

• H(D, D) = "halts"라면 → D(D)는 실제로 영원히 루프를 돈다. 모순.
• H(D, D) = "no"라면 → D(D)는 실제로 바로 멈춘다. 모순.

 

    어떤 경우에도 모순이 생기므로, H는 존재할 수 없다. 이것이 Halting Problem이다. P(N) 증명과 구조가 완전히 같다. 둘 다 "모순되는 대상을 일부러 만들어서 가정을 깨는" 대각선 논법이다.

 

---

6. 한눈에 보기

 

집합	Countable 여부	이유
N	Countably infinite	정의 자체
Z	Countably infinite	교대 매핑으로 bijection 존재
N x N	Countably infinite	$x+y$ 순서 나열로 bijection 존재
P(N)	Uncountable	대각선 논법으로 bijection 불가

 

핵심: Countably infinite한 집합들의 크기는 모두 ℵ0​로 같다. Uncountable한 집합은 ℵ0​보다 진짜로 더 큰 무한이다.