# 集合論

## 公設化集合論

### 延伸公設

若$x=y$且$x\in A$，則$y\in A$

### 構造公設
假設$C=\{x\mid P(x)\}$，其中$P(x)$是一個關於$x$之敘述，且$x$為元素，則$C$為類。

### 配對公設

若$A,B$為兩集合，則$\{A,B\}$為集合。

### 子集合公設

若$A$為集合，且$B\subseteq A$，則$B$為集合。

### 聯集公設

若$\mathcal{A}$是一些集合的集合，則$\displaystyle\bigcup_{A\in\mathcal{A}}A$也為集合。

### 冪集合公設

定義：
假設$A$為集合，則定義$\mathcal{P}(A)=\{B\mid B\subseteq A\}$
則$\mathcal{P}(A)$也為集合

### 空集合公設

$\varnothing$是集合。

由空集合，可以構造出正整數$\mathbb{N}$

定義：
$0=\varnothing$
$1=\{\varnothing\}$
$2=\{\varnothing,\{\varnothing\}\}$
依此類推

### 自然數公設
$\mathbb{N}$(包含$0$)是集合。

## 函數

函數$f$是一個圖，且滿足以下兩條件：
假設$f\subseteq A\times B$為一函數，$A,B$都是類
F1 : $\forall x\in A,\exists y\in B,\text{s.t.}\ (x,y)\in f$
F2 : $(x,y_1)\in f\land(x,y_2)\in f\implies y_1=y_2$

將$f$寫作$f:A\to B$
因為$f(x)\in B$，我們通常利用$y$來表示此元素。

拿到一函數$f$，要首先檢驗是否為Well-defined，意即
$f$是否將同一個$x$送到同一個$y$？

函數$f$是一對一(單射)函數的意思是
若$f(a)=f(b)$，則$a=b$

函數$f$是映成(滿射)函數的意思是
$\forall y\in B,\exists x\in A,\text{s.t.}\ f(x)=y$

函數$f$是對射函數的意思是$f$是一對一且映成。

### 選擇公設

假設$\Lambda$為一指標類，且指標族$\{E_\alpha\mid \alpha\in\Lambda\}$滿足以下條件：
$\forall\alpha\in\Lambda,E_\alpha\not=\varnothing$且$\alpha\not=\beta\iff E_\alpha\cap E_\beta=\varnothing$
那麼就會存在一個類$S$，其由$E_\alpha$中挑選唯一的元素組合而成。
也就是說存在一個選擇函數
$\phi:\alpha\to\displaystyle\bigcup_{\alpha\in\Lambda}E_{\alpha}$
$\alpha\mapsto\phi(\alpha)\in E_{\alpha}$

定義一些特殊函數：

恆等函數
$\text{id}_A:A\to A$
$x\mapsto x$

$B\subseteq A$上之特徵函數
$\chi_B:B\to\{0,1\}$
$x\mapsto\chi_B(x):=\begin{cases}0,&\text{if}\ x\in A-B\\1,&\text{if}\ x\in B\end{cases}$

嵌入函數$B\subseteq A$
$\iota:B\to A$
$x\hookrightarrow x$
特別的，$B=A\iff\iota=\text{id}_A$

常數函數
假設$b\in B$
$C_b:A\to B$
$x\mapsto b$

定義一函數$f:A\to B$之反函數$f^{-1}:B\to A$為一個滿足以下條件的函數：
$f^{-1}\circ f=\text{id}_A\land f\circ f^{-1}=\text{id}_B$
底下的定理能夠證明反函數存在的條件以及其唯一性。

定理：
設$f,g:A\to B$
$f=g\iff\forall x\in A,f(x)=g(x)$
假設$f=g$，給定$(x,y)\in f\iff(x,y)\in g$
所以$f(x)=g(x)$因為$f,g$都是函數。
假設$\forall x\in A,y=f(x)=g(x)$

若$(x,y)\in f$，那麼立即得到$(x,y)\in g$
同理若$(x,y)\in g$，則$(x,y)\in f$
因此得到$f\subseteq g$及$g\subseteq f$，所以$f=g$

$f:A\to B$為一對一函數若且唯若$\exists g:B\to A,\text{s.t.}\ g\circ f=\text{id}_A$

