用户: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