ⓒ 2025 AI교육연구회 withseok. All rights reserved. (위드석)
[블로그 글 내용 상업적 이용금지] ■ 위드석홈 | 위드석개발 | AI교육연구회 ■

무한도 더 큰 무한이 있다?

크기가 다른 무한의 수학적 접근, 

자연수 집합과 1:1 대응

 

 

칸토어의 1:1 대응과 ℵ₀

: “농도(기수)”로 보는 무한집합 완전 가이드

 

아래 내용은 자연수 집합 ℕ과 그와 1:1 대응(bijection)을 이루는 모든 집합(= 가산 무한집합, 농도 ℵ₀)을 중심으로, 칸토어의 이론을 체계적으로 정리한 것입니다. 정의 → 예시 → 정리와 성질 → 대비(비가산) → 흔한 오해 순서로 구성했습니다.

1) 핵심 용어 정리

  • 1:1 대응(전단사, bijection): 두 집합 A,B 사이에 서로 다른 원소들을 정확히 한 쌍씩 짝지어 빠짐없이 대응시키는 함수 f:A→B. 존재하면 |A|=|B| (같은 “농도”, 같은 “크기”)라고 말합니다. 표기: A ~ B.
  • 농도(기수, cardinality): 집합의 “크기” 개념. 유한집합은 원소 수가 기수이고, 무한집합은 ℵ(알레프) 기호로 표기.
  • ℵ₀: 자연수 집합 ℕ={0,1,2,...}의 기수. 가장 작은 무한 기수.
  • 가산(가부/가부셈 가능): ℕ과 1:1 대응 가능(=기수가 ℵ₀). 영어로 countably infinite, denumerable.

2) “가산 무한집합”의 등가적 정의

다음은 서로 동치입니다.

  1. A가 무한이고 ℕ과 1:1 대응이 존재
  2. A의 원소들을 순서대로 나열할 수 있다: A={a₀,a₁,a₂,...}
  3. |A|=ℵ₀

즉, 자연수처럼 ‘차례로 셀 수 있으면’ 가산입니다.

3) 대표적인 가산 무한집합과 명시적 1:1 대응

3-1. 정수 ℤ는 가산

정수 나열: 0,1,-1,2,-2,3,-3,...

명시적 전단사 f:ℤ→ℕ:

f(z)=
0,  z=0
2z-1, z>0
-2z, z<0

역함수 g:ℕ→ℤ:

g(n)=
0, n=0
(n+1)/2, n 홀수
-n/2, n 짝수

3-2. 유리수 ℚ는 가산

격자 (p,q)∈ℤ×ℕ≥1 위의 분수 p/q를 대각선 순회로 열거하고(중복·기약 아님은 건너뜀), 부호와 0을 섞어 배치하면 ℚ 전체를 나열할 수 있습니다. (또는 Calkin–Wilf/Stern–Brocot 트리 사용)

3-3. ℕ×ℕ은 가산

칸토어의 페어링 함수 π:ℕ²→ℕ:

π(a,b) = ((a+b)(a+b+1))/2 + b

이는 전단사입니다(역함수도 닫힌형으로 존재). 따라서 유한곱 ℕ^k도 가산.

3-4. 다른 중요한 가산 예

  • 모든 유한 길이 문자열(유한 알파벳 위)
  • 모든 유한 부분집합 P_fin(ℕ)
  • 대수적 수(정수계수 다항식의 근들의 전체): 정수계수 다항식 집합이 가산이고, 각 다항식의 근은 유한 개 → 가산 합집합은 가산 → 대수적 수는 가산
  • 컴퓨터 프로그램/증명/정리 목록: 유한 문자열이므로 가산
  • 유리 다변수 다항식, 유한 그래프(동형까지), 문법으로 생성되는 문장들 등

4) 가산 집합의 닫힘 성질

  • 유한 합/곱: 가산 ∪ 가산, 가산 × 가산 → 가산
  • 가산 개의 가산 합집합: 일반적으로 가산입니다(표준 대각선 나열). {Aₙ} 각각이 가산이면 A=∪Aₙ도 가산.

비고: “모든 Aₙ에 대해 실제 열거가 주어져 있다”는 정도의 약한 선택이 자연스럽게 쓰입니다.

5) 데데킨트 무한과 힐베르트 호텔

  • 데데킨트-무한: 어떤 진부분집합과 1:1 대응 가능(유한집합에서는 불가능). 예) ℕ ~ ℕ\{0} via n→n+1.
  • 힐베르트 호텔: 방이 꽉 차도 n→n+1 이동으로 한 방 확보, 짝수 배치로 무한 손님 수용 등 → ℵ₀+ℵ₀=ℵ₀, ℵ₀·ℵ₀=ℵ₀의 ‘직관’.

