笔记与习题：《集合论：对无穷概念的探索》（1）
第一章 集合与公理
1.1 罗素悖论
悖论出现的根源：康托最初是在*素朴*的意义上理解集合的。根据康托的理解可定义一个“概括规则”：对任何性质$\psi$，存在集合$X=\{x|\psi(x)\}$，X恰好含有所有具有性质$\psi$的对象。
罗素悖论：令$\varphi$为性质“不属于自己的集合”，即$\varphi$=“x是集合并且x$\notin$ x”，则根据“概括规则”，存在以下集合：$R=\{x|\varphi(x)\}。$
那么R属不属于R呢？如果R属于R，根据R的定义，R具有性质$\varphi$，但是性质$\varphi$恰恰是“不属于自己”，所以R不属于R；如果R不属于R，则R是不属于自己的集合，所以有性质$\varphi$，所以R属于R。
1.2 一点数理逻辑
通过建立集合论的公理化系统可以解决罗素悖论，为了理解公理化系统的建立过程，先巩固一些数理逻辑的概念。
推演：公式集到公式，记作$\Sigma\vdash\varphi$
证明：语句集到语句
理论：一个对证明封闭的语句集（语句只有在T的范围内才能得到证明）
公理：一个理论的子集，该子集可以推演出该理论的一切语句
递归（可判定，可计算）、可公理化：在一个理论中，任给一个语句，可以在有穷步内用完全机械的方法判断它是否属于公理，就称该理论的公理集是递归的，该理论是可公理化的
以上这些概念源自自然数，它们能沿用到此处，是因为公式和语句，乃至证明都可看作自然数（就像哥德尔配数那样）
“半递归”、递归可枚举：如果$\sigma\in T$，我们可以在有穷步内知道这一点，但如果$\sigma\notin T$，我们却可能无法在有穷步内得到结论
一致：一个理论是一致的当且仅当没有语句会使得从理论中能同时得到对该语句与该语句的非的证明
1.3 公理
0.存在公理：本体论的承诺——我们谈论的世界不是虚无的
1.外延公理：两个有相同元素的集合相等——集合是由其元素决定的
以上为唯一性公理，保证了下一组公理里断言存在的集合的唯一性
2.分离公理模式（概括公理、子集公理）：给（像上文所述的）“概括规则”一个限制，使集合不能通过“概括规则”独立定义，而是必须从已经存在的集合中被分离出来。（从而排除”所有集合的集合“这种概念）
定义1：$\{x|x \ne x\}$是集合，并且根据外延公理，它是唯一的，称为空集，记作$\emptyset$
练习：证明集合$\{x|x\ne x\}$是唯一的
假设存在两个集合$A$与$B$满足$\{x|x\ne x\}$
则由外延公理：$\forall x(x\in A \leftrightarrow x\in B)\leftrightarrow A=B$
$\forall x(x\in A\leftrightarrow x\in B)$因为没有$x$来导致矛盾，所以是真命题
所以$A=B$
与“存在两个集合”的假设不符，所以集合$\{x|x\ne x\}$是唯一的
定义2：令$\varphi(u)$为一个性质，则依据上面的分析$\{u| \varphi(u) \}$不一定是集合，这样的对象称之为类，特别地，不是集合的类称为真类
每个集合都是类，有些类不是集合
定义3：由分离公理，可以断定任意两个集合的交和差仍然是集合，分别定义如下：$X\cap Y=\{u|u\in X \wedge u\in Y\}$，$X- Y=\{u|u\in X \wedge u\notin Y\}$，对于任意不为空集的集合，它的任意交：$\bigcap X=\{u|\forall Y(Y\in X\rightarrow u\in Y)\}$也是集合
练习：想一想如果$X=\emptyset$会有什么问题
当X为空集时，$u\in X$恒为假，所以$X\cap Y=\emptyset$,$X-Y=\emptyset$
3.对集公理：对任意a和b，存在一个集合只以a和b为元素
4.并集公理：产生并集的概念
定义1：对于这样的$Y$，称它为$X$的并，记为$\bigcup X$。定义$X \cup Y=\bigcup \{X,Y\}$
定义2：子集——$X$的元素都是$Y$的元素——$X\subseteq Y$
真子集——$X\subseteq Y$并且$X\ne Y$——$X\subset Y$
练习：证明对任意集合X，$\emptyset \subseteq X$
由子集的定义：$X\subseteq Y \Leftrightarrow \forall x \in A,x \in B$
对于空集与任意集合X，$\forall x\in \emptyset$，$x\in X$成立，这是因为$\forall x\in \emptyset$恒假，根据逻辑公理，假命题蕴含任何命题，所以$\forall x\in \emptyset$，$x\in X$为真命题
所以对任意集合X，$\emptyset \subseteq X$
即X是任意集合的子集
5.幂集公理：以一种更快的速度产生新集合
这种集合Y称为X的幂集，记作$\mathcal{P}(X)$
插曲：我们现在已经可以用空集定义$\emptyset$，$\{\emptyset\}$，$\{ \emptyset \{\emptyset\}\}$……，记为0，1，2……（自然数），那自然数集怎么定义？
定义：对任何集合$x$，集合$x\cup\{x\}$称为$x$的后继，记为$S(x)$或者$x^+$
6.无穷公理：肯定无穷集合存在
7.基础公理（正则公理）：集合的元素都具有最小性质，排除了所有的“非基础集”，也就是“深不见底”的“集合”
定理：任何集合x都不属于自身
练习：证明不存在集合$\{x_0,x_1,\dots,x_n,x_{n+1},\dots\}$其中对任意$n$，$x_{n+1}\in x_n$。这样的集合称为无穷下降链，基础公理确保不存在无穷下降链
假设存在集合$X=\{x_0,x_1,\dots,x_n,x_{n+1},\dots\}$对任意$n$，$x_{n+1}\in x_n$
由基础公理，应当存在元素$y$，使$y\in X$且 $X\cap y=\emptyset$
由于$X$中的元素都是$x_i$的形式，设$y=x_t$，由条件可知，对任意$t$，都有$x_{t+1}\in x_t$
所以$X\cap y=\emptyset$，即$X\cap x_t=\emptyset$的条件不可能满足
所以假设违背基础公理，原命题得证
定义：$\exists !x\psi(x)$表示$\exists x \psi(x)\wedge \forall x\forall y(\psi (x)\wedge\psi(y)\rightarrow x=y)$（只是一个记法，为替换公理做准备的）
即：$\exists !x\psi(x)$表示有唯一的x具有性质$\psi$
8.替换公理模式：由映射关系建立集合——任何集合在一个函数下的像仍然是一个集合
练习：证明$\{\{0\},\{1\},\{2\},\dots\}$是集合
由存在公理、分离公理、对集公理、无穷公理易得$\{0,1,2\dots\}$是集合
构建公式$\psi(x,y):y=\{x\}$
对于任意的x，都有唯一的y使之成立
由替换公理得知，存在集合$B=\{\{0\},\{1\},\{2\},\dots\}$
所以$\{\{0\},\{1\},\{2\},\dots\}$是集合
9.选择公理：承认形式系统中某种无限次操作的合理性，进而断言某种“不可构造的存在”的合法性，但也否定了所有的“非良序集”
$ZF$：0-8组成
$ZFC$：0-9组成
习题
好多题，懒得都做，就选了后面几题做
1、如果$X$是集合。定义$-X=\{x|x\notin X\}$，证明$-X$不是集合。
假设$-X$是集合
由并集公理可得$X\cup-X$是“所有集合的集合”
由于康托悖论和罗素悖论，不存在这样的“大全集”
所以$-X$不是集合
2、证明对任意集合$X$，$\mathcal{P}(X)\subseteq X$不成立。
方法1：
若$\exists X$，使$\mathcal{P}(X)\subseteq X$
由幂集公理：$\forall X\exists Y\forall u(u\in Y \leftrightarrow u\subseteq X),Y=\mathcal{P}(X)$
则$\mathcal{P}(X)\in \mathcal{P}(X)$
再由基础公理：$\exists y(y\in \mathcal{P}(X)\wedge \mathcal{P}(X) \cap y=\emptyset)$
这样的$y$明显不存在，假设不成立
所以原命题得证
方法2：
对于$f:X→P(X)$
利用分离公理，构造$Y=\{u\in X|u\notin f(u)\}$
由幂集公理，显然$Y\in\mathcal{P}(X)$
但是$Y\notin X$（类罗素悖论）
这意味着对于任何一个集合$X$，只要是$X$一个集合，就总有一个集合$Y$不属于$X$，且这个集合$Y$属于$X$的幂集
所以$\mathcal{P}(X)\subseteq X$不成立
3、对集公理、并集公理和幂集公理都可替换为较弱的形式：
对任意$a$和$b$，存在一个集合$Y$满足$a\in Y$并且$b\in Y$。（弱对集公理）
对任意集合$X$，存在集合$Y$满足如果存在$z\in X$使得$u\in z$，则$u\in Y$。（弱并集公理）
对任意集合$X$，存在集合$Y$满足如果$u\subseteq X$，则$u\in Y$。（弱幂集公理）
用以上弱形式的公理证明对集、并集和幂集公理。
①证明对集公理
由弱对集公理：$\exists C(A\in C\wedge B\in C)$
构造$\varphi(x)$为“$x = A \vee x = B $”
由分离公理：$y \in C^{*} \leftrightarrow y \in C \wedge \varphi(y)$
所以，存在一个集合$C^{*}$，其元素正好是集合$A$和$B$
②证明并集公理
由弱并集公理：$\forall S\exists U (x \in A \wedge A \in S \rightarrow x \in U)$
构造$\varphi(x)$为“$\, \exists A(A\in S\wedge x\in A)$”
由分离公理：$y \in \cup S \leftrightarrow y\in U \wedge \varphi(y) $
所以，存在一个集合$U$，其元素正好是$S$的元素的元素。
③证明幂集公理
由弱幂集公理：$\forall X\exists Y (u\subseteq X \rightarrow u\in Y)$
构造$\varphi(x)$为“$u\in Y \rightarrow u\subseteq X$”
由分离公理：$y \in Y^* \leftrightarrow y\in Y \wedge\varphi(y)$
所以，存在一个集合$Y^*$，其元素正好为$X$的所有子集
弱公理都提供一个集合，其中包含想要的元素和一些垃圾，分离公理可以扫清垃圾以产生一个包含所有想要的元素的子集。反正就是这个思路，构造出的那个用于约束的公式对不对我就不知道了XD
