# 集合論 ## 建造集合塔 - $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$