Consistency of the V = L Axiom

11 Dec 2024

1. Universe

1.1. Von Neumann Universe

We define $\lbrace V_\alpha \rbrace$ using transfinite recursion.

• $V_0 = \varnothing$
• $V_{\alpha + 1} = V_\alpha \cup \mathcal{P}(V_\alpha)$
• When $\lambda$ is a limit ordinal, $V_\lambda = \bigcup_{\alpha < \lambda} V_\alpha$

The first few $V_\alpha$ are as follows:

• $V_1 = \lbrace \varnothing \rbrace$
• $V_2 = \lbrace \varnothing, \lbrace \varnothing \rbrace \rbrace$
• $V_3 = \lbrace \varnothing, \lbrace \varnothing \rbrace, \lbrace \lbrace \varnothing \rbrace \rbrace, \lbrace \varnothing, \lbrace \lbrace \varnothing\rbrace \rbrace \rbrace$
• $V_\omega = \mathsf{HF}$

The collection of all $V_\alpha$ for every ordinal $\alpha$ is called the Von Neumann universe.

\[V = \bigcup_{\alpha \in \mathrm{Ord}} V_\alpha\]

When $x \in y \in z$ implies $x \in z$, we call $z$ a transitive set. This is an important property of $V$.

Theorem.

1. For $\alpha \in \mathrm{Ord}$, $V_\alpha$ is transitive.
2. $V$ is transitive.

Proof. By transfinite induction.

Accordingly, we can also define $V$ as follows:

• $V_0 = \varnothing$
• $V_{\alpha + 1} = \mathcal{P}(V_\alpha)$
• When $\lambda$ is a limit ordinal, $V_\lambda = \bigcup_{\alpha < \lambda}V_\alpha$

Intuitively, $V$ appears to contain all sets. Indeed, we can prove the following:

Theorem. If $x$ is a set, then $x \in V$.

Proof. For a set $x$, we define the transitive closure $\bar{x}$ of $x$ as the smallest transitive set containing $x$ as an element. Note that this is well-defined as the intersection of transitive sets is transitive.

Assume $x \notin V$. By the axiom of separation, $y = \lbrace u \in \bar{x} : u \notin V \rbrace$ is a set, and by the axiom of foundation, there exists an $\in$-minimal element $z$ of $y$. If there exists $w \in z$ such that $w \notin V$, then by transitivity $w \in y$, contradicting the $\in$-minimality of $z$. Therefore, all elements of $z$ are in $V$, and by the axiom of replacement, $\Omega = \lbrace \alpha \in \mathrm{Ord} \mid \exists w \in z : w \in V_\alpha\rbrace$ is a set. Let $\beta = \bigcup_{\alpha \in \Omega}\alpha$. Then $\beta$ is an ordinal, and $z \in V_{\beta + 1}$. (This is where the definition of von Neumann universe $V_{\beta + 1} = \mathcal{P}(V_\beta)$ is invoked.) This yields a contradiction. ■

Consequently, $V$ is not a set. Therefore, while $V$ is a model of ZFC in the sense that it contains all sets, many mathematicians require models to be sets, so it is not a model in the strict sense. (This explains why our proof that $V$ is a ‘model’ of ZFC does not contradict Gödel’s incompleteness theorems; within ZFC, $V$ is not recognised as a valid set-theoretic object.) However, for convenience, in this article, we shall refer to $V$ as a model of set theory. Moreover, we shall understand $x \in V$ as a formal expression for “$x$ is a set”.

1.2. Gödel Constructible Universe

First, we define constructibility as follows:

Definition. Let $\mathfrak{A}$ be an $\mathcal{L}$-structure and let $A$ be the underlying domain of $\mathfrak{A}$. $u$ is constructible from $\mathfrak{A}$ if there exist some $\mathcal{L}$-formula $\phi(y, x_1, \dots, x_n)$ and $a_1, \dots, a_n \in A$ such that the following holds:

\[y \in u \iff y \in A \land \mathfrak{A} \vDash \phi(y, a_1, \dots, a_n)\]

Sometimes we abuse the notation and say that $u$ is constructible from $A$.

For example, with respect to the standard model of arithmetics, the following constructs $u = \lbrace 1, 2 \rbrace$:

• $\phi(y, x_1, x_2) : (y = x_1) \lor (y = x_2)$
• $a_1 = 1, a_2 = 2$

The following constructs $u = \lbrace 2, 5, 10, 17, \dots \rbrace$:

• $\phi(y, x_1) : \exists z (z \cdot z + x_1 = y)$
• $a_1 = 1$

Gödel’s constructibility differs from constructibility in the general sense, namely expressibility in language. For instance, since the set of real numbers expressible in language is countable, some real numbers cannot be expressed in language. Let such a real number be $r$. With respect to the standard model of real numbers, the following “constructs” $u = \lbrace r \rbrace$:

