User:C44986054/數理邏輯/集合

直觀來說，集合是一群有"相同性質"的實體，比如說都大於零的正數集合，甚至複雜的"都是連續且定義域緊緻的函數"的集合。

雖然從形式理論的觀點來看，集合論照理來說是一階邏輯理論的一種。但是從實質的內容和動機來看，不如說公理化集合論是透過增加若干公理而構成的一階邏輯"加強"版本，甚至可以將之視為一種高階邏輯。

本文敘述的是集合正規嚴謹的處理方法，建議先看完數理邏輯以後再來閱讀。

基本定義

本篇採用的是Von Neumann–Bernays–Gödel公理化集合論(NBG set theory)，本身是一種一階邏輯理論。這個理論把謂詞符號$A^{2}_{1}(x,y)$簡記成$x\in y$，也就是直觀上的"屬於"。本篇會把$\vdash_{NBG}$簡記為$\vdash$

直觀上把所有變數解釋成類(class)，也就是是一群數學實體的聚集。然後把$x\in y$解釋成$x$是構成$y$的成員(member)或是元素(element)。口語上會稱$x$屬於(belong to)$y$，另外

$(x\not\in y):=\neg(x\in y)$

口語上稱$x$不屬於$y$。

包含

$(x\subseteq y):=\forall z(z\in x\Rightarrow z\in y)$

$(x\not\subset y):=\neg(x\subseteq y)$

$(x\subset y):= (x\neq y\wedge x\subseteq y)$

口語上稱$x \subseteq y$為"$y$包含$x$"( y includes/contains x)，或是說$x$是$y$的子類(subclass)；$x\subset y$口語上稱$x$是$y$的真子類(proper subclass)。

集合

$M(x):=\exists t(x \in t)$ ($t$必須是展開這個符號定義時，首次出現的變數)

$Pr(x):=\neg[M(x)]$

會以M表記來自於德文的集合是die Menge。

直觀上$M(x)$被解釋成"$x$是某個類的成員的話，就是一個集合(Set)"；逆敘述解釋成"$x$是一個真類(proper class)"。

口語上，集合$x$包含於$y$可以另外敘述成"集合$x$是$y$的子集合(subset)"；類似的，集合$x$若是$y$的真子類，可以另外敘述成"$x$是$y$的真子集(proper subset)"。

為了簡化符號，我們對集合論裡的合式公式$\mathcal{B}$作如下約定：

$({\forall}^{M}x)\mathcal{B}:=(\forall x)[M(x)\Rightarrow \mathcal{B}]$

$({\exists}^{M}x)\mathcal{B}:=(\exists y)[M(x)\wedge \mathcal{B}]$

這樣我們不用每次把$M(x)$寫出來。如果上下文很明顯是只針對集合做討論，或是要求為集合的條件對推理沒有影響的話，我們會省略這個$M$上標。

根據量詞表示的簡化，如果只有$x$和$y$在$\mathcal{A}$完全自由(也就是類似一個雙元謂詞符號)，我們還可以進一步的作如下約定：

$[{\forall}^{M}\mathcal{A}(x,\, y)]\mathcal{B}:=(\forall x)\{[M(x)\wedge\mathcal{A}(x,\, y)]\Rightarrow \mathcal{B}\}$

$[{\exists}^{M}\mathcal{A}(x,\, y)]\mathcal{B}:=(\exists x)[M(x)\wedge\mathcal{A}(x,\, y)\wedge\mathcal{B}]$

相等

確認兩個物件是否相等的一套方法，就是確認兩個物件是不是由同一群"組件"所組成的，所以我們約定：

$(x=y) :=[\forall z(z\in x\Leftrightarrow z\in y)]$ ($z$須是展開這個符號定義時，首次出現的變數)

$(x\neq y):= \neg(x=y)$

相等有以下的重要定理，用以簡化引入新的函數符號時所需的唯一性證明：

外延定理(extensional theorem/principle)：

$\vdash (x=y)\Leftrightarrow ({\forall}^{M} z)[(z\in x)\Leftrightarrow(z\in y)]$

證明

