集合语言是描述现代数学知识的必不可少的工具。本章在给出集合语言基本术语的基础上，介绍定义和描述集合的基本方法，包括元素枚举法、性质概括法、文氏图和成员关系表，然后讨论集合的运算，以及集合等式的证明。基本集合通过集合运算构成集合表达式，可用于描述复杂的集合。集合等式的证明实际上是证明不同的集合表达式描述的是同一集合。因此，本章的核心主题是如何描述集合，这是集合论作为语言工具描述现代数学所需的最基础知识。
5.1 集合的基本概念
本节给出有关集合的一些基本术语，介绍定义集合的基本方法，即元素枚举法和性质概括法，并介绍文氏图(venndiagram)和集合成员关系表(membershiptable)。文氏图可以认为是描述集合的一种简单直观的图形方法，而成员关系表是描述集合及其元素之间隶属关系的一种表格方法。文氏图可以帮助人们直观地确定一个集合表达式所描述的集合，而成员关系表可以帮助人们证明最基本的集合等式。
5.1.1 集合的基本术语
集合是现代数学的基本概念，但也是一个很难准确定义的概念。集合论的奠基人，德国数学家康托尔(G.Cantor1845—1918)认为凡是一堆东西(acollectionofthings)都可称为集合。现在把以这种观点建立的集合论称为朴素集合论(naivesettheory)。朴素集合论会导致悖论(paradox)。因此，人们后来发展出了公理集合论(axiomaticsettheory)，以多条公理的形式界定什么是集合以排除在朴素集合论中可能导致悖论的集合，然后再推演集合论的其他内容。
我们只介绍朴素集合论中最基础的内容。因此，采用朴素集合论的观点，认为凡是放在一起作为整体进行研究的一堆东西是集合。假定在研究某个问题时，其中要研究的最基本的不再分解的东西的全体构成了一个集合，这个集合称为全集(universalset)，通常记为U。简单地说，假定存在全集U，这使得在实际研究中可持朴素集合论观点而不导致悖论。集合是作为整体研究的一堆东西，这些东西的每一个称为该集合的元素(element)。
通常使用大写字母A,B,C,··· 表示集合，小写字母a,b,c,··· 表示元素。元素a属于
(belongsto)集合A记为a∈ A。元素a不属于集合A则记为a.∈ A。注意，元素和
集合是相对的，元素属于集合，集合包含元素，集合的元素也还可以是集合。
朴素集合论认为集合的元素是确定的，即对一个元素a，要么a∈ A，要么a.∈ A， 二者必居其一。集合的元素之间没有顺序，也不重复。
到这里给出了集合、全集、元素、属于这些没有严格定义的基本概念，利用这些基
本概念，下面使用逻辑语言严格地定义集合的其他基本术语，包括子集、空集和集合相
等。实际上，以后主要是借助逻辑语言给出概念的严格定义。
定义5.1对于两个集合A和B，如果A的每个元素都属于B，则称A是B的
子集(subset)，B是A的超集(superset)，或称A包含于(beincludedin)B，B包含
(include)A，记为A. B，或B. A。也即
A . B 当且仅当.x(x∈ A → x ∈ B)
这里个体变量x的论域是全集U。
根据子集关系的定义，很容易证明下面的定理。
定理5.1（1）对任意集合A，有A. A。
（2）子集关系是传递的，即对任意集合A,B,C，若A. B 且B . C，则A. C。
读者后面可能会注意到，在讨论集合语言时，可能的研究对象不仅包括U的元素而且还包括U的所有子集。或者说，在用一阶逻辑公式定义集合论的一些术语或概念时，其中个体变量的取值不仅可能是U的元素，还可能是U的子集，也即个体变量的论域不仅包括U，还包括U的所有子集。我们把这个论域作为讨论集合语言，包括集合、函数与关系等内容时的全总域，并记为U。
不过多数时候，读者无须考虑论域到底是全集U还是全总域U，只需要知道，集合的元素仍然可以是集合，在强调集合的元素可能是集合的情况下，才需要考虑使用全总域U。通常，特别地称一个集合为集合族(afamilyofsets)，如果它的所有元素也都是集合。
定义5.2对于两个集合A和B，如果对任意元素x，x∈ A 当且仅当x ∈ B，则称集合A和B相等，记为A=B。也即
A = B 当且仅当.x(x∈ A . x ∈ B)
定义5.2基于朴素集合论的外延原则(principleofextensionality)，即两个集合只要有相同的元素则认为是相等的集合，而不考虑集合名字本身的内涵。在哲学或语言学中，一个概念（名字）的外延是它所指称的对象，而内涵是它的本质属性，也即它有别于其他概念的属性的全体。例如，“《朝花夕拾》的作者”和“《狂人日记》的作者”内涵不同（给了我们不同信息），但外延相同。对于集合，它的外延就是它包含的所有元素，而内涵则视具体的应用而定，所以将元素相同则集合相等这项原则称为外延原则。
181
根据双蕴涵逻辑等值式，即p . q ≡ (p → q) ∧ (q → p)，并比较集合相等和子集关系的定义，容易得到下面的定理。
定理5.2对于两个集合A和B，A=B当且仅当A. B 且B . A。
当A是B的子集但不等于B时，称A是B的真子集(properset)，记为A. B， 即A . B 当且仅当A . B 且A =.B。
定义5.3不包含任何元素的集合称为空集(emptyset)，记为.。也就是说，空集是使得命题.x(x.∈ .) 成立的集合。
显然，根据蕴涵式前件为假则整个蕴涵式总是为真的特点可得到下面的定理。
定理5.3空集是任何集合的子集，即对任意集合A，.. A。
定理5.4空集是唯一的，即对任意集合A，如果A也满足.x(x.∈ A)，则A=.。
证明显然，若A也满足.x(x.∈ A)，则对任意集合B也有A. B，从而A. .， 而又有. . A，因此A=.。
5.1.2 定义集合的基本方法
在使用集合语言研究应用问题时，首先可能需要给出一些集合的定义。例如，数学基础的研究通常从自然数集的定义开始，然后扩展至整数集、有理数集及实数集；研究命题逻辑，需要先定义命题逻辑公式集；研究程序设计语言，需要先定义程序中可以出现的符号集等。
人们将定义集合的方法分为元素枚举法、性质概括法和归纳定义法。在介绍证明方法时，已经介绍了集合的归纳定义法，即在归纳基给出集合的基本元素，然后在归纳步给出一些规则从集合已有元素构造更多元素。自然数集、命题逻辑公式集都可使用归纳法定义。归纳定义法适合编写计算机程序自动地构造集合的元素。这里讨论更为简单直接的元素枚举法和性质概括法。
定义集合的元素枚举法是基于朴素集合论的外延原则，将一个集合的所有元素一一地罗列出来而定义该集合。这适合在元素比较少，或者在可以按照明显的规律罗列元素时定义集合。
例子5.1下面是使用元素枚举法定义集合的例子。
（1）小于10的正整数集合：{1, 2, 3, 4, 5, 6, 7, 8, 9}。（2）C++程序标识符可出现的符号集：{A, ··· , Z, a, ··· , z, 1, ··· , 9, _ }。（3）2的所有非负整数幂构成的集合：{1, 2, 4, 8, ···} 。
集合定义的元素枚举法使用左右花括号括住集合的所有元素，元素之间使用逗号分隔。如果罗列的元素有明显规律，可使用省略号省略其中的部分元素。定义集合的性质概括法使用谓词概括一个集合的所有元素所满足的共同性质而定义该集合，通常使用下面的形式定义集合A：
A = {x | P(x)}其中，用花括号表明是对集合的定义，竖线前面的x给出集合元素的形式，后面的谓词
P(x)概括集合元素x所共同满足的性质。这个定义意味着，对任意x，x∈ A当且仅当P(x)为真，因此也称A为谓词P(x)的真值集(truthset)。朴素集合论认为任意的谓词都可概括定义一个集合，但这一点被发现可能会导致悖论。著名的罗素悖论利用性质x.∈ x 定义集合：
S = {x | x .∈ x}
这时如果不明确x的论域，或者说如果x的论域可以包括S自己的话，那么会导出悖论，因为如果谓词x.∈ x可作用于这样定义的S，那么是否有S∈ S？如果S.∈ S，则根据S的定义，S∈ S，而如果S∈ S，则同样根据S的定义，又应该有S.∈ S，也即S∈ S 不是非真即假的命题而是悖论。由于罗素悖论使用的性质只用到集合论最基本的
“元素属于集合”这个概念，从而对朴素集合论的冲击非常大。罗素悖论的通俗形式称为“理发师悖论”：一个理发师声称他一定给且只给他那个村庄中不给自己理发的人理发，但问题是，他是否应该给自己理发？他自己也是这个村庄的人。
公理集合论引入子集分离公理来避免悖论，即只允许下面形式的性质概括法定义集合A：
A = {x ∈ B | P(x)}其中，已知B是一个集合。简单地说，子集分离公理只允许通过谓词，从已知的集合中分离出一些元素，这些元素满足这个谓词从而定义了一个集合，也即在给出性质P(x)用于定义集合时，x的论域限定为一个已知的集合B。
我们假定存在全集U正是基于这一点，即在使用谓词P(x)定义集合时，如果没有明确给出x的论域，则总假定它的论域是全集U。我们说U是所研究问题中的最基本的不再分割的东西构成的集合，即对属于U的元素x都有x.∈ x，这样S={x | x .∈ x}意味着S=U，而总有U.∈ U，因为U本身不是最基本的不再分割的东西，也不属于
x 的论域。实际上，在具体研究中通常都是利用某个性质从已知的集合分离出子集，而且也很少会遇到像x .∈ x这样奇怪的性质。例子5.2下面是使用性质概括法定义集合的例子。
（1）小于10的正整数集合：{x ∈ Z+ | x< 10}。（2）2的所有非负整数幂构成的集合：{x |.k ∈ N(x=2k)}。
注意，这里一阶公式.k ∈ N(x=2k) 是公式.k(k∈ N∧ x =2k)的简写形式，对于前者可直接认为k的论域是N，对于后者则认为k的论域是全集U，而k∈ N 是特征谓词。这种将特征谓词直接与量词写在一起的形式很常见，不过这时要注意全称量词的特征谓词与后面给出性质的谓词是逻辑蕴涵关系，而存在量词的特征谓词与后面给出性质的谓词是逻辑合取关系。例如，公式.n.8(P(n))是.n(n.8→ P(n))的简写，而.n.8(P(n))是.n(n.8∧ P(n))的简写。
在使用性质概括法定义集合时，为简便起见，也通常使用下面的形式定义集合A：
A = {f(x)| P(x)}
这里f(x)是包含x的一个函数（或说表达式）。注意，这样定义意味着，对任意元素x，有：
x ∈ A 当且仅当.y(x=f(y)∧ P(y))
如果读者对一阶公式中个体变量的辖域与约束出现很熟悉的话，应该不会因为上面定义A时使用f(x)，这里又说x∈ A而感到迷惑。也许可以使用约束变量改名，换一个变量名更容易理解：即上述集合A的定义意味着，对任意元素y，y∈ A当且仅当存在x使得y=f(x)且P(x)成立。
通过在竖线前面写表达式或函数，可用下面更简便的形式定义2的所有非负整数幂构成的集合：
{2k | k ∈ N}这里并没有引入一个字母作为这个集合的名字。定义集合时没有要求一定要给集合起一个简短的名字。通常只是对那些重要的、常用的集合用固定的字母命名，例如自然数集N、整数集Z、有理数集Q、实数集R等，很多集合我们只是临时用一个字母命名，甚至不命名。
问题5.3设全集U是整数集Z。定义集合A：
A = {x 2 | 0 . x . 5}
（1）使用元素枚举法给出A。
（2）判断下面逻辑公式的真值：
. .x(x∈ A ..y(0.y.5∧ x = y2)) . .x(0.x.5→ x2 ∈ A)
. .x(x2 ∈ A → 0 . x . 5) . .x(x2 ∈ A ∧ 0 . x . 5)
【解答】（1）使用元素枚举法给出A很简单，有：
A = {02 , 12 , 22 , 32 , 42 , 52} = {0, 1, 4, 9, 16, 25}
（2）根据一阶逻辑公式的真值定义确定所给的公式的真值，这时解释的论域是全集U，即整数集Z，所有公式都是闭公式，不需要个体变量指派函数。
. 公式.x(x∈ A ..y(0.y.5∧ x = y2)) 是性质概括法定义集合A = {x2 | 0 . x . 5} 的逻辑含义，因此真值为真。当然，也可对任意的x验证该公式的真值为真。
. 公式.x(0.x.5→ x2 ∈ A)的真值为真，因为对任意的x，若0.x.5，即x=0,1,2,3,4,5，显然都有x2 ∈ A。.公式.x(x2 ∈ A → 0.x.5)的真值为假，因为论域是整数集，我们有(.1)2 =1 ∈ A，但是.1<0。.公式.x(x2 ∈ A ∧ 0 . x . 5) 的真值为假，因为论域是整数集，显然并不是所有的整数x 都有0 . x . 5 成立。
【讨论】对于性质概括法定义的集合A={f(x)| P(x)}，其中的x 如果没有特别说
明，则论域是全集U。注意这个定义的逻辑含义是对任意x∈ A当且仅当存在y使得
P(y)且x=f(y)。
这时公式.x(P(x)→ f(x)∈ A) 的真值为真，而公式.x(f(x)∈ A → P(x))的真值不一定为真，因为按照集合A的定义，对任意的x，f(x)∈ A当且仅当存在y使得P(y)为真且f(x)=f(y)。所以，对任意x，若P(x)为真，则显然存在y等于x本身使得P(x)为真且f(x)=f(x)，即f(x)∈ A。但若f(x)∈ A只意味着存在y使得P(y)为真且f(x)=f(y)，这个y不一定就是x，也就不一定得到P(x)为真。例如当f(x)=x2 时，1=f(.1)，存在1使得0.1.5且f(1)=1，但不意味着0..1.5。
所以，在利用这样定义的集合A证明其他命题时，以命题“对任意x，若f(x)∈ A
则P(x)”为前提，或者以命题“对任意x，f(x)∈ A且P(x)”为起点开始进行证明都
是错误的做法。
最后需要指出的是，性质概括法，特别是遵循子集分离公理的性质概括法虽然是最
常见的定义集合的方法，但是元素枚举法以及归纳定义法也是很有用的集合定义方法。
有时一个集合的所有元素的共同性质可能很难概括，例如很难用简单的谓词概括C++
程序的标识符中可以出现的所有符号的共同性质。而且，从计算机程序设计的角度看，
元素枚举法和归纳定义法更容易设计算法和编写程序构造出集合的元素。
5.1.3 文氏图与成员关系表
在定义集合之后，更多地需要描述和研究集合之间的关系，包括集合之间的子集关系或说包含关系，集合之间的相等关系，以及利用一些基本集合通过集合运算构造集合等。文氏图和集合成员关系表可帮助人们描述集合之间的关系，因此在介绍集合运算和集合等式之前，这里先介绍文氏图和集合成员关系表的制作方法。
文氏图是描述集合的一种图形方法，通常先绘制一个方框表示全集U，然后在方框
中绘制圆形或其他封闭图形表示一个集合，例如图5.1给出一个集合A的文氏图，圆
形封闭区域代表集合A，它处于代表全集U的方框之中，也表示A是U的子集。
图5.1一个集合A的文氏图
当要绘制多个集合的文氏图时，对任意两个集合A和B，除非特别说明没有元素同时属于A和B，否则绘制的表示A的封闭图形和表示B的封闭图形要相交，也即要有重叠区域。例如，图5.2给出了两个集合A和B的文氏图，两个圆形重叠的区域表示同时属于集合A和B的元素所在位置，而表示集合A的圆形中不与表示集合B的圆形重叠的区域表示只属于A而不属于B的元素所在位置，同样表示集合B的圆形中不与表示集合A的圆形重叠的区域表示只属于B而不属于A的元素所在位置。
图5.2两个集合A和B的文氏图
一般来说，表示n个集合的文氏图要被表示n个集合的封闭图形分割为2n 个封闭区域，所以一般来说文氏图适合表示两个或三个集合。图5.3给出了三个集合A,B和C的文氏图，可以看到，分别表示集合A,B,C的三个圆形将表示全集U的方框分割成了8个相互不重叠的封闭区域。图5.3(a)分别使用了.～.标注，例如区域.代表全集中既不在A又不在B也不在C中的元素所在的区域，而区域.表示同时在集合A,B和C中的元素所在的区域。
图5.3三个集合A,B和C的文氏图
文氏图通常将其中的一个或多个封闭区域进行填充表示所关注的集合，或者说是该文氏图所表达的某个集合表达式。例如图5.3(b)填充了图5.3(a)中标注为.的区域，以代表这个文氏图所关注，或者说所真正表示的集合。后面介绍集合运算后就可给出相应的集合表达式，这里通过图就可直观地看到它是同时在集合A和B，但不在集合C的元素所在的区域。进一步，文氏图中也可使用不同的线条或颜色填充不同的区域而表示多个关注的集合。
集合的成员关系表从某种意义上可以说是文氏图的表格表示，而且这种表格非常类似命题逻辑公式的真值表。当要研究n个集合时，集合的成员关系表有2n 行，每一行对应表示n个集合的文氏图的一个相互不重叠的封闭区域。例如表5.1给出了一个有三个集合A,B,C的集合成员关系表，前面三列分别对应集合A,B,C，下面每一行对应三个集合的文氏图的一个互不重叠的封闭区域，其中0表示全集的元素不属于对应列的集合，而1表示全集的元素属于对应列的集合因此，第一行对应全集元素既不在A又不在B，也不在C中，即对应图5.3(a)中标注为.的区域，而第二行表示全集元素只在C，而不在集合A和B中，即对应图5.3(a)中标注为.的区域等等。
表5.1有三个集合A,B,C的成员关系表
A B C · · · S
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 0
1 0 0 0
1 0 1 0
1 1 0 1
1 1 1 0
表示n个集合的成员关系表除前面n列对应n个集合之外，其他列可用于表示集合表达式，也即像文氏图使用填充那样表示所关注的某个集合。例如表5.1的最后一列表示集合S（也可以是一个集合表达式），这一列中为1的行表示该集合包含这种情形下的全集元素，因此它的第七行为1表示，当全集元素同时属于A和B而不属于C时，则属于集合S。因此这一行为1相当于在文氏图中填充了这一行所对应的区域，也即这个表中S表示的集合就是图5.3(b)所填充的区域。
当然，在成员关系表中这一列可以有多行取值为1，以对应文氏图中同时填充多个区域。表5.1的省略号表示在计算集合S的全集元素隶属关系时，可能中间还要计算其他集合的元素隶属关系。与构造命题逻辑公式真值表相同，在构造成员关系表时，我们也建议每次考虑一个集合运算。
最后，集合表达式是指使用表示集合的大写字母A,B,C等为操作数，5.2节要介绍的集合运算为运算符而构成的表达式。下面在介绍集合运算和集合等式时会给出更多的文氏图和集合成员关系表的例子，以帮助读者理解集合表达式所描述的集合，即集合表达式的运算结果。
5.2 集合运算
集合运算使得人们可以由一些基本的集合构成集合表达式描述相对复杂的集合。本节主要讨论集合交、集合并、集合差与补等集合运算的基本代数性质，最后介绍了集合的幂集，从而可以看到，在给定全集的情况下，集合运算对于全集的幂集封闭而构成了完整的集合代数系统。
5.2.1 集合交
定义5.4两个集合A和B的交(intersection)，记为A∩ B，定义为
=
A ∩ B {x | x ∈ A ∧ x ∈ B}因此，对任意元素x，x∈ A ∩ B 当且仅当x ∈ A 且x ∈ B。通俗地说，A∩ B包含那些同时在集合A和B的元素。图5.4给出了A∩ B 的文氏图和成员关系表，可以看到它的成员关系表与逻辑合取的真值表非常类似。
图5.4集合A∩ B 的文氏图和成员关系表
例子5.4设有两个自然数集子集A和B：
A = {2k +1 | k ∈ N, 0 . k . 5} B = {3k +1 | k ∈ N, 0 . k . 5}
注意，这里在性质概括法定义集合时，竖线后面使用逗号相当于逻辑合取，例如，对于A 的定义是要求k ∈ N且0.k.5。容易由元素枚举法得到：
A = {1, 3, 5, 7, 9, 11} B = {1, 4, 7, 10, 13, 16}
因此，根据集合交的定义有：A ∩ B = {1, 7}问题5.5设有两个自然数集子集A和B：
A = {2k +1 | k ∈ N} B = {3k +1 | k ∈ N}
试计算A ∩ B。
【分析】虽然这里的A和B的元素都可以有规律地罗列，但是再使用元素枚举法给出A和B的元素对于计算A∩ B 的帮助已不大，因此只能基于A ∩ B 的定义直接计算。
【解答】我们有：
=
A ∩ B {2k +1 | k ∈ N}∩{3k +1 | k ∈ N} = {x |.k ∈ N(x=2k+1)}∩{x |.k ∈ N(x=3k+1)}
= {x |.k ∈ N(x=2k+1)∧.k ∈ N(x=3k+1)}
【讨论】（1）注意，存在量词与合取没有分配律逻辑等值式。因此，上述结果无法利用存在量词与合取之间的关系做进一步的简化。
（2）作为集合计算，上面的解答可以作为A∩ B 的结果，但有些读者可能会感觉不太满意，因为对A ∩ B中元素共同性质的概括有些复杂。那么，利用整除的性质可以证明，对任意正整数a,b,c有：
a | c 且b | c当且仅当lcm(a,b)| c
这里lcm(a,b)是a和b的最小公倍数。因此对于自然数x，若存在自然数k使得x=2k+1，则2| x . 1，同样若存在自然数k使得x=3k+1，则3| x . 1，从而6| x . 1。反之，若6| x . 1，显然有2| x . 1 且3 | x . 1。因此有：
A ∩ B = {x |.k ∈ N(x=6k+1)} = {6k +1 | k ∈ N}
这就得到了一个更令人满意的计算结果，即A ∩ B 是整除6 余1 的自然数构成的集合。通过A ∩ B 的定义以及上面的例子可以看到，集合交运算与逻辑合取运算有密切
联系。我们不难根据与逻辑合取运算相关的等值式证明集合交的基本代数性质。定理5.5设A和B是任意两个集合。
（1）集合交满足交换律，即A∩ B = B ∩ A。
（2）集合交满足结合律，即A∩ (B ∩ C)=(A∩ B) ∩ C。
（3）集合交满足幂等律，即A∩ A=A。利用逻辑合取的交换律、结合律和幂等律等值式很容易证明，下面以交换律的证明作为例子展示证明集合相等的基本方法。
问题5.6证明集合交的交换律，即对任意集合A和B有A∩ B = B ∩ A。【证明】对任意x，有：
x ∈ A ∩ B 当且仅当x ∈ A ∧ x ∈ B // A ∩ B 的定义当且仅当x ∈ B ∧ x ∈ A // p ∧ q ≡ q ∧ p 当且仅当x ∈ B ∩ A // B ∩ A 的定义
从而根据集合相等的定义有A ∩ B = B ∩ A。
【讨论】（1）可以看到，逻辑等值≡ 在数学证明常用“当且仅当”进行推演。逻辑
等值具有传递性，上面的推演每一步都是“当且仅当”，因此就得到了x ∈ A ∩ B 当且
仅当x ∈ B ∩ A。
（2）上述证明是通过逻辑等值使用“当且仅当”进行推演，也可直接写成下面的集合相等形式进行推演：
A ∩ B = {x | x ∈ A ∧ x ∈ B} // A ∩ B 的定义= {xx ∈ Bx ∈ A} // p ∧ q ≡ q ∧ p = B ∩| A ∧ // B ∩ A 的定义
不难看到，这两者实质上是一样的。