集合论

前言

本文是复旦大学出版社《集合论: 对无穷概念的探索》的笔记.

ZFC公理体系

存在公理(Exi)

也即:这里总存在着一个集合.在最早的ZFC公理体系中,这条公理也被定义成:空集是存在的.然而空集定理要比这条更强一些,我们会在后面证明空集的存在性.

外延公理(Ext)

也即:两个有相同元素的集合相等.如果补充的定义,这里也可以写作:

分离公理模式(Sep)

令为条件,则: 也即:我们可以将一个集合中满足条件的元素取出组合成一个新的集合.分离公理有的时候又被叫做概括公理或者子集公理.

分离公理是对概括原则(即:对于任意条件,概括原则试图定义集合)的限制.由分离公理模式以罗素悖论可以立刻导出不存在"所有集合组成的集合".

现在我们试图用分离公理模式来定义空集,一个较为显然的办法是考虑定义,可正如我们刚刚所说的,这种集合并不合法:我们总需要指定一个才能定义,如若在这里指定一个就会有非典范的争议(虽然我们的确可以用存在公理声明存在这样的集合).因此不妨采取以下策略:

考虑如果,则可以自然定义为,此时可见这个集合并不依赖于:事实上如若有则.而总是真的,又根据存在公理,至少存在这样一个,而对于所有的,定义出来的都是同一集合,这就搞定了.

从上面的讨论也可以见到:是一个集合当且仅当.不然,我们将成为一个类.当然所有的集合都是类,而类不一定是集合,并非集合的类被称作真类.

今后用到的不加说明均表示集合,有些特殊的类会用黑体大写字母表示,例如所有集合组成的类记作,将罗素类记作.

分离公理可以定义集合的交和差,不必过多赘述.值得一提的是集合内所有元素(也是集合)的交,被定义为任意交:对任意集合,也是集合,这里要求的原因当然是我们定义需要.

配对公理(Pai)

即:对任意存在一个集合只以为元素.配对公理的显然推论是单点集是集合.

并集公理(Uni)

也即:对任意集合,可以将它的所有元素(当然也是集合了)全都并起来,根据外延公理,这样的是唯一的,称作的并,记作.特别地定义.

幂集公理(Pow)

也就是一个集合的所有子集可以组成一个新的集合,称作的幂集,记作,也有记作的.

无穷公理(Inf)

对任意集合,我们将集合称作的后继,一般记作,则: 或言之我们承认下述元素可以在一起组成一个集合: 无穷公理彻底保证了我们可以制造出无穷集合(或言:),但初看的疑问一定是为何不直接定义以下元素组成的集合存在: 首要的原因就是这样做无法递归,你怎么在最后声明"嵌套若干次集合"这个操作.另一个原因是序关系的定义对后继定义有很大的依赖性,我们将在后面讲到.

替换公理模式(Rep)

给定公式,并且对任意,都有唯一的使得成立(注意其实这里并不一定是函数),则: 也即:任何集合在一个formula下的像仍然是一个集合.

替换公理模式极其地强,我们后面会再讨论这个问题.

正则公理(Fnd)

这一则公理的形式与上面的构造性或存在性公理不同,它给予了集合一种更好的性质,并以此断定某些东西并不是集合.有的时候也称其为基础公理.它实际上断言的是上总有一个以关系限制住的"极小元",也就是说,里再没有其它元素属于了.

正则公理的一则推论是任意集合都不属于自身.考虑反证:假设有一个集合,取,则正则公理施加在上必然导出,然而,这就矛盾了.

正则公理的另一则推论是不存在无穷下降链,其中.证明非常简单,因为这里面压根不存在极小元.

然而,不存在无穷下降链并不意味着不存在无穷上升链.只需看即可发现一个显然的无穷上升链.笔者认为可以理解为:如果是集合,总可以通过之前的公理在有限次"拆包"后判定是集合.因此正则公理实际上是一个对于判定性的公理.

选择公理(AC)

也即:对于任意集合,如果它满足:

1. .
2. 中的元素两两不交.

则存在集合(当然未必唯一),对任意,是单点集合.换言之:可以从一个集合内的每个元素(当然也作为一个集合)中取出一个代表元.

选择公理极其吊诡的地方恰在于其构造集合的方式不是唯一的,也未必存在典范的构造方式.

集合的简单运算

定义和的对称差为.

对任意集合,除去常见结合律与交换律,有:

1. 分配律:.
2. 分配律:.
3. 德摩根律:.
4. 德摩根律:.

关系

ZFC公理体系已然奠定了现代数学的地基,因此相当一部分数学家相信任何数学理论都在某种意义上是关于集合的理论,并着手重建有关数学的一切.

有序对

二元关系的要素是成对出现的有顺序的对象,或称有序对,定义为,可以由配对公理得知这仍然是一个集合.容易用外延公理得到.

笛卡尔积

