베르 범주 정리

01 Dec 2024

1. 베르 공간

정리. $S$가 위상공간 $X$의 부분집합일 때, 다음은 동치이다.

• $\left( \operatorname{cl}S \right)^\circ$가 공집합이다.
• $(\operatorname{cl}S)^c$가 조밀하다.
• $S$는 어떠한 $X$의 열린 집합에서도 조밀하지 않다.

이때, $S$를 희박(rare)하다고 한다.

정의. 희박한 닫힌 집합들의 가산 합집합 $\bigcup F_n$이 희박한 공간 $X$를 베르 공간이라고 한다.

Remark. $X$가 베르 공간이다 iff $X$의 열린 조밀 집합들의 가산 교집합은 조밀하다.

예시. $\mathbb{Q}$는 베르 공간이 아니다.

• $\lbrace q \rbrace$는 닫힌 희박 집합이지만 $\bigcup_{q \in \mathbb{Q}} \lbrace q\rbrace = \mathbb{Q}$는 희박하지 않다.
• $\mathbb{Q} \setminus \lbrace q \rbrace$는 열린 조밀 집합이지만 $\bigcap_{q \in \mathbb{Q}} \left( \mathbb{Q} \setminus \lbrace q \rbrace \right) = \varnothing$은 조밀하지 않다.

2. 베르 범주 정리

콤팩트 공간에서의 칸토어 축소 정리. 다음은 동치이다.

1. $X$가 콤팩트하다.
2. 임의의 유한 교집합 속성을 가진 닫힌 집합들의 모임 $\mathcal{C}$에 대해 $\bigcap_{C \in \mathcal{C}} C \neq \varnothing$이다.

완비 거리 공간에서의 칸토어 축소 정리. 다음은 동치이다.

3. $X$가 완비 거리 공간이다.
4. 임의의 공집합이 없는 닫힌 집합열 $C_1 \supset C_2 \supset \cdots$에 대해 $\bigcap C_n \neq \varnothing$이며, 특히 $\operatorname{diam}C_n \to 0$일 때 $\bigcap C_n$은 홑원소 집합이다.

Remark. 2는 4를 함의한다. 이로부터 콤팩트 거리 공간은 완비임을 보일 수 있다. 역은 성립하지 않는다.

정리. 완비 거리 공간과 콤팩트 하우스도르프 공간은 베르 공간이다.

증명.

$X$가 완비 거리 공간 또는 콤팩트 하우스도르프 공간이라고 하자. 희박한 닫힌 집합들의 가산 모임 $\lbrace F_n \rbrace$이 주어졌을 때, 임의의 열린 집합 $U$에 대해 $U \not\subset \bigcup F_n$임을 보이면 된다. 이를 위해 $\forall n : x \not\in F_n$인 $x \in U$를 찾을 것이다.

$F_1$이 희박하므로 $x_1 \in U \setminus F_1$이 존재한다. $X$는 정칙 공간이므로 $x_1 \in U_1$, $\overline{U_1} \cap F_1 = \varnothing$인 열린 집합 $U_1$이 존재한다. 귀납적으로 다음과 같이 정의할 수 있다.

• $x_n \in U_n \setminus F_n$
• $U_n \subset U_{n - 1}$
• $\overline{U_n} \cap F_n = \varnothing$

칸토어 축소 정리에 의해 $x \in \bigcap \overline{U_n}$인 $x$가 존재한다.

3. 베르 범주 정리의 응용

연속함수열의 수렴은 거의 연속이다. $\lbrace f_n : X → (Y, d) \rbrace$가 $f$로 수렴하는 연속함수열일 때,

\[S = \lbrace x \in X : f\text{ is continuous at } x \rbrace\]

는 $X$에서 조밀하다.

KAIST POW2024-20. $f$가 연속함수이고,

\[\forall x \geq 0 : \lim_{n \to \infty} f(nx) = 0\]

라면 $\lim_{x \to \infty} f(x) = 0$이다.

병리적 함수의 존재성. $h : [0, 1] → \mathbb{R}$가 연속함수라고 하자. 임의의 $ε > 0$에 대해 다음을 만족하는 함수 $g : [0,1] → \mathbb{R}$가 존재한다.

• $\lVert h − g\rVert < ε$이다.
• $g$는 전 구간에서 연속이다.
• $g$는 전 구간에서 미분 불가능하다.

The Baire Category Theorem

01 Dec 2024

1. Baire Spaces

Theorem. Let $S$ be a subset of a topological space $X$. The following are equivalent:

• $\left( \operatorname{cl}S \right)^\circ$ is empty.
• $(\operatorname{cl}S)^c$ is dense.
• $S$ is not dense in any open set of $X$.

Such a set $S$ is said to be rare (or nowhere dense).

Definition. A space $X$ is called a Baire space if every countable union $\bigcup F_n$ of rare closed sets is rare.

Remark. $X$ is a Baire space iff every countable intersection of open dense sets in $X$ is dense.

Example. $\mathbb{Q}$ is not a Baire space.

• $\lbrace q \rbrace$ is a rare closed set, but $\bigcup_{q \in \mathbb{Q}} \lbrace q\rbrace = \mathbb{Q}$ is not rare.
• $\mathbb{Q} \setminus \lbrace q \rbrace$ is a dense open set, but $\bigcap_{q \in \mathbb{Q}} \left( \mathbb{Q} \setminus \lbrace q \rbrace \right) = \varnothing$ is not dense.

2. The Baire Category Theorem

Cantor’s Theorem on Compact Spaces. The following are equivalent:

1. $X$ is compact.
2. For any collection $\mathcal{C}$ of closed sets with the finite intersection property, $\bigcap_{C \in \mathcal{C}} C \neq \varnothing$.

Cantor's Theorem on Complete Metric Spaces. The following are equivalent:

