内容发布更新时间 : 2024/5/30 13:56:33星期一 下面是文章的全部内容请认真阅读。

第一章 集合论基础

§1.1 基本要求

1. 掌握集合、子集、超集、空集、幂集、集合族的概念。懂得两个集合间相等和包含关系

的定义和性质，能够利用定义证明两个集合相等。熟悉常用的集合表示方法。

2. 掌握集合的基本运算：并、交、余、差、直乘积、对称差的定义以及集合运算满足的基

本算律，能够利用它们来证明更复杂的集合等式。

3. 掌握关系、二元关系、空关系、全域关系、相等关系、逆关系的概念以及关系的性质：

自反性、对称性、反对称性、传递性。会做关系的乘积。了解关系的闭包运算：自反闭 包、对称闭包、传递闭包。

4. 掌握等价关系、等价类、商集的概念，了解等价关系和划分的内在联系。

5. 掌握部分序关系、部分序集、全序关系、全序集的概念以及部分序集中的特殊元素：最

大元、最小元、极大元、极小元、上确界、小确界的定义。能画出有限部分序集的Hasse 图，并根据图讨论部分序集的某些性质。

6. 掌握映射、映像、1-1映射等概念，会做映射的乘积。了解可数集合的概念，掌握可数

集合的判定方法。

7. 了解关系在数据库中的应用（数据的增、删、改）以及划分在计算机中的应用。

1

§1.2 主要解题方法

1.2.1 证明集合的包含关系

方法一. 用定义来证明集合的包含关系是最常用也是最基本的一种方法。要证明A?B，首先任取x?A，再演绎地证出x?B成立。由于我们选择的元素x是属于A的任何一个，而非特指的一个，故知给出的演绎证明对A中含有的每一个元素都成立。当A是无限集时，因为我们不能对x?A，逐一地证明x?B成立，所以证明时的假设“x是任取的”就特别重要。

例1.2.1 设A，B，C，D是任意四个非空集合，若A?C，B?D，则A×B?C×D。 证明：任取(x，y) ?A×B，往证(x，y) ? C×D。 由(x，y) ?A×B知，x?A，且y?B。又由A?C，B?D知，x?C，且y?D，因此，(x，y) ? C×D。故，A×B?C×D。

方法二. 还有一种证明集合包含关系的方法，基于集合的交和并运算的两个基本性质

A?B?A?B=A?A?B=B 以及一些已经证出的集合等式。现在我们就用此方法将上例再证一次。

由下面例1.2.2证明的结论有（A×B）?（C×D）=（A?C）×（B?D），若A?C，B?D，则A?C=A，B?D=B，因此，（A×B）?（C×D）=A×B。因此，A×B?C×D。

1.2.2 证明集合的相等

方法一. 若A，B 是有限集，要证明集合A=B当然可以通过逐一比较两集合所有元素均一一对应相等即可，但当A，B 是无限集时，一般通过证明集合包含关系的方法证得A?B，B?A即可。

例1.2.2 设A，B，C，D是任意四个集合，求证（A×B）?（C×D）=（A?C）×（B?D）。 证明：首先证明（A×B）?（C×D）?（A?C）×（B?D）。任取（x,y）?（A×B）?（C×D），则（x,y）?（A×B），且（x,y）?（C×D），故x?A，y?B，x?C，y?D， 即x?A?C，y?B?D，因此，（x,y）?（A?C）×（B?D）。

由于以上证明的每一步都是等价的，所以上述论证反方向进行也是成立的。故可证得 （A?C）×（B?D）?（A×B）?（C×D）。 因此，（A×B）?（C×D）=（A?C）×（B?D）。

方法二. 还有一种证明集合相等的方法，可以通过已证出的集合等式，通过相等变换将待证明的等式左（右）边的集合化到右（左）边的集合，或者两边同时相等变换到同一集合。

例1.2.2 设A，B，C是三个集合，已知A?B=A?C，A?B=A?C，求证B=C。

证法1：使用反证法。假设B≠C，则必存在x，满足x?B，且x?C，或者x?B，且x?C。不妨设x?B，且x?C，

2

① 若x?A，则x?A?B，但x?A?C，与A?B=A?C矛盾。 ② 若x?A，则x?A?B，但x?A?C，与A?B=A?C矛盾。 所以原假设不对，B=C。

证法2：利用已知以及集合运算的交换律、分配律与吸收律，有 B = B?(A?B) = B?(A?C)

= (B?A)?(B?C)

= (C?A) ?(B?C) = C?(A?B) = C?(A?C) = C

1.2.3 判断给定关系的性质

给出一个关系，我们可以判断它是否具有自反性、反自反性、对称性、反对称性、传递性等性质，这既可以从以集合形式给出的关系来判断，也可以从关系的关系图或关系矩阵出发来进行判断。R的集合表达式、关系图、关系矩阵三者均可以相互唯一确定，比较关系的这三种表示方法容易看出：关系的集合表达式便于书写，关系矩阵便于存储，而关系图直观、清晰。

方法一. 从关系的集合表达式判断关系的性质

设R为集合A 上的关系，

（1）若IA?R，则R具有自反性；

（2）若IA?R=?，则R具有反自反性； （3）若R-1=R，则R具有对称性；