令为集合,定义其笛卡尔积为.验证笛卡尔积的结果是集合的策略也比较简单,例如可以先用替换公里模式拿到和,并起来之后用幂集公理和分离公理.总之都是抽象废话,不再赘述了.

容易推广到个集合的笛卡尔积

二元关系

定义一个集合称作二元关系,如果存在集合.用表示,称和有关系,有时也习惯性写作.

引入以下定义:

1. 的定义域定义为.
2. 的值域定义为.
3. 如果,则称是上的二元关系.
4. 集合在下的像定义为:.
5. 集合在下的逆像定义为:.
6. 的逆定义为.
7. 二元关系和的复合定义为.

用分离公理模式得知和当然都是集合.

函数关系

函数是一种特殊的二元关系.如果二元关系满足: 则称是一个函数,其中称作在处的值,记作或者.如果,则称是从到的函数,记作.显然任何集合都有到自身的函数等同函数.

函数的外延性从而自然被外延公理导出,也即当且仅当.引出以下定义:

1. 单射:,如果,则.
2. 满射:.
3. 双射:既是单射,又是满射.

设,那么:

1. 如果,称是的一个左逆,不难发现存在左逆当且仅当是单射(依靠定义).

2. 如果,称是的一个右逆,不难发现存在右逆当且仅当是满射(需要选择公理).

3. 如果既是的左逆又是的右逆,则称为的逆,不难发现存在逆当且仅当是双射,并且逆唯一.

还有以下定义:

1. 对任意函数和集合,是一个函数,称为在上的限制.
2. 如果,则称是的扩张.
3. 定义函数是相容的,如果.容易证明此时是函数.
4. 函数的集合称为相容的系统,如果其中任何两个函数都是相容的.容易证明此时也是函数.
5. 令都是集合,则到的所有函数组成的集合定义为.容易检验这也是个集合(幂集打开再筛掉就行)
6. 此外,由柯里化过程,容易发现.

等价关系

令为二元关系,若有以下性质:

1. 自反性:.
2. 对称性:.
3. 传递性:.

则称其是一个等价关系,习惯上用表示.此时对每一,与等价的元素构成了的一个子集,这些子集把分成互不相交的若干部分,一般将关于的等价类记作,或者简写为.等价类显然是集合.容易证明.

接下来定义商集为.

对于一个集合,,如果满足:

1. .
2. .

则称是的划分.显然商集是一个划分.反之由划分也可以确定一个等价关系.

序关系

对于是二元关系,如果其满足:

1. 自反性.
2. 反对称性:.
3. 传递性.

就称其是上的偏序关系,一般干脆记作,若同时无法取等则自然地记作.此时称为偏序集.如果它还满足:

4. 连接性:对所有的.

则称是上的全序关系.此时称为全序集.

再引入以下定义:

1. 如果,,都不大于,或者说,则称为的极小元.同理可以定义极大元.
2. 如果,,都小于,或者说,则称是的最小元.同理可以定义最大元.
3. 如果.称为在中的上界.如果在中的所有上界的集合由最小元则称其为上确界.记作.同理定义下界和下确界.

容易见到以下性质:

1. 全序集中极小元等价于最小元,极大元等价于最大元.
2. 偏序集如果有最大或最小元,则它们是唯一的.
3. 集合的上确界如果存在,它可能不属于;如果它属于,则一定是的最大元.

实数的构造

自然数

早在无穷公里处我们就定义了自然数,策略是: 如果一个集合满足则称其为归纳集(从而无穷公理等价于:存在一个归纳集),容易见到用自然数表示的元素在所有归纳集中都会出现,因此自然数是最小的归纳集,有人会如此定义:.这里可以看到一个很好的性质就是,我们可以认为.

如果是自然数的某个子集,并且是归纳集而且,立刻就可以见到.这就是所谓归纳原理或者数学归纳,意为: 容易见到上的另一个好性质是,因此干脆将作为一种序关系,对于自然数,立刻见到:

1. .
2. .
3. .
4. .

可以见到这是一个全序关系.不妨定义为.既然是良序,还可以拿出第二归纳原理:如果都有可以推出,并且,则对所有的成立.

递归定理

对任意集合,,以及任意函数,存在唯一的函数满足:

1. .
2. .

为证明此,先引入定义序列是以自然数(如果你稍加思考会意识到,这里的实际上是组成的集合)或自然数集合(其实就是无穷对吧)为定义域的函数.如果定义域是则称其为长度为的有穷序列.特别地定义域为的序列为空序列,而定义域为的序列称为无穷序列.

从而我们可以自然地定义一个由集合中的元素组成的长度为的序列是一个由到的函数(再次强调这里的是一个集合),注意到所有这样的序列组成的集合是.

现在我们着手证明递归定理.

先证明存在性.处理无穷的强大武器其实是并集公理.考虑取序列,如果而对所有的,则称是基于的近似.接下来取所有的近似组成集合,令.