3. $X$ is a complete metric space.
4. For any nonempty sequence of closed sets $C_1 \supseteq C_2 \supseteq \cdots$, we have $\bigcap C_n \neq \varnothing$, and in particular, when $\operatorname{diam}C_n \to 0$, $\bigcap C_n$ is a singleton.

Remark. Statement 2 implies statement 4. From this, one can show that compact metric spaces are complete. The converse does not hold.

Theorem. Complete metric spaces and compact Hausdorff spaces are Baire spaces.

Proof.

Let $X$ be a complete metric space or a compact Hausdorff space. Given a countable collection $\lbrace F_n \rbrace$ of rare closed sets, we shall show that for any open set $U$, we have $U \not\subset \bigcup F_n$. To this end, we shall find $x \in U$ such that $\forall n : x \not\in F_n$.

Since $F_1$ is rare, there exists $x_1 \in U \setminus F_1$. As $X$ is a regular space, there exists an open set $U_1$ such that $x_1 \in U_1$ and $\overline{U_1} \cap F_1 = \varnothing$. Inductively, we define:

• $x_n \in U_n \setminus F_n$
• $U_n \subset U_{n - 1}$
• $\overline{U_n} \cap F_n = \varnothing$

By Cantor’s theorem, there exists $x \in \bigcap \overline{U_n}$.

3. Applications of the Baire Category Theorem

Convergence of continuous function sequences is almost continuous. Let $\lbrace f_n : X → (Y, d) \rbrace$ be a sequence of continuous functions converging to $f$. Then

\[S = \lbrace x \in X : f\text{ is continuous at } x \rbrace\]

is dense in $X$.

KAIST POW2024-20. Let $f$ be a continuous function such that

\[\forall x \geq 0 : \lim_{n \to \infty} f(nx) = 0\]

Then $\lim_{x \to \infty} f(x) = 0$.

Existence of pathological functions. Let $h : [0, 1] → \mathbb{R}$ be a continuous function. For any $ε > 0$, there exists a function $g : [0,1] → \mathbb{R}$ satisfying:

• $\lVert h − g\rVert < ε$.
• $g$ is continuous on the entire interval.
• $g$ is differentiable nowhere.

정렬의 삼분성과 서수의 완전성

21 Nov 2024

1. 기본 개념

정의. 다음을 만족하는 $(W, <)$를 정렬 집합_{well-ordered set}이라고 한다.

1. $(W, <)$은 전순서이다.
2. $W$의 임의의 부분집합은 최소 원소를 가진다.

정의. $(W, <)$가 정렬 집합일 때, $a \in S$에 대해 $x < a \rightarrow x \in S$인 $W$의 부분집합 $S$를 초기단_{initial segment}이라고 한다.

정리. $S$가 정렬 집합 $(W, <)$의 초기단일 때, 어떤 $a \in W$에 대해 다음이 성립한다.

\[S = W[a] := \lbrace x \in W : x < a \rbrace\]

증명. $a$를 $W \setminus S$의 최솟값으로 잡는다.

2. 정렬의 삼분성

정리.

1. 정렬 집합은 자신의 초기단과 동형일 수 없다.
2. 정렬 집합의 자기동형사상은 항등사상이다.
3. 두 정렬 집합 간 동형사상은 유일하다.

증명.

보조정리. $f: (W, <) → (W, <)$가 순서 보존이라면 $x \in W$에 대해 $x \leq f(x)$이다.

보조정리의 증명.

귀류법에 따라 $S = \lbrace x \in W : x > f(x) \rbrace$가 공집합이 아니라고 하자. $W$는 정렬 집합이므로 $c = \min S$가 존재한다. $c \in S$이므로 $c > f(c)$이며, $f$가 순서 보존이므로 $f(c) > f(f(c))$이다. 한편 $c = \min S$이므로 $f(c) \notin S$이며, $f(f(c)) \geq f(c)$이므로 모순이다. □

(1)의 증명.

$f: (W, <) → (W[a], <)$가 동형사상이라고 하자. 포함사상 $j: W[a] → W$에 대해 $jf: (W, <) → (W, <)$는 순서 보존이다. 따라서 $jf(a) \geq a$이다. 하지만 $a \notin \mathrm{im}f$이므로 모순이다. □

(2)의 증명.

$f: (W, <) → (W, <)$가 동형사상이라고 하자. $f^{-1}$ 또한 동형사상이므로 $x \in W$에 대해 $x \leq f(x)$, $f(x) \leq f^{-1}(f(x)) = x$이다. 따라서 $x = f(x)$이다. □

(3)의 증명.

$f, g: (W_1, <_1) → (W_2, <_2)$가 동형사상이라고 하자. $g^{-1}f: (W_1, <_1) → (W_1, <_1)$은 자기동형사상이므로 (2)에 의해 항등사상이다. 따라서 $f = g$이다. ■

정렬의 삼분성. $(W_1, <_1), (W_2, <_2)$가 정렬 집합일 때 다음 중 정확히 하나가 성립한다.

1. $(W_1, <_1) \sim (W_2, <_2)$
2. 어떤 $a$에 대해 $(W_1[a], <_1) \sim (W_2, <_2)$
3. 어떤 $b$에 대해 $(W_1, <_1) \sim (W_2[b], <_2)$

각 경우 동형사상은 유일하며, 또한 2, 3의 경우 $a, b$는 유일하다.

증명.

앞선 정리는 1, 2, 3이 mutually exclusive함과, 유일성에 대한 주장을 보증한다. 따라서 임의의 $(W_1, <_1), (W_2, <_2)$가 위 세 경우에 속함을 보이면 충분하다.

다음과 같이 부분함수 $f: W_1 → W_2$를 정의한다.

\[f := \lbrace (x, y) \in (W_1, W_2) : (W_1[x], <_1) \sim (W_2[y], <_2) \rbrace\]

$f$가 단사이고 순서 보존임을 쉽게 확인할 수 있다. 이제 두 가지 경우를 고려한다.

Case 1. $\mathrm{dom} f = W_1$

