基礎集合論筆記

〔主要參考汪芳庭《數學基礎》、Halmos《Naive Set Theory》〕

現代集合論的研究開始於1870年代由 Cantor 和 Dedekind 提出的樸素集合論. 不久後, 樸素集合論產生的一些悖論陸續被發現, 最著名的如 Russell 悖論和 Cantor 悖論. 為解決悖論, 數學家在20世紀初提出了多種公理集合論, 其中最為常用的是包括選擇公理的 Zermelo-Fraenkel 集合論 ($\text{ZFC}$). 如今, 公理集合論已被公認為數學的基礎理論之一.

集合論公理 (ZFC)

集合公理系統 $\text{ZF}$ 對樸素集合論做出了必要的限制, 以避免悖論的產生.

下面逐條列出 $\text{ZF}$ 的公理:

$\text{ZF0}$ (集存在公理) $\exists x(x=x)$
這是為了保證系統論域非空.

$\text{ZF1}$ (外延公理 Axiom of extensionality) $$\forall x(x\in a\leftrightarrow x\in b)\to a=b$$ 其含義為: 集由外延完全確定. 這條公理也可以寫作 $$(a\subseteq b\wedge b\subseteq a)\to a=b$$

$\text{ZF2}$ (內涵公理 Axiom schema of comprehension) 設 $s$ 為已知集, 則 $$\exists y\forall x(x\in y\leftrightarrow x\in s\wedge p(x))$$ 其中 $p(x)$ 是任一公式, $y$ 不在其中出現.

該公理通常又稱作分離公理或概括公理, 它是一條公理模式, 使用不同的公式 $p$ 可構成無窮多條公理.

Russell 悖論的產生原因是對普遍概括公理的使用, 即可以指定任何由具有性質 $p(x)$ 的 $x$ 的集合; 而 $\text{ZF}$ 的內涵公理則要求預先有一個已知的集合 $s$, 才能定義其中具有 $p(x)$ 性質的 $x$ 組成的子集, 從而嚴格限定 $y$ 在 $s$ 中的規模. 公理要求 $y$ 不在 $p(x)$ 中出現, 是為了避免循環定義問題.

仿照 Russell 悖論的做法, 我們定義 $B=\lbrace x\in A:x\not\in x \rbrace$, 則有 $B\not\in A$. 如若不然, 則或者 $B\in B$ 或者 $B\not\in B$, 若 $B\in B$, 又 $B\in A$, 就有 $B\not\in B$, 矛盾; 若 $B\not\in B$, 又 $B\in A$, 就有 $B\in B$, 同樣推出矛盾. 由於 $A$ 是任意的, 我們在這裡證明了: 不存在全集 (universe). 這表明, 形如 $\lbrace x:\varphi(x) \rbrace$ 的定義方法一定不能隨便使用, 其存在性沒有公理的保證. 特別地, Russell 定義的集合 $\lbrace x:x\not\in x \rbrace$ 肯定不是集.

藉助內涵公理, 我們可以定義集合

$$y=\lbrace x\in s:x\not= x \rbrace$$

其中 $s$ 是任意集 (由 $\text{ZF0}$ 必存在). 這個集稱為空集 (empty set), 記作 $\emptyset$, 它不包含任何元素. 這是目前為止第一個具體的集.

$\text{ZF3}$ (無序對公理 Axiom of pairing) 設 $a$, $b$ 是已知集, 則 $$\exists y\forall x(x\in y\leftrightarrow(x=a\vee x=b))$$ 也可以簡寫為 $$\exists y\thinspace(y=\lbrace a,b \rbrace)$$ 集 $\lbrace a,b \rbrace$ 稱為 $a$, $b$ 的無序對.

進而, 定義 $a$, $b$ 的有序對為

$$(a,b)=\lbrace \lbrace a \rbrace,\lbrace a,b \rbrace \rbrace$$

有序對的定義方法不唯一, 只需用某種方式區分兩個元素的 “地位” 即可.

$\text{ZF4}$ (並集公理 Axiom of union) 設 $a$ 為已知集, 則 $$\exists y\forall x(x\in y\leftrightarrow\exists t\in a(x\in t))$$

把 $\lbrace x:\exists t\in a(x\in t)\rbrace$ 記作 $\bigcup a$. 特別地, $\bigcup\lbrace a,b\rbrace$ 通常寫作 $a\cup b$.

進而, 定義交集概念: 設 $a\not=\emptyset$, 則

$$\bigcap a=\left\lbrace x\in\bigcup a:\forall t\in a(x\in t) \right\rbrace$$

這是在 $\bigcup a$ 上用內涵公理定義的. $a$ 不能為空集, 否則 $\bigcap a$ 就會是 (實際並不存在的) 全集.

$\text{ZF5}$ (冪集公理 Axiom of power set) 設 $a$ 為已知集, 則 $$\exists y\forall x(x\in y\leftrightarrow x\subseteq a)$$

該公理斷言存在的集叫做 $a$ 的冪集, 記作 $\mathcal{P}(a)$, 它由 $a$ 的所有子集組成.
特別地, $\emptyset\in\mathcal{P}(a)$, $a\in\mathcal{P}(a)$.

對任意集 $a$, 顯然有:

1. $\bigcup\mathcal{P}(a)=a$,
2. $\bigcap\mathcal{P}(a)=\emptyset$,
3. $a\subseteq\mathcal{P}(\bigcup a)$.

---

集 $x$ 的後繼, 記為 $x'$, 是指集 $x'=x\cup\lbrace x \rbrace$.
滿足如下條件的集 $a$ 叫做歸納集 (inductive set):

1. $\emptyset\in a$,
2. 若 $x\in a$, 則 $x'\in a$.