接下来应当证明以下事实:

1. 是函数.
2. .
3. .
4. .

为证明(1),只需证明是相容的函数系统即可.也就是,不妨假设,现在我们需要证明.

首先显然,从定义得知如果可以得知,归纳就证明成功了.

为证明(2),首先显然,只需证明即可.为证明此,需要证明,都存在一个近似.首先存在近似,此后只需数学归纳和并集原理就可以得到总存在近似,这就搞定了.

其次要证明.这个是显然的.

(3)也是数学归纳,不必赘述.

于是我们搞定了存在性,接下来只需要简述唯一性即可.如果还存在另一个也满足条件,只需归纳法可以证明二者相等.

只需柯里化就可以拿到带参数的版本:

令和为函数,存在唯一的函数满足:

1. .
2. .

原因自然是考虑,因此拿到了和唯一的函数即可.不必过多赘述.

递归定理可以自然地定义自然数上的加法和乘法.

等势

如果存在一个以集合为定义域,集合为值域的双射,就称集合和是等势的,记作.如果存在集合到的单射,就称的势小于等于的势,记作.既然用此符号,重要的问题在于符号是否是一个序关系,其判定中最重要的问题由下述定理给出:

Cantor-Bernstein定理

如果,则.

不妨设两个单射我们考虑一个感性的做法:考虑将这个东西画成二分图,然后要找它的完美匹配.我们不妨先把不同的连通块拆开,你会发现大部分的图都可以用来构造双射,只有一种除外:那就是以一个中节点开始不断延伸的无限的,我们在这里使用来构造即可.

如果要把上面的东西写成形式化的东西,我们可以这么写:取,,那么对于,使用构造双射,剩下的使用构造双射.

容易证明Cantor-Bernstein定理与以下定理等价:

夹逼定理

考虑Cantor-Bernstein定理应该与夹逼定理等价,必要性显然,充分性的话考虑单射,则显然有从而导出.然而单射显然有.这样就可以证明Cantor-Bernstein定理.

证明大同小异,目的是找出以中元素起点的无穷链,并将剩下的部分直接建立对应.

考虑令为双射.直接取,最后取.立刻见到.

下面构造双射: 由于这两部分互不干扰,因此显然是单射.接下来需要证明其满性,由于,从而,因而考虑: 这就搞定了.

幂集的大小

求证:.

首先容易证明,现在要证明它们的确不相同.考虑罗素悖论,假设存在一个双射,取出,然后看其原像.此时,如果,则其应该满足;反之,如果,则它又该满足,从而导出矛盾.

有穷与无穷

根据上述讨论,我们可以将自然地记作.

引入以下定义:

1. 若,就称为有穷的.
2. 若,就称为无穷的.
3. 若,就称是可数的或者可数无穷的.

见到以下结论:

1. 鸽笼原理:若,则不存在到它的真子集上的双射.从而导出如果,则.从而导出对任意有穷集合,不存在到的真子集的双射.
2. 每一无穷集合都有一个可数子集.
3. 两个可数集合的并是可数集合.
4. 作为(3)的推论,有穷个可数集合的并是可数的.
5. 作为(4)的强化,可数个可数集合的并是可数的.
6. 如果是可数的,则是可数的.
7. 作为(6)的强化,可数个可数集合的笛卡尔积是可数的.
8. 作为(7)的推论,是可数的.
9. 作为(8)的推论如果是可数的,则其有穷子集组成的集合是可数的.

从(1)开始,反证法自然是好做的.

(2)是选择公理的推论,只需递归使用选择函数每次从之前的集合中删掉已经取出的代表元的并取出新的代表元即可.

(3)(4)(5)(6)(7)(8)(9)都是对角线证明法,不必赘述(顺便一提这里还有另一种方法,就是考虑用来表示有序对).

如果避开将自然数引入势的定义,先承认选择公理,则也可以途径下述方法,我们声称以下命题等价:

1. 集合是有穷的.
2. 存在上的全序满足的每一非空子集在下有最大元和最小元.
3. 的每一非空子集族都有关系下的极大元.
4. 是戴德金有穷的:不存在到其真子集的一一映射.

(1)推(2)是显然的,因为只需规定其对集合的映射作为全序关系即可,可以轻松得出其子集的最大元(射出的自然数的并)和最小元(射出的自然数的交).

事实上有穷集合的任意全序关系下,任意非空子集都有最大元和最小元.方法是逐个比较过去找就可以了.

(2)推(1)的话考虑有最小元,有最小元,以此类推.不断做此操作,做到第步的时候,我们已经取出了.如果这个操作无法在有限步内结束,意味着子集不存在最大元,这样就矛盾了.

(1)推(3)

我们还想证明下面两条结论(承认选择公理):

1. 任何两个集合,总有.
2. 任何无穷集合,总有.