笔记与习题:《集合论:对无穷概念的探索》(2)

第二章 关系与函数

逻辑主义:将所有数学至于纯逻辑基础之上

两个信念:

(1)任何数学理论都在某种意义上是关于集合的理论

(2)任何数学命题是真的都意味着它在ZFC中得到证明

本章与下一章是以上信念的体现——用集合论的语言刻画经典数学的一些基本概念

但是很多数学问题,包括集合论的核心问题:连续统假设,在通常的ZFC中不可证明,这一点需要指出。

2.1 关系

最简单的关系:二元关系——一种对应或者映射——有序对

定义:设,为集合,,组成的有序对定义为: 证明这一定义是合理的:

首先,证明是集合

练习:证明对任何集合,,是集合

由对集公理:

即 是集合

即 是集合

即 是集合

其次,证明以下命题:

命题:任何两个有序对,, 当且仅当 且

从右边向左边使用外延公理直接证明

从左边向右边使用上述定义分① ,② 两种情况讨论,证明的详细过程略去

定义:令和为集合,则和的卡氏积定义为:

练习:证明对任意和,它们的卡氏积是集合

考虑任意一对有序对,使

根据有序对定义:

现在我们有:

所以

因此

同样地,

所以

由此可见:

所以

(以上构造的所有集合可由并集公理和幂集公理证明存在,这里为了保证证明过程的可读性,不再使用严格的形式化语言进行证明)

由分离公理:

可以知道存在一个集合

由外延公理可知,该集合是唯一的,它是所有 的有序对的集合。

也就是与的卡氏积,所以卡氏积是集合

定义:一集合称为二元关系,如果存在集合,, 。

用表示 ,称和有关系。习惯写作

定义:令为二元关系,

(1)的定义域定义为:

(2)的值域定义为:

练习:证明和都是集合

因为是集合

且

由并集公理, 是集合,且

可见

因为 是集合

所以,由分离公理可知,和都是集合

定义:

(1)集合在关系下的像:

(2)集合在关系下的逆像:

(3)二元关系的逆:

(4)二元关系和的复合:

练习:证明集合在关系下的逆像与在下的像相等

根据定义,在下的逆像由以下集合给出

另一方面,在下的像由以下集合给出

所以需要证明

这是显然的

推广:对三元序组、四元序组……n元序组的定义;对n个集合的卡氏积的定义;n元关系。(递归定义\归纳定义) 三元序组

四元序组

元序组

以上这种定义方式叫递归定义\归纳定义 个集合的卡氏积

元关系通常将写作

2.2 函数

定义:一个二元关系如果满足: 就称是一个函数。记法: , ,

如果 ,就称是到的函数,记为

练习:令和为函数。 当且仅当 ,而且对所有 ,都有

根据定义:

由题,

且对所有 ,都有

即

且

由外延公理可得


以下的内容都是构造新函数的方法

练习:如果和为函数,证明它们的复合 也是函数,并且的定义域为

如果不是函数,则

又由定义:

因为和都为函数,所以

与假设矛盾,所以是函数

由于

所以

定义:假设 为函数,而且对所有的 ,如果 ,则 ,这时就为一一函数或单射。如果 ,就称为满射,即使单射又是满射的函数称为双射

定义:如果一个函数的逆也是函数,就称其为可逆的

可逆是单射

定义:对任意函数和集合, 是一个函数,称为到上的限制。如果 ,则称是的扩张

定义:

(1)函数和是相容的,如果对所有 ,都有

(2)函数的集合称为相容的系统,如果中的任意两个函数都是相容的

推论:如果是相容的函数系统,则是函数,它的定义域 。函数是所有 的扩张

定义:令和是集合,到的所有函数组成的集合定义为:

注:空集到任何集合上都有一个空函数,所以对任何集合, ,但没有到空集的函数,所以对任何集合,

定义:函数 ,每一都是集合。这种函数称为集合的指标系统,称为指标集,指标系统写作 或

指标系统的一些性质:

(1)假设 是指标系统,则 (2)指标集有时可以是二维的,即 。这时规定 (3)对任意公式 定义:是指标系统,则的一般卡氏积为: 是上的函数并对任意 (可以用来”表达一个函数的坐标系统“不只一种…)

对任意 ,由 定义的函数 称为投射函数

选择公理(第二形式):对任意不含空集的非空集合族上都存在选择函数,即存在函数: 满足:对任意

2.3 等价与划分

定义: 令 为二元关系,则

(1)是自反的当且仅当对所有的 ,

(2)是对称的当且仅当对所有的 ,如果,则

(3)的传递的当且仅当对所有的 ,如果,且,则

(4)是等价的当且仅当是自反、对称、传递的,用表示

练习:对任意集合,如果 并满足:(1) (2) (3) ,就称是上的理想,则其上的二元关系: 是等价关系,请证明之

1.证明自反性

即对所有的

成立

成立

自反性成立

2.证明对称性

假如对

有 ,

那么也有 ,

对称性成立

3.证明传递性

假如对

有 , ;

,

由于包含关系的性质: ,且

所以有

又因为

所以 ,

所以有

传递性成立

定义:是上的等价关系, ,关于的等价类指的是集合 注:其实等价类都是集合,不是真类

练习:令为上的等价关系,则对任意 或者

定义:令为一集合, 。如果满足

(1)对所有的 ,如果 ,则

(2)

则称是的划分

定义:令为上的等价关系,则 称为的商集

定理:的商集是的划分

2.4 序

定义:令为上的二元关系,如果满足:

(1)是自反的

(2)是反对称的,即 ,如果 且 ,则

(3)是传递的

就称是上的偏序或序

(4)是连接的,即对所有的 ,如果 或

就称是上的线序或全序

记法: 是上的偏序,是偏序集

定义:令是上的偏序

极小元:如果 ,且对任意 ,有 ,则为的极小元

极大元:如果 ,且对任意 ,有 ,则为的极大元


最小元:如果 ,且对任意 ,有 ,则为的最小元

最大元:如果 ,且对任意 ,有 ,则为的最大元


上界:如果 ,且存在 使得对任意 ,都有 ,则称为在中的上界

上确界:如果在中所有上界的集合有最小元,是的上确界


下界:如果 ,且存在 使得对任意 ,都有 ,则称为在中的下界

下确界:如果在中所有下界的集合有最小元,是的下确界

注:对于线序集而言,极小元与最小元、极大元与最大元是等价的

偏序集的最大最小元是唯一的(如果有的话)

上(下)确界不一定属于,若属于,就是它的最大(小)元

习题

1、证明:令为二元关系, 。证明如果 则 且

,

因为

所以是中的元素

所以 且

2、证明如果函数是可逆的,则 , 。 集合上的恒等映射,对任意集合,如果映射 定义为 , 即规定中每个元素与自身对应,则称为上的恒等映射

函数的逆的定义:

由函数定义,

所以 ,又因为的定义域为(好像证过了)

所以

由函数定义,

所以 ,又因为的定义域为(也证过了)

所以

3、证明:令S为非空集合的非空族,为以为指标集的指标系统,则 由指标系统的性质:

即证

由并集公理,前者等价

由任意交的定义,后者等价

4、证明对于线序集而言,它的极小(大)元就是最小(大)元

线序集与偏序集相比,多了一个连接性,即它的任何两个元素都是可比的,这意味着“不大于”就是“小于或等于”,“不小于”就是“大于或等于”,因此对于线序集而言,它的极小(大)元就是最小(大)元。

5、令 是有穷的,找出 的最小、最大、极小、极大元

极小元:所有的单元素集合与空集

没有极大元

最小元:空集

没有最大元