집합론 (Set Theory)

집합론은 수학의 가장 기초적인 분야로, 모든 수학적 구조를 집합의 언어로 기술할 수 있습니다. 게오르크 칸토어(Georg Cantor)가 19세기 후반에 체계화한 이래, 집합론은 현대 수학의 토대를 형성하고 있습니다. 이 문서에서는 소박한 집합론(Naive Set Theory)의 기본 개념부터 공리적 집합론의 핵심까지 살펴봅니다.

이런 곳에 쓰여요

선수 지식: 수와 연산

난이도: ★★☆☆☆ (고등학교 기초)

집합의 정의

집합(Set)은 명확한 기준에 의하여 그 대상을 분명히 정할 수 있는 모임을 말합니다. 집합을 구성하는 각각의 대상을 원소(Element)라고 합니다.

원소 $a$가 집합 $A$에 속할 때 $a \in A$로 표기하며, 속하지 않을 때 $a \notin A$로 표기합니다.

예시로 살펴보기:

• $A = \{1, 3, 5, 7, 9\}$ (10 이하의 홀수) — $3 \in A$이고, $4 \notin A$입니다.
• $B = \{\text{사과}, \text{바나나}, \text{포도}\}$ (과일 바구니) — $\text{사과} \in B$이고, $\text{당근} \notin B$입니다.
• "우리 반에서 수학 시험 90점 이상 받은 학생들의 모임"도 집합입니다.

집합의 표현 방법

특수한 집합

• 공집합(Empty Set): 원소가 하나도 없는 집합으로 $\emptyset$ 또는 $\{\}$로 표기합니다.
• 전체집합(Universal Set): 논의의 대상이 되는 모든 원소의 집합으로 $U$로 표기합니다.
• 유한집합과 무한집합: 원소의 개수가 유한하면 유한집합, 그렇지 않으면 무한집합입니다.
• 한원소집합(Singleton): 원소가 정확히 하나인 집합. 예: $\{7\}$.

집합의 상등과 부분집합

두 집합 $A$와 $B$가 같다(Equal)는 것은 정확히 같은 원소를 가진다는 뜻입니다.

실제 증명에서는 $A \subseteq B$와 $B \subseteq A$를 각각 보여 $A = B$를 증명하는 이중 포함(Double Inclusion) 기법을 많이 사용합니다.

부분집합(Subset): $A$의 모든 원소가 $B$에도 속하면 $A$는 $B$의 부분집합입니다.

진부분집합(Proper Subset): $A \subseteq B$이고 $A \neq B$이면 $A \subsetneq B$로 표기합니다.

부분집합 관계의 성질

집합의 연산

두 집합 $A$와 $B$에 대하여 다음과 같은 기본 연산이 정의됩니다. 집합의 연산은 여러 집합을 결합하거나 비교하여 새로운 집합을 만드는 방법입니다.

합집합 (Union)

$A$와 $B$ 중 적어도 하나에 속하는 원소들의 집합입니다. "이것 또는 저것"에 해당합니다.

예시: $\{1,2,3\} \cup \{2,3,4,5\} = \{1,2,3,4,5\}$

실생활 예시: 축구 동아리 멤버가 $\{\text{민수}, \text{영희}, \text{철수}\}$이고 농구 동아리 멤버가 $\{\text{영희}, \text{철수}, \text{지은}\}$일 때, 축구 또는 농구 동아리에 속한 학생은 $\{\text{민수}, \text{영희}, \text{철수}, \text{지은}\}$입니다. 영희와 철수는 두 동아리 모두에 있지만, 합집합에서는 한 번만 셉니다.

교집합 (Intersection)

$A$와 $B$ 모두에 속하는 원소들의 집합입니다. "이것 그리고 저것"에 해당합니다.

예시: $\{1,2,3\} \cap \{2,3,4,5\} = \{2,3\}$

실생활 예시: 위의 예에서 축구 그리고 농구를 둘 다 좋아하는 학생은 $\{\text{영희}, \text{철수}\}$입니다. 검색 엔진에서 "고양이 AND 귀여운"으로 검색하면, '고양이'와 '귀여운'이 둘 다 포함된 결과만 나오는 것과 같습니다.

$A \cap B = \emptyset$이면 $A$와 $B$를 서로소(Disjoint)라고 합니다. 예를 들어, 짝수의 집합과 홀수의 집합은 공통 원소가 없으므로 서로소입니다.

차집합 (Difference)

$A$에는 속하지만 $B$에는 속하지 않는 원소들의 집합입니다. "$A$에서 $B$를 빼는" 것과 같습니다.

예시: $\{1,2,3,4\} \setminus \{2,4\} = \{1,3\}$

실생활 예시: 축구 동아리에는 가입했지만 농구 동아리에는 가입하지 않은 학생, 즉 "축구만 좋아하는 학생"을 구하는 것입니다. 위의 예에서 $A \setminus B = \{\text{민수}\}$입니다.

