集合与图论学习笔记03

定义

定义 3.1 函数

设和是两个任意集合，是从到的二元关系。若具有如下性质：

(1)的定义域;

(2) 如果，则。

则称关系是从到的函数，记为；并称为的象，为的原象，记为。的值域记为。也可以称是从到的映射

定义 3.2 象与原象

设，，

定义，称为在下的象

，称为在下的原象

定义 3.3 满射单射与双射

(1) 设函数，若，则称为满射
(2) 设函数，若，有，则称为单射（或内射）
(3) 设函数，若既是满射，又是单射，则称为双射（一一对应）

定义 3.4 函数相等

设函数，，若对于任意的，有，则称和相等，记为

定义 3.5 逆函数

设函数是双射，的逆关系称为的逆函数，记为。若，则

函数的逆关系不一定是函数

下面证明，如果是到的双射，它的逆函数也是双射

证明： 点击查看证明

先证明是到的函数

是一个满射，故则

设

则，由于为单射，，则是函数

再证明是双射

首先证明是满射，即证明对任意，存在，使得

设，

对于每一个，必定存在，使

从而对每一个，都有，即

所以是满射

再证明是单射，即证明对于任意的

当时，。若，，则，

又因为是函数，所以

所以是单射

显然

定义 3.6 复合函数

设函数，，称复合关系为从到的复合函数，记为，且，有

注意复合函数与复合关系的记法不同，复合函数采用函数习惯记法，要将变元放在函数记号的右侧，即。所以用记号，而不用

我们证明复合关系是函数即

，，则从到的复合关系是从到的函数

证明： 点击查看证明

首先要证明在中的任一元素，都有中的元素与之对应

，，使得

对于，，使得

有复合关系定义

然后再证明对中的每个元素，都只对应中的一个元素

，若有，使得，

根据复合关系定义，，使得，

，使得，

，，，并且是函数，则

由于，，，而是函数，所以

所以从到的复合关系是函数

容易知道

定义 3.7 恒等函数

设函数，若对所有的，成立，则称为上的恒等函数，记为

容易知道

定义 3.8 等势与基数

是任意两个集合，若存在一个双射，则称和对等（或等势），记为，或称和的基数相同

的基数记为，或者，和的基数相同记为或者

定义 3.9 有限集和无限集

设为一个集合，若为空集或与集合的基数相同，则称为有限集，且

若集合不是有限集，则称为无限集

无限集必和它的一个真子集对等

证明： 点击查看证明

设无限集，取出一列元素

定义的真子集