• $\phi(y, x_1) : x_1 = y$
• $a_1 = r$

That is, Gödel’s constructibility is more versatile than linguistic constructibility in that it allows initialisation of free variables to arbitrary elements. Nonetheless, it is constrained to have only finite number of free variables.

We now define $\lbrace L_\alpha \rbrace$ using transfinite recursion:

• $L_0 = \varnothing$
• $L_{\alpha + 1} = \lbrace x : x \text{ is constructible from } L_\alpha \rbrace$
• When $\lambda$ is a limit ordinal, $L_\lambda = \bigcup_{\alpha < \lambda} L_\alpha$
• $L = \bigcup_{\alpha < \lambda} L_\alpha$

We can easily show that $L_\alpha = V_\alpha$ when $\alpha < \omega$. Specifically, when $\alpha = n$, we can construct $x \in V_\alpha$ with at most $n$ disjunctions. Therefore:

• $L_1 = \lbrace \varnothing \rbrace$
• $L_2 = \lbrace \varnothing, \lbrace \varnothing \rbrace \rbrace$
• $L_3 = \lbrace \varnothing, \lbrace \varnothing \rbrace, \lbrace \lbrace \varnothing \rbrace \rbrace, \lbrace \varnothing, \lbrace \lbrace \varnothing\rbrace \rbrace \rbrace$
• $L_\omega = \mathsf{HF}$

However, $L_{\omega + 1} \subsetneq V_{\omega + 1}$. This is because although $\mathcal{P}(\mathbb{N}) \subset V_{\omega + 1}$ is uncountable, since the set of first-order logical sentences and $L_\omega$ are both countable, $L_{\omega + 1}$ is countable. In general, when $\alpha$ is countable, $L_\alpha$ is countable.

Nevertheless, $L$ shares many properties with $V$. For instance:

Theorem. For $\alpha \in \mathrm{Ord}$, the following hold:

1. $L_\alpha$ is transitive. (Therefore $L$ is transitive)
2. $\alpha \in L_{\alpha + 1} \setminus L_{\alpha}$

Proof. By transfinite induction.

Note that $L$ is not a set since it contains all ordinals. However, there exists a first-order formula $\mathsf{IsInL}_\alpha(x)$ that expresses $x \in L_\alpha$. The proof is intricate and involves arithmetising propositions using Gödel numbers. (See link) At any rate, this means that we may understand $x \in L$ as a formal expression expressing $\exists \alpha \in \mathrm{Ord} :\mathsf{IsInL}_\alpha(x)$. The two will be co-extensional for models of ZF.

2. Relativisation

2.1. Relativisation of Formulas

Definition. Let $T$ be an $\mathcal{L}$-theory and $\psi$ an $\mathcal{L}$-formula. We define the relativisation $\phi^\psi$, read as the relativisaion of $\phi$ respect to $\psi$, as the formula where all quantifiers in $\phi$ are restricted to satisfy $\psi$.

Using $\mathsf{PA}$ as an example, if $\psi(x) : \exists z(z + z = x)$ and $\phi(x) : \exists z(z \cdot z = x)$, then:

\[\phi^\psi(x) : \exists z (\psi(z) \land z \cdot z = x)\]

Semantically, $\phi(x)$ expresses “$x$ is a perfect square” while $\phi^\psi(x)$ expresses “$x$ is a square of an even number”.

When it is clear that what $\psi(x)$ is supposed to express is $x \in S$, then we abuse the notation and write $\phi^S$ instead of $\phi^\psi$. Hence in the case of the previous example, we may write $\phi^E$ instead, where $E$ is the set of even numbers. That is,

\[\phi^E(x) : \exists z \in E (z \cdot z = x)\]

To use a bit of metaphoric expression, $\phi^S$ is how $\phi$ is “seen from” $S$.

For example, let $o(x)$ be the first-order formula expressing “$x$ is an ordinal”. Specifically, it is defined as:

\[o(x) : \mathrm{tr}(x) \land \forall y \in x \; \mathrm{tr}(y)\]

where $\mathrm{tr}(x) : \forall y \in x \; \forall z \in y (z \in x)$ expresses “$x$ is transitive”. By the abuse of notation, we may write $\phi^{\mathrm{Ord}}$ instead of $\phi^o$. $\phi^{\mathrm{Ord}}$ is how $\phi$ is “seen from” the class of all ordinals. Define:

• $\phi_1 : \forall x \exists y \forall z (z \subset x \rightarrow z \in y)$
• $\phi_2 : \forall x \forall y \exists z (z = x \cup y)$

That is, $\phi_1$ expresses closure under power set operation and $\phi_2$ expresses closure under set union. We have:

