---
# System prepended metadata

title: 課程｜集合論
tags: [課程]

---

# 集合論

## 建造集合塔
- $V_0=\{\}$
- $V_1=PV_0\cup V_0=\{\{\}\}$
- $V_2=PV_1\cup V_1=\{\{\},\{\{\}\}\}$
- $V_3=PV_2\cup V_2=\{~\{\}~,~\{\{\}\}~,~\{\{\{\}\}\}~,~\{\{\},\{\{\}\}\}~\}$
- $V_{i+1}=PV_i\cup V_i$
- $V_\omega=\cup_{i\in N}V_i$
- 偽演算法
    ```clike=
    N = {0,1,...}
    w = 最小的序數
    α = 0
    Repeat:
        For each $i\in N$ :
            $V_{α+i+1}=PV_{α+i}$
        V_{α+w}=\cup V_{α+i}
        α = α + w
    ```
    - 不嚴謹地說
        - $V_{α+i+1}$ 必定比 $V_{α+i}$ 大
        - $V_{α+w}$ 必定比 $V_{α+i}$ 大
## 意義
- Implication 1 (邏輯)
    - ZF中所有性質、敘述，皆可以用 1st order predicate logic 表達
    - $\forall、\neg、\land$ 三個符號就足夠了
        - $\exists x f \equiv \neg (\forall c \neg f)$
        - $f \lor g \equiv \neg (\neg f \land \neg g)$
        - $f\Rightarrow g \equiv \neg f \lor g$
        - $f\Leftrightarrow g \equiv (f\Rightarrow g) \land (g\Rightarrow f)$
        - $f=g \equiv$ 可互相替換
- Implication 2 (集合)
    - 任兩個集合 $a、b$ 之間，只有一種 irreducible 的關係，即 $a\in b$
        - $a\notin b \equiv \neg(a\in b)$
        - $a\subseteq b \equiv \forall x (x\in a\Rightarrow x\in b)$
        - $a\subsetneq b \equiv (a\subseteq b) \land (~\exists c (c\in b \land c\notin a)~)$
    - $a=b$ 代表的意義是
        - $(~\forall x~a\in x\Leftrightarrow b\in x~)\land (~\forall y~y\in a\Leftrightarrow y\in b~)$
        - 在沒介紹外延公理時，不可以只寫 $A\subseteq B\land B\subseteq A$
## ZF 6 公理
- `空集公理` ： $\exists A \forall x x\notin A$
    - 存在一個集合沒有任何元素，寫成 $\phi$、$\{\}$
- `外延公理` ： $\forall R~\forall S~(~\forall x~x\in R \Leftrightarrow x\in S)~\Rightarrow R=S$
    - 集合的唯一性，兩集合有相同的元素則兩集合相等
- `配對公理` ： $\forall x~\forall y~\exists S~\forall z~z\in S \Leftrightarrow (z=x \lor z=y)$
    - 由二個元素造出一個集合，寫成 $\{x,y\}$ 或 $\{x\}=\{x,x\}$
- `聯集公理` ： $\forall A~\exists B~\forall x~(x\in B \Leftrightarrow \exists c (x\in c \land c\in A))$
    - 若 $A=\{\{a,b\},\{c\}\}$，則 $B=\{a,b,c\}$
    - 給定 $x,y,z$
        - 3 次 Pairing，得到 $\{\{x,y\},\{z\}\}$ 
        - 1 次 Union，得到 $\{x,y,z\}$
    - 給定 $x_1,x_2,...,x_n$
        - $n-1$ 次 Pairing + $n/2-1$ 次 union，得到 $\{x_1,x_2,...,x_n\}$
        - 再 1 次 Union，得到 $\cup S=x_1\cup x_2\cup ... \cup x_n$
    - 一元聯集 $\cup A$ 可以推廣到二元聯集 $A\cup B=\cup\{A,B\}$