($\Rightarrow$)$\forall z(z\in x\Leftrightarrow z\in y)\vdash\forall z\{\exists t(z \in t)\Rightarrow[(z\in x)\Leftrightarrow(z\in y)]\}$ (1)$\forall z(z\in x\Leftrightarrow z\in y)$ (Hyp) (2)$z\in x\Leftrightarrow z\in y$ (MP with 1, A4) (3)$\exists t(z \in t)\Rightarrow[(z\in x)\Leftrightarrow(z\in y)]$ (MP with 2, A1) (4)$\forall z\{\exists t(z \in t)\Rightarrow[(z\in x)\Leftrightarrow(z\in y)]\}$ (GEN with 3) ($\Leftarrow$)$\forall z\{\exists t(z \in t)\Rightarrow[(z\in x)\Leftrightarrow(z\in y)]\}\vdash\forall z(z\in x\Leftrightarrow z\in y)$ (1)$\forall z\{\exists t(z \in t)\Rightarrow[(z\in x)\Leftrightarrow(z\in y)]\}$ (Hyp) (2)$\neg\forall t[\neg(z \in t)]\Rightarrow[(z\in x)\Leftrightarrow(z\in y)]$ (MP with 1, A4) (3)$\neg\forall t[\neg(z \in t)]\Rightarrow\neg\neg[(z\in x)\Leftrightarrow(z\in y)]$ (D1 with 2, DN) (4)$\neg[(z\in x)\Leftrightarrow(z\in y)]\Rightarrow\forall t[\neg(z \in t)]$ (MP with 3, T) (5)$\forall t[\neg(z \in t)]\Rightarrow[\neg(z \in t)]$ (A4) (6)$\neg[(z\in x)\Leftrightarrow(z\in y)]\Rightarrow\neg(z \in t)$ (D1 with 4, 5) (7)$(z \in t)\Rightarrow[(z\in x)\Leftrightarrow(z\in y)]$ (MP with 6, T) (8)$\forall t\{(z \in t)\Rightarrow[(z\in x)\Leftrightarrow(z\in y)]\}$ (GEN with 7) (9)$(z \in x)\Rightarrow[(z\in x)\Leftrightarrow(z\in y)]$ (MP with 8, A4) (10)$(z \in y)\Rightarrow[(z\in x)\Leftrightarrow(z\in y)]$ (MP with 8, A4) (11)$(z \in x)\Rightarrow[(z\in x)\Rightarrow(z\in y)]$ (D1 with 9, $\mathcal{A}\wedge\mathcal{B}\vdash\mathcal{A}$) (12)$(z \in y)\Rightarrow[(z\in y)\Rightarrow(z\in x)]$ (D1 with 10, $\mathcal{A}\wedge\mathcal{B}\vdash\mathcal{B}$) (13)$(z\in x)\Rightarrow(z\in y)$ (MP with 11, A2) (14)$(z\in y)\Rightarrow(z\in x)$ (MP with 12, A2) (15)$(z\in x)\Leftrightarrow(z\in y)$ ($\mathcal{A},\mathcal{B}\vdash\mathcal{A}\wedge\mathcal{B}$) (16)$\forall z(z\in x\Leftrightarrow z\in y)$ (GEN with 15)

此定理的直觀意義，就是兩個類相等當且僅僅當它們有一樣的集合作為它們的成員。

從屬公理

$(T)$ $(x=y)\Rightarrow[(x\in z)\Leftrightarrow(y\in z)]$

這個類的公理保證相等的集合會屬於同個類。(T取自子集合的德文Teilmenge)

元定理：

NGB集合論是帶等號的一階邏輯。

證明提示：

對於(E2)，考慮到不含函數符號的原子公式只有$t\in x$和$x\in t$兩種，然後注意到從屬公理本身就是(E2)的等價條件針對$x\in t$的情況，$t\in x$的狀況只要對等號的定義套用(A4)即可。

空集合公理

$(N)$ $({\exists}^{M} x)({\forall}^{M} y)(y\not\in x)$

此公理配上外延定理容易證明

$(\exists! n)[M(n)\wedge({\forall}^{M} y)(y\not\in n)]$

所以根據函數符號與唯一性，可以引入新的常數符號$\varnothing$和新公理

$M(\varnothing)\wedge({\forall}^{M} y)(y\not\in \varnothing)$

口語上稱$\varnothing$為空集合(empty set)。

配對公理

$(P)$ $({\forall}^{M} x)({\forall}^{M} y)({\exists}^{M} p)({\forall}^{M} z)[(z\in p)\Leftrightarrow (z=x\vee z=y)]$

也就是對所有的集合$x$跟$y$有一個集合$p$，只擁有$x$跟$y$兩個當元素。而由外延定理我們可以證明：

$M(x)\wedge M(y)\vdash(\exists! p)\{M(p)\wedge({\forall}^{M}z)[(z\in p)\Leftrightarrow(z=x\vee z=y)]\}$

根據這個定理，(對變數$x$和$y$)可以定義一個新的雙元函數符號$\{x,\,y\}$，並增加如下的公理