• $\mathsf{ZFC} \not\vdash \phi_1^\mathrm{Ord}$
• $\mathsf{ZFC} \vdash \phi_2^\mathrm{Ord}$,

since the set of ordinals is closed under union but not under power set. Put in another way, $\phi_1$ successfully distinguishes the class of all sets — what ZFC tries to describe — and the class of ordinals, while $\phi_2$ cannot. Generalising this observation, for a theory $T$ and a set $A$, the more formulas $\phi$ such that $T \vdash \phi \leftrightarrow \phi^A$, the better $A$ “conforms” to the description of $T$.

This leads us to the following definition.

Definition. For an $\mathcal{L}$-theory $T$ and a set $A$, $\phi$ is said to be absolute with respect to $A$ if for every $\mathcal{L}$-formula $\phi$,

\[T \vdash \forall x_1, \dots, x_n \in A (\phi(x_1, \dots, x_n) \leftrightarrow \phi^A(x_1, \dots, x_n))\]

Note that the definition simply becomes $T \vdash \phi^A$ when $\phi$ has no free variables, and it is given that $T \vdash \phi$.

2.2. $L$-Relativisation

Our goal now is to show that the axioms of ZF are absoulte with respect to $L$. That is:

Theorem 1. If $\phi$ is an axiom of ZF, then $\mathsf{ZF} \vdash \phi^L$.

That is to say,

“When seen from $L$, $L$ is a model of ZF” can be proved in ZF.

Of course, we only know that $L \subset V$ and do not know whether $V = L$, which leaves open the possibility of some set $x$ not belonging to $L$. Yet according to Theorem 1 states is that, even if there exists such a set $x$, its abscence does not break the internal consistency of $L$.

For example, suppose some set $x = \lbrace y, z \rbrace$ is absent from $L$. At first glance, the absence of $x$ seems to suggest that $L$ does not satisfy the pairing axiom $\mathsf{Pair}$:

\[\mathsf{Pair} := \forall y, z \; \exists x \; \forall w: w \in x \leftrightarrow (w = y \lor w = z)\]

However, the pairing axiom as viewed from inside $L$ is:

\[\mathsf{Pair}^L := \forall y, z \in L \; \exists x \in L \; \forall w \in L: w \in x \leftrightarrow (w = y \lor w = z)\]

Note that the quantification $\forall y, z$ is also restricted to $L$. That is, the absence of $x = \lbrace y, z \rbrace$ causes problems in $L$ only when $y, z \in L$. Conversely, if $x = \lbrace y, z \rbrace \notin L$ implies $y, z \notin L$, then $L$ satisfies $\mathsf{Pair}^L$. This is, $L$ lacks sets only in a way that maintains internal consistency.

Although we do not give the full proof, we highlight that the key reason Theorem 1 holds is that $L$, like $V$, is a transitivie class of sets, which leads to the following lemma.

Lemma. The following predicates are absolute with respect to $L$ in ZF:

1. $x \in y$
2. $x \subset y$
3. $x = \bigcup y$
4. $x = \lbrace y, z \rbrace$
5. $\alpha \in \mathrm{Ord}$
6. $x$ is transitive
7. $\Delta_0$ formulas

From this lemma, it is not too difficult to prove Theorem 1. Moreover, we can prove:

Theorem 2. $\mathsf{ZF} \vdash (V = L)^L$

Here, $V = L$ is a formal expression standing for $\forall x (x \in L)$. At first glance it may seem that $(V = L)^L$ is thus the trivial proposition $\forall x \in L (x \in L)$. However, when we actually expand $V = L$ as a first-order formula, we have:

\[\forall x \; \exists \alpha \; (\alpha \in \mathrm{Ord} \land x \in L_\alpha)\]

so $(V = L)^L$ becomes:

\[\forall x \in L \; \exists \alpha \in L \; (\alpha \in \mathrm{Ord})^L \land (x \in L_\alpha)^L\]

Note particularly that since $\alpha \in \mathrm{Ord}$ and $x \in L_\alpha$ are formal expressions of first-order formulas rather than a genuine $\in$-relation, they must likewise be relativised to $L$. Thus, to prove $(V = L)^L$ in ZF, we must prove that $\alpha \in \mathrm{Ord}$ and $x \in L_\alpha$ are also absolute. The former follows from the previous lemma, and the latter also “almost” follows from the lemma, except that $x \in L_\alpha$ is a $\Sigma_1$-sentence, so slightly more argument is required to secure its absoluteness.

From Theorems 1 and 2, we can prove:

Theorem 3. $\mathsf{ZFL} \vdash \phi \implies \mathsf{ZF} \vdash \phi^L$