정리의 3번 경우에 해당하여 증명이 끝난다.

Case 2. $\mathrm{dom} f \subsetneq W_1$

먼저 어떤 $a \in W$에 대해 $\mathrm{dom}f = W_1[a]$임을 보인다. $x \in \mathrm{dom}f$라면 $W_1[x] \sim W_2[f(x)]$이다. 해당 동형의 동형사상을 $\phi$라고 하면 $x’ < x$에 대해 $W_1[x’] = W_2[\phi(x’)]$이므로 $x’ \in \mathrm{dom}f$이다. 따라서 $\mathrm{dom} f$는 초기단이다.

두 번째로 $\mathrm{im} f = W_2$임을 보인다. $\mathrm{dom}f = W_1[a]$라고 하자. 앞선 문단과 비슷한 논증으로 $\mathrm{im}f$ 또한 $W_2$의 초기단임을 알 수 있다. $\mathrm{im}f = W_2[b]$라면, $(a, b) \in f$이므로 $a \in \mathrm{dom}f$이며 모순이다. ■

3. 서수의 완전성

서수의 완전성. 모든 정렬 집합은 어떤 서수와 순서 동형이다.

증명. $(W, <)$가 정렬 집합이라고 하자. 다음과 같이 $A, S$를 정의한다.

\[\begin{gather} A = \lbrace a \in W : W[a] \sim \alpha_a \text{ where $\alpha_a \in$Ord} \rbrace\\ S = \lbrace \alpha_a \in \mathrm{Ord} : a \in A\rbrace \end{gather}\]

$S$가 서수이고 $A$가 초기단임을 쉽게 보일 수 있다. $S = \beta$, $A = W[c]$라고 하자. $f: A → S; a \mapsto \alpha_a$는 $(A, <)$와 $(S, \in)$의 순서동형사상이다. 즉, $W[c] \simeq \beta$이므로 $c \in A$이며, 이는 모순이다. 따라서 $A = W \sim \beta$이다. ■

4. 치환 공리

위 증명에서 $S$의 존재성은 치환 공리꼴 없이 보장되지 않는다. 왜냐하면 부랄리포르티 역설에 의해 $\mathrm{Ord}$는 집합이 아니며, 이에 따라 분류 공리꼴로 $S$의 존재성을 보장할 수 없기 때문이다.

치환 공리의 필요성을 보여주는 다른 예시로, 치환 공리꼴 없이는 $\omega + \omega$의 존재성을 보장할 수 없다. 각 $n \in \mathbb{N}$에 대해 $\omega + n$이 존재함은 짝 공리와 합집합 공리로 보일 수 있지만, $\omega + \omega := \cup_{n \in \mathbb{N}} (\omega + n)$가 존재함은 보일 수 없다. 그렇다고 임의의 집합들의 합집합을 허용하는 공리를 추가할 수는 없는데, 이는 “모든 집합들의 집합”을 집합으로 만듦으로써 러셀의 역설을 일으키기 때문이다.

위 두 경우에서 우리에게 필요한 것은, “잘 정의된 일대일 대응 관계 $R(x,y)$와 집합 $X$가 주어졌을 때 $\lbrace y : R(x, y), x \in X \rbrace$는 집합이다”라는 내용의 공리이다. 이 공리가 치환 공리이다. 치환 공리를 사용하면 $\omega = \lbrace 0, 1, 2, … \rbrace$와 관계 $R(x, y): y = \omega + x$에 대해 $\mathrm{im}R\vert_\omega = \lbrace \omega, \omega + 1, \omega + 2, … \rbrace$가 존재하며, $\omega \cup \mathrm{im}R\vert_\omega = \omega + \omega$가 존재함을 보일 수 있다.

Trichotomy and Completeness of Ordinals

21 Nov 2024

1. Basic Concepts

Definition. A set $(W, <)$ is called a well-ordered set if it satisfies the following conditions:

1. $(W, <)$ is a total order.
2. Every non-empty subset of $W$ has a least element.

Definition. If $(W, <)$ is a well-ordered set, a subset $S$ of $W$ such that $x < a \rightarrow x \in S$ for some $a \in S$ is called an initial segment.

Theorem. If $S$ is an initial segment of a well-ordered set $(W, <)$, then for some $a \in W$, the following holds:

\[S = W[a] := \{ x \in W : x < a \}\]

Proof. Let $a$ be the least element of $W \setminus S$.

2. Trichotomy of Order

Theorem.

1. A well-ordered set cannot be isomorphic to its initial segment.
2. The only order-preserving automorphism of a well-ordered set is the identity map.
3. The isomorphism between two well-ordered sets is unique.

Proof. We first prove the following lemma:

Lemma. If $f: (W, <) \to (W, <)$ is order-preserving, then for all $x \in W$, $x \leq f(x)$.

Proof of the Lemma. Assume for contradiction that $S = \lbrace x \in W : x > f(x) \rbrace$ is nonempty. Since $W$ is a well-ordered set, there exists a least element $c = \min S$. Since $c \in S$, we have $c > f(c)$, and since $f$ is order-preserving, it follows that $f(c) > f(f(c))$. On the other hand, since $c = \min S$, we have $f(c) \notin S$, and thus $f(f(c)) \geq f(c)$, leading to a contradiction. □

Proof of (1).

Assume $f: (W, <) \to (W[a], <)$ is an isomorphism. The inclusion map $j: W[a] \to W$ implies that $jf: (W, <) \to (W, <)$ is order-preserving. Therefore, $jf(a) \geq a$. However, since $a \notin \mathrm{im}f$, this leads to a contradiction. □

Proof of (2).

Assume $f: (W, <) \to (W, <)$ is an isomorphism. Since $f^{-1}$ is also an isomorphism, for all $x \in W$, we have $x \leq f(x)$ and $f(x) \leq f^{-1}(f(x)) = x$. Thus, $x = f(x)$. □

Proof of (3).