（4）若R?R-1?IA，则R具有反对称性； （5）若R2?R，则R具有传递性。

方法二. 从关系图判断关系的性质

定义1.2.1 设A={x1，x2，…，xn}，R是A上的二元关系。以A中的元素为顶点，在图中用“。”表示顶点。若xiRxj，则从顶点xi向xj引有向弧，称所画出的图为R的关系图，记作G(R)。

（1）若R的关系图中每点都有反身弧，则R具有自反性；

（2）若R的关系图中任意一点都没有反身弧，则R具有反自反性；

（3）在R的关系图中，如果两不同点之间有有向弧的话，那么就一定成对出现，则R具有对称性；

（4）在R的关系图中，若任意两个不同点之间的有向弧都不成对出现，则R具有反对称性。

（5）对于R的关系图中的任意三点a,b,c，不存在这样的情形：有a到b的有向弧，b到c的有向弧，但无a到c的有向弧，则R具有传递性。

方法三. 从关系矩阵判断关系的性质

3

定义1.2.2 设A={x1，x2，…，xn}，R是A上的二元关系。称矩阵M(R)=（rij）n×n为R的关系矩阵，其中

rij=??1,?0,xiRxj否则

（1）若R的关系矩阵的主对角线元素都为1，则R具有自反性； （2）若R的关系矩阵的主对角线元素都为0，则R具有反自反性； （3）若R的关系矩阵为对称矩阵，则R具有对称性；

（4）在R的关系矩阵中，若以主对角线为对称的元素都不同时为1，则R具有反对称性。

在关系矩阵中，若对{0,1}中的元素的加法使用逻辑加法（0+1=0，0+1=1+0=1+1=1），则对于任意的R，S ?A×A，均有 M(R?S)=M(R)?M(S).

由此可见，可以使用矩阵的乘法（加法使用逻辑加法）来做关系的乘积，从而确定其集合表达式。故可以通过计算M(R2)来判断R是否具有传递性。

（5）如果M(R)2中某元素sij=1，那么M(R)相应位置元素rij也一定为1，则R具有传递性。

例1.2.3 设A={1，2，3，4}，R是A上的二元关系，R={（1，1），（3，1），（1，3），（3，3），（3，2），（4，3），（4，1），（4，2），（1，2）}

（1）画出R的关系图； （2）写出R的关系矩阵；

（3）说明R是否具有自反性、反自反性、对称性、反对称性、传递性。 解：（1）R的关系图如图1.1所示。

4 2

1 3

图1.1

?1?0（2）R的关系矩阵M(R)是??1??1

101110110?0?? 0??0?4

（3）方法一：从集合形式给出的关系看，由于（2，2）?R，故R不具有自反性；由于（1，1）?R，故R不具有反自反性；由于（3，2）?R，但（2，3）?R，故R不具有对称性；由于（3，1）?R，（1，3）?R，故R不具有反对称性；经计算得

R2={（1，1），（3，1），（1，3），（3，3），（3，2），（4，3），（4，1），（4，2），（1，2）} =R，

故R具有传递性。

方法二：从关系图上看，由于结点2处无反身弧，故R不具有反自反性；由于（1，1）?R，故R不具有反自反性；由于结点2与4之间的有向弧不是成对出现的，故R不具有对称性；由于结点1和3之间的有向弧是成对出现的，所以R不具有反对称性；由于不存在这样的情形：有a到b的有向弧，b到c的有向弧，但无a到c的有向弧，可见R具有传递性。

方法三：从关系矩阵来看，由于关系矩阵主对角线元素不全是1，故R不具有自反性；由于关系矩阵主对角线元素存在非零元素，故R不具有反自反性；由于该矩阵不是对称矩阵，故R不具有对称性；由于以主对角线为对称的元素有同时为1的，所以R不具有反对称性；经计算可得

?1?02

M(R)= ??1??1故可知，R具有传递性。

101110110?0??= M(R)， 0??0?1.2.4 求非空集合上的所有等价关系

非空集合A上的一个等价关系R，决定了A上的一个划分，这个划分就是商集A/R，由A/R又确定了A上的一个等价关系，这个等价关系实际上就是R。同样，非空集合A上的一个划分π确定了A上的一个等价关系R，由R又决定了A上的一个划分，即商集A/R，这个商集A/R实际上就是π。因此，在A上的等价关系和A上的划分之间建立了一个一一对应，A上等价关系的数目和A上的划分的数目是一样的。所以，要想求出非空集合A上的所有等价关系，只需先求出A上的所有划分，再找出由它们确定的等价关系即可。

例1.2.4 设A={a,b,c}，求出A上的所有等价关系。 解：由第二类Stirling数易知，A上共有5个划分： п1={{a，b，c}}， п2={{a}，{b，c}}， п3={{b}，{a，c}}， п4={{c}，{a，b}}， п5={{a}，{b}，{c}}。

因此，A上的等价关系共有5个：

由п1确定的等价关系是A上的全域关系EA， 由п2确定的等价关系是IA?{(b，c)，(c，b)}， 由п3确定的等价关系是IA?{(a，c)，(c，a)}， 由п4确定的等价关系是 IA?{(a，b)，(b，a)}， 由п5确定的等价关系是A上的相等关系IA。

5