$pf:$
($\implies$)
假設$f$是一對一函數，我們令$g:B\to A$如下：
$g(x):=\begin{cases}x,&\text{if}\ x\in\text{ran}(f)\\C_a(x),&\text{if}\ x\in A-\text{ran}(f)\end{cases}$
其中$a\in A$
那麼對於任意$x\in A$，我們都有$(g\circ f)(x)=g(f(x))=x=\text{id}_A(x)$
我們可以得到$g\circ f=\text{id}_A$
($\Longleftarrow$)
假設$\exists g:B\to A,\text{s.t.}\ g\circ f=\text{id}_A$
給定$f(x_1)=f(x_2)$：
因為$x_1=g(f(x_1))=g(f(x_2))=x_2$，所以$f$是一對一函數。

因此我們得到結論$f:A\to B$為一對一函數若且唯若$\exists g:B\to A,\text{s.t.}\ g\circ f=\text{id}_A$

$f:A\to B$為映成函數若且唯若$\exists g:B\to A,\text{s.t.}\ f\circ g=\text{id}_B$

為了證明此定理，我們先定義函數的像與逆像
假設$f:A\to B$及$C\subseteq A,D\subseteq B$
$f(C):=\{y\in B\mid \exists x\in C,\text{s.t.}\ y=f(x)\}$
$f^{-1}(D):=\{x\in A\mid f(x)\in D\}$

($\implies$)
假設$f:A\to B$為映成函數
對於任意的$b\in B$，我們都有$f^{-1}(\{b\})\not=\varnothing$
且$\displaystyle\bigcup_{b\in B}f^{-1}(\{b\})=A$(顯然)
又如果$b_1\not=b_2$，我們知道$f^{-1}(\{b_1\})\cap f^{-1}(\{b_2\})=\varnothing$
因為如果交集非空，假設$a\in f^{-1}(\{b_1\})\cap f^{-1}(\{b_2\})$，那麼$f(a)\in\{b_1\}\cap\{b_2\}$
推得$f(a)\in\varnothing$為矛盾。
因此由選擇公設得知，存在一個選擇函數
$g:B\to A$
$b\mapsto g(b)\in f^{-1}(\{b\})$
因此$f(g(b))=b=\text{id}_B(b)$，對於任意$b\in B$皆成立。
所以我們可得到結論$f\circ g=\text{id}_B$

($\Longleftarrow$)
假設$\exists g:B\to A,\text{s.t.}\ f\circ g=\text{id}_B$
給定$y\in B$，我們有$y=\text{id}_B(y)=(f\circ g)(y)=f(g(y))$
所以存在$g(y)\in A$使得$y=f(g(y))$，因此$f$是映成函數

我們得到結論$f:A\to B$為映成函數若且唯若$\exists g:B\to A,\text{s.t.}\ f\circ g=\text{id}_B$

$f:A\to B$為對射函數若且唯若$\exists g:B\to A,\text{s.t.}\ f\circ g=\text{id}_B\land g\circ f=\text{id}_A$且$g=f^{-1}$

($\implies$)
假設$f:A\to B$是對射函數
那麼$f$是一對一且為映成函數
所以$\exists g_1:B\to A,\text{s.t.}\ g_1\circ f=\text{id}_A$以及$\exists g_2:B\to A,\text{s.t.}\ f\circ g_2=\text{id}_B$
假設$g_2(b)=a$，那麼$f(g_2(b))=f(a)=b$
又因為$g_1(f(a))=a$，我們可以知道$g_1(b)=a$
因此$\forall b\in B,g_1(b)=g_2(b)$，可得$g_1=g_2$
定$g=g_1$
接下來我們證明$g=f^{-1}$
假設$g(b)=a$，我們就有$f(g(b))=f(a)=b$
因此$f^{-1}(b)=f^{-1}(f(g(b)))=f^{-1}(f(a))=a=g(b)$
對於任意$b\in B$都成立
所以我們可以得到$g=f^{-1}$，證明了反函數之唯一性。

($\Longleftarrow$)
假設$\exists g:B\to A,\text{s.t.}\ f\circ g=\text{id}_B\land g\circ f=\text{id}_A$且$g=f^{-1}$
我們需要證明$g$是一對一且映成