Assume $f, g: (W_1, <_1) \to (W_2, <_2)$ are isomorphisms. The composition $g^{-1}f: (W_1, <_1) \to (W_1, <_1)$ is an automorphism, and by (2), it must be the identity map. Therefore, $f = g$. ■

Trichotomy of Order. For well-ordered sets $(W_1, <_1)$ and $(W_2, <_2)$, exactly one of the following holds:

1. $(W_1, <_1) \sim (W_2, <_2)$
2. For some $a$, $(W_1[a], <_1) \sim (W_2, <_2)$
3. For some $b$, $(W_1, <_1) \sim (W_2[b], <_2)$

In each case, the isomorphism is unique, and in cases 2 and 3, $a$ and $b$ are unique.

Proof.

The preceding theorems guarantee that 1, 2, and 3 are mutually exclusive and establish the claim of uniqueness. Therefore, it suffices to show that any pair of well-ordered sets $(W_1, <_1)$ and $(W_2, <_2)$ falls into one of the three cases.

We define a partial function $f: W_1 \to W_2$ as follows:

\[f := \{ (x, y) \in (W_1, W_2) : (W_1[x], <_1) \sim (W_2[y], <_2) \}\]

It can be easily verified that $f$ is injective and order-preserving. We now consider two cases.

Case 1. $\mathrm{dom} f = W_1$

This corresponds to case 3 of the theorem, concluding the proof.

Case 2. $\mathrm{dom} f \subsetneq W_1$

First, we show that for some $a \in W$, $\mathrm{dom}f = W_1[a]$. If $x \in \mathrm{dom}f$, then $W_1[x] \sim W_2[f(x)]$. Let $\phi$ be the isomorphism of that isomorphism. For $x’ < x$, we have $W_1[x’] = W_2[\phi(x’)]$, thus $x’ \in \mathrm{dom}f$. Therefore, $\mathrm{dom} f$ is an initial segment.

Next, we show that $\mathrm{im} f = W_2$. Assume $\mathrm{dom}f = W_1[a]$. By a similar argument as above, we can show that $\mathrm{im}f$ is also an initial segment of $W_2$. If $\mathrm{im}f = W_2[b]$, then $(a, b) \in f$, which implies $a \in \mathrm{dom}f$, leading to a contradiction. ■

3. Completeness of Ordinals

Completeness of Ordinals. Every well-ordered set is order-isomorphic to some ordinal.

Proof. Let $(W, <)$ be a well-ordered set. We define $A$ and $S$ as follows:

\[\begin{gather} A = \{ a \in W : W[a] \sim \alpha_a \text{ where } \alpha_a \in \mathrm{Ord} \}\\ S = \{ \alpha_a \in \mathrm{Ord} : a \in A \} \end{gather}\]

It can be easily shown that $S$ is an ordinal and $A$ is an initial segment. Let $S = \beta$ and $A = W[c]$. The function $f: A \to S; a \mapsto \alpha_a$ is an order isomorphism between $(A, <)$ and $(S, \in)$. Thus, $W[c] \simeq \beta$, which implies $c \in A$, leading to a contradiction. Therefore, $A = W \sim \beta$. ■

4. Axiom of Replacement

The existence of $S$ in the above proof cannot be guaranteed without the Axiom of Replacement. This is because, due to Burali-Forti’s paradox, $\mathrm{Ord}$ is not a set, and thus the existence of $S$ cannot be guaranteed by the Axiom of Separation (see: List of ZFC Axioms).

Another example demonstrating the necessity of the Axiom of Replacement is that without it, we cannot guarantee the existence of $\omega + \omega$. For each $n \in \mathbb{N}$, the existence of $\omega + n$ can be shown using the Axiom of Pairing and the Axiom of Union, but the existence of $\omega + \omega := \bigcup_{n \in \mathbb{N}} (\omega + n)$ cannot be established. However, we cannot simply add an axiom allowing the union of arbitrary sets, as this would make “the set of all sets” a set, leading to Russell’s paradox.

In both cases, what we need is an axiom stating that “given a well-defined one-to-one correspondence $R(x,y)$ and a set $X$, the collection $\lbrace y : R(x, y), x \in X \rbrace$ is a set.” This axiom is the Axiom of Replacement. Using the Axiom of Replacement, we can show that given:

\[\begin{gather} \omega = \lbrace 0, 1, 2, ... \rbrace \\ R(x, y): y = \omega + x, \end{gather}\]

the image $\mathrm{im}R|_\omega = \lbrace \omega, \omega + 1, \omega + 2, … \rbrace$ exists, and thus $\omega \cup \mathrm{im}R|_\omega = \omega + \omega$ exists.

유리수와 실수의 집합론적 정의

20 Nov 2024

1. 칸토어의 동형성 정리

칸토어의 동형성 정리. 가산이고 양끝점이 없으며 조밀한 전순서 집합은 순서 동형에 대해 유일하다.

증명 1. (Back-and-Forth Argument)

$n$번째 단계에서 가장 인덱스가 작은 $a_k \in A \setminus \mathrm{dom} f_n$을 순서 동형성을 만족하게끔 임의의 $b \in B \setminus \mathrm{im} f_n$과 대응시키고, 가장 인덱스가 작은 $b_l \in B \setminus (\mathrm{im} f_n \cup \lbrace b \rbrace)$ 를 순서 동형성을 만족하게끔 임의의 $a \in A \setminus (\mathrm{dom}f_n \cup \lbrace a_k\rbrace)$ 와 대응시킨다. (그림의 파란색은 ‘가장 인덱스가 작은’으로 선택된 원소)

증명 2. (Only-Forth Argument)

$n$번째 단계에서 가장 인덱스가 작은 $a_k \in A \setminus \mathrm{dom} f_n$을 순서 동형성을 만족하게끔 가장 인덱스가 작은 $b_l \in B \setminus \mathrm{im}f_n$과 대응시킨다.

잘못된 증명. (Incorrect Only-Forth Argument)