Proof. We prove by induction on the proof length of $\mathsf{ZFL} \vdash \phi$. When the proof length is 0, $\phi$ is an axiom of ZFL. When $\phi$ is an axiom of ZF, it follows from Theorem 1, and when $\phi$ is $V = L$, it follows from Theorem 2.

Now assume $\phi$ is proved by applying an inference rule to $\lbrace \psi_1, \dots, \psi_n \rbrace$. The proof length of $\psi_k$ is smaller than that of $\phi$, so by the induction hypothesis $\mathsf{ZF} \vdash \psi_k^L$. We can easily show that logical axioms and inference rules are absolute with respect to $L$. Using modus ponens as an example, this means that:

\[\mathsf{ZF} \vdash ((\phi \land \phi \rightarrow \psi) \rightarrow \psi)^L\]

Therefore, if $(\psi_1 \land \dots \land \psi_n) \rightarrow \phi$ is logically valid, then $(\psi_1^L \land \dots \land \psi_n^L) → \phi^L$ is also logically valid, and consequently $\mathsf{ZF} \vdash \phi^L$. ■

As a corollary of Theorem 3, we obtain Theorem 4:

Theorem 4. If ZF is consistent, then ZFL is also consistent.

Proof. If ZFL is inconsistent, then $\mathsf{ZFL} \vdash \varnothing \neq \varnothing$, and by Theorem 3, $\mathsf{ZF} \vdash (\varnothing \neq \varnothing)^L \iff \mathsf{ZF} \vdash \varnothing \neq \varnothing$, which contradicts the consistency of ZF. ■

Therefore, V = L is consistent with ZF.

초한귀납과 초한재귀

05 Dec 2024

1. 초한귀납법

정리. $P$가 서수 위에서 정의된 속성이고 임의의 $\alpha \in \mathrm{Ord}$에 대해

\[[ \forall \beta < \alpha : P(\beta)] → P(\alpha)\]

가 성립할 때, $P$는 모든 서수에 대해 참이다.

Remark. $P$의 정의역인 $\mathrm{Ord}$는 집합이 아닌 진모임_{proper class}이므로 “술어” 대신 “속성”이란 표현을 사용한다.

증명. 서수가 정렬 순서라는 사실과 귀류법을 사용한다.

$\lnot P(\lambda)$인 $\lambda$가 존재한다고 하자. $\Omega = \lbrace \alpha \in \lambda : \lnot P(\alpha) \rbrace$는 공집합이 아닌 정렬 집합이므로 최소 원소 $\alpha_0$가 존재한다. 이때 $\forall \beta < \alpha_0 : P(\beta)$이므로 가정에 의해 $P(\alpha_0)$가 되어 모순이다. ■

응용. 폰 노인만 계층에서 $V_\alpha$는 추이적이다. 따라서 $V_{\alpha + 1} = V_\alpha \cup \mathcal{P}(V_\alpha)$ 대신 $V_{\alpha + 1} = \mathcal{P}(V_\alpha)$로 정의할 수 있다.

2. 초한재귀적 정의

Motivation. 자연수의 재귀적 정의를 생각해 보자. $n$개의 집합 $x_1, \dots , x_n$이 주어졌을 때 집합을 출력하는 함수 $g$가 존재한다면 다음과 같이 $f: \mathbb{N} → V$을 정의할 수 있을 것이다.

\[f(n) = g(f(0), \dots, f(n - 1))\]

문제는 $g$가 고정된 수의 매개변수만을 가질 수 있다는 것이다. 따라서 다음과 같이 $g$의 매개변수를 순서쌍으로 묶는다.

\[f(n) = g(\langle f(0), \dots, f(n - 1) \rangle)\]

이 순서쌍은 $\lbrace (0, f(0)), \dots, (n - 1, f(n - 1)) \rbrace = f \upharpoonright n$과 같이 표현할 수 있다. 즉,

\[f(n) = g(f \upharpoonright n).\]

이를 서수에 대해서 일반화하면 다음과 같다.

정리. $G: V → V$가 모임함수(class function)이라고 하자. 다음을 만족하는 모임함수 $F: \mathrm{Ord} → V$가 존재한다.

\[F(\alpha) = G(F \upharpoonright \alpha)\]

증명. 초한귀납법을 겁나게 쓰면 된다. (불친절해서 ㅈㅅ)

Transfinite Induction and Transfinite Recursion

05 Dec 2024

1. Transfinite Induction

Theorem. Let $P$ be a property defined on ordinals, and suppose that for any $\alpha \in \mathrm{Ord}$,

\[[ \forall \beta < \alpha : P(\beta)] → P(\alpha).\]

Then $P$ is true for all ordinals.

Remark. Since $\mathrm{Ord}$, the domain of $P$, is a proper class rather than a set, we use the term “property” instead of “predicate”.