一對一的部分：
給定$f(x_1)=f(x_2)$，因為$f^{-1}:B\to A$也是函數，我們可得
$x_1=f^{-1}(f(x_1))=f^{-1}(f(x_2))=x_2$
因此$f$是一對一

映成的部分：
給定$b\in B$，因為$f(f^{-1}(b))=b$，所以$f$是映成函數。

得到結論$f:A\to B$為對射函數若且唯若$\exists g:B\to A,\text{s.t.}\ f\circ g=\text{id}_B\land g\circ f=\text{id}_A$且$g=f^{-1}$

也因此我們可以知道若$f$是對射函數，則$f^{-1}$存在且唯一，且$f^{-1}$也是對射函數

定義：
我們說$A,B$兩集合是一一對應的就是存在一個對射函數$f:A\to B$

乘積類之推廣定義：
假設$\{A_i\}_{i\in I}$為指標族，且我們定$A=\displaystyle\bigcup_{i\in I}A_i$，則我們定義其乘積為
$\displaystyle\prod_{i\in I}A_i:=\{f\mid f:I\to A\land\forall i\in I,f(i)\in A_i\}$

以及定義乘積類到$A_i$上的投影：
$p_i:\displaystyle\prod_{i\in I}A_i\to A_i$
$x\mapsto x(i)$

### 替換公設

若$A$為一集合，且存在一映成函數$f:A\to B$
則$B$為集合。

定義：
假設兩個類$A,B$
定義符號$B^A:=\{f\mid f:A\to B\}$

定理：
假設$A$是一個類
$2^A$與$\mathcal{P}(A)$是一對一對應的。
$pf:$
我們說$F:\mathcal{P}(A)\to 2^A$
$F(B):=\chi_B$

則$F$是一對一的
給定$F(B_1)=F(B_2)$
$\chi_{B_1}=\chi_{B_2}$
$\iff\forall x\in B_1,\chi_{B_1}(x)=\chi_{B_2}(x)=1$
$\iff\forall x\in B_2,\chi_{B_2}(x)=\chi_{B_1}(x)=1$
因此$x\in B_1\iff B_2$，所以$B_1=B_2$
推得$F$是一對一。

$F$是映成
給定$g\in 2^A$
考慮$g^{-1}(\{1\})\subseteq A$，我們可得$g^{-1}(\{1\})\in\mathcal{P}(A)$

因此我們得到$2^A$與$\mathcal{P}(A)$是一對一對應的。

一些事實：

若$A,B$為兩個集合，則
$B^A$也是集合。
道理很簡單，因為$A\times B$也是集合，又我們知道如果$f\in B^A$，那麼$f$就會是$A\times B$的子集合。
也因此我們可以馬上得到$B^A\subseteq\mathcal{P}(A\times B)$
根據冪集合公設與子集合公設，$B^A$是一個集合。

若$\{A_i\}_{i\in I}$為集合的指標集合，且$I$也是集合，那麼$\displaystyle\prod_{i\in I}A_i$也是集合。

我們先證明$\displaystyle\prod_{i\in I}A_i\subseteq A^I$，其中$A=\displaystyle\bigcup_{i\in I}A_i$
假設$f\in\displaystyle\prod_{i\in I}A_i$
我們立即知道$f:I\to A\land\forall i\in I,f(i)\in A_i$，所以$f\in A^I$是明顯的。

更廣義的說，假設$\{B_i\}_{i\in I}$滿足$\forall i\in I,B_i\subseteq A_i$，那麼$\displaystyle\prod_{i\in I}B_i\subseteq A^I$
道理也很簡單，就是因為$\displaystyle\bigcup_{i\in I}B_i\subseteq\displaystyle\bigcup_{i\in I}A_i$。

我們透過聯集公設得知$\displaystyle\bigcup_{i\in I}A_i=A$也是集合，也因此$A^I$也是集合，再由子集合公設得知$\displaystyle\prod_{i\in I}A_i$也是集合。

## 關係與序

假設$A,B$是兩個集合
我們定義一個關係就是一個圖$R\subseteq A\times B$
特別的，我們說$R$是$A$上的一個關係就是指$R\subseteq A\times A$