- `子集公理群` ： 對任何不包含 $R$ 的 formula $f$, $\forall S~\forall x_1~...~\forall x_n~\exists R~\forall x~(x\in R \Leftrightarrow ((x\in S) \land f) )$，其中 $x_1,x_2,...,x_n$ 是 $f$ 的 free variables
    - `定義 formula`
        - $a\in b$ 是
        - $f$ 是 $\Rightarrow$ $\neg f$ 和 $\forall x f$ 也是
        - $f$ 和 $g$ 是 $\Rightarrow$ $f \land g$ 也是
        - 除此之外都不是
    - `定義` ： 
        - $\{x:x\in S\land f\}$ 或 $\{x\in S:f\}$ 表示 Axiom 5 當中的 $R$
        - $A\cap B=\{x\in A:x\in B\}$
        - $A\setminus B=\{x\in A:x\notin B\}$
        - $\cap S\equiv\{x\in\cup S:\forall~y~y\in S\Rightarrow x\in y\}$
            - 注意 $\cap \phi$ 是一個真類，根據全集定理不存在
    - `全集定理` ： $\neg (\exists A \forall x x\in A)$ 不存在集合所有東西的集合
        - 證明：假設相反 $\exists A \forall x x\in A$
        - Axiom 5 表示存在集合 $B=\{x\in A:x\notin x\}$
        - 因此 $B\in B \Leftrightarrow B\notin B$
- `冪集公理`：$\forall A~\exists P~\forall x~x\in P\Leftrightarrow x\subseteq A$
    - 寫成 $\mathscr{P}A$，是 ZF 公理中，唯一可以讓無窮集合的大小變大的公理
    - 可以用冪集公理+子集公理群，把一個(可能無窮)集合的每個集合都加上括號
## 函數與選擇公理
- **多元組 (tuples)**
    - 定義 $\langle a,b\rangle =\{\{a\},\{a,b\}\}$
    - Lemma : $\langle a,b\rangle =\langle c,d\rangle \Leftrightarrow a=c \land b=d$
        - 根據 $\{a\}$ 是否等於 $\{c,d\}$ 討論
    - $\cup \langle a,b\rangle =\{a,b\}$
    - $\cap \langle a,b\rangle =\{a\}$
    - $\cup\cap \langle a,b\rangle =a$
    - $\cup\{x\in\{a,b\}:\{x\}=\{a,b\}\lor x\ne a\}=\cup\{b\}=b$
    - $\langle x_1,x_2,...,x_n\rangle=\langle\langle\langle x_1,x_2\rangle,x_3\rangle...\rangle,x_n\rangle$
    - 笛卡爾積 $A\times B$
        - $A\times B=\{x\in \mathscr{PP}(A\cup B):\exists~a~\exists~b~x=\langle a,b\rangle\land a\in A \land b\in B\}$
        - $A_1\times A_2\times ...\times A_n=\langle a_1,a_2,...,a_n\rangle$
- **關係 (relation)**
    - 二(多)元關係：一個 ordered pair (n-tuples) 的集合
        - 建構好 ordered pair 之後，用 pairing 和 union
    - 關係 on $A$：$A\times A$ 的任一子集合
        - 用子集公理
    - 恆等關係 on $A$：$I_A=\{x\in A\times A : \exists~a~a\in A \land x=\langle a,a\rangle\}$
    - 定義域：$dom R \equiv\{a\in \cup\cup R : \exists~b~\langle a,b\rangle\in R\}$
    - 值域：$ran R \equiv\{b\in \cup\cup R : \exists~a~\langle a,b\rangle\in R\}$
    - 反關係：$R^{-1} \equiv \{\langle b,a\rangle\in ranR\times domR : \langle a,b\rangle \in R\}$
    - 合成關係：給定集合 $R、S$，$R\circ S \equiv \{\langle s,r\rangle\in dom S\times ran R : \exists~x~\langle s,x\rangle \in S,\langle x,r\rangle \in R\}$
    - 侷限關係：$R_{|A} \equiv \{x\in R:\exists~a~\exists~b~x= \langle a,b\rangle \land a\in A\}$
    - 映像：$R[A] \equiv \{b\in \cup\cup R : \exists~a\in A~\langle a,b\rangle\in R\}$
    - 一些觀察：
        - Binary relation $\Leftrightarrow$ $R\subseteq domR\times ranR$
        - $R^{-1}$ 是 relation
        - $dom~R^{-1}=ran~R$，$ran~R^{-1}=dom~R$
        - $R$ 是 relation $\Rightarrow$ $(R^{-1})^{-1}=R$
        - $(R\circ S)^{-1}=S^{-1}\circ R^{-1}$