$n$번째 단계에서 가장 인덱스가 작은 $a_k \in A \setminus \mathrm{dom} f_n$을 순서 동형성을 만족하게끔 임의의 $b \in B \setminus \mathrm{im}f_n$와 대응시킨다.

잘못된 이유. $\mathrm{im} \left[ \bigcup f_n \right]$이 $B$ 전체를 소진한다는 보장이 없다. 일례로 모든 경우 선택된 $b$의 인덱스가 짝수인 경우가 가능하다.

2. 데데킨트 절단

정의. 전순서 집합 $(P, <)$에 대하여 $P$의 부분집합 $A, B$가 다음을 만족할 때 $(A, B)$를 절단이라고 한다.

1. $A \sqcup B = P$
2. 임의의 $a \in A, b \in B$에 대해 $a < b$이다.

추가로 다음을 만족할 때 데데킨트 절단이라고 한다.

1. $A$는 최대 원소를 가지지 않는다.

추가로 다음까지 만족할 때 틈이라고 한다.

1. $B$는 최소 원소를 가지지 않는다.

Remark

1. $P$가 완비이다 ⇔ $P$는 틈을 가지지 않는다.
2. $P = \mathbb{Q}$일 때 틈은 무리수 집합을, 데데킨트 절단은 실수 집합을 나타낸다.

3. 완비화 정리

완비화 정리. $(P, <)$가 양끝점이 없는 조밀한 전순서라면 다음을 만족하는 완비 전순서 $(C, \prec)$가 순서 동형에 대해 유일하게 존재한다.

1. $P \subseteq C$
2. $\prec$는 $P$에서 $<$와 일치한다.
3. $P$는 $C$에서 조밀하다. 즉, $c_1 < c_2 \in C$에 대해 $c_1 < p < c_2$를 만족하는 $p \in P$가 언제나 존재한다.
4. $C$는 양끝점이 없다.

유일성 증명. $(C, \prec)$와 $(C^\ast, \prec^\ast)$가 조건을 만족하는 완비 전순서라고 하자. 다음과 같이 정의된 $\phi: C → C^\ast$는 순서 동형 사상이다.

1. $c \in P$라면 $\phi(c)=c$
2. $c \notin P$라면 $\phi(c) = \sup^\ast \lbrace p \in P : p \prec c \rbrace$

존재성 증명. 다음과 같이 정의한다.

\[\begin{gather} \mathcal{G} = \lbrace (A, B) : (A, B) \text{ is a gap of } P \rbrace \\ \mathcal{D} = \lbrace (A, B) : (A, B) \text{ is a Dedekind cut of } P \rbrace \\ \mathcal{P} = \mathcal{D} \setminus \mathcal{G} \end{gather}\]

라고 하자. 다음과 같이 $\mathcal{D}$에 순서를 준다.

\[(A_1, B_1) \prec (A_2, B_2) \iff A_1 \subset A_2\]

$(A, B) \in \mathcal{P}$라면 어떤 $p$에 대해 $B = \lbrace x \in P : x \geq p \rbrace$이며, 이때 $(A, B) = [p]$라고 적자. 즉,

\[\mathcal{P} = \lbrace [p] : p \in P \rbrace\]

$(\mathcal{P}, \prec) \sim (P, <)$임을 쉽게 확인할 수 있다. 이제 다음을 보인다.

Claim. $\mathcal{D}$는 $\mathcal{P}$에 대해 완비화 정리의 4가지 조건을 모두 만족하는 확장이다.

1, 2, 4는 자명하다. 3을 보인다.

$\mathfrak{d}_1 = (A_1, B_1), \mathfrak{d}_2 = (A_2, B_2) \in \mathcal{D}$에 대해 $\mathfrak{d_1} \prec \mathfrak{d}_2$, 즉 $A_1 \subset A_2$라고 하자. $p \in A_2 \setminus A_1$이며 $p$가 $B$의 최소 원소가 아닌 $p \in P$가 존재한다. 그러한 $p$에 대해 $\mathfrak{d}_1 \prec [p] \prec \mathfrak{d}_2$이다. □

마지막으로 다음을 보인다.

Claim. $(\mathcal{D}, \prec)$는 완비이다.

$\mathcal{S}$가 위로 유계인 $\mathcal{D}$의 공집합이 아닌 부분집합이라고 하자. 다음과 같이 정의한다.

\[\begin{gather} A_\mathcal{S} = \bigcup \lbrace A : (A, B) \in \mathcal{S} \rbrace\\ B_\mathcal{S} = \bigcap \lbrace B : (A, B) \in \mathcal{S} \rbrace \end{gather}\]

$(A_\mathcal{S}, B_\mathcal{S}) \in \mathcal{D}$이며, $\mathcal{S}$의 최소 상계임을 확인할 수 있다. ◾

집합론적 실수의 정의. 다음을 만족하는 집합 $(R, <)$은 순서 동형에 대해 유일하다.

1. 완비 전순서 집합이다.
2. 양끝점이 없다.
3. 분리 가능하다(separable). 즉, $Q \subset R$이 존재하여 $Q$는 가산집합이고 $R$에서 조밀하다.

증명. 칸토어의 동형성 정리와 완비화 정리로부터 따라 나온다.

Set-theoretic Definitions of Rational and Real Numbers

20 Nov 2024

1. Cantor’s Isomorphism Theorem

Cantor’s Isomorphism Theorem. Any countable, dense, linear order without endpoints is unique up to order isomorphism.

Proof 1. (Back-and-Forth Argument)

At the $n$-th step, map the least-indexed $a_k \in A \setminus \mathrm{dom} f_n$ to an arbitrary $b \in B \setminus \mathrm{im} f_n$ so that order isomorphism is preserved, and then map the least-indexed $b_l \in B \setminus (\mathrm{im} f_n \cup \lbrace b \rbrace)$ to an arbitrary $a \in A \setminus (\mathrm{dom}f_n \cup \lbrace a_k\rbrace)$ so that order isomorphism is preserved. (In the diagram, blue indicates the ‘least-indexed’ elements.)