Proof. Suppose there exists $\lambda$ such that $\lnot P(\lambda)$. Then $\Omega = \lbrace \alpha \in \lambda : \lnot P(\alpha) \rbrace$ is a non-empty well-ordered set, so it has a minimal element $\alpha_0$. Since $\forall \beta < \alpha_0 : P(\beta)$, by hypothesis we have $P(\alpha_0)$, which is a contradiction. ■

Application. Show that the von Neumann hierarchy may be defined as $V_{\alpha + 1} = \mathcal{P}(V_\alpha)$ instead of $V_{\alpha + 1} = V_\alpha \cup \mathcal{P}(V_\alpha)$.

2. Transfinite Recursive Definition

Motivation. Consider recursive definitions on natural numbers. Given $n$ sets $x_1, \dots , x_n$ and a function $g$ that outputs a set, we would like to define $f: \mathbb{N} → V$ as follows:

\[f(n) = g(f(0), \dots, f(n - 1))\]

The problem is that $g$ can only take a fixed number of parameters. Therefore, we group the parameters of $g$ into an ordered pair:

\[f(n) = g(\langle f(0), \dots, f(n - 1) \rangle)\]

This ordered pair can be represented as $\lbrace (0, f(0)), \dots, (n - 1, f(n - 1)) \rbrace = f \upharpoonright n$. That is,

\[f(n) = g(f \upharpoonright n).\]

Generalising this to ordinals, we obtain the following:

Theorem. Let $G: V → V$ be a class function. There exists a class function $F: \mathrm{Ord} → V$ satisfying

\[F(\alpha) = G(F \upharpoonright \alpha)\]

Proof. Apply transfinite induction extensively. (Sorry for the brevity, lol.) It is worth remarking that the proof does not depend on the axiom of choice, for the well-orderedness of ordinals is provable from ZF. Note, however, that the proof that every well-ordered set is order isomorophic to an ordinal does require AC.

콤팩트성과 그물

01 Dec 2024

콤팩트성

정의. $X$가 위상공간이라고 하자.

1. 임의의 열린 덮개가 유한한 부분덮개를 가질 때 $X$를 콤팩트하다고 한다.
2. 임의의 점렬 $\lbrace x_n \in X \rbrace$가 수렴하는 부분점렬을 가질 때 $X$를 점렬 콤팩트_{sequentially compact}하다고 한다.
3. 임의의 무한집합 $S \subset X$가 극점을 가질 때 $X$를 극점 콤팩트_{limit point compact}하다고 한다.

정리.

1. 콤팩트 $\rightarrow$ 극점 콤팩트
2. 점렬 콤팩트 $\rightarrow$ 극점 콤팩트
3. 극점 콤팩트 $\not\rightarrow$ 콤팩트
4. 극점 콤팩트 $\not\rightarrow$ 점렬 콤팩트

증명.

1. $S \subset X$가 극점이 없는 무한집합이라고 하자. $\overline{S} = S \cup S’ = S$이므로 $S$는 닫힌 집합이며, $X \setminus S$는 열린 집합이다. 임의의 $s \in S$에 대해, $s$가 극점이 아니므로 $U_s \cap S = \lbrace s \rbrace$인 $s$의 근방 $U_s$가 존재한다. 따라서 다음 $X$의 열린 덮개는 유한한 부분덮개를 가지지 않는다.

\[\mathcal{C} = \lbrace X \setminus S \rbrace \cup \bigcup_{s \in S} \lbrace U_s \rbrace\]

1. $S \subset X$가 무한집합이라고 하자. $S$의 원소들을 임의로 추출하여 점렬 $\lbrace s_n \rbrace \;(n \neq m \implies s_n \neq s_m)$을 만든다. $X$가 점렬 콤팩트하므로 $\lbrace s_n \rbrace → s$이며, $s$는 $S$의 극점이다.
2. 순서 토폴로지가 주어진 $\omega_1$은 극점 콤팩트하지만 콤팩트하지 않다.
3. $X = \mathbb{N} \times \lbrace 0, 1 \rbrace$, $\mathbb{N}$에는 이산 토폴로지가 주어지고 $\lbrace 0, 1\rbrace$에는 자명한 토폴로지가 주어짐.

Remark. 4의 올바르지 못한 “증명”

$X$가 극점 콤팩트하다고 하자. 점렬 $(x_n)$이 주어졌을 때, $S = \lbrace x_n : n \in \mathbb{N}\rbrace$이 유한집합이라면 $(x_n)$은 수렴하는 부분점렬을 자명하게 가진다. $S$가 무한집합이라면 $X$의 극점 콤팩트성에 의해 $x \in S’$가 존재한다. 이제 다음 조건을 만족하는 $x$의 근방들의 가산 모임 $\mathcal{U} = \lbrace U_n \rbrace$을 정의한다.