$R$是$A$上的一個關係
我們說$R$具有：
(1)自反性：$\forall x\in A,(x,x)\in R$
(2)對稱性：$(x,y)\in R\implies (y,x)\in R$
(3)遞移性：$(x,y)\in R\land (y,z)\in R\implies(x,z)\in R$
(4)反自反性：$\forall x\in A,(x,x)\not\in R$
(5)反對稱性：$(x,y)\in R\land (y,x)\in R\implies x=y$
(6)不對稱性：$(x,y)\in R\implies (y,x)\not\in R$

若$R$滿足(1),(2),(3)，則我們說$R$是$A$上的一個等價關係。

假設$R$是$A$上的一個等價關係，我們定義：
$[x]:=\{y\in A\mid (x,y)\in R\}$

定理：
若$y\in[x]$，那麼$[x]=[y]$
給定$a\in[x]$
我們可以得知$(a,x)\in R$
由假設$y\in[x]\iff (x,y)\in R$
$\iff (a,y)\in R$
$\iff a\in [y]$
即$[x]=[y]$

假設$x,y\in A$，$R$是$A$上的一個等價關係
則$[x]=[y]$或是$[x]\cap[y]=\varnothing$

假設$[x]\cap[y]=\varnothing$，就可得到結論
假設$[x]\cap[y]\not=\varnothing$，我們需要證明$[x]=[y]$
如果$k\in[x]\cap[y]$，那麼$(k,x)\in R$且$(k,y)\in R$
根據對稱性與遞移性，可得$(x,y)\in R$，也因此$y\in[x]$且$x\in[y]$
也就是說$[x]=[y]$

定義$A$上的分割$P$為：
$P=\{E_{\alpha}\}_{\alpha\in\Lambda}$
其中$E_{\alpha}\cap E_{\beta}=\varnothing\lor E_{\alpha}=E_{\beta}$對於任意$\alpha,\beta\in\Lambda$都成立。
以及$\displaystyle\bigcup_{\alpha\in\Lambda}E_{\alpha}=A$

那麼可以很自然的發現，$A$上的等價關係$R$之所有等價類就會形成$A$上的一個分割。
因此我們可以將$[x]$視為某個集合上的一個點
定義$A$上關於$R$之商空間$A/R$：
$A/R:=\{[x]\mid x\in A\}$
我們同時也可以定義$A$上的正規映射：
$p:A\to A/R$
$x\mapsto [x]$
很容易發現$p$是一個函數。

因此我們可以利用此定義來協助我們分析某個定義域為$A$的函數$f:A\to B$。
假設$R:=\{(x,y)\in A\times A\mid f(x)=f(y)\}$
不難看出$R$是$A$上的一個等價關係。
定義以下兩個函數
$s:A/R\to f(A)$
$[x]\mapsto f(x)$
以及
$\iota:f(A)\to B$
$y\mapsto y$

我們可以輕易得知$f=\iota\circ s\circ p$
且$p$是映成函數，$s$為對射函數，$\iota$為一對一函數。

### 偏序

回顧：
若$R$滿足關係性質(1),(3),(5)，則我們說$R$是$A$上的一個偏序。
若$R$滿足關係性質(1),(3),(6)，則我們說$R$是$A$上的一個嚴格偏序。

定義：
若$R_1$是$A$上的一個偏序關係，我們就說$(A,R)$是一個偏序集合。
通常我們將$R$寫作$\le$，且如果$x\le y$，我們也將$y\ge x$視為同一件事情。
如果$R_2$是$A$上的一個嚴格偏序，我們就會將$R$寫作$<$
我們也定義$x\le y\iff x<y\lor x=y$以及$x<y\iff x\not=y\land x\le y$
跟偏序關係同理，$y>x$跟$x<y$代表同一件事情。

設$(A,\le),(B,\le)$為兩個偏序集合
我們簡記$(A,\le),(B,\le)$分別為$A,B$

定義函數$f:A\to B$為遞增，若其滿足
$x\le y\implies f(x)\le f(y)$
嚴格遞增
$x<y\implies f(x)<f(y)$

若$a\in A$，定義$S_a:=\{x\mid x<a\}$為$A$之initial segment。