Proof 2. (Only-Forth Argument)

At the $n$-th step, map the least-indexed $a_k \in A \setminus \mathrm{dom} f_n$ to the least-indexed $b_l \in B \setminus \mathrm{im}f_n$ so that order isomorphism is preserved.

Incorrect Proof. (Incorrect Only-Forth Argument)

At the $n$-th step, match the least-index $a_k \in A \setminus \mathrm{dom} f_n$ to an arbitrary $b \in B \setminus \mathrm{im}f_n$ so that order isomorphism is preserved.

Why this is incorrect: There is no guarantee that $\mathrm{im} \left[ \bigcup f_n \right]$ exhausts all of $B$. For example, it is possible that only $b$’s with even indices are chosen in every step.

2. Dedekind Cuts

Definition. For a linearly ordered set $(P, <)$, a pair of subsets $A, B$ of $P$ is called a cut if:

1. $A \sqcup B = P$
2. For any $a \in A, b \in B$, $a < b$.

Furthermore, it is a Dedekind cut if:

1. $A$ has no greatest element.

It is called a gap if, in addition:

1. $B$ has no least element.

Remark

1. $P$ is complete ⇔ $P$ has no gaps.
2. As will be seen, for $P = \mathbb{Q}$, gaps correspond to irrational numbers while Dedekind cuts correspond to real numbers.

3. Completion Theorem

Completion Theorem. If $(P, <)$ is a dense linear order without endpoints, then there exists a unique (up to order isomorphism) complete linear order $(C, \prec)$ satisfying:

1. $P \subseteq C$
2. $\prec$ coincides with $<$ on $P$
3. $P$ is dense in $C$: for any $c_1 < c_2 \in C$, there exists $p \in P$ with $c_1 < p < c_2$
4. $C$ has no endpoints.

Uniqueness Proof. Suppose $(C, \prec)$ and $(C^\ast, \prec^\ast)$ are complete linear orders satisfying the conditions. Define $\phi: C \to C^\ast$ as follows:

1. If $c \in P$, then $\phi(c)=c$
2. If $c \notin P$, then $\phi(c) = \sup^\ast \lbrace p \in P : p \prec c \rbrace$

This $\phi$ is an order isomorphism.

Existence Proof. Define:

\[\begin{gather} \mathcal{G} = \lbrace (A, B) : (A, B) \text{ is a gap of } P \rbrace \\ \mathcal{D} = \lbrace (A, B) : (A, B) \text{ is a Dedekind cut of } P \rbrace \\ \mathcal{P} = \mathcal{D} \setminus \mathcal{G} \end{gather}\]

Define an order on $\mathcal{D}$ by:

\[(A_1, B_1) \prec (A_2, B_2) \iff A_1 \subset A_2\]

If $(A, B) \in \mathcal{P}$, then for some $p$, $B = \lbrace x \in P : x \geq p \rbrace$, and we write $(A, B) = [p]$. That is,

\[\mathcal{P} = \lbrace [p] : p \in P \rbrace\]

It is easy to check that $(\mathcal{P}, \prec) \sim (P, <)$. Now, we show the following:

Claim. $\mathcal{D}$ is an extension of $\mathcal{P}$ satisfying all four conditions of the Completion Theorem.

Conditions 1, 2, and 4 are clear. We show 3.

Let $\mathfrak{d}_1 = (A_1, B_1), \mathfrak{d}_2 = (A_2, B_2) \in \mathcal{D}$ with $\mathfrak{d}_1 \prec \mathfrak{d}_2$, i.e., $A_1 \subset A_2$. There exists $p \in A_2 \setminus A_1$ such that $p$ is not the least element of $B$, i.e., $p \in P$. For such $p$, we have $\mathfrak{d}_1 \prec [p] \prec \mathfrak{d}_2$. □

Finally, we show:

Claim. $(\mathcal{D}, \prec)$ is complete.

Let $\mathcal{S}$ be a nonempty, upward-bounded subset of $\mathcal{D}$. Define:

\[\begin{gather} A_\mathcal{S} = \bigcup \lbrace A : (A, B) \in \mathcal{S} \rbrace\\ B_\mathcal{S} = \bigcap \lbrace B : (A, B) \in \mathcal{S} \rbrace \end{gather}\]

Then $(A_\mathcal{S}, B_\mathcal{S}) \in \mathcal{D}$ and is the least upper bound of $\mathcal{S}$. ◾

Set-theoretic Definition of the Real Numbers. A set $(R, <)$ satisfying the following is unique up to order isomorphism:

1. It is a complete linear order.
2. It has no endpoints.
3. It is separable; i.e., there exists $Q \subset R$ which is countable and dense in $R$.

Proof. This follows from Cantor’s Isomorphism Theorem and the Completion Theorem.

칸토어-슈뢰더-베른슈타인 정리

19 Nov 2024

정리. 두 집합 $X, Y$에 대해 $|X| \leq |Y|$, $|X| \geq |Y|$라면 $|X| = |Y|$이다.

매우 당연해 보이지만 $\leq$가 단사함수의 존재성으로, $=$가 전단사함수의 존재성으로 정의된다는 점에서 트리키한 함수 핸들링을 요구한다.

여담으로 “칸토어-베른슈타인 정리(위키피디아)” 또는 “슈뢰더-베른슈타인 정리(나무위키)”라고도 부르는데 “칸토어-슈뢰더 정리”라고 부르는 경우는 못 봤다. 홍대병에 취해 있다면 “칸토어-슈뢰더 정리”라고 불러보자.

첫 번째 증명

조건에 의해 단사함수 $f: X \to Y, g: Y \to X$가 존재한다. $Z := \mathrm{Im} f$가 $Y$와 같다면 증명이 끝나므로 $Z \subsetneq Y$라고 하자.