$\{[\neg M(x)\vee\neg M(y)]\wedge(\{x,\,y\}=\varnothing)\}\vee\{M(x)\wedge M(y)\wedge({\forall}^{M} z)[(z\in \{x,\,y\})\Leftrightarrow (z=x\vee z=y)]\}$

方便起見，$\{x,\,x\}$簡記為$\{x\}$

$(x,\,y):=\{\{x\},\,\{x,y\}\}$

稱為有序對(ordered pair)

n元有序對

$(x):= x$

$(x_1,\,x_2,\,....,\,x_n,\,x_{n+1}):=((x_1,\,x_2,\,....,\,x_n),\,x_{n+1})$

類的存在公理

$(b1)$ $\exists r({\forall}^{M} a)({\forall}^{M} b)\{[(a,b)\in r]\Leftrightarrow (a\in b)\}$(集合的屬於關係)

$(b2)$ $\forall x\forall y\exists i({\forall}^{M} a)\{(a\in i)\Leftrightarrow[(a\in x)\wedge(a\in y)]\}$(類的交集)

$(b3)$ $\forall x\exists c({\forall}^{M} a)[(a\in c)\Leftrightarrow(a\not\in x)]$(類的"補集")

$(b4)$ $\forall x\exists d({\forall}^{M} a)\{(a\in d)\Leftrightarrow\exists b[(a,b)\in x)]\}$(關係的"定義域")

$(b5)$ $\forall x\exists z({\forall}^{M} a)({\forall}^{M} b)\{[(a,b)\in z]\Leftrightarrow(a\in x)\}$

$(b6)$ $\forall x\exists v({\forall}^{M} a)({\forall}^{M} b)({\forall}^{M} c)\{[(a,b,c)\in v]\Leftrightarrow[(b,c,a)\in x]\}$(三元關係的"偶重排")