定义单射$f(x)=\left{\right. $

如此可得与等势

凡不能与自身的任一真子集对等的集合为有限集

定义3.10 可列集

若存在从到的双射，则称为可列无限集，简称可列集或可数集。

个集合是可列集的充要条件是它的元素可以排成一个无穷序列的形式

任何一个无限集必含有一个可列子集

证明： 点击查看证明

设无限集，递归地选取

由于非空，选取

假设已选取各不相同，考虑集合非空，可以继续选择

根据上述选取，定义

为容易知道是一个单射，所以是可列的

可列集的任何无限子集必为可列集

证明： 点击查看证明

可列，枚举为，其中

无限集，有

定义集合

由于无限，所以无限，由是子集，可以将按照自然数大小排序，容易得到一个双射，故是可列的，所以容易得到是可列的

可列集中加入有限个元素（或删去有限个元素），仍为可列集

证明： 点击查看证明

枚举即可

有限个可列集之并仍为可列集

证明： 点击查看证明

交叉枚举即可，如：

可列个可列集之并仍为可列集

证明： 点击查看证明

不妨设可列个可列集为

…

按照对角线方法排列

每一斜线上两下标之和相同

则是可列的

设为有限集或可列集，为任意无限集，则

证明： 点击查看证明

取中一个可列子集，则也是可列的，所以存在双射

由于且且且

定义映射

$g(x)=\left{\right. $

是双射，所以是双射，所以

是不可列集，基数记为，也记为，也称为连续统

证明： 点击查看证明

使用反证法

假设是可列的，规定其中每一个实数唯一表示成一个尾数不为0的十进制无限小数

其中

现在取一个十进制小数

其中 $t_{i}=\left{\right.$

满足，，，且故矛盾！

所以不可列

设实数则的基数都是

证明： 点击查看证明

先证明

取一无限点列

中点对应中点

中点对应中点

中点对应中点

中点对应中点

…

其他点保持不变，这样的到一个一一对应，所以

再由无限集并有限集的并和无限集的基数相同知的基数都和它们相等

这时构造映射，所以这四个区间的基数都是

的基数是

证明： 点击查看证明

任取记

取一一对应按照顺序枚举即可

的基数都是

证明： 点击查看证明

先证

构造双射

故基数是

由无限集并上可列集的并和无限集的基数相同知道的基数也是

定义 3.11 基数序关系

若存在单射，则称的基数小于等于的基数，记为

若且则称的基数小于的基数，记为

设是任意集合，那么
(1) 若，则。
(2) 若，，则

（伯恩斯坦（F. Bernstein）定理） 若和是两个集合，且，，则

证明： 点击查看证明

记

定义映射

任意有

若

则

则

则

则

即所以单调递增

记

记

我们证明

有

由于知道

所以有

是所有的并，所以

再证明

已知所以

所以，由于是所有的并

所以

所以且所以

即

所以

是单射，与通过一一对应

定义

$h(x)=\left{\right.$

这里定义，如果，那么

所以存在唯一使得

下面证明是双射

先证明是单射

若则，是单射得到结果

若则，由单射得到结果

若则，不可能相等

所以是单射

再证明是满射

对任意

若，则存在使得所以

若，则，取则

所以是满射

所以是双射

所以 若，，则即伯恩斯坦（F. Bernstein）定理成立

（蔡梅罗（Zermelo）定理）（三歧性） 设和是任意两个集合，那么，，三者中恰有一个成立

证明： 点击查看证明

先给出良序集和序同构的定义

是全序集，是序关系，的每一个非空子集都有一个关于的最小元

这里说明一个全序集是良序的当且仅当不存在一个无限下降链

假设存在无限下降链，取集合可知没有最小元矛盾

假设全序集不是良序的，则存在非空子集没有最小元，从中任取，由于不是最小元，存在使得，依此类推可以得到无限下降链

设是两个全序集，如果有一个双射满足，有等价于，那么这个双射称为序同构，，也称和序同构，记作

先证明 良序定理：任何集合都可良序化，即存在一个关系使得是良序集

记表示的所有非空子集的集合

由选择公理，存在函数 $F:\mathcal{P}{0}(X)\rightarrow XF(S)\in SS\in \mathcal{P}{0}(X)F$ 就是从每个非空子集中选出一个元素

定义一个子集是链：

如果是良序集，并且对于每个都有

这里的是中在之前所有元素的集合

简单来说，链中每个元素都是由函数在还没有选取的集合中选出来的

容易知道链的并还是链

取

下面证明

假设，则

取定义，在上定义序：

保持的序，并且为最大元。

下面证明是链

有 $M’{\prec a}=M{\prec a}a=F(X-M_{\prec a})=F(X-M’_{\prec a})$

有 $M’{\prec m}=Mm=F(X-M)=F(X-M’{\prec m})$

所以是链

得到所以

所以上有一个良序

再证明良序集基本引理

良序集不能与其真前段同构

设是同构，则是无限下降链，矛盾

再证明良序集比较定理

设和是良序集，则恰有以下的一个成立

• （序同构）
• （对某个，序同构于的真前段）
• （对某个，序同构于的真前段）

定义集合

即由所有满足在中的前段与在中的前段同构的配对组成

下面证明是一个函数

设且则且

所以

由于是良序的，两个前段同构当且仅当否则一个前段是真前段，良序集不能与真前段同构

所以是函数

同理可以证明是单射

下面证明是的初始段

设即存在使得

有是的真前段

由于在同构下对应其中满足

所以所以即

所以是的初始段

同理可证是的初始段

根据定义容易得到和都是保序的，所以是序同构

令

我们只需要证明不可能出现是的真前段并且是的真前段的情况

假设其中

那么则则矛盾

又由于良序集不能与真前段同构，知道其他三种情况是互斥的，所以必定是列出的三种情况之一

最后，证明三歧性

对任意，存在良序

对良序集比较定理的第一种情况，显然

对第二种情况，存在单射所以

假设存在

根据伯恩斯坦（F. Bernstein）定理 有

所以存在双射

又有所以

所以存在双射

这说明良序集和自己的真前段同构，矛盾！

所以

第三种情况对称地成立

综上，蔡梅罗（Zermelo）定理成立

（康托尔（Contor）定理） 对于任何集合，必有

证明： 点击查看证明

定义一个映射有

显然是一个单射

所以

下面证明

假设不成立，则存在双射

我们称的为的内部元素，否则为外部元素

设为的所有外部元素组成的集合，显然，所以

由于是双射，则存在使得

如果则是内部元素，与定义矛盾

如果则矛盾

所以不可能是一个双射

综上， 康托尔（Contor）定理成立

设是有限集，则

证明： 点击查看证明

容易知道

假设它们相等，那么存在一个双射

设在中选个元素，是双射，由抽屉原理知必存在矛盾！

所以

即

证明： 点击查看证明

设二进制小数的集合是

二进制有限小数集合，二进制无限小数集合

下面先证明是可列集，的基数是

容易知道 任意一个二进制有限小数其中

容易构造双射有

容易知道是可列的，所以是可列的

对我们构造一个到的双射

下面证明是单射

若则存在最小的使得

不妨设

则

则在位后全为，在位后全为，这与序列不最终全为矛盾！

所以

再证明是满射

对任意，用二进制展开时，不选择包含无限后缀为的展开，这样每一个唯一对应一个，且

综上

所以

做一个映射

对的每一个子集，

其中 $a_{i}=\left{\right.$

显然这是一个双射，因此即

是两个集合，记

即可列个做笛卡尔积的基数为

证明： 点击查看证明

先构造

对

再构造

它们都显然是一个单射，所以

证明： 点击查看证明

容易知道

容易知道

下面构造一个映射

对

，

构造

对，显然即是一个单射

所以

所以

证明： 点击查看证明

只需证

构造

对

记

即可

所以

即可列个做笛卡尔积的基数为

证明： 点击查看证明

只需证

记为二进制无限小数

有

则

这里用到了

也就是

另外地

类似上面有限个的证法也是可以的

康托尔悖论

集合是由具有某些性质的元素所组成，因此也可以假设集合是由所有集合所组成

问：与的基数哪一个基数更大

一方面由康托尔定理知

另一方面

又因为是所有集合所组成的集合，所以

则矛盾！

ZFC 公理

外延公理

若两集合有相同元素，则两者相等

配对公理

存在集合其元素恰好是和

分离公理模式

设为一个关于集合的性质，以表示集合满足性质，则对任意集合存在集合

并集公理

任意集合存在相应的并集

简单来说，就是存在一个并集使得中的元素是所有中元素的元素，这里的可以看作若干个集合组成的集合，的概念就是这些集合的并

幂集公理

任意集合子集构成集合

无穷公理

存在无穷集

替换公理模式

是一个以集合为定义域的函数，则存在集合

正则公理

任意一个非空集合都含有一个对从属关系极小的元素

选择公理

设集合的每个元素都非空，则存在函数使得（这个函数称为选择函数）