第5章 集合论基础
本章导引
集合论作为数学中最富创造性的伟大成果之一，是19世纪末由德国数学家格奥尔格·康托尔①创立起来的。现在，集合已经发展成为数学及其他各学科不可缺少的描述工具，并且成为数学中最基本的概念。在计算机科学中，集合论不仅可以表示数和数的运算，还可以应用于非数值领域中信息的表示和处理，在程序设计语言、数据结构、操作系统、数据库以及人工智能等课程中有着广泛的应用。
一般认为，康托尔建立的集合体系属于朴素集合论体系，将满足相关性质的个体放在一起组成集合。但在康托尔体系中隐含着矛盾，这就是著名的理发师问题②。为了消除悖论，产生了集合论的公理体系。
5.1 集合的概念与表示
定义?5-1 把具有某种性质的个体汇集在一起，就形成一个集合（set）。在集合中，个体通常被称为元素（element）或成员。
例如，所有企鹅汇集在一起形成的集合；所有自然数形成的集合；所有鲁东大学的学生汇集在一起形成的集合等。
一般情况下，用大写字母表示集合，而集合中的元素通常用小写字母表示。如果元素a是集合A中的元素，记为a?A，读作“a属于A”；如果元素a不是集合中的元素，记为，读作“a不属于A”。
例5-1 （1）全体自然数构成的全体，称为自然数集合，用N表示。
（2）全体整数构成的全体，称为整数集合，用Z表示。
（3）全体实数、有理数、复数构成的全体，分别称为实数集合、有理数集合、复数集合，分别用R、Q、C表示。
（4）C语言中的所有标识符构成的集合。
（5）全体英文字母构成的集合。
□
在集合中，元素之间是互不相同的，相同的元素只能出现一次。同一个元素在集合中的出现没有先后顺序，即集合和集合是同一个集合。对元素而言，要么属于某个集合，要么不属于该集合，二者必居其一。
一般来说，集合有两种表示方法：列举法和描述法。
列举法。当一个集合中元素的个数有限时，通常将集合中的所有元素列举出来，这种方法称为列举法，又称枚举法。例如：
?????????
等，都是用列举法表示的集合。
描述法。通常通过刻画集合中元素具备的性质来表示集合，这种方法称为描述法。一般地，用谓词P(x)表示x具备的性质，用{x|P(x)}表示具有性质P的全体元素构成的集合。例如：
R={x | x是一个实数}表示实数集合；
N={x | x是正整数或零}表示自然数集合；
表示区间中的所有实数组成的集合。
例5-2 用列举法表示下列集合。
（1）不大于10的非负偶数组成的集合。
（2）与轴的交点组成的集合。
（3）式子的所有值组成的集合。
解：
（1）。
（2）。
（3）根据a、b的正负值，对上述情况进行如下3种情况的分析。
① 当时，；
② 当或时，；
③ 当时，。
因此，上述集合用列举法表示为。
□
例5-3 用描述法表示下列集合。
（1）正偶数集。
（2）被3除余2的正整数的集合。
（3）平面直角坐标系上坐标轴上的点组成的集合。
解：
（1）；
（2）；
（3）。
□
5.2 集合之间的关系
定义?5-2 设A、B是两个集合，如果集合A中的每个元素都是集合B中的元素，称集合A是集合B的子集（subset），记作或，如果A不是B的子集，记作。形式化表示如下：
AB???
例5-4 设，，，则有，，，CA等成立。
□
从定义5-2可以看出，对任意集合A来讲，成立。
定义5-3 设A、B是两个集合，如果A是B的子集，同时B也是A的子集，称两集合相等③，即
如果集合A和B不相等，记为A ? B，即
如果集合A是集合B的子集，并且A ? B，则称集合A是集合B的真子集（proper subset），记为，即
定义?5-4 不含任何元素的集合称为空集（empty set），记为?。空集可以符号化表示如下。
需要说明的是，空集是客观存在的。例如，集合就是空集，因为在实数范围内x2+1=0是不成立的。
定理5-1 空集是一切集合的子集。
分析：证明空集是任意集合的子集，只能从子集的定义出发。对空集中的任意元素而言，判断它在给定的任意集合中。由于空集中不含任何元素，因此这里需要利用命题逻辑中蕴涵联结词的相关性质，如果前提不成立，蕴涵式一定为真。
证明：
由于空集中不含有任何元素，因此x??为假，进而对任意集合A而言，必有x?? x?A为真，即对任意元素x，x??x?A为永真式。因此，?成立。
□
推论5-1 空集是唯一的。
分析：对于唯一性的判断，通常采用反证法进行。利用反证法的思路是，假设存在两个空集?1、?2，通过证明?1=?2来证明空集的唯一性。证明两个集合相等可以根据定义5-3，通过证明二者互为子集来证明，而二者互为子集可以利用定义5-2来证明。
证明：略。
定义5-5 在讨论的范围内，一切元素构成的集合称为全集，用U表示。
集合论中的全集与谓词逻辑中的全总个体域不一样，全总个体域是绝对的，包含了宇宙间的一切个体，而集合论中的全集是相对的，是相对唯一的。
定义?5-6 集合A中元素的个数称为集合的基数或势（cardinality），记为|A|。如果一个集合的基数是有限的，称该集合为有限集合，反之称其为无限集合。
常见的集合，例如，自然数集合N、整数集合Z、有理数集合Q、实数集合R等都是无限集合。在这些集合中，自然数集合称为可数集合（enumerable set），因为它的记法与常用的记法一致，其元素可以一个一个地数出来。
定义5-7 设有A、B两个集合，如果存在一一映射：，则称集合A和B是等势的。凡与自然数集合N等势的集合，称为可数集合（countable set）或可列集。可列集的基数记为，读作“阿列夫零”。
例5-5 证明以下集合是可数集合。
（1）。
（2）整数集合Z。
（3）素数集合。
（4）有理数集合Q。
分析：要证明上述集合是可数集合，只需在上述集合与自然数集合之间建立一一映射 即可。
证明：
（1）集合是正奇数集合，可以在该集合与自然数之间建立如下的一一映射：
可见，集合是可数集合。
（2）在整数集合Z与自然数集合N之间可以建立如下的一一映射：
可见，整数集合Z也是可数集合。
（3）在素数集合与自然数集合之间可以建立如下的一一映射：
可见，素数集合也是可数集合。
（4）有理数中的任何数字可以表示为分数的形式（是整数且）。因此可以将有理数中的元素以的形式排列成一个有序图形，然后从开始，沿着一条穿过整个图形的路径把所经过的有理数与自然数配对：
可见，有理数集合也是可数集合。
□
5.3 集合的运算
定义5-8 设A、B为两个集合，则
（1）由A和B的全体元素构成的集合称为A和B的并集（union），记为，即
（2）?由A和B的公共元素构成的集合称为A和B的交集（intersection），记为，即
（3）由属于集合A但不属于集合B的元素构成的集合称为A和B的差集（difference），记为，即
（4）由属于集合A但不属于集合B，或者属于集合B而不属于集合A的元素构成的集合，称为集合A和B的对称差（symmetric difference），记为，即
（5）设U为全集，对任意，称为集合A的补集（complement），记为 ，即
例5-6 设U = {1,2,3,4,5,6,7,8,9,10}，集合A = {1,2,3,4,5}，集合B = {2,4,6,8,10}，则有
□
例5-7 满足的集合的个数有多少？
解：通过并集运算的分析，得知集合中必须包含3，而对于元素1和2可以包含，也可以不包含。因此，集合可以是以下4种情况：。即满足上述运算的集合的个数为4个。
□
例5-8 已知，，，计算的值。
解：根据差集运算的定义，有
因此有。
□
上述集合之间的运算可以用韦恩④图（Venn diagram）直观地表示，韦恩图是用封闭曲线表示集合及其关系的图形，其构造方式如下：用一个矩形内部的点代表全集U，用矩形内部的圆或者其他封闭曲线的内部表示U的子集，用阴影区域表示集合之间运算结果构造的新的集合。
设集合A、B是全集U的子集，图5-1给出了集合的交集、并集、差集、对称差以及补集的韦恩图。
图5-1 集合运算的韦恩图表示
定义5-9 设A是一个集合，由A的所有子集组成的集合称为A的幂集（power set），记为或，即
例5-9 设A={1,2,3}，求该集合的幂集。
解：
按A的全部子集从小到大进行分类。
含有0个元素的子集，即空集，只有个：?。
含有1个元素的子集，有个：{1}、{2}、{3}。
含有2个元素的子集，有个：{1,2}、{1,3}、{2,3}。
含有3个元素的子集，有个：{1,2,3}。
所以，集合A={1,2,3}的全部子集总数为
集合A的幂集为
□
定理5-2 设集合A中有n个元素，则中有个元素。
证明：
□
由于中元素的个数即为集合的子集个数，即集合有个不同的子集，读者可以进一步考虑，集合有多少个真子集？有多少个非空子集？又有多少个非空真子集呢？
进一步考虑，如何通过编程求出一个集合的幂集呢？这是程序设计中非常经典的一个问题——遍历解空间。可以发现，含有3个元素的集合幂集中有8个集合，含有4个元素的集合幂集中有16个集合，恰好对应深度为3和4的完全二叉树的叶结点数目。将该问题与数的进制转换思想结合起来，可以得到集合的幂集，即含有3个元素的集合幂集中有8个元素，可以将元素是否在相应的子集中用1和0表示，则幂集中的8个元素可以用长度为3的二进制串来表示，分别表示为000，001，…，111，对应0～7的二进制；而含有4个元素的集合幂集中有16个元素，可以用长度为4的二进制串来表示，分别表示为0000，0001，…，1111，对应0～15的二进制。程序5-1如下所示。
程序5-1 计算集合的幂集
#include<stdio.h>
#include<math.h>
#define N 3
int main()
{
int a[N]={1,2,3};
int number,temp;
int i;
for(number=0;number<(int)pow(2.0,N);number++)
{
temp=number;
for(i=0;i<N;i++)
{
if(temp%2)
printf("%d",a[i]);
temp=temp/2;
}
printf("\n");
}
return 0;
}
程序运行结果如图5-2所示。
图5-2 程序运行结果
根据集合的运算，可以得到如下有关运算的许多性质。
定理5-3 设全集为U，A、B为U的子集，则有如下恒等式成立。
（1）交换律：，。
（2）结合律：，。
（3）分配律：，。
（4）吸收律：，。
（5）幂等律：，。
（6）德摩根律：，。
（7）矛盾律：。
（8）排中律：。
（9）零律：，。
（10）同一律：，。
（11）双重否定律：。
对上述恒等式的证明，可以采用韦恩图来说明，也可以采用两个集合相等的定义进行严格证明。以为例说明上述恒等式的证明过程。
证明：
为了证明，考虑到恒等式两边都是集合，因此根据两个集合相等的定义，需要证明二者互为子集，即和，下面分别证明。
（1）??对任意的，有，因此有和都成立，即，。因而有。因此，成立。
（2）对任意的，有和都成立，即，。因而有 ，即。因此，。
□
5.4 序偶与笛卡儿积
定义5-10 设有两个元素x、y，二者按照一定的顺序组成的二元组称为序偶（ordered pair），记为< x, y >，其中x称为序偶的第一元素，y称为序偶的第二元素。
例?5-10 平面直角坐标系中点的坐标就是序偶，如(1,2)、(?1,3)等；<操作码，地址码>这条单地址指令也是序偶。
在序偶中，元素是有顺序的，即两个序偶< x, y >和< u, v >相等，当且仅当它们的第一元素和第二元素都相等。
例5-11 设序偶，根据序偶相等的条件，可知
，
解得。
考虑序偶反映的是两个元素按照一定的顺序构成的二元组，可以在此基础上进行推广，得到n元有序组的概念。
定义?5-11 设有n个元素，它们按照一定的顺序组成的n元组称为n元有序组，记为<>。
同样，两个n元有序组<>和<>相等，当且仅当ai=bi，其中。
定义5-12 设A、B为两任意集合，以集合A中的元素为第一元素，集合B中的元素为第二元素组成序偶，所有这样的序偶构成的集合，称为A与B的笛卡儿⑤积（Cartesian product）或叉积，记为，符号化表示为
例5-12 （1）设集合，集合，则有
（2）设R为实数集合，则是平面直角坐标系上所有点构成的集合。
可以证明，。当时，可以表示为。
定理5-4 （1）笛卡儿积不满足交换律，即，如果，则。
（2）笛卡儿积对集合的交运算和并运算满足分配律，即
该定理中的（1）是显然的，以（2）中的前两个公式为例对分配律进行证明。
分析：要证明笛卡儿积对集合的交运算和并运算满足分配律，关键在于要清楚笛卡儿积的本质是集合，不同的是集合中的元素是序偶。而要证明两个集合相等，只需证明二者互为子集即可。
证明：
（1）证明。
对中的任意序偶< a, b >，根据笛卡儿积的定义，有，。根据集合并集的定义，知或。进一步可得或。即，因此。
对中的任意序偶，根据集合并集的定义，有或，即或。所以，。因此有。所以有。
根据上述两点，可以得到。
（2）证明。
对中的任意序偶，根据笛卡儿积的定义，可得。根据集合交集的定义，有，。因而有，。所以。因此，。
对中的任意序偶，根据交集的定义，可得，。因此有，，成立，即，。所以。因此，。
□
与序偶到n元有序组的扩展类似，可以将笛卡儿积的定义从两个集合推广到n个集合。
定义?5-13 设为任意n个集合，它们的笛卡儿积为由这些集合中的元素构成的所有n元有序组构成的集合，表示为，形式化表示如下：
5.5 容斥原理
定义5-14 容斥，指在计算某类物的数目时，要排斥那些不应包含在这个数目中的数目，但同时要包容那些被错误排斥了的数目作为补偿。这种原理称为容斥原理（the principle of inclusion-exclusion），又称包含排斥原理（include exclusion principle）。
定理5-5 设A、B为任意有限集合，则有