1. $n < m \implies U_n \supset U_m$
2. $V$가 $x$의 근방일 때, $\exists U \in \mathcal{U} : U \subset V$

이로부터 다음 조건을 만족하는 함수 $k: \mathbb{N} → \mathbb{N}$을 정의할 수 있다.

1. $x_{k(n)} \in U_n$
2. $n < m \implies k(n) < k(m)$
3. $n \neq m \implies x_{k(n)} \neq x_{k(m)}$

2가 가능한 이유는 $k(i)$가 $i \leq n$까지 정의되었을 때 $T = S \setminus \lbrace x_i : i \leq k(n) \rbrace$가 여전히 $x$를 극점으로 가지기 때문이다. 즉, $(x_n)$은 수렴하는 부분점렬 $(x_{k(n)})$을 가진다.

위 증명이 올바르지 않은 이유는 볼드체 부분이 일반적으로 가능하지 않기 때문이다. 대신 다음이 성립한다.

정리. 1차 가산 $T_1$ 공간에서 극점 콤팩트성과 점렬 콤팩트성은 동치이다.

$T_1$은 조건 3을 일반적으로 성립시키는 데 필요하다.

그물과 점렬

정의. $(J, \leq)$가 원순서_preorder라고 하자. 임의의 $x, y \in J$에 대해 $x, y \leq z$인 $z \in J$가 존재한다면 $(J, \leq)$를 방향 집합_{directed set}이라고 한다.

정의. $K$가 $(J, \leq)$의 부분집합이라고 하자. 임의의 $x \in J$에 대해 $x \leq y$인 $y \in K$가 존재한다면 $K$를 공종_cofinal이라고 한다.

Remark 1. $(J, \leq)$가 방향 집합이면 $J$는 $J$에서 자명하게 공종이다. 한편 $K \subset J$가 공종이라면 $(K, \leq)$ 또한 방향 집합이다.

Remark 2. 이후 드러나듯이, 방향성은 수렴의 일반화와 관련되는 조건이다.

정의. $(J, \leq)$가 방향 집합이라고 하자. 위상공간 $X$에 대해 $J$에서 $X$로 가는 함수 $f: J → X$를 그물_net이라고 한다. 특히, $\alpha \in J$에 대해 $f(\alpha)$를 $x_\alpha$와 같이 표기한다.

정의. 그물 $(x_\alpha)$가 $x$로 수렴한다는 것은, 임의의 $x$의 근방 $U$에 대해 어떤 $\alpha \in J$가 존재하여

\[\alpha \leq \beta \implies x_\beta \in U\]

인 것이다.

방향성에 의해, 특정한 $\alpha \in J$에 대해 $\alpha \leq \beta$인 $\beta$들만 고려해도 $\mathrm{im} f$ 전체를 포섭할 수 있음을 유의하라. 즉, 임의의 $x_\gamma$에 대해 $\alpha, \gamma \leq \beta$인 $\beta$가 존재한다. 달리 말해, 그물이 $x$로 수렴한다는 것은 임의의 $x$의 근방 $U$가 주어졌을 때, 그물의 어느 원소에서 시작하든 간에 위로 충분히 올라가다 보면 어느 지점부터 이후의 모든 원소가 $U$에 속한다는 것이다.

일반 위상 공간에서의 그물의 수렴은 1차 가산 공간에서 점렬의 수렴과 대응된다. 즉,

정리. $X$가 1차 가산 공간이라고 하자.

1. $A \subset X$에 대해, $x \in \bar{A}$일 필요충분조건은 $x$로 수렴하는 점렬 $(x_n)$이 존재하는 것이다.
2. $f: X → Y$에 대해, $f$가 연속일 필요충분조건은 임의의 점렬 $(x_n)$에 대해 $x_n → x$라면 $f(x_n) → f(x)$인 것이다.

정리. $X$가 위상 공간이라고 하자.

1. $A \subset X$에 대해, $x \in \bar{A}$일 필요충분조건은 $x$로 수렴하는 그물 $(x_\alpha)$가 존재하는 것이다.
2. $f: X → Y$에 대해, $f$가 연속일 필요충분조건은 임의의 그물 $(x_\alpha)$에 대해 $x_\alpha → x$라면 $f(x_\alpha) → f(x)$인 것이다.

증명.

1. $\mathcal{U}_x$를 $x$의 근방들의 집합이라고 하자. 역포함관계로 $\mathcal{U}_x$에 순서 $\leq$를 준다. $x \in \bar{A}$라면 임의의 $U_\alpha \in \mathcal{U}_x$에 대해 $x_\alpha \in U_\alpha \cap A, x_\alpha \neq x$인 $x_\alpha$가 존재한다. $x_\alpha → x$임을 확인하라.