若$A$為一個全序集合，則$\forall a,b\in A,a\le b\lor b\le a$
我們也稱$A$為一個線性序集合或是鍊。

若$C$是$A$之子集合且滿足
$\forall x\in A,\exists y\in C,\text{s.t.}\ y\ge x\implies x\in C$
我們就說$C$是$A$之lower set。

若$m$是$A$中之最小(minimal)元素，則
$m\in A\land\forall x\in A,x\ge m$
顯然此時$A$必須是一個全序集合。

若$m$是$A$中之極小元素，則
$\forall x\in A,\text{if}\ x\le m\implies x=m$
顯然此時$A$可以是一個偏序集合。

假設$C$是$A$之子集合
若$l$是$C$之下界，則
$\forall x\in C,l\le x$

最大，極大，上界之定義方式類似。

假設$A$是一個全序集合
若$A$是一個良序集合，則$A$的所有子集合都有最小元素。

#### 偏序集合間之同構

假設$(A,\le),(B,\le)$為兩個偏序集合
我們說$f:A\to B$為一個同構映射，若$f$是一個對射函數且$x\le y\iff f(x)\le f(y)$

定理：
若$A,B$為兩個偏序集合，且$f:A\to B$是一個同構映射，則$x<y\iff f(x)<f(y)$

$pf:$
因為$x<y$，所以$x\le y$，因此$f(x)\le f(y)$
如果$f(x)=f(y)$，那麼$f(y)\le f(x)$，因此$y\le x$為矛盾。
因此$f(x)<f(y)$
反之亦然。

若$A$為全序集合，$B$為偏序集合，若$f:A\to B$為對射且遞增之映射，則$f$為同構映射。

$pf:$
因為$f:A\to B$為對射且遞增之映射，所以我們只需證明$f(x)\le f(y)\implies x\le y$。
假設$f(x)\le f(y)$，因為$A$是個全序集合，我們有$x\le y\lor y<x$
如果$f(x)<f(y)$且$x=y$，那麼與$f$是函數矛盾
如果$f(x)<f(y)$且$y<x$，那麼$f(y)<f(x)$也是矛盾
所以$f(x)<f(y)\implies x<y$
如果$f(x)=f(y)$，因為$f$是一對一，立即推得$x=y$
因此若$f(x)\le f(y)$，則$x\le y$
我們可以得到$f$是同構映射之結論。

定義：
假設$A,B$為兩個偏序集合，我們記$A\sim B$來表示$A$同構於$B$。

定理：

假設$A$是良序集合。
$B$是$A$的一個lower set若且唯若$B=A$或$B$是$A$的一個initial segment。

$pf:$

($\implies$)
假設$B$是$A$的一個lower set。
若$B=A$，則結論顯然。
若$B\not=A$，則$A-B\not=\varnothing$。
因此$A-B$有最小元素$m$，我們證明$B=S_m$。
($\subseteq$)
假設$B\not\subseteq S_m$，也就是說：
$\exists x\in B\land x\not\in S_m$
由於$x\ge m$，推得$m\in B$，可是$m\in A-B$，矛盾。
故$B\subseteq S_m$。
($\supseteq$)
假設$B\not\supseteq S_m$，也就是說：
$\exists x\in S_m\land x\not\in B$
由於$x\in S_m\implies x\in A$得到$x\in A-B\land x<m$
這與$m$是$A-B$中的最小元素矛盾。
因此$B\supseteq S_m$。

故我們推得$B=S_m$，也就是$B$是$A$的某個initial segment。

($\Longleftarrow$)
假設$B=A$或$B$是$A$的某個initial segment。
如果$B=A$
任意給定$x\in A$，必定有$x\in B$，所以$B$顯然是$A$的一個lower set。
如果$B$是$A$的某個intial segment $S_a$：
給定$x\in A$以及$\exists y\in B,\text{s.t.}\ y\ge x$
因為$B=S_a$，所以$a>y\ge x$，也就是說$x\in S_a=B$。
因此$B$也是一個$A$的lower set。

我們推得結論：
$B$是$A$的一個lower set若且唯若$B=A$或$B$是$A$的一個initial segment。

## 良序集合三一律