임의의 $y \in Z \setminus Y$ (그림에서 빈 점으로 표시) 에 대해,

• $x_1^y = g^{-1}(y)$
• $x_{n+1}^y = g(f(x_n))$

와 같이 두어, $h: X \to Y$를 다음과 같이 정의한다.

• $h_y(x_1^y) = y$
• $h_y(x_{n+1}^y) = f(x_n)$

다음이 성립함을 확인하라.

\[x^y_n = x^z_m \iff y = z, n = m\]

따라서 다음의 함수 $h: X → Y$는 well-defined이다.

\[h(x) = \begin{cases} h_y(x) &x = x^y_n \text{ for some } y, n \\\\ f(x) &\text{otherwise} \end{cases}\]

$h$가 전단사임을 확인하라. ◾

두 번째 증명

보조정리 (기수의 샌드위치 정리). $A_1 \supseteq B \supseteq A_2$에 대해 $|A_1| = |A_2|$라면 $|A_1| = |B| = |A_2|$이다.

증명. $f: A_1 → A_2$가 전단사라고 하자. $B_1 = B$로 둔다. 다음과 같이 $\lbrace A_n\rbrace , \lbrace B_n\rbrace , \lbrace C_n\rbrace $을 정의한다.

\[\begin{gather} A_{n+1} = f[A_n]\\ B_{n+1} = f[B_n]\\ C_n = A_n \setminus B_n \end{gather}\]

$C = \bigcup C_n$ (그림에서 색칠되지 않은 영역), $D = A_1 \setminus C$ (그림에서 색칠된 영역) 라고 하자. $f[C] \subset C, f[D] \subset D$임을 확인하라. 따라서 다음의 $g: B_1 → A_2$는 전단사이다. (화살표)

\[g(x) = \begin{cases} x & x \in C\\ f(x) & x \in D \end{cases}\]

본 정리의 증명. $f: X → Y, g: Y → X$가 전사일 때 $gf[X] \subseteq g[Y] \subseteq X$이고, $| gf[X] | = | X |$이므로, 보조정리에 의해 $|g[Y]| = |Y| = |X|$이다. ◾

잘 생각해 보면 두 증명은 사실 같다.

Cantor–Schröder–Bernstein Theorem

19 Nov 2024

Theorem. For two sets $X, Y$, if $|X| \leq |Y|$ and $|X| \geq |Y|$, then $|X| = |Y|$.

Although this may seem obvious, it requires some delicate function handling, since $\leq$ is defined by the existence of an injective function, while $=$ is defined by the existence of a bijective function.

As a side note, the theorem is often called the “Cantor–Bernstein theorem” or the “Schröder–Bernstein theorem”, but I’ve never seen it called the “Cantor–Schröder theorem.” If you’re feeling a bit pretentious, it’s an open option.

First Proof

By assumption there exists $f: X \to Y, g: Y \to X$ injective. If $Z := \mathrm{Im} f$ equals $Y$, the proof is done, so let us assume $Z \subsetneq Y$.

For any $y \in Z \setminus Y$ (represented as an empty dot in the diagram),

• let $x_1^y = g^{-1}(y)$
• let $x_{n+1}^y = g(f(x_n))$

Now define a function $h: X \to Y$ as follows:

• $h_y(x_1^y) = y$
• $h_y(x_{n+1}^y) = f(x_n)$

Check that the following holds:

\[x^y_n = x^z_m \iff y = z, n = m\]

Thus, the function $h: X \to Y$ defined by

\[h(x) = \begin{cases} h_y(x) &x = x^y_n \text{ for some } y, n \\\\ f(x) &\text{otherwise} \end{cases}\]

is well-defined. Verify that $h$ is bijective. ◾

Second Proof

Lemma (Sandwich Theorem for Cardinals). If $A_1 \supseteq B \supseteq A_2$ and $|A_1| = |A_2|$, then $|A_1| = |B| = |A_2|$.

Proof. Assume $f: A_1 \to A_2$ is bijective. Let $B_1 = B$. Define the sequences $\lbrace A_n\rbrace , \lbrace B_n\rbrace , \lbrace C_n\rbrace$ as follows:

\[\begin{gather} A_{n+1} = f[A_n]\\ B_{n+1} = f[B_n]\\ C_n = A_n \setminus B_n \end{gather}\]

Let $C = \bigcup C_n$ (the unshaded region in the diagram) and $D = A_1 \setminus C$ (the shaded region). Verify that $f[C] \subset C$ and $f[D] \subset D$. Then, define $g: B_1 \to A_2$ as follows (represented as arrows in the diagram).

\[g(x) = \begin{cases} x & x \in C\\ f(x) & x \in D \end{cases}\]

Then $g$ is bijective.

Proof of the main theorem. Given $f: X \to Y$ and $g: Y \to X$ are injective, we have $gf[X] \subseteq g[Y] \subseteq X$ and $| gf[X] | = | X |$. By the lemma, we obtain $|g[Y]| = |Y| = |X|$. ◾

Upon closer reflection, the two proofs are essentially the same.

ZFC 공리의 목록

18 Nov 2024

공리명	의미
외연 공리	집합은 원소의 모임이다.
공집합 공리*	공집합이 존재한다.
짝 공리*	$X, Y$로부터 $Z = \lbrace X, Y \rbrace$를 정의할 수 있다.
합집합 공리	$X = \lbrace Y_i \rbrace$로부터 $Z = \bigcup Y_i$를 정의할 수 있다.
멱집합 공리	$X$로부터 $\mathcal{P}(X)$를 정의할 수 있다.
분류 공리꼴**	$X$로부터 $Y = \lbrace y \in X : \phi(y) \rbrace$를 정의할 수 있다. ($\phi$는 1차 논리식)
무한 공리	모든 자연수를 포함하는 집합이 존재한다.
정칙 공리	$\in$은 정렬 순서이다.
치환 공리꼴	$X$로부터 $f[X]$를 정의할 수 있다. ($f$는 class function)
선택 공리	집합족 $\lbrace X_i \rbrace$에 대해 각 $X_i$의 원소를 하나씩 선택할 수 있다.