6) 비가산(uncountable)의 탄생: 대각선 논법과 연속체

  • 칸토어의 정리: 임의의 집합 X에 대해 |P(X)|>|X|. 특히 |P(ℕ)|>|ℕ|, 즉 P(ℕ)는 비가산.
  • 실수 ℝ의 기수는 2^ℵ₀=|{0,1}^ℕ| (이진 전개와 거의 전단사; 유한하게 끝나는 1-꼬리 중복은 가산하므로 무시 가능).
  • 대각선 논법: {0,1}^ℕ을 나열한다고 가정하면, 대각 성분을 뒤집어 만든 새로운 열이 목록에 없음 → 비가산.

요약:

|ℕ| = ℵ₀ < |ℝ| = 2^ℵ₀

7) 기수 연산(핵심만)

  • ℵ₀ + n = ℵ₀ (유한 손님 추가)
  • ℵ₀ + ℵ₀ = ℵ₀ (두 열을 교차 나열)
  • ℵ₀ · ℵ₀ = ℵ₀ (페어링 함수)
  • ℵ₀^ℵ₀ = 2^ℵ₀ (부등식 2^ℵ₀ ≤ ℵ₀^ℵ₀ ≤ (2^ℵ₀)^ℵ₀ = 2^ℵ₀ 로 결론)

8) 순서형(ordinal) vs 기수(cardinal) 한 줄 비교

  • 순서형: 잘순서화된 집합의 “위치/순서 구조” 크기(예: ω는 ℕ의 표준 순서형).
  • 기수: “몇 개인가”만. ℵ₀는 ω의 기수. (선택공리 하에서 모든 기수는 어떤 순서형의 초기구간)

9) 연속체 가설(CH) 아주 짧게

ℵ₀ < |X| < 2^ℵ₀ 인 집합 X가 있는가?

없다고 주장하는 명제가 CH. 고델(1940)과 코언(1963)에 의해

ZFC 공리계에서 독립임이 밝혀졌습니다(참·거짓 모두 모형이 존재).

10) 흔한 오해 정리

  • “조밀(dense)” vs “가산/비가산”: ℚ는 ℝ에서 조밀하지만 가산입니다. “어디에나 있다”는 위상적 성질과 “몇 개인가”는 별개.
  • 측도/길이 vs 기수: [0,1]\ℚ는 측도 1(거의 전부)이지만 기수는 2^ℵ₀. 한편 ℚ는 측도 0이지만 무한(가산).
  • 무한의 크기는 하나가 아니다: ℵ₀보다 큰 무한(예: 2^ℵ₀)이 실제로 존재합니다(칸토어의 핵심 발견).

11) 작은 증명 스케치(핵심 아이디어)

  1. ℤ 가산: 위 3-1 전단사.
  2. ℚ 가산: 분모·분자 격자를 대각선으로, 기약만 취해 중복 제거.
  3. 가산 합집합 가산: Aₙ={aₙ,₀,aₙ,₁,...}라면 (n,k)의 사선 순회로 A=∪Aₙ 나열.
  4. ℝ 비가산: xₙ의 이진 전개로 행렬을 만들고, 대각을 뒤집은 새 수 y가 모든 xₙ과 달라서 목록에 없음.

12) 빠른 연습 문제(정답 바로 아래)

  1. {0,1}* (유한 이진 문자열 전체)는 가산인가? → 예. 길이별로 나열 후 길이 증가.
  2. (0,1)∩ℚ는 가산인가? → 예. ℚ의 부분집합이므로 가산.
  3. ℝ\ℚ는 가산인가? → 아니오. 비가산(연속체 크기).
  4. 대수적 수는 가산인가? → 예. (위 3-4 논증)
  5. ℕ^ℕ의 기수는? → 2^ℵ₀.
  6. ℕ×ℤ는 가산인가? → 예. ℕ×ℕ과 동일 크기.

13) 수업·블로그용 요약 문장(한 줄 버전)

  • 가산 무한집합: 자연수처럼 차례로 셀 수 있는 무한; 농도는 ℵ₀.
  • 대표 예: ℕ,ℤ,ℚ,ℕ^k, 유한 문자열, 대수적 수.
  • 실수 ℝ: 비가산; 농도는 2^ℵ₀; 대각선 논법의 귀결.
  • 기수 연산: ℵ₀+ℵ₀=ℵ₀, ℵ₀·ℵ₀=ℵ₀, ℵ₀^ℵ₀=2^ℵ₀.
  • CH: ℵ₀와 2^ℵ₀ 사이 크기의 집합이 있는지? → ZFC에서 독립.
320x100
저작자표시 비영리 변경금지 (새창열림)

'ㅡ■ Math-Text' 카테고리의 다른 글

가산 무한 vs 비가산 무한 — 유리수의 가산성과 조밀성, 그리고 “모래알 vs 모래사장 vs 실수선” 비유  (0) 2025.10.20
칸토어의 대각선 논법 — 무한 속에서 ‘더 큰 무한’을 발견하다  (1) 2025.10.04

+ Recent posts

티스토리툴바