정의. $(x_\alpha)_{\alpha \in J}$가 그물이라고 하자. $(I, \preceq)$가 방향 집합이고, $g: (I, \preceq) → (J, \leq)$가 순서 보존이며, $\operatorname{im}g$가 공종일 때, $(x_{g(\beta)})_{\beta \in I}$를 $(x_\alpha)$의 부분그물이라고 한다.

정리. $X$가 콤팩트할 필요충분조건은 임의의 그물이 수렴하는 부분그물을 가지는 것이다.

Remark. ”수렴하는 점렬이 존재한다“는 ”수렴하는 그물이 존재한다“보다 강한 조건이지만, ”임의의 점렬이 수렴하는 부분점렬을 가진다”는 “임의의 그물이 수렴하는 부분그물을 가진다”보다 강하지도, 약하지도 않은 조건임에 유의하라. 주어는 후자가 더 강하고, 술어는 전자가 더 강하다. 따라서 콤팩트성과 점렬 콤팩트성은 일반적으로 시사 관계가 없다. 구체적으로,

정리.

1. 콤팩트 $\not\rightarrow$ 점렬 콤팩트
2. 점렬 콤팩트 $\not\rightarrow$ 콤팩트

증명.

1. $[0, 1]^{[0, 1]}$은 티호노프 정리에 의해 콤팩트하지만 점렬 콤팩트하지 않다.
2. Long line과 $\omega_1$은 점렬 콤팩트하지만 콤팩트하지 않다.

Compactness and Nets

01 Dec 2024

Compactness

Definition. Let $X$ be a topological space.

1. $X$ is said to be compact if every open cover has a finite subcover.
2. $X$ is said to be sequentially compact if every sequence $\lbrace x_n \in X \rbrace$ has a convergent subsequence.
3. $X$ is said to be limit point compact if every infinite set $S \subset X$ has a limit point.

Theorem.

1. Compact $\rightarrow$ Limit point compact
2. Sequentially compact $\rightarrow$ Limit point compact
3. Limit point compact $\not\rightarrow$ Compact
4. Limit point compact $\not\rightarrow$ Sequentially compact

Proof.

1. Let $S \subset X$ be an infinite set with no limit points. Since $\overline{S} = S \cup S’ = S$, $S$ is a closed set and $X \setminus S$ is an open set. For any $s \in S$, since $s$ is not a limit point, there exists a neighbourhood $U_s$ of $s$ such that $U_s \cap S = \lbrace s \rbrace$. Therefore, the following open cover of $X$ has no finite subcover:

\[\mathcal{C} = \lbrace X \setminus S \rbrace \cup \bigcup_{s \in S} \lbrace U_s \rbrace\]

1. Let $S \subset X$ be an infinite set. Arbitrarily extract elements of $S$ to form a sequence $\lbrace s_n \rbrace \;(n \neq m \implies s_n \neq s_m)$. Since $X$ is sequentially compact, $\lbrace s_n \rbrace → s$, and $s$ is a limit point of $S$.
2. $\omega_1$ with the order topology is limit point compact but not compact.
3. $X = \mathbb{N} \times \lbrace 0, 1 \rbrace$, where $\mathbb{N}$ is given the discrete topology and $\lbrace 0, 1\rbrace$ is given the trivial topology.

Remark. An incorrect “proof” of 4

Suppose $X$ is limit point compact. Given a sequence $(x_n)$, if $S = \lbrace x_n : n \in \mathbb{N}\rbrace$ is a finite set, then $(x_n)$ trivially has a convergent subsequence. If $S$ is an infinite set, then by the limit point compactness of $X$, there exists $x \in S’$. Now we define a countable collection of neighbourhoods of $x$, $\mathcal{U} = \lbrace U_n \rbrace$, satisfying the following conditions:

1. $n < m \implies U_n \supset U_m$
2. For any neighbourhood $V$ of $x$, $\exists U \in \mathcal{U} : U \subset V$

From this, we can define a function $k: \mathbb{N} → \mathbb{N}$ satisfying the following conditions:

1. $x_{k(n)} \in U_n$
2. $n < m \implies k(n) < k(m)$
3. $n \neq m \implies x_{k(n)} \neq x_{k(m)}$

Condition 2 is possible because when $k(i)$ is defined for $i \leq n$, $T = S \setminus \lbrace x_i : i \leq k(n) \rbrace$ still has $x$ as a limit point. Thus, $(x_n)$ has a convergent subsequence $(x_{k(n)})$.