공리명	논리식(자유변수는 $\forall$로 양화)
외연 공리	$X = Y \leftrightarrow (z \in X \leftrightarrow z \in Y)$
공집합 공리*	$\exists Z : z \not\in Z$
짝 공리*	$\exists Z : z \in Z \leftrightarrow (z = X \lor z = Y)$
합집합 공리	$\exists Z : z \in Z \leftrightarrow \exists x \in X (z \in x)$
멱집합 공리	$\exists Z : z \in Z \leftrightarrow (w \in z \rightarrow w \in X)$
분류 공리꼴**	$\exists Z : z \in Z \leftrightarrow (z \in X \land \phi(z))$
무한 공리	$\exists Z : \varnothing \in Z \land (z \in Z \rightarrow z \cup \lbrace z \rbrace \in Z)$
정칙 공리	$\exists x \in X : \forall y \in X [ y \not\in x]$
치환 공리꼴	$\displaylines{[\forall x \in X \; \exists! y :\phi(x, y)] \rightarrow [\exists Y \; \forall x \in X \; \exists y \in Y : \phi(x, y)]}$
선택 공리	$\displaylines{\varnothing \notin X \rightarrow \exists f : X \rightarrow \bigcup X [ f(x) \in x ]}$

Remarks.

• 정칙 공리는 다음과 동치

\[\exists x \in X : x \cap X = \varnothing\]

• (*)로 표시된 공리는 분류 공리꼴로부터 유도할 수 있다.
• (**)로 표시된 공리는 치환 공리꼴로부터 유도할 수 있다.
  • 분류 공리꼴의 내용은 “X가 집합이다 → f[X]가 집합이다(f는 함수)”이라는 것이다. f가 함수임을(즉, f의 정의역이 집합임을) 선결적으로 요구함에 유의하라.

공리의 필요성

정리. 다음의 정리들은 선택 공리를 필요로 한다.

• $f: X → Y$가 전사일 때, 어떤 $X$의 부분집합 $Z$에 대해 $f\vert_Z$는 전단사이다.

• $\varnothing \not\in \lbrace X_i\rbrace$일 때 $\prod X_i \neq \varnothing$이다.

• 정렬 원리: 임의의 집합에 정렬 순서를 줄 수 있다.

• 초른의 보조정리: $(X, <)$의 임의의 체인이 $X$에서 상계를 가진다면, $X$는 극댓값_{maximal element}을 가진다.

정리. 다음의 정리들은 치환 공리꼴을 필요로 한다.

• $\omega + \omega$가 존재한다.

• 서수 완전성 정리. 모든 정렬 순서는 서수와 순서 동형이다.

List of ZFC Axioms

18 Nov 2024

Name	Meaning
Extensionality	Set is an unordered collection of elements.
Existence*	There exists the empty set.
Pairing*	From $X, Y$ follows $Z = \lbrace X, Y \rbrace$.
Union	From $X = \lbrace Y_i \rbrace$ follows $Z = \bigcup Y_i$.
Power Set	From $X$ follows $\mathcal{P}(X)$.
Separation Schema**	From $X$ follows $Y = \lbrace y \in X : \phi(y) \rbrace$, where $\phi$ is a first-order formula.
Infinity	There exists a set containing all the natural numbers.
Regularity	$\in$ is a well-ordering.
Replacement	From $X$ follows $f[X]$, where $f$ is a class function definable in first-order logic.
Choice	Every collection of nonempty sets $\lbrace X_i \rbrace$ has a choice function.

Name	Formula (Free variables are to be quantified by $\forall$)
Extensionality	$X = Y \leftrightarrow (z \in X \leftrightarrow z \in Y)$
Existence*	$\exists Z : z \not\in Z$
Pairing*	$\exists Z : z \in Z \leftrightarrow (z = X \lor z = Y)$
Union	$\exists Z : z \in Z \leftrightarrow \exists x \in X (z \in x)$
Power Set	$\exists Z : z \in Z \leftrightarrow (w \in z \rightarrow w \in X)$
Separation Schema**	$\exists Z : z \in Z \leftrightarrow (z \in X \land \phi(z))$
Infinity	$\exists Z : \varnothing \in Z \land (z \in Z \rightarrow z \cup \lbrace z \rbrace \in Z)$
Regularity	$\exists x \in X : \forall y \in X [ y \not\in x]$
Replacement	$\displaylines{[\forall x \in X \; \exists! y :\phi(x, y)] \rightarrow [\exists Y \; \forall x \in X \; \exists y \in Y : \phi(x, y)]}$
Choice	$\displaylines{\varnothing \notin X \rightarrow \exists f : X \rightarrow \bigcup X [ f(x) \in x ]}$

Remarks.

• Regularity is equivalent to the following:

\[\exists x \in X : x \cap X = \varnothing\]

• Those marked by (*) can be derived from the Separation.

• Those marked by (**) can be derived from the Replacement.

Replacement is strictly stronger than Separation:

• Separation can be stated as: If $X$ is a set and $f$ is a function, then $f[X]$ is a set.
• Replacement can be stated as: If $X$ is a set and $f$ is a class function, then $f[X]$ is a set.

The proof of following theorems require Choice.

• If $f: X → Y$ is surjective, there exists a subset $Z$ of $X$ such that $f\vert_Z$ is bijective.
• If $\varnothing \not\in \lbrace X_i\rbrace$, then $\prod X_i \neq \varnothing$.
• Well-ordering Principle. Every set can be well-ordered.
• Zorn’s Lemma. If every chain of $(X, <)$ is bounded in $X$, $X$ has a maximal element.

The proof of following theorems require Replacement.

• $\omega + \omega$ exists.
• Completeness of Ordinals. Every well-ordered set is order-isomorphic to a unique ordinal.