假設$A,B$為兩個良序集合，$S_a,S_b$分別為$A,B$中的initial segment，則以下情形恰一種會成立
(1)$A\sim B$
(2)$A\sim S_b$
(3)$S_a\sim B$

意思就是良序集合間只有大小之差別。

為了證明三一律，我們先證明一些引理
以下$A$為良序集合

引理1：
假設$f$是$A$到$A$的子集合之同構映射，則$\forall x\in A,x\le f(x)$。

$pf:$
我們證明$E=\{x\mid x>f(x)\}=\varnothing$
假設$E\not=\varnothing$，那麼由於$A$是良序集合，我們假設$E$中之最小元素為$s_0$
因為$s_0>f(s_0)$而且$f$是遞增的，所以$f(s_0)>f(f(s_0))$，因此$f(s_0)\in E$，可是$s_0>f(s_0)$，這與$s_0$是$E$中之最小元素矛盾，因此$E=\varnothing$。
我們得到若$f$是$A$到$A$的子集合之同構映射，則$\forall x\in A,x\le f(x)$之結論。

引理2：
不存在自$A$到$A$之initial segment $S_a$之同構映射。

$pf:$
假設存在$f:A\to S_a$之同構映射
那麼由引理1可得$a\le f(a)\implies f(a)\not\in S_a$
可是$f$是映成函數，也就是說$\text{ran}{(f)}=S_a$，矛盾。
因此不存在自$A$到$A$之initial segment $S_a$之同構映射。

推論：
良序集合無法同構於自己的一個initial segment。
也就是說不存在同構於自己的一個initial segment的良序集合。

引理3：
假設$B$也是一個良序集合
若$A\sim S_b$，則不存在$C\subseteq A$使得$B\sim C$。

$pf:$
假設$C\subseteq A,\text{s.t.}\ B\sim C$
那麼根據假設以及條件，我們可以知道
$f:A\to S_b$以及$g:B\to C$都是同構映射
可是$f\circ g:B\to D\subseteq S_b$也會是一個同構映射，因此依據引理2，得到矛盾。
所以若$A\sim S_b$，則不存在$C\subseteq A$使得$B\sim C$。

引理4：
假設$S_x,S_y$皆為$A$之initial segment，若$x<y$，則$S_x$是$S_y$之initial segment。

$pf:$
我們必須證明$S_x=\{\alpha\in S_y\mid \alpha<x\}$
也就是說只要$\alpha\in S_x$，則$\alpha\in S_y$且$\alpha<x$
首先因為$S_x=\{\alpha\in A\mid\alpha<x\}$，所以第二個條件成立，而且由於$x<y$，推得$\alpha<x<y$
因此$\alpha\in S_y$，故$S_x=\{\alpha\in S_y\mid\alpha
<x\}$。
也就是說$S_x$其實就是$S_y$之initial segment。

接下來我們就可以證明三一律了

$pf:$

首先我們證明(1),(2),(3)彼此互斥。
若$A\sim B$：
假設$A\sim S_b$，那麼$A\sim B\sim S_b$為矛盾。
假設$S_a\sim B$，那麼$A\sim S_a$為矛盾。
所以$A\not\sim S_b\land S_a\not\sim B$

若$A\sim S_b$：
假設$A\sim B$，那麼$B\sim S_b$為矛盾。
假設$S_a\sim B$，那麼根據引理3得到矛盾。
所以$A\not\sim B\land S_a\not\sim B$

若$S_a\sim B$，同理可證$A\not\sim B\land S_b\not\sim A$

故(1),(2),(3)彼此互斥。

至於存在性，我們首先考慮以下$A$之子集合：
$C:=\{x\in A\mid\exists y\in B,\text{s.t.}\ S_y\sim S_x\}\subseteq A$
我們將證明$F:C\to B$為函數，且若令$D=\text{ran}(F)$以及$F:C\to D$，則$F$為同構映射。
以及證明$C$與$D$皆分別為$A$與$B$之lower set。
那麼我們就可以證明存在性了。