The above proof is incorrect because the bold portion is not generally possible. Consider, for instance, a topological space where $x \in S’$ has uncountably many neighbourhoods which form uncountably infinite distinct classes of containment chain. Hence, in the diagram below, the same-coloured sets contain one or the other properly, but distinct-coloured sets do not, although they need not be strictly disjoint either. Such a space may be limit point compact yet not be sequentially compact, for there is no guaranteed way to enumerate the points of $S$ into a series such that whichever open set one chooses, for a large enough index, all points after that index is included in that open set. (Exercise: Convince yourself that this is not the case if the open sets can be arranged to form only finite distinct classes of chain, or countably infinite distinct classes of chain.)

Instead, the following holds:

Theorem. In first countable $T_1$ spaces, limit point compactness and sequential compactness are equivalent.

Note that $T_1$-ness is also required, for without it Condition 3 cannot be guaranteed.

Nets and Sequences

Definition. Let $(J, \leq)$ be a preorder. If for any $x, y \in J$, there exists $z \in J$ such that $x, y \leq z$, then $(J, \leq)$ is called a directed set.

Definition. Let $K$ be a subset of $(J, \leq)$. If for any $x \in J$, there exists $y \in K$ such that $x \leq y$, then $K$ is said to be cofinal.

Remark 1. If $(J, \leq)$ is a directed set and $K \subset J$ is cofinal, then $(K, \leq)$ is also a directed set.

Remark 2. As will be shown, cofinality is related with the generalisation of convergence.

Definition. Let $(J, \leq)$ be a directed set. For a topological space $X$, a function $f: J → X$ is called a net. In particular, for $\alpha \in J$, we denote $f(\alpha)$ as $x_\alpha$.

Definition. A net $(x_\alpha)$ converges to $x$ if, for any neighbourhood $U$ of $x$, there exists some $\alpha \in J$ such that

\[\alpha \leq \beta \implies x_\beta \in U\]

The convergence of nets in general topological spaces corresponds to the convergence of sequences in first countable spaces. That is,

Theorem. Let $X$ be a first countable space.

1. For $A \subset X$, $x \in \bar{A}$ if and only if there exists a sequence $(x_n)$ converging to $x$.
2. For $f: X → Y$, $f$ is continuous if and only if for any sequence $(x_n)$, if $x_n → x$ then $f(x_n) → f(x)$.

Theorem. Let $X$ be a topological space.

1. For $A \subset X$, $x \in \bar{A}$ if and only if there exists a net $(x_\alpha)$ converging to $x$.
2. For $f: X → Y$, $f$ is continuous if and only if for any net $(x_\alpha)$, if $x_\alpha → x$ then $f(x_\alpha) → f(x)$.

Proof.

1. Let $\mathcal{U}_x$ be the set of neighbourhoods of $x$. Give $\mathcal{U}_x$ the order $\leq$ by reverse inclusion. If $x \in \bar{A}$, then for any $U_\alpha \in \mathcal{U}_x$, there exists $x_\alpha \in U_\alpha \cap A, x_\alpha \neq x$. Verify that $x_\alpha → x$.

Definition. Let $(x_\alpha)_{\alpha \in J}$ be a net. If $(I, \preceq)$ is a directed set, $g: (I, \preceq) → (J, \leq)$ is order-preserving, and $\operatorname{im}g$ is cofinal, then $(x_{g(\beta)})_{\beta \in I}$ is called a subnet of $(x_\alpha)$.

Theorem. $X$ is compact if and only if every net has a convergent subnet.

Remark. Note that “there exists a convergent sequence” is a stronger condition than “there exists a convergent net”, but “every sequence has a convergent subsequence” is neither stronger nor weaker than “every net has a convergent subnet”. The subject (for every sequence v. for every net) is stronger in the latter case, while the predicate (there exists a subsequence v. there exists a subnet) is stronger in the former case. Therefore, compactness and sequential compactness have no implication relation in general. Specifically,

Theorem.

1. Compact $\not\rightarrow$ Sequentially compact
2. Sequentially compact $\not\rightarrow$ Compact

Proof.

1. $[0, 1]^{[0, 1]}$ is compact by Tychonoff’s theorem but not sequentially compact.
2. The long line and $\omega_1$ are sequentially compact but not compact.

베르 범주 정리

01 Dec 2024

1. 베르 공간

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

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

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

정의. $X$가 위상공간이라고 하자. 각 $n \in \mathbb{N}$에 대해 $F_n$이 내부가 공집합인 $X$의 닫힌집합이라고 하자. $\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 is called a Baire space if every countable union of closed sets, each with empty interior, has empty interior. Equivalently, every countable intersection of dense open sets is dense.

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

• $\lbrace q \rbrace$ is a closed set with empty interior, but $\bigcup_{q \in \mathbb{Q}} \lbrace q\rbrace = \mathbb{Q}$ has nonempty interior.
• $\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$에서 조밀하다.

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