- **函數 (function)**
    - 給定一個集合 $R$：
        - single-valued：每個 a 都可唯一決定 b
        - single-rooted：每個 b 都可唯一決定 a
    - 函數 $\equiv$ single-valued relation
    - injective：single-rooted
    - surjective：co-domain = range
    - bijective：以上同時滿足
    - `左反定理`：
        - 若 $F:A\rightarrow B$ 且 $A\ne \phi$, 則存在 function $L:B\rightarrow A$ 使得 ： $L\circ F = I_A \Leftrightarrow F$ 是 injective
        - 證明：
            - $\Leftarrow$ ： $L=F^{-1}\cup((B\setminus ran F)\times \{a\})$ 對任意 $a\in A$
            - $\Rightarrow$ ： $x=L(F(x))=L(F(y))=y$
    - `右反定理`：
        - 若 $F:A\rightarrow B$ 且 $A\ne \phi$, 則存在 function $R:B\rightarrow A$ 使得 ： $F\circ R = I_B \Leftrightarrow F$ 是 surjective
        - 證明：
            - $\Rightarrow$ ： 任何 $y\in B$，$x=R(y)$ 滿足 $F(x)=y$，故為 surjective
            - $\Leftarrow$ ： 先取 $F^{-1}$ 為 relation，根據選擇公理取 function $R\subseteq F^{-1}$
                - (可能有多個 x 對到同一個 y，使用選擇公理)
- **選擇公理 (choice axiom)**
    - 第一種形式：
        - 每個 relation $R$ 都有一個 function $F$ ，使得 $F\subseteq R$ 而且 $dom F = dom R$

## 自然數
- 定義：
    - 先行者、後繼者：$x^+=x\cup\{x\}$
    - $\{\phi^{+n}:n\in \mathcal{N}\}$ ： 此蒐集體有 inductive 的性質，但不知是否為集合
    - `Inductive Set A`
        - $\phi\in A$
        - $\forall~x~x\in A\Rightarrow x^+\in A$
    - `無窮公理`：$\exists~A~\phi\in A\land(\forall~x~x\in A\Rightarrow x^+\in A)$
        - 集小歸納集 $w$
        - $=\{x:x~\text{is in every inductive set}\}$
        - $=\{x\in A:\forall~B~(\phi\in B\land(\forall y~y\in B\Rightarrow y^+\in B))\Rightarrow x\in B\}$
    - `Peano System`：$(N,F,e)$
        - (1) $e\notin ranF$
        - (2) $F$ 是 injection
        - (3) $M$ 是 $N$ 的 subset，滿足以下兩點則 $M=N$
            - $e\in M$
            - $x\in M\Rightarrow F(x)\in M$
    - `Transitive Set T`
        - $\forall~x~\forall~y~(x\in y\land y\in T)\Rightarrow x\in T$
        - $\forall~y~y\in T\Rightarrow y\subseteq T$
        - $\cup T \subseteq T$
        - $T\subseteq \mathcal{P}T$