$(b7)$ $\forall x\exists w({\forall}^{M} a)({\forall}^{M} b)({\forall}^{M} c\{[(a,b,c)\in w]\Leftrightarrow[(a,c,b)\in x]\}$(三元關係的"奇重排")

補類

由$(b3)$和外延定理，(對變數$x$)我們可以增加新的單元函數符號$x^c$和公理

$({\forall}^{M} a)[(a\in x^c)\Leftrightarrow(a\not\in x)]$

口語上稱$x^c$為類$x$的補類(complement of class)。特別注意到${\varnothing}^c$是包含所有東西的類，特稱為宇類(universal class)。易知$\vdash Pr({\varnothing}^c)$，也就是直觀來講，無所不包的實體不被視為一個集合。

類的存在元定理

如果合式公式$\mathcal{C}$內所有的量詞可以縮寫成${\forall}^{M}$或是${\exists}^{M}$的形式，稱$\mathcal{C}$為敘述性的(predicative)

元定理：(metatheorem of class existence, 類的存在元定理)

$\mathcal{C}$是一段敘述性的$wf$，全部的變數有$x_1,\,x_2,\,....,\,x_n,\,y_1,\,y_2,\,....,\,y_m$。則

$\vdash\exists a({\forall}^{M} x_1)({\forall}^{M} x_2)....({\forall}^{M} x_n)\{[(x_1,x_2,....,x_n)\in a]\Leftrightarrow\mathcal{C}\}$

證明

雖然這個元定理和七條類存在公理是等價的，但NGB集合論最大的賣點就是有限條的公理，所以與其把類的存在元定理轉為公理模式，不如採用七條類存在公理。

關係

日常生活中所稱的關係，都代表兩個人兩件事的關聯。但如果列舉什麼東西或人被關聯在一起，跟說清楚怎麼樣有關聯是一樣的。

$({\exists}^{M} a)({\exists}^{M} b)[p=(a,\,b)\wedge(a\in A)\wedge(b\in B)]$

顯然是敘述性的，所以由類的存在元定理和外延定理，(對變數$x$和$y$)可以定義一個新的雙元函數符號$x\times y$和公理：

$({\forall}^{M} p)\{(p\in x\times y)\Leftrightarrow({\exists}^{M} a)({\exists}^{M} b)[p=(a,\,b)\wedge(x\in A)\wedge(y\in B)]\}$

口語稱為類$x$和類$y$的笛卡爾積(Cartesian product)，所謂$\displaystyle A$裡的元素和$\displaystyle B$裡元素的關係(relation)，就是某個$R \subseteq A \times B$的集合。$(a,b) \in R$習慣上會以$\displaystyle aRb$表示。

函數

一個函數($f:A\rightarrow B$)事實上可以被當成一種關係($F \subseteq A \times B$)滿足:

   $ (\forall a \in A\,\exists! b \in B) ( aFb )$

注意到$\displaystyle bFa$不一定成立，這跟相等的$\displaystyle a=b \Rightarrow b=a$是不同的。

等價關係

如果$\displaystyle A = B$，笛卡爾積$A \times B = A \times A$會簡寫成$\displaystyle A^2$的符號。事實上相等($= \subseteq A^2$)就是

$ \{(a,a)|\, a \in A\}$

這樣的關係，但是我們直觀上還知道相等有些很熟悉的性質:

   (1)$\displaystyle a=a$
   
   (2)$\displaystyle a=b \Rightarrow b=a$
   
   (3)$a=b \wedge b=c \Rightarrow a=c$

而數學上，如果一個關係$\displaystyle \sim \subseteq X^2$滿足:($\forall a,b,c \in X$)

   (1)自反性(reflexivity): $\displaystyle a\sim a$
   
   (2)對稱性(symmetric property): $\displaystyle a\sim b \Rightarrow b\sim a$
   
   (3)遞移性(transitivity): $a\sim b \wedge b\sim c \Rightarrow a\sim c$

稱$\displaystyle \sim$為$\displaystyle X$上的一個等價關係(equivalence relation)。

商集合

$\displaystyle \sim$是$\displaystyle X$上的一個等價關係，$x \in X$則

   $[x]_{\sim} := \{y \in X|\, x\sim y \}$

稱$\displaystyle x$的等價類(equivalence class)，

從等價類的定義我們很容易發現

$a\notin [b]_{\sim}\Rightarrow [a]_{\sim}\cap[b]_{\sim}=\varnothing$

也就是等價類是被等價關係區分的清楚的，要嘛相等要嘛不相等的個體。

進一步的，我們可以定義

   $X/\sim := \{[x]_{\sim}|x \in X\,\}$

稱為$\displaystyle x$除上$\displaystyle \sim$的商集合(quotient space)

集合的公理

類的存在性公理對於集合的應用是遠遠不夠的，需要額外的公理。

聯集公理

$\displaystyle(U)$ $\forall f\exists s\forall a\{(a\in s)\Leftrightarrow\exists x[(a\in x)\wedge(x\in f)]\}$

直觀來說，公理的變數$\displaystyle f$代表的是"一群"集合$\displaystyle x$。根據外延原理，上面所敘述的$s$對每個$f$都是唯一存在的，我們把稱它為$f$的聯集(Union set)並表記為

$\displaystyle s = \bigcup f$

或是

$\displaystyle s = \bigcup_{x\in f} x$

冪集公理

$\displaystyle (W)$ $\forall x\exists w\forall y[(y\in w)\Leftrightarrow(y\subseteq x)]$

公理所述的$w$，直觀上來講就是所有$x$的子集合所構成的集合。我們稱為$x$的冪集(power set)，以$\mathcal{P}(x)$或是$2^x$表示。

子集公理

$(S)$$\forall x\exists s\forall Y\forall a\{(a\in s)\Leftrightarrow[(a\in x)\wedge(a \in Y)]\}$

有了這個公理，就可以證明

計數

有限

   $Fin(X):=(\exists \alpha)[(\alpha\in\omega)\wedge(X\cong\alpha)]$

$f:\omega\times\omega\to\omega:f(n,m)=2^{n}3^{m}$

可數集合的子集合也是可數，所以$\omega\times\omega$可數

   定理：
   
   $(\mathcal{A}\cong\omega)\wedge\{\forall A[(A\in\mathcal{A})\Rightarrow(A\cong\omega)]\}\vdash (\bigcup\mathcal{A}\cong\omega)$

   證明:
   
   將假設所列的雙射表示如下
   
   $F:\omega\to\mathcal{A}$是雙射。
   
   ($\displaystyle F(k)$記為$\displaystyle A_k$)
   
   $\forall k\in\omega$，設$f_k:\omega\to A_k$是雙射。
   
   先假設$\forall\alpha\forall\beta\{[(\alpha,\beta\in\omega)\wedge(\alpha\neq\beta)]\Rightarrow(A_{\alpha}\cap A_{\beta} =\varnothing)\}$則我們取
   
   $g:\bigcup_{k\in\omega}A_k\to\omega\times\omega:g[f_k(n)]=(k,n)$
   
   兩集合的聯集可以拆成三個不相交的部分，故定理得證。$\Box$

選擇公理

use MathJax