$\text{ZF6}$ (無限公理 Axiom of infinity) 歸納集是存在的, 即 $$\exists s(\emptyset\in s\wedge\forall x(x\in s\to x'\in s))$$

令 $\omega$ 是所有歸納集的交集, 則容易知道, $\omega$ 是最小的歸納集. 我們可以按歸納集的定義逐個寫出 $\omega$ 的開頭幾個元素:

$$\emptyset,\enspace\lbrace \emptyset \rbrace,\enspace\lbrace \emptyset,\lbrace \emptyset \rbrace \rbrace,\enspace\lbrace \emptyset,\lbrace \emptyset \rbrace,\lbrace \emptyset,\lbrace \emptyset \rbrace \rbrace \rbrace,\enspace\cdots$$

若集 $x$ 的元素的元素還是 $x$ 的元素, 則稱 $x$ 為可遞集 (transitive set). 即

$$y\in t\in x\Longrightarrow y\in x$$

換句話說, 可遞集 $x$ 的任意元素都是 $x$ 的子集. 可遞集關於後繼運算是封閉的, 從而 $\omega$ 的所有元素都是可遞集.

現規定 $0=\emptyset$, 則可以用集合構造出直觀意義的自然數:

$$\begin{align*} &0 = \emptyset \\ &1 = 0' = 0\cup\lbrace 0 \rbrace = \lbrace \emptyset \rbrace = \lbrace 0 \rbrace \\ &2 = 1' = 1\cup\lbrace 1 \rbrace = \lbrace \emptyset,\lbrace \emptyset \rbrace \rbrace = \lbrace 0,1 \rbrace \\ &\cdots\cdots \end{align*}$$

自然地, $\omega=\lbrace 0,1,2,\cdots \rbrace$ 叫做自然數集, $\omega$ 中元素稱為自然數. 這種構造出自 von Neumann. 事實上, Zermelo 最初定義自然數時使用的是另一種構造: $n'=\lbrace n \rbrace$, 但 von Neumann 的構造相對於 Zermelo 版本有許多優勢, 例如, 可以更方便地定義序關係: $x<y\Longleftrightarrow x\in y$.

於是我們可以根據自然數的集合構造重寫 Peano 公理:

1. $0\in\omega$,
2. 若 $n\in\omega$, 則 $n'\in\omega$,
3. 若 $S\subseteq\omega$, 且滿足 (i) $0\in S$, (ii) $n\in S\Longrightarrow n'\in S$, 則 $S=\omega$.
4. 對任意 $n\in\omega$, $n'\not=0$,
5. 若 $m,n\in\omega$, $m'=n'$, 則 $m=n$,

(3) 根據 $\omega$ 的最小性易證; (4) 是顯然的; 下面證明 (5).

引理: 對任意 $n\in\omega$, $n$ 不是 $n$ 的任何元素的子集; 特別地, $n\not\in n$.

令 $S$ 為滿足上述條件的 $x$ 的集合, 只需證明 $S=\omega$. 顯然 $0\in S$. 設 $n\in S$, 則 $n\not\in n$, 所以 $n'$ 不是 $n$ 的子集; 對任意集 $x$, 若 $n'\subseteq x$, 則 $n\subseteq x$, 由 $n\in S$ 知 $x\not\in n$, 所以 $n'$ 不是 $n$ 的任何元素的子集. 因此 $n'$ 不是 $n'$ 的任何元素的子集, 從而 $n'\in S$. 由 (3), $S=\omega$.

設 $m,n\in\omega$, 且 $m'=n'$, 則 $n\in n'=m'$, 所以或者 $n=m$ 或者 $n\in m$. 同理, 或者 $m=n$ 或者 $m\in n$. 若 $n\not=m$, 則 $n\in m$ 和 $m\in n$ 同時成立, 由可遞性知 $n\in n$. 這與引理矛盾. $\square$

有了上述 Peano 公理, 我們可以期待這樣定義的集合在 “行為” 上與直觀的自然數無異. 因此, $\omega$ 一般也可記作 $\mathbb{N}$. (下文兩符號混用)

歸納定理 (Recursion theorem): 設集 $a$ 和函數 $h:a\to a$ 已知, 且 $x_0\in a$, 則存在唯一函數 $f:\omega\to a$ 滿足

1. $f(0)=x_0$,
2. $f(n')=h(f(n))$.

證明略. 該定理保證了遞歸定義的合理性.

---

以上的 $\text{ZF1}$ 至 $\text{ZF6}$ 是 Zermelo 於1908年提出的, 另外兩條公理則是為使系統更完備, 以及為排除異常集而後續追加的. 這裡先列出 $\text{ZF7}$ 和 $\text{ZF8}$, 其具體作用參見後文.

$\text{ZF7}$ (替換公理 Axiom schema of replacement) 設集 $a$ 和公式 $\varphi(x,y)$ 滿足單值性條件: $$\forall x\in a\thinspace(\exists!y\thinspace\varphi(x,y))$$ 則如下對象也是集: $$\lbrace y:\exists x\in a\thinspace\varphi(x,y) \rbrace$$

$\text{ZF8}$ (正則公理 regularity axiom) 每個非空集都有 $\in$-極小元, 即 $$\forall a\not=\emptyset\thinspace\exists x\in a\thinspace(x\cap a=\emptyset)$$

---

$\text{AC}$ (選擇公理 Axiom of choice) 設 $a$ 是由非空集組成的集族, 則存在以 $a$ 為定義域的函數 $f$ 滿足 $$\forall x\in a(f(x)\in x)$$ 函數 $f$ 叫做族 $a$ 的選擇函數, 它從族 $a$ 的每個成員集 $x$ 內選出一個代表 $f(x)$.

推論 (單值化原則): 對任意關係 $r\subseteq a\times b$, 若其定義域 $\text{Dom}(r)=a$, 則 $r$ 可以單值化為以 $a$ 為定義域的函數, 即存在 $a$ 到 $b$ 的函數 $f\subseteq r$. 換句話說, 任何一個非單值的關係 $r$ 可以 “切削” 為一個函數 $f$.

使用選擇公理, 我們能證明任意無限集都有可數子集. 這個問題在數學分析中往往被一筆帶過, 甚至不會提及證明中對選擇公理的隱含使用, 但如果要以真正嚴格的方式寫出證明, 其實並不那麼容易.

證明: 設 $X$ 為無限集, $f$ 為 $X$ 的所有非空子集到 $X$ 的選擇函數, 即 $f:\mathcal{P}(X)\setminus\lbrace \emptyset \rbrace\to X$, $A\mapsto f(A)\in A$. 令 $\mathcal{C}$ 為 $X$ 的所有有窮子集構成的集, 則對任意 $A\in\mathcal{C}$, $X-A$ 非空, 所以 $X-A$ 屬於 $f$ 的定義域. 定義函數 $g:\mathcal{C}\to\mathcal{C}$, $g(A)=A\cup\lbrace f(X-A) \rbrace$. 對 $g$ 使用歸納定理: 選定 $\emptyset$ 為初始值, 則存在函數 $h:\omega\to\mathcal{C}$, $h(0)=\emptyset$, 且對任意 $n\in\omega$, $h(n')=h(n)\cup\lbrace f(X-h(n)) \rbrace$. 令 $v(n)=f(X-h(n))$, 則容易看出 $v:\omega\to X$ 是一個單射, 從而必存在 $X$ 的子集 $S$ 可與 $\omega$ 建立雙射, 即 $S\subseteq X$ 是可數集. $\square$

自然數的性質

加法和乘法

根據歸納定理(參見上文), 對任意 $m\in\omega$, 存在唯一的函數 $f_m:\omega\to\omega$ 滿足

$$\begin{align*} &f_m(0) = m, \\ &f_m(n') = (f(n))' \end{align*}$$

定義自然數加法為 $m+n=f_m(n)$, 則有 $m+0=m$, $m+n'=(m+n)'$.

同理, 對任意 $m\in\omega$, 存在唯一的函數 $g_m:\omega\to\omega$ 滿足

$$\begin{align*} &g_m(0) = 0, \\ &g_m(n') = g_m(n)+m \end{align*}$$

定義自然數乘法為 $m\cdot n=f_m(n)$.

自然數的序

稱兩自然數 $m$, $n$ 是可比的, 如果有 $m\in n$, $m=n$, $n\in m$ 之一成立. 我們有

命題: 任意兩個自然數都是可比的.

這一命題又叫做三分律.

證明: 首先, 對任意 $n\in\omega$, 令 $S(n)$ 為所有與 $n$ 可比的 $m\in\omega$ 的集合; 進而令 $S$ 為所有使得 $S(n)=\omega$ 的 $n$ 的集合. 只須證明 $S=\omega$ 即可. 顯然, $0\in S(0)$, 假設 $m\in S(0)$, 由於 $m\not\in 0$, 或者 $0=m$ 或者 $0\in m$, 不論如何都有 $0\in m'$, 歸納可知 $S(0)=\omega$. 假設 $S(n)=\omega$, 由 $n'\in S(0)$ 知 $0\in S(n')$, 若 $m\in S(n')$. 則可能有: $n'\in m$, $n'=m$ 或 $m\in n'$, 前兩種情況下都有 $n'\in m'$. 在第三種情況下, 若 $m=n$, 則 $m'=n'$; 若 $m\in n$, 則由 $m'\in S(n)$ 知 $n\in m'$, $n=m'$, $m'\in n$ 必居其一, 第一種情況是不可能的, 否則 $n\subseteq m$, 與 $m\in n$ 矛盾 (任何自然數不能是其元素的子集). 因此在所有可能的情況下都有 $m'\in S(n')$, 歸納知 $S(n')=0$. 最後, $S(0)=\omega$, $S(n)=\omega$ $\Longrightarrow$ $S(n')=\omega$, 從而 $S=\omega$. $\square$

由 $n\in\omega$ 的可遞性知, $m\in n$ 的一個必要條件是 $m\subseteq n$. 更確切地說, $m\in n$ $\Longleftrightarrow$ $m\subseteq n$ 且 $m\not=n$. 下面把 $m\in n$ 寫作 $m<n$, 把 $m\subseteq n$ 寫作 $m\leq n$. 若 $m\leq n$ 且 $n\leq m$, 則 $m=n$.

構造整數和有理數

整數

考慮 $\mathbb{N}^2$ 上的二元關係 $R$:

$$R=\lbrace ((m,n),(p,q)):m,n,p,q\in\mathbb{N},\thinspace m+q=n+p \rbrace$$

把 $R$ 記作 $\sim$, 則

$$(m,n)\sim(p,q)\Longleftrightarrow m+q=n+p,\enspace m,n,p,q\in\mathbb{N}$$

顯然, $\sim$ 是一個等價關係.

關於這個等價關係的所有等價類的集 (商集) 用 $\mathbb{Z}$ 來表示:

$$\mathbb{Z}=\mathbb{N}^2/{\sim}=\lbrace \left[(m,n)\right]:m,n\in\mathbb{N} \rbrace$$

---

$\mathbb{Z}$ 上加法定義為 $$\left[(m,n)\right]+\left[(p,q)\right]=\left[(m+p,n+q)\right]$$

容易驗證, 這樣定義的加法是合理的, 且它滿足交換律和結合律. 把 $\left[(0,0)\right]$ 這個特殊的等價類叫做 $\mathbb{Z}$ 的零元, 記作 $\overline{0}$. $\forall a\in\mathbb{Z}\thinspace(a+\overline{0}=a)$.

$\mathbb{Z}$ 中每個元素都有唯一負元, 這條性質是自然數加法所不具備的: $$-\left[(m,n)\right]=\left[(n,m)\right]$$

據此可以在 $\mathbb{Z}$ 上定義減法: $b-a=b+(-a)$.

$\mathbb{Z}$ 上乘法定義為 $$\left[(m,n)\right]\cdot\left[(p,q)\right]=\left[(mp+nq,mq+np)\right]$$

交換律, 結合律和分配律很容易驗證. 把 $\left[(1,0)\right]$ 叫做 $\mathbb{Z}$ 的乘法單位元, 記作 $\overline{1}$. $\forall a\in\mathbb{Z}\thinspace(a\cdot\overline{1}=a)$.

定義 $\mathbb{Z}$ 中的序如下:

$$\left[(m,n)\right]<\left[(p,q)\right]\Longleftrightarrow m+q<n+p$$

---

考慮 $\mathbb{Z}$ 的子集 $\overline{\mathbb{N}}$:

$$\overline{\mathbb{N}}=\lbrace \left[(0,0)\right],\left[(1,0)\right],\cdots,\left[(n,0)\right],\cdots \rbrace$$

顯然, 可以在 $\overline{\mathbb{N}}$ 和自然數集 $\mathbb{N}$ 之間建立保運算, 保序的雙射 $f$, 這表明 $\overline{\mathbb{N}}$ 和 $\mathbb{N}$ 是同構的. 稱 $f$ 把 $\mathbb{N}$ 同構嵌入 $\mathbb{Z}$.

有理數

仿照定義整數集的做法, 首先定義 $\mathbb{Z}\times\left(\mathbb{Z}-\lbrace 0 \rbrace\right)$ 上的二元關係 $R$, 記作 $\sim$:

$$(a,b)\sim(c,d)\Longleftrightarrow ad=bc,\enspace a,b,c,d\in\mathbb{Z},\enspace b,d\not=0$$

定義 $\mathbb{Q}=(\mathbb{Z}\times\left(\mathbb{Z}-\lbrace 0 \rbrace\right))/{\sim}$.

$\mathbb{Q}$ 上加法定義為 $\left[(a,b)\right]+\left[(c,d)\right]=\left[(ad+bc,bd)\right]$. $\mathbb{Q}$ 上乘法定義為 $\left[(a,b)\right]\cdot\left[(c,d)\right]=\left[(ac,bd)\right]$. $\mathbb{Q}$ 中的序定義為 $\left[(a,b)\right]<\left[(c,d)\right]\Longleftrightarrow ad<bc$.

考慮 $\mathbb{Q}$ 的子集 $\overline{\mathbb{Z}}=\lbrace \left[(p,1)\right]:p\in\mathbb{Z} \rbrace$. 則 $\overline{\mathbb{Z}}$ 與 $\mathbb{Z}$ 同構, 表明 $\mathbb{Z}$ 可以嵌入 $\mathbb{Q}$.

算術超濾與實數

濾子

設 $\mathbb{N}$ 上的子集族 $F\in\mathcal{P}(\mathbb{N})$ 滿足:

1. $\emptyset\not\in F$, $\mathbb{N}\in F$,
2. 若 $a,b\in F$, 則 $a\cap b\in F$,
3. 若 $a\subseteq b\subseteq \mathbb{N}$ 且 $a\in F$, 則 $b\in F$.

則稱 $F$ 為 $\mathbb{N}$ 上的濾子. 若濾子 $F$ 滿足條件4:

4. $\forall a\subseteq\mathbb{N}(a\in F\vee \mathbb{N}-a\in F)$ (極大性),

則稱 $F$ 為 $\mathbb{N}$ 上的超濾 (ultrafilter). 進而, 若超濾 $F$ 滿足條件5:

5. $\mathbb{N}$ 的任意有限子集不屬於 $F$,

則稱 $F$ 為 $\mathbb{N}$ 上的自由超濾.

令 $F_{\sigma}=\lbrace a\subseteq \mathbb{N}:$ $\mathbb{N}-a$ 是有限集$\rbrace$, 則 $F_{\sigma}$ 滿足上面的條件1, 2, 3, 5. $F_{\sigma}$ 中任意集的餘集都是有限集, 所以我們把 $F_{\sigma}$ 稱作餘有限子集濾子或 Fréchet 濾子.

子集族 $F_n=\lbrace a\subseteq \mathbb{N}:n\in a\rbrace$ 是超濾, 但不是自由超濾. 這種超濾稱為 $\mathbb{N}$ 上的主超濾, 每個主超濾 $F_n$ 都含有單點集 $\lbrace n\rbrace$.

---

命題: 設 $F$ 是 $\mathbb{N}$ 上的超濾, 且 $a_1\cup a_2=a\in F$, 則 $a_1\in F\vee a_2\in F$.

證明: $\mathbb{N}-a=(\mathbb{N}-a_1)\cap(\mathbb{N}-a_2)\not\in F$, 所以有 $\mathbb{N}-a_1\not\in F$ 或 $\mathbb{N}-a_2\not\in F$, 即 $a_1\in F\vee a_2\in F$. $\square$

由上述命題知, 若有限集 $a=\lbrace n_1\rbrace\vee\lbrace n_2\rbrace\vee\cdots\vee\lbrace n_k\rbrace\in F$, 則必有某個單點集 $\lbrace n_i\rbrace\in F$, 同時若有 $\lbrace n_i\rbrace$, $\lbrace n_j\rbrace$ 同時屬於 $F$, 就有 $\lbrace n_i\rbrace\wedge\lbrace n_j\rbrace=\emptyset\in F$, 矛盾. 所以有且僅有一個單點集 $\lbrace n_i\rbrace\in F$, 即 $F$ 為 $\mathbb{N}$ 上的主超濾. 換句話說, $\mathbb{N}$ 上非自由的超濾一定是某個主超濾. 反過來, 要想得到 $\mathbb{N}$ 上的非主超濾, 我們把 Fréchet 濾子擴張為極大濾子, 使之成為一個超濾. 這一點的可行性由濾子擴張原則保證: 任何濾子都可以擴張成一個超濾, 它可以用選擇公理來證明 (參見下文).

直觀來看, 濾子相應於自然數性質的相容組合 (關係網), 而超濾相應於自然數性質的極大相容組合 (極大關係網). 假定 $a=\lbrace x\in\mathbb{N}:p(x)\rbrace$, $b=\lbrace x\in\mathbb{N}:q(x)\rbrace$ 且 $a,b\in F$, 則 $a\cap b=\lbrace x\in\mathbb{N}:p(x)\wedge q(x)\rbrace\in F$, 由於 $a\cap b\not=\emptyset$, 必存在 $x\in\mathbb{N}$ 滿足 $p(x)\wedge q(x)$, 這就是 “相容” 性質的含義. 特別地, 主超濾 $F_n$ 相當於用自然數 $n$ 的所有性質 “濾” 出唯一的自然數, 其中必包含集 $\lbrace n\rbrace=\lbrace x\in\mathbb{N}:x=n\rbrace$ 和 $\mathbb{N}=\lbrace x\in\mathbb{N}:x=x\rbrace$ (作為最 “狹窄” 和最 “寬泛” 的性質).

命題: $F$ 是超濾 $\Longleftrightarrow$ $F$ 是極大濾子.

證明: 設 $F$ 為超濾, 若有更大的濾子 $G\supset F$. 因為 $G\not=F$, 所以存在 $a\in G$ 且 $a\not\in F$, 則 $\mathbb{N}-a\in F\subset G$, $\mathbb{N}-a\cap a=\emptyset\in G$, 矛盾. 反過來設 $F$ 是極大濾子, 若存在 $a\in F$ 使得 $\mathbb{N}-a\not\in F$, 故對任意 $b\in F$ 都有 $b\cap a\not=\emptyset$. 拿 $a$ 與 $F$ 中元素分別取交, 並將交集與更大的集添加入 $F$, 便得到一個更大的濾子, 矛盾. $\square$

超濾變換

把 $\mathbb{N}$ 上所有超濾組成的集記作 $\beta\mathbb{N}$. 設 $F\in\beta\mathbb{N}$, $f\in{}^{\mathbb{N}}{\mathbb{N}}$, 則如下子集族 $G$ 也是 $\mathbb{N}$ 上的超濾:

$$G=\lbrace a\subseteq \mathbb{N}:f^{-1}\left[a\right]\in F\rbrace$$

若 $a\not\in G$, 則有 $f^{-1}\left[\mathbb{N}-a\right]=\mathbb{N}-f^{-1}\left[a\right]\in F$ ($f\left[\mathbb{N}\right]\subseteq\mathbb{N}$ $\Longrightarrow$ $f^{-1}\left[\mathbb{N}\right]=\mathbb{N}$), 即 $\mathbb{N}-a\in G$, 這保證了 $G$ 的極大性. 其餘幾條性質顯然滿足.

稱這樣定義的 $G$ 為 $F$ 在變換 $f$ 下的像, 記作 $f(F)$. $\mathbb{N}$ 上的一元運算 $f$ 確定了 $\beta\mathbb{N}$ 上的一個一元運算, 稱作超濾空間的超濾變換 $f:F\mapsto f(F)$.

把 $\mathbb{N}$ 上的主超濾 $F_n$ 記作 $\overline{n}$, 那麼顯然有 $f(\overline{n})=\overline{f(n)}$, 這表明自然數集 $\mathbb{N}$ 與所有主超濾組成的集是同構的. 若取 $f$ 為常函數 $f(x)=m$, 則對任何超濾 $F$ 都有 $f(F)=\overline{m}$, 故非主超濾在超濾變換下有可能退化為主超濾. 進而, 若 $f$ 在 $b\in F$ 上取常值 $m$, 同樣有 $f(F)=\overline{m}$. 這是因為, 只要有某個 $b\in F$ 被 $f$ 映到單點集 $\lbrace m\rbrace$, 由超濾的性質, 我們立即能知道 $G=f(F)$ 是主超濾 $\overline{m}$.

若函數 $f\in{}^{\mathbb{N}}{\mathbb{N}}$ 滿足 $\lbrace n:f(n)=m\rbrace\in F$, 則稱 $f$ 關於超濾 $F$ 幾乎等於 $m$, 記作 $f=_{F} m$. 所以, 我們有

$$f=_{F} m \Longrightarrow f(F)=\overline{m}$$

一般地, 若 $\lbrace n:f(n)=g(n)\rbrace\in F$, 則稱 $f$ 和 $g$ 關於 $F$ 幾乎相等, 記作 $f=_{F} g$.

$$f=_{F} g \Longrightarrow f(F)=g(F)$$

如若不然, 假設 $b\in f(F)$ 且 $b\not\in g(F)$, 則 $g^{-1}\left[\mathbb{N}-b\right]=\mathbb{N}-g^{-1}\left[b\right]\in F$, 所以有

$$f^{-1}\left[b\right]\cap\mathbb{N}-g^{-1}\left[b\right]\cap\lbrace n:f(n)=g(n)\rbrace\in F$$

左式為 $\emptyset$, 矛盾. $\square$

構造非標準算術模型

$\mathbb{N}$ 上的超濾 $F$ 若滿足如下性質, 則稱之為算術超濾: $$f(F)=g(F)\Longrightarrow f=_{F} g$$

並非每個超濾都是算術超濾. 顯然, 主超濾都是算術超濾; 若 $F$ 是算術超濾, 則 $f(F)$ 也是算術超濾.

接下來的構造依賴於非主算術超濾的存在性, 這裡省略證明. 一個連續統假設蘊含非主算術超濾存在的證明可參見汪芳庭《數學基礎》.

每個非主算術超濾 $F$ 都聯繫著一個算術模型 $^{*}{\mathbb{N}}$:

$$^{*}{\mathbb{N}}=\lbrace f(F):f\in {}^{\mathbb{N}}{\mathbb{N}}\rbrace$$

取定非主算術超濾 $F$, 定義 $^{*}{\mathbb{N}}$ 上的運算如下:

$$\begin{align*} &f(F)+g(F) = (f+g)(F)\\ &f(F)\cdot g(F) = (f\cdot g)(F) \end{align*}$$

設 $h$ 是 $\mathbb{N}$ 上的一元運算, 定義

$$h(f(F)) = (h\circ f)(F)$$

這樣就把 $h$ 的定義域從 $\mathbb{N}$ 延拓到 $^{*}{\mathbb{N}}$ 上.

$^{*}{\mathbb{N}}$ 中的序定義為 $$f(F)<g(F) \Longleftrightarrow \lbrace n:f(n)<g(n)\rbrace\in F$$

又記作 $f<_{F} g$ ($f$ 關於 $F$ 幾乎小於 $g$). $F$ 是非主超濾, 所以 $\lbrace n:f(n)<g(n)\rbrace$ 是無限集, 我們可以把 $f(F)$ 和 $g(F)$ 想象成兩個數列, 那麼序的定義是很直觀的: $f(F)<g(F)$ 當且僅當兩者的無窮多個 “分量” 具有此關係.

---

令 $f=m$ 為常函數, 則 $f(F)=\overline{m}$ 是主超濾, 由所有主超濾構成的集記作 $\overline{\mathbb{N}}\in{}^{*}{\mathbb{N}}$, 記 $\mathbb{N}_{\infty}={}^{*}{\mathbb{N}}-\overline{\mathbb{N}}$. 如前文所述, $\mathbb{N}$ 與 $\overline{\mathbb{N}}$ 同構, 所以 $\mathbb{N}$ 可同構嵌入 $^{*}{\mathbb{N}}$. 如下命題表明, $\overline{\mathbb{N}}$ 是 $^{*}{\mathbb{N}}$ 的初始段.

命題: $\tau\in\mathbb{N}_{\infty}$ $\Longrightarrow$ $\forall m\in \mathbb{N}(\tau>\overline{m})$.

證明: 反設 $\tau=g(F)\leq\overline{m}$, 則 $\lbrace n:g(n)\leq m\rbrace\in F$, 即

$$\lbrace n:g(n)=0\rbrace\cup\cdots\cup\lbrace n:g(n)=m\rbrace\in F$$

由超濾的性質, 必有 $k\leq m$ 使得 $\lbrace n:g(n)=k\rbrace\in F$, 即 $\tau=g(F)=\overline{k}$, 矛盾. $\square$

由此可知, 自然數的非標準模型 $^{*}{\mathbb{N}}$ 相對於 $\mathbb{N}$ 加入了 “無窮大自然數”. 因此 $^{*}{\mathbb{N}}$ 的形象為

$$0,1,2,\cdots,n,\cdots,\tau,\tau+1,\cdots$$

對於這些無窮大自然數, 容易驗證其具有如下性質:

1. 序保持:

$$\forall n\in\mathbb{N}(h(n)<g(n)) \Longrightarrow \forall \tau\in\mathbb{N}_{\infty}(h(\tau)<g(\tau))$$

2. 單調性保持:

$$\forall i,j\in\mathbb{N}(i<j\to h(i)<h(j)) \Longrightarrow \forall x,y\in\mathbb{N}_{\infty}(x<y\to h(x)<h(y))$$

3. 分數單調性保持:

$$\forall i,j\in\mathbb{N}(i<j\to h(i)l(j)<h(j)l(i)) \Longrightarrow \forall x,y\in\mathbb{N}_{\infty}(x<y\to h(x)l(y)<h(y)l(x))$$

自然數的非標準模型有另一種 (不那麼顯式的) 構造方法, 使用了一階邏輯的緊緻性定理

構造實數

效仿上文從 $\mathbb{N}$ 構造整數和有理數的方法, 我們從 $^{*}{\mathbb{N}}$ 出發構造出整數和有理數的非標準模型:

$$^{*}{\mathbb{Z}} = \lbrace \cdots,-\tau\cdots,-n,\cdots,-1,0,1,\cdots,n,\cdots,\tau,\cdots\rbrace$$ $$^{*}{\mathbb{Q}} = \left\lbrace \frac{p}{q}:p,q\in{}^{*}{\mathbb{Z}},p\not=0\right\rbrace$$ $^{*}{\mathbb{Q}}$ 中含兩類元素, 一類比任意自然數都要大, 另一類則是有限元素, 它們構成的集記作 $\mathbb{Q}_{<}=\lbrace x\in{}^{*}{\mathbb{Q}}:\exists k\in\mathbb{N}\thinspace|x|<k\rbrace$, 稱為 $^{*}{\mathbb{Q}}$ 的 Archimedes 子集, 而 $^{*}{\mathbb{Q}}$ 自身則是一個非 Archimedes 序域. $^{*}{\mathbb{Q}}$ 的另一重要子集是 $$\mathbb{I}=\left\lbrace \alpha\in{}^{*}{\mathbb{Q}}:\forall k\in \mathbb{N}-\lbrace 0\rbrace\left(|\alpha|<\frac{1}{k}\right)\right\rbrace$$ $\mathbb{I}$ 中元素稱為無窮小, 其定義是直觀的.

無窮小的另一種構造方法是, 在系統中添加公式集 $\Sigma=\lbrace |\alpha|<1/n:n\in\mathbb{N}\rbrace$, 隨後用緊緻性定理說明其可被滿足.

定義 $\mathbb{Q}_{<}$ 上的二元關係 $\sim$: $x\sim y$ $\Longleftrightarrow$ $x-y\in \mathbb{I}$, 則 $\sim$ 顯然是一個等價關係. 記 $x\in \mathbb{Q}_{<}$ 所在等價類為 $\left[x\right]$, 所有等價類構成的集記作 $\mathbb{Q}_{<}/{\sim}$.

在 $\mathbb{Q}_{<}/{\sim}$ 中定義運算:

$$\begin{align*} &\left[x\right]+\left[y\right] = \left[x+y\right] \\ &\left[x\right]\cdot\left[y\right] = \left[x\cdot y\right] \end{align*}$$

定義序:

$$\left[x\right]<\left[y\right] \Longleftrightarrow x<y \wedge x\not\sim y$$

容易驗證, 結構 $\langle \mathbb{Q}_{<}/{\sim},+,\cdot,<,\left[0\right],\left[1\right]\rangle$ 是一個序域. 下面記

$$\mathbb{R} = \mathbb{Q}_{<}/{\sim} = \lbrace \left[x\right]:x\in\mathbb{Q}_{<}\rbrace$$

下面來證明 $\mathbb{R}$ 的完備性.

引理1: $\mathbb{Q}$ 在 $\mathbb{R}$ 中稠: $\forall a,b\in\mathbb{R}(a<b\to \exists r\in\mathbb{Q}(a<r<b))$.

證明: 由 $\mathbb{R}$ 的 Archimedes 性易證. $\square$

引理2: $\mathbb{R}$ 中嚴格單調遞增有上界的有理數列必有上確界.

證明: 設有理數列 $r_i=m_i/n_i$ 滿足 $r_0<r_1<\cdots\leq k\in\mathbb{N}$, 不妨設 $r_1>0$, 則有

$$\frac{m_i}{n_i}<\frac{m_{\tau}}{n_{\tau}}\leq k,\enspace \tau\in\mathbb{N}_{\infty}$$

記 $a=\left[m_{\tau}/n_{\tau}\right]\in\mathbb{R}$, 則 $a$ 為數列 $r_i$ 的上界. 任取 $b<a$, 因 $\mathbb{Q}$ 在 $\mathbb{R}$ 中稠, 可取 $p,q\in\mathbb{N}$ 使得 $b<p/q<a$, 若對任意 $r_i$ 都有 $r_i<p/q$, 那麼就有 $r_{\tau}<p/q$, 故 $a=\left[m_{\tau}/n_{\tau}\right]\leq p/q$, 矛盾. 因此, $b$ 不是 $r_i$ 的上界, 故 $a$ 是 $r_i$ 的上確界. $\square$

定理: 單調遞增有上界的實數列必有上確界.

證明: 設實數列 $x_n$ 滿足 $x_0\leq x_1\leq\cdots\leq k$, 若 $x_i$ 在某一項後恆為常數, 則該常數即為上確界; 若 $x_n$ 有嚴格單調遞增的子列, 則可以取有理數列 $r_i$ 滿足

$$x_{n_0}<r_0<x_{n_1}<r_1<\cdots<r_i<x_{n_i}<\cdots\leq k$$ $r_i$ 的上確界即為 $x_n$ 的上確界. $\square$

這種構造方法將實數定義為有限分數的等價類, 其想法可以追溯到古希臘 (Eudoxus). 另外兩種常見的定義實數的方法是 Dedekind 分割和 Cantor 的有理數基本列構造法, 可以證明, 不同方法構造出的實數是同構的. 相比其他構造方法, 使用非主算術超濾的方法依賴於 (弱形式的) 選擇公理, 原因是它最初構造出的域包含非標準成分, 隨後通過模去無窮小才回到標準實數域.

序與序數

偏序與全序

若集 $X$ 上的二元關係 $R$ 滿足自反性, 反對稱性 ($xRy$, $yRx$ $\Longrightarrow$ $x=y$) 和傳遞性 (傳遞性與集合的可遞性在英文裡是同一個詞, 在此作區別是為強調前者是關係的性質, 後者是集合的性質), 則稱 $R$ 為 $X$ 上的偏序 (partial order) 關係, 記作 $\leq$. 進而, 如果對任意 $x,y\in X$, 都有 $x\leq y$ 或 $y\leq x$, 則稱 $\leq$ 為一個全序 (total order), 有時也稱作線序. 一個全序集通常叫做一條鏈 (chain). 偏序集 $X$ 連同其上的偏序關係 $R$ 形成偏序結構 $\langle X,R\rangle$. 例如, 給定集 $a$, $\langle \mathcal{P}(a),\subseteq\rangle$ 就是一個偏序結構. 僅當 $a$ 為空集或單點集時, $\subseteq$ 是 $\mathcal{P}(a)$ 上的全序.

若集 $X$ 上的二元關係 $R$ 滿足反自反性 ($x\cancel{R} x$), 非對稱性 ($xRy$ $\Longrightarrow$ $y\cancel{R} x$) 和傳遞性, 則稱 $R$ 為 $X$ 上的嚴格偏序關係, 記作 $<$; 相應地, 也把 $\leq$ 叫做弱偏序.

顯然, 上文定義的自然數的序 $\in$ 和 $\subseteq$ 分別是嚴格偏序和弱偏序.

---

設 $X$ 為偏序集,

1. 若 $\forall y\in a\thinspace y\not<x$, 則稱 $x$ 是 $X$ 的極小元,
2. 若 $\forall y\in a\thinspace x\leq y$, 則稱 $x$ 是 $X$ 的最小元. ($y\leq x$ $\Longrightarrow$ $y=x$)

極大元和最大元的定義類似. 最小元一定是極小元, 但反之不一定; 最小元若存在必唯一, 極小元則可能不唯一. 設非空集 $A$ 不是單點集, 考慮 $A$ 的所有非空子集的集合 $\mathcal{C}$, 以 $\subseteq$ 為 $\mathcal{C}$ 上的偏序, 則 $\mathcal{C}$ 中的每個單點集都是極小元, 但 $\mathcal{C}$ 沒有最小元.

設 $E$ 為偏序集 $X$ 的子集, $a\in X$, 若對任何 $x\in E$ 都有 $a\leq x$, 則稱 $a$ 為 $E$ 的一個下界. 把 $E$ 的所有下界的集合記作 $\underline{E}$, 若 $\underline{E}$ 有最大元 $a^{*}$, 則稱 $a^{*}$ 為 $E$ 的下确界, 記作 $\inf E$. 類似地, $E$ 的上確界定義為它的所有上界構成的集合的最小元, 記作 $\sup E$.

設 $A$ 為全序集, $B\subsetneq A$, 若 $B$ 滿足

$$\forall x\in B\thinspace\forall y\in A\thinspace(y<x\to y\in b)$$

則稱 $B$ 為 $A$ 的初始段 (initial segment). 例如, 開區間 $(-\infty,0)$ 是 $\mathbb{R}$ 的初始段.

良序

若集 $X$ 上的二元關係 $R$ 滿足如下性質, 就叫做 $X$ 上的良序 (well-order):

1. 反自反性: $\forall x\in X\thinspace\neg(xRx)$,
2. 傳遞性: $\forall x,y,z\in X\thinspace(xRy\wedge yRz\to xRz)$,
3. 三分律: $\forall x,y\in X\thinspace(xRy\vee x=y\vee yRx)$,
4. 良基性: $X$ 的任意非空子集都有 $R$-極小元.

良序集 $X$ 連同其上的良序 $R$ 形成良序結構 $\langle X,R\rangle$. 因為有三分律, 極小元就是最小元, 所以良序集的任意非空子集都有最小元.

若 $S$ 是良序集, $x\in S$, 則 $S$ 的初始段可以更容易地表示為

$$S_x=\lbrace t\in X:t<x \rbrace$$

全序集的初始段不一定能這樣表示. 例如, 帶通常序的有理數集 $\mathbb{Q}$ 是全序集, 但不滿足良基性, 其初始段 $\lbrace x\in\mathbb{Q}:x<0\vee x^2<2 \rbrace$ 就不能表示為上述形式.

命題: 設 $S$ 為良序集, $f:S\to S$ 是增函數, 則對任意 $x\in S$ 都有 $f(x)\geq x$.

證明: 假設 $X=\lbrace x\in S:f(x)<x \rbrace$ 非空, 則它必有最小元 $m$. 因為 $f(m)<m$, 所以 $f(f(m))<f(m)$, 而這與 $m$ 的最小性矛盾. $\square$

兩個推論:

1. 良序集到自身的同構映射只有恆同映射. 這是因為, 對任意 $x\in S$ 都有 $f(x)\geq x$, $f^{-1}(x)\geq x$ $\Longrightarrow$ $f(x)=x$;
2. 良序集不能與自身的初始段同構. 否則, 同構映射 $f:S\cong S_u$ 的值域為 $\lbrace x:x<u \rbrace$, 所以有 $f(u)<u$, 與上述命題矛盾.

---

自然數集 $\mathbb{N}$ 上的歸納法很容易推廣到一般的良序集. 我們有

超限歸納法: 設 $X$ 是良序集, $p(x)$ 是 $x$ 的某個性質, 則 $$\forall x\in X\thinspace((\forall y<x:p(y))\to p(x))\Longrightarrow \forall x\in X:p(x)$$

換句話說, 設 $X$ 的子集 $S=\lbrace x\in X:p(x) \rbrace$, 若對任意 $x\in X$, 都有 $s(x)\in S$, 則 $S=X$. 證明幾乎是顯然的: 反設 $S\not=X$, 則 $X-S$ 非空, 由良基性知必有最小元 $x_0\in X-S$; 但 $s(x_0)\subseteq S$, 由歸納假設可知 $x_0\in S$, 矛盾. $\square$

自然數的第二歸納法 (強歸納法) 是超限歸納法的直接推論.

良序集基本定理: 對任意良序集 $A$ 和 $B$, 有 $$A\cong B\vee \exists y\in B\thinspace(A\cong B_y)\vee\exists x\in A\thinspace(B\cong A_x)$$

即: $A$ 與 $B$ 同構, $A$ 與 $B$ 的初始段同構, 或 $B$ 與 $A$ 的初始段同構, 三者必居其一.
證明略 (在直觀上是顯然的). 該定理保證了序數的可比性.

序數

$\in$-良序的可遞集叫做序數 (ordinal). 設集 $\alpha$ 是一個序數, 則它滿足

1. $\in$-反自反性: $\forall x\in\alpha\thinspace(x\not\in x)$,
2. $\in$-傳遞性: $\forall x,y,z\in\alpha\thinspace(x\in y\wedge y\in z\to x\in z)$,
3. $\in$-三分律: $\forall x,y\in\alpha\thinspace(x\in y\vee x=y\vee y\in x)$,
4. $\in$-良基性: $\alpha$ 的任意非空子集有 $\in$-極小元,
5. $\alpha$ 是可遞集: $y\in x\wedge x\in\alpha\to y\in\alpha$.

基本性質

下面是序數的幾個簡單性質.

性質1: 若 $\alpha\not=0$, 則 $0\in\alpha$. 這一點由 $\in$-最小元的存在性容易看出.

性質2: 序數的元素也是序數: $x\in\alpha$ $\Longrightarrow$ $x$ 是序數.
證明: 由 $\alpha$ 的可遞性知 $x\in\alpha$ $\Longrightarrow$ $x\subseteq\alpha$, 所以 $x$ 是 $\in$-良序集 (良序集的子集也是良序集). 設 $z\in y$, $y\in x$, 則由 $\alpha$ 的可遞性知 $y\in\alpha$, $z\in\alpha$, 又由 $\in$-傳遞性得 $z\in x$, 從而 $x$ 也是可遞集. 故 $x$ 是序數. $\square$

性質3: 設 $\alpha$ 為序數, $\xi\in\alpha$, 則 $\alpha_{\xi}=\xi$, 換句話說, 序數的初始段就是其端點.
證明: $\xi$ 為端點的初始段恰為 $\lbrace t\in\alpha:t\in\xi \rbrace$, 所以對任意 $t\in\alpha_{\xi}$ 都有 $t\in\xi$, 即 $\alpha_{\xi}\subseteq\xi$; 又由 $\alpha$ 的可遞性知, $t\in\xi\in\alpha$ $\Longrightarrow$ $t\in\alpha$, 所以對任意 $t\in\xi$ 都有 $t\in\alpha_{\xi}=\lbrace t\in\alpha:t\in\xi \rbrace$, 即 $\xi\subseteq\alpha_{\xi}$. $\square$

性質4: 若序數 $\alpha$ 和 $\beta$ 同構 ($\alpha\cong\beta$), 則 $\alpha=\beta$.
證明: 設 $f:\alpha\cong\beta$, 我們證明 $\forall x\in\alpha\thinspace(f(x)=x)$. 記 $S=\lbrace \xi\in\alpha:f(\xi)=\xi \rbrace$, 對任意 $\xi\in\alpha$, $\alpha-\alpha_{\xi}$ 的最小元就是 $\xi$, 由 $f$ 的保序性知, $\beta-f\left[\alpha_{\xi}\right]$ 的最小元應為 $f(\xi)$. 所以若 $\alpha_{\xi}\subseteq S$, 則 $f(\xi)$ 和 $\xi$ 有相同的初始段, 因此有 $f(\xi)=\xi$. 由超限歸納法原理, $S=\alpha$, 從而 $\alpha\subseteq\beta$. 完全對稱地有 $\beta\subseteq\alpha$, 所以 $\alpha=\beta$. $\square$

性質5: 由良序集基本定理, 結合上述性質, 立即有

$$\alpha\in\beta\vee \alpha=\beta\vee \beta\in\alpha$$

三者必居其一 (否則與 $\in$-反自反性矛盾). 這給出了序數的可比性.

性質6: 若集 $A$ 由序數組成, 那麼 $a$ 是 $\in$-良序集, 因為它滿足:

1. $\in$-反自反性: 假設 $\alpha\in\alpha$, 則由序數的 $\in$-反自反性即有 $\alpha\not\in\alpha$,
2. $\in$-傳遞性: 由序數的可遞性即得,
3. $\in$-三分律: 由序數的可比性即得,
4. $\in$-良基性: 設 $B$ 為 $A$ 的任意非空子集, 任取 $\alpha\in B$, 若 $\alpha\cap B=\emptyset$, 則 $\alpha$ 自身是極小元; 否則由 $\alpha\cap B$ 的良基性知 $\alpha\cap B$ 有極小元 $\beta$, 顯然, $\beta$ 是 $B$ 的極小元. $\square$

構造新序數

顯然, 所有自然數和 $\omega$ 都是序數. 注意, 自然數集 $\omega$ 自身也是一個序數, 對任意自然數 $n$, 由於 $n\in\omega$, 我們可以說 $\omega$ 是一個比任何自然數都大的序數, 同時也是最小的超限序數. 那麼自然要問: 除自然數和 $\omega$ 外, 是否還存在其他的序數? 答案是肯定的.

下面給出兩種構造新序數的規則:

(1) 序數 $\alpha$ 的後繼 $\alpha'$ 也是序數. 形如 $\alpha'$ 的序數稱為後繼序數.
證明: 顯然 $\alpha'$ 是 $\in$-良序集; 設 $x\in y\in\alpha'$, 當 $y=\alpha$ 時, 顯然有 $x\in\alpha\subseteq\alpha'$, 即 $x\in\alpha'$, 當 $y\in\alpha$ 時, 由 $\alpha$ 的可遞性, 同樣由 $x\in\alpha\subseteq\alpha'$. $\square$

(2) 若集 $a$ 的元素都是序數, 則 $\bigcup a$ 也是序數, 且是 $a$ 的上確界.
證明: $\bigcup a$ 的元素都是序數, 所以 $\bigcup a$ 是序數. $\bigcup a$ 是 $a$ 的上確界, 因為 $\alpha\in a$ $\Longrightarrow$ $\alpha\subseteq\bigcup a$, 即 $\alpha\leq \bigcup a$, 故 $\bigcup a$ 是 $a$ 的上界; 若 $\beta\in\bigcup a$, 則 $\exists\alpha\in a\thinspace(\beta\in\alpha)$, 即 $\beta<\alpha$, 故 $\beta$ 不是 $a$ 的上界. $\square$

除 $0$ 以外的所有自然數都是後繼序數. 對自然數集 $\omega$ 使用規則(2), 得到 $\bigcup\omega=\omega$ 是序數, 這是不同於 $0$ 和後繼序數的第三類序數, 稱作極限序數. 設序數 $\alpha\not=0$, 則 $\alpha$ 是極限序數的一個充要條件是

$$\beta\in\alpha\Longrightarrow \beta'\in\alpha$$

證明略. 這表明極限序數必是歸納集.

命題: $\alpha$ ($\not=0$) 是極限序數的一個充要條件是 $\alpha=\bigcup\alpha$.

因此, 極限序數是它自身的上確界.

證明: ($\Longrightarrow$) 設 $\alpha$ 是極限序數, 由 $\alpha$ 的可遞性知 $\bigcup\alpha\subseteq\alpha$; 另一方面, 設 $x\in\alpha$, 則由上一命題知 $x\in x'\in\alpha$, 於是有 $x\in\bigcup\alpha$, 故 $\alpha\subseteq\bigcup\alpha$, 從而有 $\alpha=\bigcup\alpha$.
($\Longleftarrow$) 反設 $\alpha=\bigcup\alpha$ 但 $\alpha$ 不是極限序數, 則 $\alpha=\beta'$, 由 $\bigcup\beta'=\beta$, 得

$$\alpha=\bigcup\alpha=\bigcup\beta'=\beta\in\beta'=\alpha$$

與 $\in$-反自反性矛盾. $\square$

替換公理

使用後繼規則, 我們可以得到 $\omega$ 之後的一些超限序數:

$$\omega,\omega',\omega'',\cdots,\omega^{(n)},\cdots\tag{1}$$

隨後一個很自然的想法是把它們並起來得到更大的序數

$$\bigcup\lbrace \omega^{(n)}:n\in\omega \rbrace=\omega\cup\omega'\cup\omega''\cup\cdots\tag{2}$$

直觀上看, 上面的序數序列能與自然數集一一對應, 二者規模相同, 所以序列中的全部序數應當構成一個集. 但問題是, 僅使用最初版本的 Zermelo 公理 ($\text{ZF1}$ 至 $\text{ZF6}$), 我們無法斷言它的確是集. 為完善序數理論, Fraenkel 和 Skolem 分別於1922和1923年提出了替換公理, 也就是 $\text{ZF7}$.

$\text{ZF7}$ (替換公理 Axiom schema of replacement) 設集 $a$ 和公式 $\varphi(x,y)$ 滿足單值性條件: $$\forall x\in a\thinspace(\exists!y\thinspace\varphi(x,y))$$ 則如下對象也是集: $$\lbrace y:\exists x\in a\thinspace\varphi(x,y) \rbrace$$ 其含義為: 已知集上可定義函數的值域也是集.

有了這條公理, 我們就可以斷言序數序列 $(1)$ 中的全部序數構成集, 從而根據並集公理可得到集合 $(2)$, 它是一個新的序數. 該序數沒有最大元, 所以它是極限序數. 這個序數一般記作 $\omega2$ ($\not=2\omega=\omega$), 它同構於字典序的集 $2\times\omega$.

---

下面是替換公理的一個重要應用:

序型定理: 每個良序集都有與之同構的唯一序數: $A$ 是良序集 $\Longrightarrow$ $\exists!\alpha\thinspace(A\cong\alpha)$.

證明: 唯一性顯然. 存在性: 用序數依次給 $A$ 的初始段進行編號, 即作 $A$ 的子集 $B=\lbrace x\in A:\exists\beta\thinspace A_x\cong\beta \rbrace$, 則由替換公理知 $\alpha=\lbrace \beta:\exists x\in A\thinspace \beta\cong A_x \rbrace$ 也是集. $\alpha$ 的元素都是序數, 所以它是 $\in$-良序集; 設 $\gamma\in\beta\in\alpha$, 則 $\gamma=\beta_{\gamma}$, 且存在序同構 $f:\beta\cong A_x$, 把 $f$ 限制在 $\beta_{\gamma}$ 上即有 $\gamma\cong (A_{x})_{f(\gamma)}=A_{f(\gamma)}$, 所以 $\gamma\in\alpha$, 這就證明了 $\alpha$ 是可遞集, 即它是一個序數. 現假設 $\alpha\cong A_{y}$, 由於存在某個 $\beta\cong A_y$, 所以就有 $\alpha=\beta\in\alpha$, 這與 $\in$-反自反性矛盾; 再假設 $A\cong\alpha_{\xi}\in\alpha$, 就必存在 $w\in A$ 使得 $A_w\cong\alpha_{\xi}$. $A_w\cong A$, 矛盾. 所以由良序集基本定理, 必有 $\alpha\cong A$. $\square$

這個與良序集同構的序數叫做該良序集的序型 (order type), 有相同序型的良序集必同構, 據此可以對良序集進行分類. 序型相當於在良序集的同構類中選出的一個代表元.

序數宇宙

用 $\textbf{On}$ 表示所有序數構成的對象. 稱 $\textbf{On}$ 為序數宇宙, $\alpha$ 是序數, 可以寫作 $\alpha\in\textbf{On}$. 那麼, $\textbf{On}$ 是不是集?

假設 $\textbf{On}$ 是集, 因為 $\textbf{On}$ 的元素都是序數, 它必是 $\in$-良序集. 又由於序數的元素也是序數, 所以有 $x\in y\in\textbf{On}$ $\Longrightarrow$ $x\in\textbf{On}$, 即 $\textbf{On}$ 是可遞集. 由此可知, $\textbf{On}$ 自身也是序數, $\textbf{On}\in\textbf{On}$, 這與序數的反自反性矛盾. 這就是 Burali-Forti 悖論. 悖論產生的原因是假定了 $\textbf{On}$ 是集, 因此 $\textbf{On}$ 不能是集. 我們一般稱它為一個真類.

$\textbf{On}$ 上的超限歸納法: 若 $\forall\alpha((\forall\beta<\alpha:p(\beta))\to p(\alpha))$, 則 $\forall\alpha p(\alpha)$.
證明方法與通常的第二歸納法證明類似. $\square$

從而, 我們有一般序數 $\delta$ 上的歸納定義: 對任給的集運算 $\varphi$, 唯一存在序數 $\delta$ 上的函數 $\psi_{\delta}$ 滿足

$$\forall \alpha<\delta(\psi_{\delta}(\alpha)=\varphi(\psi_{\delta}\upharpoonright \alpha))$$

其中, 集運算 $\varphi$ 是指, 對任意集 $x$, 唯一指定一個集 $y$ 與之對應. (之所以不稱之為函數, 是因為其 “定義域” 不是集而是整個集宇宙, 基於此, 集運算也常稱作類函數.) 符號 $\psi\upharpoonright\alpha$ 表示把函數 $\psi$ 限制在集 $\alpha$ 上, $\alpha$ 是集, 由替換公理, $\psi\upharpoonright\alpha$ 也是集.

證明: 唯一性由 $\textbf{On}$ 上的超限歸納法易證. 存在性: 對 $\delta\in\textbf{On}$ 作歸納. $\delta=0$ 時取 $\psi_0=0$; $\delta>0$ 時, 假設對每個 $\gamma<\delta$ 都存在 $\gamma$ 上的函數 $\psi_{\gamma}$ 滿足

$$\psi_{\gamma}(\alpha)=\varphi(\psi_{\gamma}\upharpoonright \alpha),\enspace \alpha<\gamma$$

當 $\delta$ 是後繼序數時, 設 $\delta=\gamma'$, 定義 $\psi_{\delta}$ 如下:

$$\forall \alpha<\delta(\psi_{\delta}(\alpha)=\varphi(\psi_{\gamma}\upharpoonright \alpha))$$

當 $\delta$ 是極限序數時, 對任意 $\alpha<\delta$ 都有 $\alpha'<\delta$, 按歸納假設可定義 $\psi_{\alpha'}$, 令

$$\psi_{\delta}(\alpha)=\psi_{\alpha'}(\alpha)$$

容易驗證, 這樣定義的 $\psi_{\delta}$ 符合要求. 由超限歸納法原理得證. $\square$

進一步可以將歸納定義推廣到 $\textbf{On}$ 上. 對任意給定的集運算 $\varphi$, 唯一存在序數函數 $\psi$ 滿足

$$\psi(\alpha)=\varphi(\psi\upharpoonright\alpha)$$

證明: 取 $\delta=\alpha'$, 則唯一存在 $\alpha'$ 上的函數 $\psi_{\alpha'}$ 滿足

$$\psi_{\alpha'}(\gamma)=\varphi(\psi_{\alpha'}\upharpoonright \gamma),\enspace \gamma<\alpha'$$

令 $\psi(\alpha)=\psi_{\alpha'}(\alpha)$ 即可. $\square$

序數算術

歸納定義序數的加法如下:

1. $\alpha+0=\alpha$,
2. $\alpha+\beta'=(\alpha+\beta)'$,
3. $\alpha+\beta=\bigcup\lbrace\alpha+\gamma:\gamma<\beta\rbrace$, 若 $\beta$ 是極限序數.

由(3)可知, $1+\omega=\omega\not=\omega+1$, 故交換律對序數加法不成立. 直觀來看, 這就相當於在無窮序列的開頭和末尾添加一個元素的區別.

乘法定義如下:

1. $\alpha\cdot 0=0$,
2. $\alpha\cdot\beta'=\alpha\cdot\beta+\beta$,
3. $\alpha\cdot\beta=\bigcup\lbrace\alpha\cdot\gamma:\gamma<\beta\rbrace$, 若 $\beta$ 是極限序數.

同樣, 由 $2\omega=\omega\not=\omega2=\omega+\omega$ 可知交換律不成立. 直觀來看, 這種區別仍然是不同排序方式造成的, 例如, $1,2,3,4,\cdots$ 和 $1,3,5,\cdots,2,4,6\cdots$ 顯然是不同的, 兩者分別同構於字典序的 $\omega\times2$ 和 $2\times\omega$.

冪運算的定義也類似,

1. $\alpha^0=1$,
2. $\alpha^{\beta+1}=\alpha^{\beta}\cdot\alpha$,
3. $\alpha^{\beta}=\bigcup\lbrace\alpha^{\gamma}:\gamma<\beta\rbrace$, 若 $\beta$ 是極限序數.

例如, 按定義, $2^{\omega}=\bigcup\lbrace2^n:n\in\omega\rbrace=\omega$, 與我們熟知的基數算術 ($2^{\omega}\not=\omega$) 截然不同.

下文我們將看到, 基數指數運算 $\kappa^{\lambda}$ 的結果可顯式地定義為全體 $\lambda$ 到 $\kappa$ 的映射構成的集合的基數, 序數指數運算也有類似但略為複雜的顯式定義.

定義映射 $f:\beta\to \alpha$ 的支集為所有滿足 $f(b)>0$ 的 $b\in\beta$ 構成的集合, 進而, 稱 $f$ 為有限支集的, 若 $f$ 的所有支集都為有限集. 把所有有限支集映射 $f:\beta\to\alpha$ 構成的集合記作 $[\beta\to\alpha]$, 定義 $[\beta\to\alpha]$ 上的序如下: 對任意 $f_1\not=f_2$, 考慮集 $\lbrace b\in\beta:f_1(b)\not=f_2(b)\rbrace$ 的最大元 $b_m$, 比較 $f_1(b_m)$ 和 $f_2(b_m)$. 由有限支集條件, 這顯然是一個良序.

下面來證明集 $[\beta\to\alpha]$ 的序型即為 $\alpha^{\beta}$, 為此只需驗證歸納定義即可. 這對於有限序數顯然成立. 若 $\gamma=\beta+1=\beta\cup\lbrace\beta\rbrace$, 則每個映射 $f\in[\gamma\to\alpha]$ 可看成一個有序對, 由一個 $\beta$ 到 $\alpha$ 的有限支集映射和一個 $\lbrace\beta\rbrace$ 到 $\alpha$ 的映射組成, 排序時先比較 $f(\beta)$, 所以 $[\gamma\to\alpha]$ 同構於字典序的 $\alpha\times[\beta\to\alpha]$. 若 $\gamma$ 是極限序數, 設 $\xi\in\gamma$, 則 $[\xi\to\alpha]$ 構成 $[\gamma\to\alpha]$ 的初始段, 且它與 $[\gamma_{\xi}\to\alpha]$ 同構. $[\gamma\to\alpha]$ 是所有這樣的初始段的並, 所以它的序型恰為 $\alpha^{\xi}$ ($\xi=\gamma_{\xi}$) 的上確界. $\square$

正則公理

1917年, Dmitry Mirimanoff 發現 Zermelo 的公理系統不能排除一種異常集的存在, 這種集形成 $\in$-降鏈:

$$\cdots\in x_{n+1}\in x_n\in \cdots\in x_2\in x_1\in x_0$$

特殊情況是 $x\in x$. $\in$-降鏈的存在意味著集的原始組成可以不存在. 為消除這種異常集, von Neumann 於1925年提出正則公理.

$\text{ZF8}$ (正則公理 regularity axiom) 每個非空集都有 $\in$-極小元, 即 $$\forall a\not=\emptyset\thinspace\exists x\in a\thinspace(x\cap a=\emptyset)$$ 其中, $x\cap a=\emptyset$ 意思是: $x$ 是 $a$ 的 $\in$-極小元, $\forall t\in a\thinspace t\not\in x$.

$\in$-極小元的存在使得 $\in$-降鏈不能出現. 特別地, $\forall x(x\not\in x)$ (注意, 我們先前排除 Russell 悖論時並沒有排除一個集合可以屬於其自身). 設 $a=\lbrace x\rbrace$, 則 $x$ 為 $a$ 的 $\in$-極小元, 若 $x\in x$, 則 $x\not\in a$, 矛盾. $\square$

反過來, 在承認選擇公理的前提下, “$\in$-降鏈不存在” 蘊含正則公理. 假設非空集 $S$ 不滿足正則公理, 即任意 $x\in S$, $x\cap S\not=\emptyset$, 設 $g$ 為 $S$ 的一個選擇函數, 歸納定義函數 $f$ 如下:

$$\begin{align*} &f(0)=g(S) \\ &f(n+1)=g(f(n)\cap S) \end{align*}$$

則 $\cdots\in f(n+1)\in f(n)\in\cdots\in f(1)\in f(0)$ 形成一 $\in$-降鏈, 與假定 $\in$-降鏈不存在矛盾. $\square$

不存在 $\in$-降鏈 $\cdots\in x_2\in x_1\in x_0$ 的集合 $x_0$ 稱為良基集. 使用正則公理可以證明, $\text{ZFC}$ 集宇宙中的所有集都是良基集, 這也就印證了上文的斷言, 所有集都是在空集上反覆應用集運算得到的. (當然, 也存在接受非良基集的集論系統.)

有了正則公理, $\in$-反自反性和 $\in$-良基性自動滿足, 序數的定義可以簡化成: 滿足 $\in$-三分律的可遞集.

定義序數函數 $v_{\alpha}$:

1. $v_0=0=\emptyset$,
2. $v_{\alpha+1}=\mathcal{P}(v_{\alpha})$,
3. $v_{\alpha} = \bigcup_{\beta<\alpha}v_{\beta}$, $\alpha$ 為極限序數.

把每個 $v_{\alpha}$ 的元素叫做良基集, 並把良基集構成的類記作 $\mathbf{V}$: $$\mathbf{V}=\bigcup_{\alpha\in\mathbf{On}}v_{\alpha}$$ 顯然, 所有序數都是良基集. 進一步, 藉助正則公理可以證明: 所有集都是良基集. 因此, $\text{ZF}$ 集合論的論域被限制在良基集類 $\mathbf{V}$, 從空集開始使用集運算可得到一切集.

選擇公理的進一步討論

等價形式

下面我們證明幾個選擇公理的重要等價形式.

良序定理 ($\text{WO}$): 任何非空集上都有良序. (注意不要與斷言自然數集的任意非空子集都有最小元的良序原理混淆.)

證明: 設 $S$ 為非空集, 我們斷言 $S$ 和某個序數 $\theta$ 之間存在雙射. 選取元素 $\Omega\not\in S$. 設 $g$ 為 $S$ 的一個選擇函數, $g(S)=a_0$, 歸納定義 $a_{\alpha}$ 如下:

$$a_{\alpha}=\begin{cases} g(S\setminus\lbrace a_{\beta}:\beta<\alpha\rbrace),&S\not=\lbrace a_{\beta}:\beta<\alpha\rbrace \\ \Omega,&S=\lbrace a_{\beta}:\beta<\alpha\rbrace \end{cases}$$

由於 $S$ 是集合 (而 $\textbf{On}$ 的規模遠大於集), 所以必存在極小的 $\theta$ 使得 $a_{\theta}=\Omega$, $S=\lbrace a_{\beta}:\beta<\theta\rbrace$ 與 $\theta=\lbrace \beta:\beta<\theta\rbrace$ 之間存在雙射, 於是導出 $S$ 上的良序. $\square$

另一種證明參見命題演算的緊緻性定理.

反過來, 設 $S$ 為非空集組成的集族, 我們用良序定理在 $\bigcup S$ 上建立一個良序, 並定義選擇函數為: 從每個 $x\in S$ ($x\subseteq\bigcup S$) 中選出最小元. 此即 $\text{WO}\Longrightarrow\text{AC}$.

Zorn 引理: 若非空偏序集 $S$ 的每個全序子集 (每一條鏈) 在 $S$ 中都有上界, 則 $S$ 必有極大元.

證明: 反設 $S$ 沒有極大元. 任取 $a_0\in S$, 歸納定義 $a_\alpha\in S$ 使得 $\alpha<\beta$ $\Longrightarrow$ $a_{\alpha}<a_{\beta}$ (這裡使用了選擇公理). 假定對任意 $\beta<\alpha$ 都定義了 $a_{\beta}$, 則 $\lbrace a_{\beta}\rbrace_{\beta<\alpha}$ 是 $S$ 中的一條鏈. 若 $\alpha$ 是極限序數, 則該鏈必有上界 $a_{\alpha}\not\in\lbrace a_{\beta}\rbrace_{\beta<\alpha}$, 且 $a_{\alpha}\in S$; 若 $\alpha=\gamma+1$ 是後繼序數, 由假設 $S$ 無極大元知必存在 $a_{\alpha}\in S$ 使得 $a_{\alpha}>a_{\gamma}$. 由此真類 $\textbf{On}$ 可嵌入集 $S$, 矛盾. $\square$

Tukey 引理: 設非空集 $S$ 滿足 $x\in S$ $\Longleftrightarrow$ $x$ 所有有限子集都屬於 $S$ (該條件一般稱作 "有限特徵"), 則 $S$ 按 $\subseteq$ 有極大元.

證明: 我們用 Zorn 引理來證明 Tukey 引理. $S$ 按 $\subseteq$ 成非空偏序集, 任取 $S$ 的全序子集 $b$, 由並集的性質, $x\in b$ $\Longrightarrow$ $x\subseteq\bigcup b$, 即 $\bigcup b$ 是 $b$ 的上界. 只需證 $\bigcup b\in S$, 由 Zorn 引理即可知 $S$ 有 $\subseteq$-極大元. 由於 $b$ 是全序子集, $\bigcup b$ 的任意有限子集必為 $b$ 的某個子集 $x$ 的有限子集, 故必屬於 $S$, 由 $S$ 的有限特徵知, $\bigcup b\in S$. $\square$

Tukey 引理的一個應用是證明任意向量空間都有基. 令向量空間 $V$ 的線性無關組的集合為 $S$, 則 $S$ 顯然具有有限特徵, 故 $S$ 按 $\subseteq$ 有極大元 $w$, 這就是向量空間的一個基. 一般的, 由該命題確保存在的基稱為 Hamel 基.

Hamel 基可用於構造病態反例. 例如著名的 Cauchy 方程問題: 設 $\mathbb{R}$ 上的函數 $f$ 滿足方程 $f(x+y)=f(x)+f(y)$, 那麼 $f$ 是否一定是線性函數 $f(x)=kx$ ? 答案是否定的. 把 $\mathbb{R}$ 看作 $\mathbb{Q}$ 上的無窮維線性空間, 取它的一個 Hamel 基, 設它的一個元素為 $\alpha$, 考慮函數 $f$ 把 $x\in\mathbb{R}$ 映射為它的 (有理數) $\alpha$-坐標. $f$ 顯然滿足 Cauchy 方程, 但其值恆為有理數, 所以必不是線性函數.

最後, 我們用 Tukey 引理證明選擇公理. 由此表明選擇公理, Zorn 引理和 Tukey 引理的等價性.

證明: 設 $a$ 為非空集組成的集族, 作 $b=\lbrace g:$ $g$ 是 $a$ 的某個子族的選擇函數 $\rbrace$, 顯然 $b$ 具有有限特徵. 由 Tukey 引理, $b$ 按 $\subseteq$ 有極大元 $f$. 只需證 $\text{Dom}(f)=a$ 即可. 反設存在 $x\in a-\text{Dom}(f)$, 取 $y\in x$, 則 $f\cup\lbrace (x,y)\rbrace\in b$, 與 $f$ 的極大性矛盾. 故 $f$ 即為要求的 $a$ 的選擇函數. $\square$

濾子擴張原則

濾子擴張原則: 設 $F_0$ 是集 $a$ 上的濾子, 則存在 $a$ 上的超濾 $F\supseteq F_0$.

該定理保證非主超濾的存在性.

證明: 我們用 Zorn 引理證明濾子擴張原則. 設 $F_0$ 是集 $a$ 上的濾子, 作偏序集 $P=\lbrace G\supseteq F_0:G$ 是 $a$ 上的濾子$\rbrace$, 任取 $P$ 的鏈 $L$, 只需證明 $L$ 在 $P$ 中有上界. $L=\emptyset$ 時, $P$ 中任何元素都是 $L$ 的上界; $L\not=\emptyset$ 時, $L$ 在 $P$ 中的上界為 $\bigcup L$: 首先容易驗證 $\bigcup L$ 是濾子, 進而因 $F_0\subseteq \bigcup L$, 所以 $\bigcup L\in P$, 最後由並集的性質知 $G\in L$ $\Longrightarrow$ $G\subseteq \bigcup L$, 即 $\bigcup L$ 是 $L$ 的上界. 由 Zorn 引理知 $P$ 有極大元 $F$, $F$ 必為某個極大濾子, 故為超濾. $\square$

設 $A$ 為 $\mathbb{N}$ 的非空子集族, 且滿足

$$\forall a_1,\cdots,a_n\in A(a_1\cap\cdots\cap a_n\not=\emptyset)$$

則稱 $A$ 具有有限交性質. 設 $A$ 具有有限交性質, 令

$$F=\lbrace x\supseteq a:\exists a_1,\cdots,a_n\in A(x\supseteq a_1\cap\cdots\cap a_n)\rbrace$$

則 $F$ 是一個濾子. 由濾子擴張原則, 濾子 $F$ 可擴張為一個超濾. 特別地, 主超濾 $F_n$ 可視為單點集 $\lbrace n\rbrace$ 生成的超濾.

基數

集合的勢

集 $A$ 與集 $B$ 等勢, 是指存在 $A$ 到 $B$ 的雙射, 記作 $A\approx B$. 例如, $\mathbb{N}\approx \mathbb{Z}\approx \mathbb{Q}$, $\mathbb{R}\approx \mathcal{P}(\mathbb{N})$. 符號 $A\preccurlyeq B$ 表示存在集 $A$ 到集 $B$ 的單射, $A\prec B$ 表示 $A\preccurlyeq B$ 但 $A\not\approx B$.

定理: 對任意集 $A$, 都有 $A\prec \mathcal{P}(A)$.

證明: $A\preccurlyeq \mathcal{P}(A)$ 是顯然的, 只需證 $A\not\approx \mathcal{P}(A)$. 假設存在滿射 $f:A\to \mathcal{P}(A)$, 令 $B=\lbrace x\in A:x\not\in f(x)\rbrace$, 因為 $B\in\mathcal{P}(A)$, 所以 $B$ 必有原像. 設 $f(x_0)=B$, 若 $x_0\in f(x_0)=B$, 則 $x_0\not\in B$; 若 $x_0\not\in B$, 則由 $B$ 的定義知 $x_0\in B$, 矛盾. $\square$

---

Cantor-Bernstein-Schröder 定理: $X\preccurlyeq Y\wedge Y\preccurlyeq X$ $\Longrightarrow$ $X\approx Y$.

證明: 設 $f:X\to Y$, $g:Y\to X$ 是單射, 作如下集合序列:

$$\begin{align*} &\lbrace A_i\rbrace:\enspace A_0=X,\enspace A_{i+1}=(g\circ f)(A_i) \\ &\lbrace B_i\rbrace:\enspace B_0=g(Y),\enspace B_{i+1}=(g\circ f)(B_i) \\ &\lbrace C_i\rbrace:\enspace C_0=Y,\enspace C_{i+1}=(f\circ g)(C_i) \\ &\lbrace D_i\rbrace:\enspace D_0=f(X),\enspace D_{i+1}=(f\circ g)(D_i) \end{align*}$$

則

$$\begin{align*} &X=A_0\supseteq B_0\supseteq A_1\supseteq B_1\supseteq \cdots \\ &Y=C_0\supseteq D_0\supseteq C_1\supseteq D_1\supseteq \cdots \end{align*}$$

定義映射 $h:X\to Y$

$$h(x) = \begin{cases} f(x),&\exists n\in\mathbb{N}\enspace\text{s.t.}\enspace x\in A_n-B_n\\ g^{-1}(x),&\text{otherwise}. \end{cases}$$

容易驗證,

$$\begin{align*} &h(A_i-B_i) = D_i-C_{i+1} \\ &h(B_i-A_{i+1}) = C_{i}-D_{i} \\ &h\left(\bigcap_{i=1}^{\infty}A_i\right) = \bigcap_{i=1}^{\infty}C_i \end{align*}$$

所以 $h$ 是雙射. $\square$

該證明也可以採用如下更為抽象的表述. 令 $\varphi=g\circ f$, $X'=X-g(Y)$, 考慮 $X$ 的子集族 $$\mathcal{F}=\lbrace A\subseteq X:X'\cup \varphi(A)\subseteq A\rbrace$$ 顯然 $X\in\mathcal{F}$, 所以 $\mathcal{F}$ 非空. 對任意 $A\in\mathcal{F}$, $X'\cup \varphi(A)\subseteq A$, 故 $X'\subseteq A$, $\varphi(A)\subseteq A$, 於是 $\varphi(X')\subseteq\varphi(A)$, $\varphi(\varphi(A))\subseteq\varphi(A)$, 從而有 $$X'\cup\varphi\left(X'\cup\varphi(A)\right)=X'\cup\varphi(X')\cup\varphi(\varphi(A))\subseteq X'\cup\varphi(A)$$ 即 $X'\cup\varphi(A)\in\mathcal{F}$.

令 $A_0=\bigcap_{A\in\mathcal{F}}A$, 任取 $x_0\in X'\cup \varphi(A_0)$, 則

$$\begin{align*} x_0&\in X'\cup\left(\bigcap_{A\in\mathcal{F}}h(A)\right) \\ &=\bigcap_{A\in\mathcal{F}}\left(X'\cup h(A)\right) \\ &\subseteq\bigcap_{A\in\mathcal{F}}A=A_0 \end{align*}$$

故 $A_0\in\mathcal{F}$. 又由於 $A_0\supseteq X'\cup\varphi(A_0)\in\mathcal{F}$, 所以 $A_0=X'\cup\varphi(A_0)$. 令 $B_0=X-A_0$, 則

$$B_0=X-X'-g(f(A_0))=g(Y-f(A_0))$$

所以 $g^{-1}(B_0)=Y-f(A_0)$. 定義映射 $h:X\to Y$

$$h(x) = \begin{cases} f(x),& x\in A_0 \\ g^{-1}(x),&x\in B_0. \end{cases}$$

則 $h$ 是雙射. $\square$

推論: 若 $A\subseteq B\subseteq C$ 且 $A\approx C$, 則 $A\approx B\approx C$.

基數

若序數 $\kappa$ 滿足 $\forall \alpha<\kappa(\alpha\not\approx \kappa)$, 則稱 $\kappa$ 是一個基數. 例如, 自然數 $n$, $\omega$ 都是基數, 但 $\omega+1$ 不是基數, 因為 $\omega+1\approx \omega$. 簡單來說, 基數是用於計數的數, 序數是用於編號的數; 序數與元素的排列次序有關, 而基數只關心集合的規模大小 (元素多少), 所以在對無限集計數時, 我們只需使用互相等勢的序數中最小的一個即可, 這就是要求基數與更小的序數不等勢的原因. 超限基數 $\kappa$ 作為序數一定是極限序數, 否則假設 $\kappa=\alpha+1$, 有如下雙射 $f:\kappa\to\alpha$:

$$f(\beta)=\begin{cases} 0, &\beta=\alpha \\ \beta, &\omega\leq\beta<\alpha \\ \beta+1, &\beta<\omega \end{cases}$$

用 $|A|$ 表示集 $A$ 的基數, 若 $A\approx \kappa$, 則 $|A|=\kappa$. 在承認良序定理 (選擇公理) 的前提下, 任意集都有基數. 首先, 任取集 $A$, 可以用良序定理使其成為良序集, 那麼必存在序數 $\alpha$ 與之同構, 與 $\alpha$ 等勢的最小序數即是 $A$ 的基數; 反過來, 若任意集 $A$ 都有基數 $\kappa$, 由於存在雙射 $A\to \kappa$, $\kappa$ 的 $\in$-良序就誘導了 $A$ 的良序. 由此可知, 良序定理與命題 “任意集都有基數” 等價.

基數的可比性是顯然的:

$$\begin{align*} \kappa\approx \lambda\Longleftrightarrow \kappa=\lambda \\ \kappa\preccurlyeq \lambda\Longleftrightarrow \kappa\leq\lambda \\ \kappa\prec \lambda\Longleftrightarrow \kappa<\lambda \end{align*}$$

由於任何集都有基數, 集合的勢也一定是可比的.

這一點也可以直接用 Zorn 引理證明: 對任意集 $X$, $Y$, 考慮 $\Sigma=\lbrace (A,f)\mid A\subseteq X,f:A\hookrightarrow Y\rbrace$.

---

定理: 比 $\kappa$ 大的最小基數是 $\kappa^{+}=\lbrace \beta:\beta\preccurlyeq\kappa\rbrace$.

證明: 首先, $\kappa^{+}$ 的元素都為序數, 所以它是 $\in$-良序集. 進而對任意 $\gamma\in\beta\in\kappa^{+}$, 有 $\gamma\subseteq\beta\preccurlyeq\kappa$, 所以 $\gamma\in\kappa^{+}$, 故 $\kappa^{+}$ 是序數. 任取 $\beta\in\kappa^{+}$, $\beta\preccurlyeq\kappa$, 顯然 $\beta\not\approx\kappa^{+}$, 所以 $\kappa^{+}$ 是一個基數. 又由於 $\lambda<\kappa^{+}$ $\Longrightarrow$ $\lambda\preccurlyeq\kappa$ $\Longrightarrow$ $\lambda\leq\kappa$, 故 $\kappa^{+}$ 是大於 $\kappa$ 的最小基數. $\square$

命題: 設集 $a$ 的元素都是基數, 則 $\bigcup a$ 也是基數, 且是 $a$ 的上確界.

證明: 已知 (參見上文) $\bigcup a$ 是序數且是 $a$ 的上確界, 故只需證 $\bigcup a$ 是基數. 任取 $\alpha\in\bigcup a$, 存在某個 $\kappa\in a$ 使得 $\alpha\in\kappa$, 於是 $\alpha\subseteq\kappa\subseteq\bigcup a$, 若 $\alpha\approx\bigcup a$, 便有 $\alpha\approx \kappa$ 與 $\kappa$ 是基數矛盾. $\square$

據此, 可以讓每個序數 $\alpha$ 聯繫到一個基數:

1. $\omega_0 = \omega$,
2. $\omega_{\alpha+1} = \omega_{\alpha}^{+} = \lbrace \beta:\beta\preccurlyeq\omega_{\alpha}\rbrace$, ($\omega_{\alpha+1}$ 稱作 $\omega_{\alpha}$ 的後繼基數)
3. $\omega_{\alpha} = \bigcup\lbrace \omega_{\gamma}:\gamma<\alpha\rbrace$, 其中 $\alpha$ 是極限序數. (此時, $\omega_{\alpha}$ 稱作極限基數)

$\omega_{\alpha}$ 也寫作 $\aleph_{\alpha}$. 可以證明, 每個比 $\omega$ 大的基數都是某個 $\aleph_{\alpha}$.

基數算術

Hessenberg 定理: $\kappa\geq\omega$ $\Longrightarrow$ $\kappa\times\kappa\approx\kappa$.

證明: $\kappa=\kappa\times\lbrace 0\rbrace\subseteq\kappa\times\kappa$, 故只需歸納證明 $\kappa\times\kappa\preccurlyeq\kappa$ 即可. 假設 $\omega\leq\lambda<\kappa$ 時有 $\lambda\times\lambda\preccurlyeq\lambda$. 首先定義 $\kappa\times\kappa$ 上的 “標準序”: $(\alpha_1,\beta_1)<(\alpha_2,\beta_2)$ 當且僅當

1. $\max\lbrace \alpha_1,\beta_1\rbrace<\max\lbrace \alpha_2,\beta_2\rbrace$, 或
2. $\max\lbrace \alpha_1,\beta_1\rbrace=\max\lbrace \alpha_2,\beta_2\rbrace$ 且 $\alpha_1<\alpha_2$, 或
3. $\max\lbrace \alpha_1,\beta_1\rbrace=\max\lbrace \alpha_2,\beta_2\rbrace$, $\alpha_1=\alpha_2$ 且 $\beta_1<\beta_2$.

即先按 $\max\lbrace \alpha,\beta\rbrace$, 然後按字典序排序.

$\kappa$ 的良序性保證了該標準序是良序, 所以存在唯一的序數 $\gamma$ 與 $\kappa\times\kappa$ 同構. 下面只需證明 $\gamma\leq\kappa$. 反設 $\gamma>\kappa$, 取同構映射 $f:\gamma\to\kappa\times\kappa$, 設 $f(\kappa)=(\alpha,\beta)$, 則 $\kappa$ 與 $\kappa\times\kappa$ 中以 $(\alpha,\beta)$ 為端點的初始段 $A$ 同構. 若 $\alpha$, $\beta$ 都為有限數, 則其確定的初始段也有限, 不可能與 $\kappa$ 同構, 所以其中至少有一比 $\omega$ 大. 令 $\delta=\max\lbrace \alpha,\beta\rbrace+1$, 由於 $\kappa$ 是極限序數, $\alpha,\beta\in\kappa$, 所以有 $\omega\leq\delta<\kappa$, 由歸納假設, 有 $\delta\times\delta\approx\delta\prec\kappa$. 因為 $(\alpha,\beta)<(\delta,\delta)$, 所以 $\kappa\approx A\approx\delta\times\delta$, 矛盾. 故 $\kappa\times\kappa\preccurlyeq\kappa$. $\square$

定義基數的加法和乘法如下:

$$\begin{align*} \kappa+\lambda &= |\kappa\times\lbrace 0\rbrace\cup\lambda\times\lbrace 1\rbrace| \\ \kappa\cdot\lambda &= |\kappa\times\lambda| \end{align*}$$

容易驗證, 基數的加法和乘法滿足交換律, 結合律和分配律.

由 Hessenberg 定理可得基數計算的基本公式: 設 $\kappa\geq\omega$ 且 $\kappa\geq\lambda$, 則

1. $\kappa+\lambda=\kappa$,
2. $\kappa\cdot\lambda=\kappa$.

基數的指數運算定義為: $\kappa^{\lambda}=|{}^{\lambda}{\kappa}|$, 其中 $^{\lambda}{\kappa}=\lbrace f\mid f:\lambda\to\kappa\rbrace$. 則顯然有

1. $\kappa^{\lambda+\mu}=\kappa^{\lambda}\cdot\kappa^{\mu}$,
2. $(\kappa^{\lambda})^{\mu}=\kappa^{\lambda\cdot\mu}$.

命題: 若 $2\leq \kappa\leq\lambda$ 且 $\lambda\geq\omega$, 則 $\kappa^{\lambda}=2^{\lambda}=|\mathcal{P}(\lambda)|$.

證明: 對每個映射 $f:\lambda\to\lambda$, 有 $f\subseteq\lambda\times\lambda$, 於是 $^{\lambda}{\lambda}\subseteq\mathcal{P}(\lambda\times\lambda)$. 所以有 $^{\lambda}{2}\subseteq{}^{\lambda}{\kappa}\subseteq{}^{\lambda}{\lambda}\subseteq\mathcal{P}(\lambda\times\lambda)\approx\mathcal{P}(\lambda)\approx{}^{\lambda}{2}$. $\square$

---

$\text{CH}$ (連續統假設) $$2^{\omega_0}=\omega_1$$ $\text{GCH}$ (廣義連續統假設) $$\forall\alpha(2^{\omega_{\alpha}}=\omega_{\alpha+1})$$

根據 Gödel 和 Cohen 的工作, 連續統假設成立與否獨立於 $\text{ZFC}$.