定$F:C\to B$，我們先檢驗其是否為Well-defined。
F1：依據$C$之定義可得。
F2：給定$x_1=x_2$，我們必須說明$F(x_1)=F(x_2)$
設$y_1=F(x_1),y_2=F(x_2)$
由於$B$是良序集合，$y_1\le y_2\lor y_1\ge y_2$
假設$y_1\not=y_2$，則：
若$y_1>y_2$，那麼$S_{y_2}$就會是$S_{y_1}$的initial segment，因此$S_{y_2}\not\sim S_{y_1}$。
可是$S_{x_1}\sim S_{y_1}\sim S_{x_2}\sim S_{y_2}$，產生了矛盾，因此我們推得$y_1\le y_2$。
若$y_1<y_2$，同理可得$y_1\ge y_2$，因此可能的情況只有$y_1=y_2$
這說明了$F$是well-defined。

令$D=\text{ran}(F)$及$F:C\to D$，顯然地，$f$是映成函數。
我們接下來必須證明$F$是一對一且$x_1\le x_2\iff F(x_1)\le F(x_2)$。

一對一：
給定$F(x_1)=F(x_2)=y$，我們有：
$S_{x_1}\sim S_y\sim S_{x_2}$，因此若$x_1<x_2$或是$x_2<x_1$，根據引理2皆會推得矛盾，故$x_1=x_2$。
我們推得$F$是一對一的。

$x_1\le x_2\iff F(x_1)\le F(x_2)$：
($\implies$)
假設$x_1\le x_2$：
若$x_1=x_2$，因為$F$是一個函數，我們可以得知$F(x_1)=F(x_2)$。
若$x_1<x_2$，我們假設$F(x_1)>F(x_2)$，那麼：
$S_{x_1}\sim S_{F(x_1)}\land S_{x_2}\sim S_{F(x_2)}$以及$S_{x_1},S_{F(x_2)}$分別是$S_{x_2},S_{F(x_1)}$之initial segment，根據引理3得知：
若$S_{x_1}\sim S_{F(x_1)}$，則不存在任何$S_{F(x_1)}$之子集合$X$使得$S_{F(x_1)}\sim X$。
故$S_{F(x_2)}\sim S_{x_2}$為矛盾。
因此我們可以得知若$x_1\le x_2\implies F(x_1)\le F(x_2)$
($\Longleftarrow$)
同理可得$F(x_1)\le F(x_2)\implies x_1\le x_2$

故我們推得$x_1\le x_2\iff F(x_1)\le F(x_2)$，也因此$F:C\to D$是一個同構映射。

接下來我們證明$C$是一個$A$的lower set。
給定$\alpha\in A$以及存在$x\in C,\text{s.t.}\ \alpha\le x$
我們必須推得$\alpha\in C$。

因為$x\in C$，我們可以知道$\exists y\in D,\text{s.t.}\ S_y\sim S_x$。
也就是說存在一個同構映射$g:S_x\to S_y$，又因為$S_\alpha\subseteq S_x$
因此我們可以知道$g|_{S_\alpha}:S_\alpha\to S_{g(\alpha)}$也是一個同構映射，推得$S_\alpha\sim S_{g(\alpha)}$，所以$\alpha\in C$。

同理，考慮$F$之反函數，也可得到$D$是一個$B$的lower set，因此根據定理，$C=A$或$C$是$A$的initial segment及$D=B$或$D$是$B$的initial segment。

接下來我們要說明$C$是$A$之initial segment且$D$是$B$之initial segment的情形不會成立。

假設$S_a=C,S_b=D$
因為$S_a\sim S_b\sim C\sim D$，我們得知$S_a\sim S_b$，由$C$之定義，$a\in C$，矛盾。
也因此$C$是$A$之initial segment且$D$是$B$之initial segment的情形不會成立。

也就是說必定會有以下三種情況產生：
(1)$C=A$且$D=B$
(2)$C$是$A$的initial segment且$D=B$
(3)$C=A$且$D$是$B$的initial segment

意即：
(1)$A\sim B$
(2)$S_a\sim B$
(3)$A\sim S_b$

而我們已經證明了這三個情況彼此互斥，故良序集合會有三一律之定理。

### Lower set之討論

設$A$是一偏序集合，且$B\subseteq A$。

對於$b\in B$，定義$\downarrow b:=\{x\in A\mid x\le b\}$
而定義$\downarrow B:=\displaystyle\bigcup_{b\in B}\downarrow b$