여집합 (Complement)

전체집합 $U$에서 집합 $A$를 뺀 나머지입니다. "$A$에 속하지 않는 모든 것"입니다.

실생활 예시: 우리 반 전체가 40명($U$)이고 수학을 좋아하는 학생이 15명($A$)이면, 수학을 좋아하지 않는 학생은 $40 - 15 = 25$명($A^c$)입니다.

대칭차집합 (Symmetric Difference)

$A$와 $B$ 중 정확히 하나에만 속하는 원소들의 집합입니다.

예시: $\{1,2,3\} \triangle \{2,3,4\} = \{1,4\}$

집합 연산의 법칙

집합 연산에는 다양한 대수적 법칙이 성립합니다. 전체집합 $U$ 아래 집합 $A$, $B$, $C$에 대하여:

분배법칙의 증명 (원소 추적)

$A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$를 증명합니다.

임의의 원소 $x$에 대하여:

따라서 $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$가 성립합니다. $\blacksquare$

드모르간 법칙

드모르간 법칙(De Morgan's Laws)은 집합 연산에서 여집합과 합집합·교집합 사이의 관계를 나타내는 중요한 법칙입니다.

첫 번째 법칙의 증명

($\subseteq$ 방향) $x \in (A \cup B)^c$라 하자.

1. $x \notin (A \cup B)$ — 여집합의 정의
2. $x \notin A$ 그리고 $x \notin B$ — 합집합의 정의의 부정
3. $x \in A^c$ 그리고 $x \in B^c$ — 여집합의 정의
4. $x \in A^c \cap B^c$ — 교집합의 정의

($\supseteq$ 방향) $x \in A^c \cap B^c$라 하자.

1. $x \in A^c$ 그리고 $x \in B^c$ — 교집합의 정의
2. $x \notin A$ 그리고 $x \notin B$ — 여집합의 정의
3. $x \notin A \cup B$ — 합집합의 정의의 부정
4. $x \in (A \cup B)^c$ — 여집합의 정의

양쪽 포함이 성립하므로 $(A \cup B)^c = A^c \cap B^c$입니다. $\blacksquare$

일반화된 드모르간 법칙

유한 또는 무한 개의 집합에 대해서도 확장됩니다.

예시: $U = \{1,2,3,4,5,6,7,8,9,10\}$, $A = \{1,2,3\}$, $B = \{3,4,5\}$일 때:

• $A \cup B = \{1,2,3,4,5\}$, $(A \cup B)^c = \{6,7,8,9,10\}$
• $A^c = \{4,5,6,7,8,9,10\}$, $B^c = \{1,2,6,7,8,9,10\}$
• $A^c \cap B^c = \{6,7,8,9,10\}$ ✓

벤 다이어그램

벤 다이어그램(Venn Diagram)은 집합과 그 관계를 시각적으로 나타내는 도구입니다. 영국의 수학자 존 벤(John Venn)이 1880년에 도입하였습니다.

두 집합의 벤 다이어그램

기본 구성

• 직사각형: 전체집합 $U$를 나타냅니다.
• 원: 개별 집합을 나타냅니다.
• 겹치는 영역: 교집합을 나타냅니다.

두 집합의 벤 다이어그램으로 표현할 수 있는 영역

세 집합의 벤 다이어그램

세 집합의 경우 총 $2^3 = 8$개의 구분 영역이 만들어지며, 이를 통해 세 집합 사이의 모든 관계를 시각적으로 파악할 수 있습니다.

포함-배제 원리

벤 다이어그램에서 유도되는 원소 개수 공식입니다.

예시: 학생 40명 중 수학 동아리 25명, 과학 동아리 20명, 두 동아리 모두 가입 10명이면 적어도 하나의 동아리에 가입한 학생 수는 $25 + 20 - 10 = 35$명입니다.

멱집합

집합 $A$의 멱집합(Power Set) $\mathcal{P}(A)$는 $A$의 모든 부분집합을 원소로 갖는 집합입니다. 쉽게 말해, 원래 집합에서 만들 수 있는 모든 "부분 모임"을 모아놓은 것입니다.

예시

$A = \{1, 2, 3\}$일 때:

원소의 개수가 $n$인 집합의 멱집합의 원소 개수는 $2^n$입니다. 위 예시에서는 $2^3 = 8$개입니다.

멱집합의 성질

• $A \subseteq B \iff \mathcal{P}(A) \subseteq \mathcal{P}(B)$
• $\mathcal{P}(A \cap B) = \mathcal{P}(A) \cap \mathcal{P}(B)$
• $\mathcal{P}(A) \cup \mathcal{P}(B) \subseteq \mathcal{P}(A \cup B)$ (일반적으로 등호 불성립)

카르테시안 곱

카르테시안 곱(Cartesian Product)은 두 집합의 원소로 만든 순서쌍(Ordered Pair)의 집합입니다. 순서쌍 $(a, b)$에서는 순서가 중요합니다. 즉 $(1, 2) \neq (2, 1)$입니다.

예시

$A = \{1, 2\}$, $B = \{x, y, z\}$일 때:

$|A \times B| = |A| \cdot |B| = 2 \times 3 = 6$입니다.

카르테시안 곱은 일반적으로 교환법칙이 성립하지 않습니다. 즉, $A \times B \neq B \times A$입니다(단, $A = B$이거나 둘 중 하나가 공집합인 경우는 예외입니다).

$n$중 카르테시안 곱

특히 $A \times A$는 $A^2$로 표기하며, 평면 좌표 $\mathbb{R}^2 = \mathbb{R} \times \mathbb{R}$이 대표적인 예입니다.

카르테시안 곱과 집합 연산

• $A \times (B \cup C) = (A \times B) \cup (A \times C)$
• $A \times (B \cap C) = (A \times B) \cap (A \times C)$
• $A \times (B \setminus C) = (A \times B) \setminus (A \times C)$
• $(A \cup B) \times C = (A \times C) \cup (B \times C)$

관계

집합 $A$에서 집합 $B$로의 관계(Relation)는 카르테시안 곱 $A \times B$의 부분집합 $R \subseteq A \times B$입니다. $(a, b) \in R$일 때 $a \mathrel{R} b$로 표기합니다.

집합 $A$ 위의 관계의 성질

관계 $R \subseteq A \times A$에 대하여:

동치관계 (Equivalence Relation)

반사적이고 대칭적이며 추이적인 관계를 동치관계라 하고, 흔히 $\sim$으로 표기합니다.

예시: 정수 집합에서 "mod $n$ 합동" 관계 — $a \sim b \iff n \mid (a - b)$.

동치관계 $\sim$이 주어지면 각 원소 $a$에 대한 동치류(Equivalence Class)를 정의합니다.

모든 동치류의 모임은 $A$의 분할(Partition)을 형성합니다. 즉, 서로 다른 동치류는 서로소이고, 모든 동치류의 합집합은 $A$ 전체입니다.

순서관계 (Order Relation)

반사적이고 반대칭적이며 추이적인 관계를 반순서(Partial Order)라 하고, $(A, \leq)$를 반순서집합(Poset)이라 합니다.

반순서에서 모든 두 원소가 비교 가능하면($a \leq b$ 또는 $b \leq a$) 전순서(Total Order)라 합니다.

• 반순서 예: $(\mathcal{P}(\{1,2,3\}), \subseteq)$ — $\{1\}$과 $\{2\}$는 비교 불가능
• 전순서 예: $(\mathbb{R}, \leq)$ — 임의의 두 실수는 비교 가능

함수

집합 $A$에서 집합 $B$로의 함수(Function) $f: A \to B$는 관계의 특별한 경우로, $A$의 각 원소에 $B$의 원소가 정확히 하나 대응되는 관계입니다.

함수의 유형

함수의 합성과 역함수

$f: A \to B$, $g: B \to C$일 때 합성함수 $g \circ f: A \to C$는 $(g \circ f)(a) = g(f(a))$로 정의됩니다.

• $f$와 $g$가 모두 단사이면 $g \circ f$도 단사입니다.
• $f$와 $g$가 모두 전사이면 $g \circ f$도 전사입니다.
• $f$가 전단사이면 역함수 $f^{-1}: B \to A$가 존재하고, $f^{-1} \circ f = \text{id}_A$, $f \circ f^{-1} = \text{id}_B$입니다.

상(Image)과 역상(Preimage)

$f: A \to B$이고 $S \subseteq A$, $T \subseteq B$일 때:

역상은 집합 연산을 잘 보존합니다:

• $f^{-1}(T_1 \cup T_2) = f^{-1}(T_1) \cup f^{-1}(T_2)$
• $f^{-1}(T_1 \cap T_2) = f^{-1}(T_1) \cap f^{-1}(T_2)$
• $f^{-1}(T^c) = (f^{-1}(T))^c$

집합의 크기 (기수)

유한집합의 크기는 원소의 개수 $|A|$로 자연스럽게 정의됩니다. 그러나 무한집합에서도 "크기"를 비교할 수 있을까요?

대등 (Equinumerous)

두 집합 $A$와 $B$ 사이에 전단사 함수가 존재하면 $A$와 $B$는 대등(Equinumerous)하다고 하고, $|A| = |B|$ 또는 $A \sim B$로 표기합니다.

가산집합과 비가산집합

자연수 집합 $\mathbb{N}$과 대등한 집합을 가산 무한(Countably Infinite)이라 합니다. 유한이거나 가산 무한인 집합을 통틀어 가산(Countable)이라 합니다. "가산"이란 원소를 첫 번째, 두 번째, 세 번째, ... 하고 번호를 매겨 나열할 수 있다는 뜻입니다.

칸토어의 대각선 논법

실수 집합 $\mathbb{R}$이 비가산임을 보이는 칸토어의 유명한 증명입니다. 이 증명은 수학 역사상 가장 아름답고 놀라운 논증 중 하나로 꼽힙니다.

증명 (귀류법): $(0, 1)$의 실수가 가산이라고 가정하면 다음과 같이 나열할 수 있습니다:

새로운 실수 $r^* = 0.d_1^* d_2^* d_3^* \cdots$를 다음과 같이 구성합니다: $d_n^* \neq d_{nn}$ (예를 들어, $d_{nn} = 5$이면 $d_n^* = 6$, 그 외에는 $d_n^* = 5$).

그러면 $r^*$는 모든 $r_n$과 $n$번째 소수점 자릿수에서 다르므로, 나열에 포함되지 않습니다. 이는 모든 실수를 나열했다는 가정에 모순입니다. $\blacksquare$

칸토어의 정리

임의의 집합 $A$에 대하여 $|A| < |\mathcal{P}(A)|$입니다. 즉, 어떤 집합이든 그 멱집합보다 작습니다.

이 정리는 무한의 "크기"가 하나가 아니라 무한히 많은 단계로 이루어져 있음을 보여줍니다:

공리적 집합론

소박한 집합론에서는 "모든 성질 $P$에 대해 $\{x \mid P(x)\}$가 집합이다"라고 가정합니다. 그러나 이 가정은 모순을 초래합니다.

러셀의 역설 (Russell's Paradox)

$R = \{x \mid x \notin x\}$로 정의하면:

• $R \in R$이면 정의에 의해 $R \notin R$ — 모순
• $R \notin R$이면 정의에 의해 $R \in R$ — 모순

이 역설은 무제한적인 집합 구성이 불가능함을 보여주었고, 공리적 집합론의 필요성을 제기했습니다.

ZFC 공리계

체르멜로-프렝켈 공리계에 선택 공리를 추가한 ZFC(Zermelo–Fraenkel with Choice)는 현대 수학의 표준 기초입니다.

선택 공리와 동치 명제들

선택 공리(Axiom of Choice, AC)는 직관적으로 자명해 보이지만, 놀라운 결과들과 동치입니다:

• 초른의 보조정리(Zorn's Lemma): 모든 사슬이 상계를 가지는 반순서집합은 극대원소를 가진다.
• 정렬 원리(Well-Ordering Theorem): 모든 집합은 정렬 가능하다.
• 티호노프 정리: 콤팩트 공간의 임의의 곱은 콤팩트이다.

선택 공리에서 유도되는 반직관적인 결과로는 바나흐-타르스키 역설(구를 유한 조각으로 분해한 후 재조립하면 같은 크기의 구 두 개를 만들 수 있다)이 있습니다.

첨수 가족과 일반화된 연산

집합들의 모임을 첨수 집합(Index Set) $I$로 표현하면 다양한 연산을 일반화할 수 있습니다.

정의

첨수 집합 $I$에 대하여 첨수 가족(Indexed Family) $\{A_i\}_{i \in I}$는 각 $i \in I$에 집합 $A_i$를 대응시키는 함수입니다.

일반화된 합집합과 교집합

예시: $A_n = \left(-\frac{1}{n}, \frac{1}{n}\right)$, $n \in \mathbb{N}^+$이면:

일반화된 카르테시안 곱

선택 공리는 정확히 "$\prod_{i \in I} A_i \neq \emptyset$이다 (모든 $A_i \neq \emptyset$일 때)"라는 주장과 동치입니다.

순서수와 기수 (개요)

집합론에서는 자연수를 순서수(Ordinal)로 구성합니다.

폰 노이만 순서수

각 자연수를 다음과 같이 정의합니다:

일반적으로 $n = \{0, 1, 2, \ldots, n-1\}$이며, 후속자 연산은 $S(n) = n \cup \{n\}$입니다.

초한 순서수

모든 자연수 뒤의 첫 번째 극한 순서수가 $\omega$입니다:

$\omega$ 이후에도 $\omega + 1, \omega + 2, \ldots, \omega \cdot 2, \ldots, \omega^2, \ldots, \omega^\omega, \ldots$와 같이 순서수가 계속됩니다.

집합 항등식 증명 — 세 가지 방법 비교

집합 등식을 증명하는 데에는 크게 세 가지 방법이 사용됩니다. 같은 항등식 $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$를 세 가지 방법으로 모두 증명하여 비교하겠습니다.

방법 1: 원소 추적법 (Element-chasing)

임의의 원소 $x$를 잡고, 양변에 속하는 조건이 논리적으로 동치임을 보이는 방법입니다. 가장 보편적이며 엄밀한 증명법입니다.

임의의 $x$에 대하여:

모든 단계가 동치($\iff$)이므로 등식이 성립합니다. $\blacksquare$

방법 2: 벤 다이어그램에 의한 검증

세 집합 $A$, $B$, $C$로 만들어지는 8개 영역 각각에 대하여, 좌변과 우변에 포함되는지 여부를 확인합니다.

⑤열과 ⑧열이 모든 행에서 일치하므로 $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$가 성립합니다. $\blacksquare$

방법 3: 대수적 방법 (집합 대수)

이미 증명된 집합 법칙(교환, 결합, 흡수 등)만을 사용하여 한쪽 변을 다른 쪽으로 변환합니다.

사실 분배법칙 자체를 대수적으로 유도하려면 순환 논법이 됩니다. 따라서 대수적 방법은 이미 확립된 법칙들로부터 새로운 항등식을 유도할 때 위력을 발휘합니다. 예를 들어:

이처럼 대수적 방법은 기존 법칙의 조합으로 깔끔하게 새 결과를 얻을 수 있습니다. $\blacksquare$

함수의 단사·전사·전단사 판정

함수 $f: A \to B$가 단사/전사/전단사인지 판정하는 다양한 방법을 정리합니다.

단사(Injective) 판정법

방법 1: 정의 직접 사용

$f(a_1) = f(a_2)$를 가정하고 $a_1 = a_2$를 유도합니다.

예시: $f: \mathbb{R} \to \mathbb{R}$, $f(x) = 2x + 3$

방법 2: 대우 사용

$a_1 \neq a_2$이면 $f(a_1) \neq f(a_2)$임을 보입니다. 단조함수(순증가 또는 순감소)의 단사성을 보일 때 유용합니다.

예시: $f(x) = x^3$은 순증가이므로 $a_1 \neq a_2 \implies a_1^3 \neq a_2^3$ $\quad\checkmark$

방법 3: 좌역함수(Left Inverse) 존재

$g \circ f = \text{id}_A$인 $g: B \to A$가 존재하면 $f$는 단사입니다.

증명: $f(a_1) = f(a_2)$이면 $a_1 = g(f(a_1)) = g(f(a_2)) = a_2$ $\quad\blacksquare$

방법 4: 핵(Kernel) 확인 (선형사상의 경우)

선형사상 $T: V \to W$에서 $\ker T = \{\mathbf{0}\}$이면 $T$는 단사입니다. 이 방법은 선형대수학에서 중심적으로 사용됩니다.

전사(Surjective) 판정법

방법 1: 정의 직접 사용

임의의 $b \in B$에 대하여 $f(a) = b$인 $a \in A$를 구성합니다.

예시: $f: \mathbb{R} \to \mathbb{R}$, $f(x) = 2x + 3$. 임의의 $y \in \mathbb{R}$에 대해 $x = \frac{y-3}{2}$로 두면 $f(x) = y$ $\quad\checkmark$

방법 2: 치역과 공역 비교

$\text{Im}(f) = B$임을 직접 확인합니다. 치역을 구한 뒤 공역과 같은지 비교합니다.

방법 3: 우역함수(Right Inverse) 존재

$f \circ h = \text{id}_B$인 $h: B \to A$가 존재하면 $f$는 전사입니다. (이 방향은 선택 공리를 필요로 합니다.)

전단사(Bijective) 판정법

다음 조건들은 모두 동치입니다:

• $f$가 단사이고 전사
• 역함수 $f^{-1}: B \to A$가 존재
• 유한집합의 경우: $|A| = |B|$이고 $f$가 단사 (또는 전사)

가산성 — 전단사 구성의 다양한 방법

무한집합이 자연수 집합과 같은 크기(가산)임을 보이려면 전단사 함수를 명시적으로 구성해야 합니다. 여기서는 $\mathbb{Z}$와 $\mathbb{Q}$에 대하여 여러 가지 전단사 구성법을 제시합니다.

$\mathbb{N}$과 $\mathbb{Z}$의 전단사

방법 1: 교대 나열

$0, 1, -1, 2, -2, 3, -3, \ldots$ 순서로 나열합니다. 명시적 함수:

예: $f(0) = 0$, $f(1) = -1$, $f(2) = 1$, $f(3) = -2$, $f(4) = 2$, $\ldots$

방법 2: 절댓값 기준 정렬

예: $g(0) = 1$, $g(1) = 2$, $g(-1) = 3$, $g(2) = 4$, $g(-2) = 5$, $\ldots$

$\mathbb{N}$과 $\mathbb{Q}^+$의 전단사

방법 1: 칸토어의 지그재그(대각선 열거)

양의 유리수를 $p/q$ 격자 위에 배열한 뒤, 대각선 방향으로 지그재그 순회하면서 기약분수만 선택합니다:

방법 2: 스턴-브로코 트리(Stern–Brocot Tree)

스턴-브로코 트리는 모든 양의 유리수를 정확히 한 번씩 기약분수 형태로 포함하는 이진 트리입니다. 루트를 $1/1$로 놓고, 메디안트(mediant) $\frac{a+c}{b+d}$를 이용하여 트리를 구축합니다. 너비 우선 탐색(BFS)으로 방문하면 자연수와의 전단사를 얻습니다.

방법 3: 쌍함수(Pairing Function)

칸토어 쌍함수 $\pi: \mathbb{N} \times \mathbb{N} \to \mathbb{N}$을 사용합니다:

이 함수는 $\mathbb{N}^2 \to \mathbb{N}$의 전단사이며, $\mathbb{Q}^+ \hookrightarrow \mathbb{N}^2$ ($p/q \mapsto (p, q)$)이므로 가산성이 따릅니다.

비가산성 — 칸토어의 두 가지 증명

실수 집합의 비가산성을 칸토어는 두 가지 서로 다른 방법으로 증명하였습니다.

증명 1: 대각선 논법 (1891)

이 증명은 위에서 이미 소개하였습니다. 핵심은 "나열된 모든 실수의 $n$번째 자릿수와 다른 수를 구성"하는 것입니다.

증명 2: 구간 축소법 (1874, 칸토어의 최초 증명)

$[0,1]$의 실수를 $r_1, r_2, r_3, \ldots$로 나열했다고 가정합니다.

1. $r_1$을 포함하지 않는 닫힌 구간 $[a_1, b_1] \subseteq [0, 1]$을 잡습니다.
2. $r_2$를 포함하지 않는 $[a_2, b_2] \subseteq [a_1, b_1]$을 잡습니다.
3. 이 과정을 반복하여 축소하는 닫힌 구간의 수열 $[a_1, b_1] \supseteq [a_2, b_2] \supseteq \cdots$를 얻습니다.
4. 칸토어의 구간 축소 정리(실수의 완비성)에 의해 $\bigcap_{n=1}^{\infty} [a_n, b_n] \neq \emptyset$이므로, 교집합에 속하는 실수 $r^*$는 모든 $r_n$과 다릅니다.

이는 모순이므로 $[0,1]$은 가산이 아닙니다. $\blacksquare$

칸토어 정리의 증명

정리: 임의의 집합 $A$에 대해 $A$에서 $\mathcal{P}(A)$로의 전사 함수는 존재하지 않습니다. 따라서 $|A| < |\mathcal{P}(A)|$입니다.

증명: $f: A \to \mathcal{P}(A)$가 전사라고 가정합니다. 다음 집합을 정의합니다:

$D \subseteq A$이므로 $D \in \mathcal{P}(A)$입니다. $f$가 전사이므로 $f(d) = D$인 $d \in A$가 존재합니다. 그런데:

• $d \in D$이면, $D$의 정의에 의해 $d \notin f(d) = D$ — 모순
• $d \notin D$이면, $D$의 정의에 의해 $d \in f(d) = D$ — 모순

어느 경우든 모순이므로 전사 함수 $f$는 존재하지 않습니다. $\blacksquare$

기수 산술과 연속체 가설

기수(Cardinal Number)는 집합의 크기를 나타내는 수입니다. 유한 기수는 자연수와 같지만, 초한 기수는 고유한 산술 규칙을 따릅니다.

기수의 비교

$|A| \leq |B|$는 단사 함수 $f: A \hookrightarrow B$가 존재할 때 정의됩니다.

초한 기수의 산술

$\kappa$, $\lambda$가 무한 기수이고 $\kappa \geq \lambda \geq \aleph_0$이면:

초한 기수의 덧셈과 곱셈은 "큰 쪽이 이기는" 규칙을 따르지만, 거듭제곱은 기수를 진정으로 키웁니다.

연속체 가설 (CH)

일반화된 연속체 가설 (GCH): 모든 순서수 $\alpha$에 대하여 $2^{\aleph_\alpha} = \aleph_{\alpha + 1}$이다.

괴델(1940)은 ZFC가 무모순이면 ZFC + CH도 무모순임을 구성적 전체(constructible universe) $L$을 사용하여 보였습니다. 코엔(1963)은 강제법(forcing)을 발명하여 ZFC + $\neg$CH도 무모순임을 보였습니다. 따라서 연속체 가설은 ZFC에서 독립입니다.

순서수 — 초한 귀납법과 초한 재귀

정렬순서 (Well-Ordering)

전순서집합 $(W, \leq)$에서 모든 비어있지 않은 부분집합이 최소원소를 가지면 정렬순서(Well-Ordering)라 합니다.

• 정렬순서 예: $(\mathbb{N}, \leq)$ — 자연수의 모든 비어있지 않은 부분집합은 최솟값을 가집니다.
• 정렬순서가 아닌 예: $(\mathbb{Z}, \leq)$ — $\mathbb{Z}$ 자체에 최솟값이 없습니다.

초한 귀납법 (Transfinite Induction)

정렬순서집합 $(W, \leq)$ 위에서 성질 $P$를 증명하려면:

1. 기저 단계: $P(\min W)$를 증명
2. 후속자 단계: $P(\alpha) \implies P(\alpha + 1)$을 증명
3. 극한 단계: 극한 순서수 $\lambda$에 대해, 모든 $\beta < \lambda$에서 $P(\beta)$이면 $P(\lambda)$를 증명

이 세 단계가 모두 성립하면, 모든 $\alpha \in W$에 대해 $P(\alpha)$가 성립합니다.

초한 재귀 (Transfinite Recursion)

초한 재귀 정리는 순서수에 대한 함수를 재귀적으로 정의할 수 있음을 보장합니다:

여기서 $F \restriction \alpha$는 $\alpha$보다 작은 모든 순서수에서의 $F$의 값입니다. 이 정리의 응용 예:

• 폰 노이만 계층: $V_0 = \emptyset$, $V_{\alpha+1} = \mathcal{P}(V_\alpha)$, $V_\lambda = \bigcup_{\beta < \lambda} V_\beta$
• 순서수 산술: $\alpha + 0 = \alpha$, $\alpha + (\beta + 1) = (\alpha + \beta) + 1$, $\alpha + \lambda = \sup_{\beta < \lambda}(\alpha + \beta)$
• 하트독스 수: 임의의 집합 $A$에 대해 $A$에 단사로 매장할 수 없는 최소 순서수 $\aleph(A)$의 존재

순서수 산술의 비교환성

순서수의 덧셈과 곱셈은 교환법칙이 성립하지 않습니다:

$1 + \omega = \omega$인 이유: $\{*\} \cup \{0, 1, 2, \ldots\}$는 $*$을 가장 앞에 놓으면 $\omega$와 같은 순서형을 가집니다. 반면 $\omega + 1 = \{0, 1, 2, \ldots, *\}$는 자연수 뒤에 원소 하나가 더 있으므로 $\omega$와 다른 순서형입니다.

선택 공리와 동치 명제들

선택 공리(AC)는 현대 수학에서 가장 논쟁적이면서도 불가결한 공리입니다. 직관적으로는 당연해 보이지만, 놀라운 결과들을 함축합니다.

동치 명제들의 상세

1. 초른의 보조정리 (Zorn's Lemma)

반순서집합 $(P, \leq)$에서 모든 사슬(전순서 부분집합)이 상계를 가지면, $P$는 극대원소를 가진다.

응용:

• 모든 벡터공간은 기저를 가진다 (하멜 기저의 존재)
• 모든 진이데알은 극대이데알에 포함된다
• 모든 필터는 초필터로 확장된다

2. 정렬 원리 (Well-Ordering Theorem)

모든 집합은 정렬순서를 부여할 수 있다.

이 정리는 체르멜로가 1904년에 증명하였으며, 선택 공리를 최초로 명시적으로 사용한 결과입니다. 직관적으로는 $\mathbb{R}$에 정렬순서를 부여할 수 있다는 뜻이지만, 그 정렬순서를 명시적으로 구성하는 것은 불가능합니다.

3. 티호노프 정리 (Tychonoff's Theorem)

콤팩트 위상공간의 임의의(무한 포함) 곱공간은 곱위상에서 콤팩트이다.

유한 개의 곱에 대해서는 선택 공리 없이도 증명 가능하지만, 무한 곱에 대해서는 AC가 필수적입니다. 실제로 켈리(Kelley, 1950)는 티호노프 정리가 AC와 동치임을 보였습니다.

동치관계와 분할의 대응

관계 절에서 동치관계와 분할의 대응을 간략히 언급하였습니다. 여기서는 이 대응을 엄밀하게 증명합니다.

정의 복습

동치관계: 반사적, 대칭적, 추이적인 관계 $\sim$ (집합 $A$ 위)

분할: $A$의 부분집합들의 모임 $\{B_i\}_{i \in I}$로서 (1) 각 $B_i \neq \emptyset$, (2) $i \neq j$이면 $B_i \cap B_j = \emptyset$, (3) $\bigcup_{i \in I} B_i = A$

정리: 동치관계 → 분할

$\sim$이 $A$ 위의 동치관계이면, 동치류들의 모임 $A/{\sim} = \{[a] \mid a \in A\}$는 $A$의 분할입니다.

증명:

1. 비어있지 않음: 반사성에 의해 $a \in [a]$이므로 $[a] \neq \emptyset$.
2. 서로소: $[a] \cap [b] \neq \emptyset$이면 어떤 $c \in [a] \cap [b]$가 존재합니다. 그러면 $c \sim a$이고 $c \sim b$입니다. 대칭성과 추이성에 의해 $a \sim b$이므로 $[a] = [b]$입니다. 대우를 취하면 $[a] \neq [b]$이면 $[a] \cap [b] = \emptyset$.
3. 합집합이 $A$: 반사성에 의해 모든 $a \in A$는 $a \in [a]$이므로 $A \subseteq \bigcup [a]$. 역 포함은 자명합니다.

$\blacksquare$

정리: 분할 → 동치관계

$\{B_i\}_{i \in I}$가 $A$의 분할이면, $a \sim b \iff$ 어떤 $i$에 대해 $a, b \in B_i$로 정의한 $\sim$은 동치관계입니다.

증명:

1. 반사성: $a \in A$이면 분할의 조건 (3)에 의해 어떤 $B_i$에 $a \in B_i$이므로 $a \sim a$.
2. 대칭성: $a \sim b$이면 $a, b \in B_i$이므로 $b, a \in B_i$, 즉 $b \sim a$.
3. 추이성: $a \sim b$이고 $b \sim c$이면 $a, b \in B_i$이고 $b, c \in B_j$입니다. $b \in B_i \cap B_j$이므로 조건 (2)에 의해 $B_i = B_j$. 따라서 $a, c \in B_i$이므로 $a \sim c$.

$\blacksquare$

예시: 모듈러 산술

$\mathbb{Z}$ 위에서 $a \equiv b \pmod{3}$으로 정의한 동치관계의 동치류:

이 세 동치류는 $\mathbb{Z}$의 분할을 형성하며, 몫집합 $\mathbb{Z}/3\mathbb{Z} = \{[0], [1], [2]\}$는 3개의 원소를 가집니다.

순서관계의 분류

순서관계는 수학 전반에 걸쳐 핵심적인 역할을 합니다. 여기서는 부분순서, 전순서, 정렬순서를 체계적으로 비교합니다.

부분순서 (Partial Order)

반사적, 반대칭적, 추이적인 관계. 모든 원소 쌍이 비교 가능할 필요는 없습니다.

대표적 예:

• $(\mathcal{P}(S), \subseteq)$ — 부분집합 관계
• $(\mathbb{N}, \mid)$ — 정수의 약수 관계 ($a \mid b$: $a$가 $b$의 약수)

전순서 (Total Order, Linear Order)

부분순서이면서 비교가능성을 추가로 만족합니다: 모든 $a, b$에 대해 $a \leq b$ 또는 $b \leq a$.

대표적 예: $(\mathbb{R}, \leq)$, $(\mathbb{Z}, \leq)$, 사전식 순서

정렬순서 (Well-Order)

전순서이면서 모든 비어있지 않은 부분집합이 최소원소를 가지는 순서.

부분순서집합의 중요 개념

부분순서집합 $(P, \leq)$에서:

• 상계(Upper Bound): 부분집합 $S$의 모든 원소 이상인 원소
• 하계(Lower Bound): 부분집합 $S$의 모든 원소 이하인 원소
• 상한(Supremum, lub): 상계들 중 가장 작은 것
• 하한(Infimum, glb): 하계들 중 가장 큰 것
• 극대원소(Maximal): $m \leq a$이면 $m = a$인 원소 (최대와 다름!)
• 최대원소(Maximum): 모든 $a$에 대해 $a \leq m$인 원소

집합론의 역설과 해결

소박한 집합론(Naive Set Theory)의 무제한적 집합 구성 원리는 여러 역설을 초래하였으며, 이는 공리적 집합론의 발전을 촉진하였습니다.

러셀의 역설 (1901)

"자기 자신을 포함하지 않는 모든 집합의 집합"은 모순을 초래합니다. $R = \{x \mid x \notin x\}$로 정의하면, $R \in R$과 $R \notin R$ 중 어느 쪽도 모순 없이 성립할 수 없습니다.

칸토어의 역설 (1899)

"모든 집합의 집합" $V$가 존재한다고 가정하면, 칸토어 정리에 의해 $|V| < |\mathcal{P}(V)|$이어야 합니다. 그런데 $\mathcal{P}(V) \subseteq V$이므로(모든 집합의 집합이니까) $|\mathcal{P}(V)| \leq |V|$, 모순입니다.

부랄리-포르티의 역설 (1897)

"모든 순서수의 집합" $\Omega$가 존재한다고 가정하면, $\Omega$ 자체가 정렬집합이므로 순서수입니다. 그러면 $\Omega \in \Omega$이 되는데, 순서수의 정의에 의해 $\Omega < \Omega$이 되어 모순입니다.

역설의 해결: 공리적 집합론

이 역설들은 공통적으로 "너무 큰 모임"을 집합으로 취급한 데서 비롯됩니다. 해결책들:

참고자료

• Halmos, P. R. — Naive Set Theory, Springer, 1974
• Enderton, H. B. — Elements of Set Theory, Academic Press, 1977
• Jech, T. — Set Theory, Springer, 2003
• Hrbáček, K. & Jech, T. — Introduction to Set Theory, Marcel Dekker, 1999
• Kunen, K. — Set Theory: An Introduction to Independence Proofs, North-Holland, 1980
• Devlin, K. — The Joy of Sets, Springer, 1993
• 논리학 — 드모르간 법칙의 논리적 기초
• 이산수학 — 집합과 관계의 응용
• 수 체계 — 집합론적 수의 구성
• 추상대수학 — 집합 위의 대수적 구조