- 定理：
    - (1) $w$ 是 inductive set
    - (2) `歸納法原理`：若 $I$ 是 $w$ 的 inductive subset，則 $I=w$
        - 證明 $I=\{x\in w:p(n)\}$ 是 inductive set，則 $w$ 每個元素都有 $p(n)$ 性質
        - (1) $e$ 有 $p(n)$ 性質
        - (2) $x$ 有 $p(n)$ 性質 $\rightarrow$ $F(x)$ 有 $p(n)$ 性質
    - (3) $w$ 是 transitive set
        - 取 $p(n): x\subseteq w$
    - (4) 每個 $x\in w$ 都是 transitive set
        - 取 $p(n): y\in x\Rightarrow y\subseteq x$
    - (5) 前行者觀察一：若 $x\in w,x\ne\phi$，則 $x$ 有 predecessor $y$
        - 取 $p(n): x\ne \phi\Rightarrow x$ 有 predecessor
    - (6) 前行者觀察二：若 $x,y\in w$，則 $x^+=y^+\Rightarrow x=y$
        - $x=(\cup x)\cup x=\cup(x^+)=\cup(y^+)=(\cup y)\cup y=y$
    - (7) $\langle w,\sigma,\phi\rangle$ 是 Peano System
    - (8) `建構自然數 class $N$`：$n\equiv \phi^{+n}$
- 極小歸納集 $w$ 同構於任意一個皮亞諾系統
    - 遞迴定理：$(w,\sigma,\phi)\rightarrow(N,F,e)$
        - 任意的 $e$，$N$ 滿足 $e\in N$，及函數 $F:N\rightarrow N$ ，都存在`唯一`的函數 $G:w\rightarrow N$，使得 $G(\phi)=e$ 且 $G(x^+)=F(G(x))$
        - 證明：
            - (1) 好函數: $g\in w\times N$
                - (a) $\phi\in dom~g\rightarrow g(\phi)=e$
                - (b) $x^+\in dom~g\rightarrow x\in dom~g~\land~g(x^+)=F(g(x))$
            - (2) 好函數集合
                - $G\equiv\{g\in \mathscr{P}(w\times N):\mbox{g is a good function}\}$
            - (3) 好函數觀察
                - 若 $x\in dom~g$ 且 $g$ 是好函數，則存在好函數 $h$ 使得 $x^+\in dom~h$ 以及 $h(x^+)=F(g(x))$
            - (4) $G:w\rightarrow N$ 是函數
                - $I=\{x\in w:G[\{x\}] \mbox{ has at most one element}\}$
                - $\phi\in I$
                - $x\in I\Rightarrow F(y)\in I$
                - $\phi\in dom~G$
                - $x\in dom~G\Rightarrow F(y)\in dom~G$
            - (5) $G:w\rightarrow N$ 是好函數
            - (6) $G:w\rightarrow N$ 是唯一的好函數
    - $w$ 同構於任一 Peano system：$(w,\sigma,\phi)\rightarrow(N,F,e)$
        - 若 $\langle N,F,e\rangle$ 是 Peano system，存在`唯一的雙射`函數 $G:w\rightarrow N$，使得 $G(\phi)=e$ 且 $G(x^+)=F(G(x))$
        - 證明：
            - (1) $G$ 是 surjection ： $I=\{x\in N:x\in ranG\}$
                - $e\in I$
                - $y\in I\Rightarrow F(y)\in I$
            - (2) $G$ 是 injection ： $I=\{x\in w:\forall z\ne x\rightarrow G(z)\ne G(x)\}$
                - $\phi\in I$
                - $x\in I\Rightarrow F(y)\in I$

## 自然數的運算
- Total Ordering
    - 遞移律：$xRy,~yRz\rightarrow xRz$
    - 三一律：以下三者恰一成立 $xRy$，$yRx$，$x=y$
- `屬於∈` 是 $w$ 的 Total Ordering
    - (1)`暖身性質`: 若 $x,y\in w$，則 $x\in y\leftrightarrow x^+\in y^+$
    - (2)`不自屬觀察`: 任意 $x\in w$，$x\notin x$
    - (3)`包空集觀察`: 每個 $x\in w$ 都包含 $\phi$
    - (3)遞移律：每個 $x\in w$ 都是 transitive set
    - (4)三一律：$I=\{~x\in w:\forall y\in w,(x\in y)\lor(y\in x)\lor(x=y)~\}$
        - $x\in y\Rightarrow x^+\in y^+\Rightarrow x^+=y~\lor~x^+\in y$
        - $x=y\Rightarrow y\in x^+$
        - $y\in x\Rightarrow y\in x^+$