性質：
(1)$\downarrow B\supseteq B$，等號成立若且唯若$B$是lower set。
(2)$\downarrow B$是一個lower set。
(3)若$C\supseteq B$且$C$是一個lower set，則$C\supseteq\downarrow B$

$pf:$
(1)
假設$x\in B$
由於$x\in\downarrow x\subseteq\displaystyle\bigcup_{b\in B}\downarrow b=\downarrow B$
因此$B\subseteq\downarrow B$

假設等號成立，也就是$\downarrow B\subseteq B$
那麼若$x\in A$且存在$y\in B,\text{s.t.}\ y\ge x$，我們必須證明$x\in B$
$y\in B\land y\ge x\implies x\in\downarrow y\subseteq\downarrow B=B$
假設$B$是一個lower set，我們必須證明$\downarrow B\subseteq B$
$x\in\downarrow B\implies\exists b\in B,\text{s.t.}\ x\in\downarrow b\implies\exists b\in B,\text{s.t.}\ x\le b$
由於$B$是一個lower set，我們得到$x\in B$
因此$\downarrow B\subseteq B$

故等號成立若且唯若$B$是lower set。

(2)
假設$x\in\downarrow B$且$\exists y\in\downarrow B,\text{s.t.}\ y\ge x$
因為$y\in\downarrow B$，所以$\exists b\in B,\text{s.t.}\ y\in\downarrow b$
得到$b\ge y\ge x$，由遞移性得到$b\ge x$，所以$x\in\downarrow b$，得到$x\in\downarrow B$

(3)
假設$x\in\downarrow B$
$\iff x\in\displaystyle\bigcup_{b\in B}\downarrow b$
因為$C\supseteq B$，所以$\forall b\in B\implies b\in C$
也因此我們說$\displaystyle\bigcup_{b\in B}\downarrow b\subseteq\displaystyle\bigcup_{c\in C}\downarrow c$
假設$k\in\displaystyle\bigcup_{b\in B}\downarrow b$
$\iff\exists b\in B,\text{s.t.}\ k\in\downarrow b$
$\iff\exists b\in B,\text{s.t.}\ k\le b$
$\implies\exists c\in C,\text{s.t.}\ k\le c$
$\iff k\in\displaystyle\bigcup_{c\in C}\downarrow c$
所以$x\in\displaystyle\bigcup_{c\in C}\downarrow c=\downarrow C$
又因為$C$是一個lower set，$\downarrow C=C$
得到$C\supseteq\downarrow B$
意即，$\downarrow B$是包含$B$的所有lower set中最小的。

推論：$\displaystyle\bigcap_{l\in L}l=\downarrow B$
其中$L:=\{C\mid C\ \text{is a lower set containing}\ B\}$
因為$\downarrow B\in L$，因此$\displaystyle\bigcap_{l\in L}l=\downarrow B$。

假設$\{B_i\}_{i\in I}$為一個$A$中的lower set的指標集合，則：
$\downarrow(\displaystyle\bigcup_{i\in I}B_{i})=(\displaystyle\bigcup_{i\in I}B_{i})$
$\downarrow(\displaystyle\bigcap_{i\in I}B_i)\subseteq(\displaystyle\bigcap_{i\in I}B_{i})$

$pf:$
設$x\in\downarrow(\displaystyle\bigcup_{i\in I}B_{i})$
$\iff x\in\displaystyle\bigcup_{b\in\bigcup_{i\in I}B_i}\downarrow b$
$\iff\exists b\in\displaystyle\bigcup_{i\in I}B_i,\text{s.t.}\ x\in\downarrow b$
$\iff\exists b\in\displaystyle\bigcup_{i\in I}B_i,\text{s.t.}\ x\le b$
$\iff\exists i\in I,\text{s.t.}\ \exists b\in B_i\land x\le b$
$\iff\exists i\in I,\text{s.t.}\ x\in B_i$因為$B_i$是一個lower set
$\iff x\in\displaystyle\bigcup_{i\in I}B_i$
因此$\downarrow(\displaystyle\bigcup_{i\in I}B_{i})=(\displaystyle\bigcup_{i\in I}B_{i})$

推論：任意一個lower set之指標族的聯集與交集也都是lower set