- `嚴格包含 ⊊` 也是 $w$ 的 Total Ordering
- 大小關係: $x<y \leftrightarrow x\in y$
    - $x<y\Rightarrow x^+\le y$
- 加法: $x+y=A_y(x)$
    - $A_y(\phi)=y$
    - $A_y(x^+)=A_y(x)^+$
    - 給定 $n\in N$ 都有 $x+n=x^{+n}$
        - 假設事先給定 $n\in N$，定義 $I=\{x\in w:x+n=x^{+n}\}$
    - 加法結合律、加法交換律、加法消去律
- 乘法: $x\cdot y=M_y(x)$
    - $M_y(0)=0$
    - $M_y(x+1)=A_y(M_y(x))=M_y(x)+y$
- 減法/除法
- 良序
    - 非空子集有`最小元素`
        - 注意定義不是極小而是最小
    - 良序定理：`w with < 是良序`
        - 若 $S$ 是沒有最小元素的子集合
        - $I=\{x\in w|~\text{比 x 小的 w 成員都不在 S 裡}\}=w$
    - 良序則有強歸納法原理
        - 若 $S$ 滿足 (1) $0\in S$ (2) $\forall y<x,~y\in x\rightarrow x\in S$ 則 $x\in S$
        - 取 $C=w\setminus S$，$y$ 是 $C$ 最小元素
- $\mathcal{N}$ 不一定等於 $w$
    - $\mathcal{N}$ 是集合 $\Rightarrow$ $\mathcal{N}=w$
    - $\mathcal{N}\ne w$ $\Rightarrow$ $\mathcal{N}$ 不是集合 
- $(w_y,\sigma_y,y)$ 是 Peano System
    - 容易驗證三個條件

## 整數、有理數、實數
- 整數
    - 整數 $\langle A,+,\cdot,<\rangle$ 
        - `可交換有序環`
        - 正元素是良序
    - 代數定義
        - 可交換單群:封閉、結合、交換、單位元素
        - 可交換群:封閉、結合、交換、單位元素、反元素
        - 可交換環:加法可交換群、非 0 乘法可交換單群、分配律
        - 有序:有線性序、正數相乘為正數、加法保持線性序
    - 建構
        - $Z_0^-=\{0\}\times w$
        - $Z_0^+=w\times \{0\}$
        - 整數 $Z=Z_0^-\cup Z_0^+$
    - 簡寫
        - $[+x]=\langle x,0\rangle$
        - $[-x]=\langle 0,x\rangle$
        - $0_Z=\langle 0,0\rangle$
        - $1_Z=\langle 1,0\rangle$
    - 定義與檢驗
        - 乘法、加法、<
        - 分配律、加法結合律
        - 可交換環、有線性序、正數相乘為正數、加法保持線性序
- 有理數
    - 有理數 $\langle Q,+,\cdot,<\rangle$ 
        - `極小有序體`
    - 代數
        - 可交換環:加法可交換群、非 0 乘法可交換`單群`、分配律
        - 體:加法交換群、非 0 乘法交換`群`、分配律
        - 有序:有線性序、正數相乘為正數、加法保持線性序
        - 有序體:有序 + 可交換環、非 0 乘法反元素
    - 等價關係 $R\subseteq A\times A$
        - reflexive + transitive + symmetric
        - 等價子集 $[x]_R=\{y\in A:\langle x,y\rangle\in R\}$
        - $[x]_R=[y]_R \Leftrightarrow \langle x,y\rangle\in R$
        - 商集 $A/R=\{C\in\mathcal PA~:~\exists x(x\in A)\land (C=[x]_R)\}$
            - e.g. $A=\{1,2,3,4,5,6\}$，$aRb\iff 3|a-b$
            - $A/ R=\{\{1,4\},\{2,5\},\{3,6\}\}$
    - 建構
        - 有理數等價關係 $Q$
            - $\langle a,b\rangle Q\langle c,d\rangle\iff a\cdot d=b\cdot c$
        - 有理數 $\mathcal Q=(Z\times Z^{\pm})/Q$
        - $[\langle a,b\rangle]_Q=\frac{a}{b}=a/b$
    - 定義與檢驗
        - 乘法、加法、<、單位元素、反元素
        - 分配律、有序
        - 極小(可構造出任何的 $[\langle a,b\rangle]_Q=\frac{a}{b}=a/b$ )
    - 有理數的稠密性
    - `阿基米德性質`
        - 有理數的子集 $R$ 滿足 (1) 不空不滿 (2) 向下封閉
        - 則對任意的 $q\in \mathcal Q^+$，可以找到 $p\in R$、$r\notin R$ 使得 $p+q=r$
        - 證明
            - 任意取 $a\in R$ 、 $b\notin R$，把中間每長度 $q$ 切成一份
            - 根據向下封閉與餘數定理，存在 $n$ 使得 $a+qn\in R$ 、 $a+(q+1)n\notin R$
- 實數
    - 實數
        - 有序體
        - 子集合有上界就有最小上界(上確界)
    - 戴德金切割
        - 有理數的子集 $R$ 滿足 (1) 不空不滿 (2) 向下封閉 (3) 無最大者
    - 建構
        - $\mathcal R=\{x\in\mathcal P\mathcal Q:x~\text{滿足 (1)(2)(3) }\}$
        - e.g.
            - $R=\{x\in Q~:~x\cdot x<2\}~\rightarrow \sqrt{2}$
            - $R=\{x\in Q~:~x\cdot x<q\}~\rightarrow q$
    - 性質
        - 證明一個集合是實數 (在 $\mathcal R$ 裡)，等價於證明他是 戴德金切割
        - 若 $S\subseteq \mathcal R$ 有上界，則 $\cup S$ 是 $S$ 的最小上界

## 集合的容量
- 集合間的關係
    - $A$ injective to $B$ ($A \preceq B$): 存在 injection
    - $A$ surjective to $B$ : 存在 surjection
    - $A$ bijective to $B$ ($A \approx B$): 存在 bijection
- 有限與無限
    - 有限集合: $S$ 和某個 $x\in w$ 有 bijection
        - 定義 $|S|=x$
    - 無限集合: 反之
- 性質
    - $A \approx B \rightarrow PA \approx PB$
    - 任意集合 $S$， $S \not\approx PS$
    - $A \approx B$ $\iff$ $A$ 到 $B$ 有 injection，$B$ 到 $A$ 也有 injection
    - `鴿籠原理`: 有限集合 $\iff$ 和每個 proper subset 都沒有 bijection
    - 有限集合
        - $|x\cup\{a\}|=|x|+1$
        - $x\subsetneq y~\rightarrow |x|<|y|$
        - $x\subseteq y~\rightarrow |x|\le|y|$
        - $f:A\rightarrow B$，$A\approx B$，則 $f$ 是 injective $\leftrightarrow$ $f$ 是 surjective
    - `實數和自然數冪`: $R\approx Pw$
- 選擇定理
    - WO(Well Order Principle): 每個集合都可以被良序排序
    - AC(Axiom of Choice): 每個 relation，都有個 domain 相同的 subset 為 function
    - CF(Choice Function): 存在 $f:PB->B$ 使得 $f(x)\subseteq x$ 總是成立
    - ZL(Zorn's Lemma): 若 $S$ 的每個子 chain $C$ 都有上界，則 $S$ 有最大元素
    - CC(Cardinal Comparability): 任兩集合，必定 $A\preceq B$ 或 $B\preceq A$

