第三章 集合及其运算

1、第三章 集合及其运算 集合论产生于16世纪末。当时，只是由于微积分学的需要，人们只对数集进行了研究。19世纪末，即 1876一1883年间，康托尔（Gaorge Cantor 1845一1918年,德国数学家）对任意元素的集合进行了系统的研究，提出了无限集的势、序型等概念，奠定了集合论的基础。康托尔被公认为集合论的创始人。 集合论是一门研究数学基础的学科，它试图从一个比“数”更简单的概念集合（sets）出发，定义数及其运算，进而发展到整个数学。在这一点上它取得了极大的成功。我们介绍集合论则不仅因为此，而且因为计算机科学及应用的研究，也和集合论理论有着极密切的关系。集合不仅可用来表示数及其运算，

2、更可以用于非数值信息的表示和处理。像数据的删节、插入、排序，数据间关系的描述，数据的组织和查询都很难用传统的数值计算来处理，但却可以用集合运算来实现。 德国数学家康托尔（cantor）开创的集合论被称为朴素集合论，因为他没有对集合论作完全形式的刻划，从而导致了理论的不一致（产生了悖论，见节）。为弥补朴素集合论的不足，本世纪初出现了各种公理化的集合论体系。1904-1908年间，策墨罗（Zormelo）给出了第一个集合论的公理系统。之后，集合论迅速发展，逐步形成公理化集合论和抽象集合论；并且在集合论的基础上,实变函数论、泛函分析、概率论和信息论等许多数学学科，先后建立起来。集合论已成为现代数学中

3、重要的组成部分。鉴于离散数学学科所要达到的目的，我们不准备引入复杂、抽象的集合论形式系统，但我们将借鉴公理化集合论的思想，以避免悖论；同时将利用已有的形式化知识，使集合论的介绍更加简明、深入。 集合及其运算的有关基础知识，在中学课本上已有介绍，因此我们在第一篇里已经使用了一些集合论术语。但是，为了知识的系统性和完整性，本章仍然要对这些知识作扼要的介绍，有些方面的讨论较之中学数学要更宽广、更深入、更系统, 因而抽象性抽象性和理论性更强。  3.1 集合的基本概念 集合是作为整体识别的、确定的、互相区别的一些对象的总体。 严格地说这算不得集合的定义，因为“总体”只是“集合”一词的同义反复

4、。在集合论中，集合是一个不作定义的原始概念（就像几何学中的点、线、面等概念）。不过，上述关于集合概念的描述，有益于对它的内涵作直观的理解和认识。 例3.1 （1）“南京大学全体学生”为一集合，其组成对象是学生。 （2）“全体自然数0，1，2，3，”为一集合，其组成对象是各自然数。（注意，我们所说的自然数与中学课本定义的自然数略有不同,这是计算机界目前的一个流行做法,让自然数有别于正整数,包括数0。） （3）获1988年诺贝尔文学奖的作家构成一个集合，尽管它只有一个对象埃及作家纳吉布马夫兹。 （4）育才中学的所有班级组成一集合，其组成对象是班级，而不是学生，因为集合中对象是整体识别的。（5）“好

5、书”的全体不构成集合，因为难以对每一本书的好坏作出确定的判断。（6）方程x(x2-2x+1)=0的所有根组成一个集合，它只有一个对象0和一个（而不是两个）对象1，因为集合中对象是相互区别的。 （7）方程x2 +x+1=0的根组成一个集合。当讨论复数时，它由两个对象组成；当讨论实数时，它是一个没有任何对象的特定集合。 组成集合的对象称为集合的成员（members）或元素（elements） 请注意，这里“对象”的概念是相当普遍的，可以是任何具体的或抽象的客体，还可以是集合，因为人们有时以集合为其讨论的对象，而又需涉及它们的一个总体以集合为其元素的集合。例如，育才中学所有班级的全体构成的集合，以学

6、生班级集体为其元素; 又如集合1，1，2，1，2,其中成员有，又有以，为元素的集合。因此，尽管集合与其成员是两个截然不同的概念，但一个集合完全可以成为另一个集合的元素。 通常用大写拉丁字母A，B，C等表示集合，用小写字母a, b, c等表示集合的元素。但是，这种表示形式不是绝对的。a作为A的元素时，并不排斥a作为集合的可能性。同样，集合A也可能是别的集合的元素。 元素对于集合的隶属关系是集合论的另一基本概念。当对象a是集合A的成员时，称a属于A，记为 aA 当对象a不是集合A的成员时，称a不属于A，记为 Ø(aA)或aÏA 对任何对象a和任何集合A，或者aÎA或者

7、aÏA,两者恰居其一。这正是集合对其元素的“确定性”要求。 集合的规定方式有三种： （l）列举法：规定一个集合A时，将A中元素一列举，或列出足够多的元素以反映A中成员的特征，表示形如 A a1，a2，an或 A =a1，a2，a3, （2）描述法；规定一个集合A时，将A中元素的特征用一个谓词公式来描述，表示形如 A =x | P(x)或 A =x : P(x)其意义为：集合A由且仅由满足谓词公式P(x)的对象所组成，即 aÎA 当且仅当 P(a) 真注意：Ax | P(x)中x为约束变元，它仅仅是集合的符号表示的一部分，没有独立的意义，A中完全可能没有x这个元素。对x可以改

8、名，却不能代入。即x | P(x) = y | P(y)（P中无约束变元y），但5 | P(5)没有意义。 （3）归纳法：在3.3节中详细介绍。在前面几章里，我们已用归纳法定义了公式集合、个体项集合等。 例3.2 （1）0，lx½x0xl （2）N = 0，1，2，3， = x½x是自然数 I+ = 1，2，3， = x½x是正整数 （3）Nn0，1，2，n-1 x½ xÎN0xn （4）I ，-3，-2，-l，0，l，2，3， =x½x是整数 （5）E = ，-4，-2，0，2，4，x½x是偶数 = x½x

9、06;I2½x (2½x表示2整除x) （6）前n个自然数集合的集合 = 0,0 , 1，0，1，2， = x½x= Nn LnÎI+ = Nn ½nÎ I+ （7）没有任何元素的特定集合（称为空集）记为Æ Æx½x¹x 定义3.1 空集和只含有有限多个元素的集合称为有限集（finite sets），否则称为无限集（infinite sets）。集合中成员的个数称为集合的基数（cardinality）（无穷集合的基数概念将在以后重新严格定义）。集合A的基数表示为 | A |。 例3.3 例42之

10、（l）(3)（7）是有限集，其它为无限集。|0，1|=2，| Æ |0，|Æ| = 1注意a¹a，前者为一对象，后者为仅含该对象的单元素集合；Æ ¹Æ，前者是没有元素的集合，后者是恰含一个元素空集的单元素集。 集合论依赖于三大基本原理：外延公理（extensionality axiom）、概括公理（comprehension axiom）和正规公理（regularity axiom）。它们从根本上规定了集合概念的意义。外延公理：两个集合 A和 B相等当且仅当它们具有相同的元素。即对任意集合A，B。 A = B «"

11、x(xÎA«xÎB) 例3.4 根据外延公理， 0，l l，0xx(x2 - 2x l) 0 = x êx1x0因此，外延公理事实上刻划了集合的下列特性：集合成员的“相异性”、“无序性”，及集合表示形式的不唯一性。 概括公理: 对任意个体域，任一谓词公式都确定一个以该域中的对象为元素的集合。即对给定个体域U，对任意谓词公式P(x)，存在集合s，使得 Sx êxÎUP(x) 概括公理规定了集合成员的确定性,以及集合的描述法表示的理论依据，它还规定了空集的存在性, P(x)永假时集合S为空集。 康脱的朴素集合论不是这样表述概括原理的，他描

12、述如下，并称之为抽象原理（abstraction principle）。 抽象原理: 对任意谓词公式P(x)，均存在集合S，使得 = xïP(x) 朴素集合论的问题就出在这里。罗素（Russell）指出；滥用抽象原理导致集合论悖论。 罗素悖论:考虑谓词xÏx据抽象原理；有集合B，使 BxïxÏx 现在问；“BÎB吗？”若回答是，则B满足谓词xÏx,即BÏB;若回答否，则B不满足谓词xÏx，从而有Ø(BÏB),即BÎB。于是有 BÎB «BÏB 因此，在我们

13、今后的讨论中，总是约定有一个个体域作为讨论的基础，它被称为全集，常记为U。虽然我们也用Sx êp(x) 表示P（x）所规定的集合（正像先前已指出的那样），但它总被认为是 Sx êxÎUP(x)的简写，因为约定xÎU恒真，从而从合取式中省略xÎU。 正规公理：不存在集合A1, A2 , A3 ,，使得 ÎA3 Î A2 ÎA1正规公理的一个自然推论是：对任何集合A，A¹A（否则有ÎAÎAÎA）。从而规定了集合A与A的不同层次性,因而正规公理也就规定了集合不能是自己的成员 定义3

14、.2 集合A称为集合B的子集合（或子集，subsets），如果A的每一个元素都是B的元素，即 "x(xÎA®xÎB)A是B的子集，表示为AÍB（或BÊA），读作“A包含于B”（或“B包含A”）。 集合之间的子集关系或包含关系是集合之间最重要的关系之一。读者必须彻底弄清子集关系和隶属关系这两个完全不同的概念。例3.5 a，b Í a，c，b，d，a，b，c Í a，b，c，a Í a，b，但a Ëa，b，只有a Î a，b 。不过存在这样两个集合，其中一个既是另一个的子集、又是它的元素。

15、例如，lÎ 1，l，且1Í 1，l。 关于子集关系我们有以下定理和定义（以下 Û 表示术语“当且仅当”）。 定理3.1对任意集合A，B，AB当且仅当A Í B且B Í A 。特别地，对任意集合A, A Í A 。 证 AB Û "x (xÎA«xÎB) Û "x (xÎAxÎB)(xÎBxÎA) Û "x(xÎAxÎB)"x (xÎBxÎA) Û

16、AÍBBÍA定理3.2 对任意集合A，A Í U。证 因xÎU恒真，因而"x(xÎA®xÎU)恒真，故A Í U。 定理3.3 设A，B，C为任意集合，若A Í B , B Í C，则A Í C。 证 设x为A中任一元素由于A Í B，因此xÎB;又因为B Í C，故xÎC。这就是说，A的所有元素都是C的成员，故A Í C。 定理3.4 对任何集合A，Æ Í A。证 因xÎÆ恒假，故&q

17、uot;x(xÎÆ® xÎA)恒真，即Æ Í A恒真。定理3.5 空集是唯一的。证 设有空集Æ1, Æ 2据定理3.4，应有Æ1 Í Æ2和Æ2 Í Æ1，从而由定理3.1知Æ1= Æ2。 定理 3.6 设 A 为一有限集合，| A | = n，那么 A的子集个数为2n。 证 A有子集：没有元素的子集 Æ，计 个（ 1）; 恰含A 中一个元素的子集计 个,恰含A中两个元素的子集计 个, , 恰含A中n个元素的子集计 个。因此A

18、的子集个数为 +=2n 设集合A = 1，Æ, 1, 3 , 则A有23 = 8个子集，分别为：Æ，1，Æ，1，3，1，Æ，1，1，3，Æ，1，3，1，Æ，1，3。 定义3.3 集合 A称为集合 B的真子集，如 AÍB且A ¹ B。“A是B的真子集”记为AÌB。显然，Æ是所有非空集合的真子集。3.2 集合运算集合运算指以集合为运算对象、以集合为值的运算。 定义3.4 设A，B为任意集合。 （l） AB称为A与B的并集（union set），定义为 ABxxAxB称为并运算。 （2） A

19、B称为A与B的交集（intersection set），定义为 AB =xxAx B称为交运算。 （3） A-B称为A与B的差集（difference set），定义为 A-BxxAx Ï B- 称为差运算。 （4）A称为A的补集（complement set），定义为 A=U-A =x | xÏA称为补运算，它是一元运算，是差运算的特例。 例3.6 设U0, 1，2，3，9，A = 2，4，B = 4, 5, 6 ,7， C = 0，8，9，Dl, 2, 3： AÈB2，4，5，6，7， AÈBÈCÈDU AÇB 4，A&

20、#199;C= Æ A-B = 2，B-A =5，6，7，A- C =2，4 A =0，l，3，5，6，7，8，9，B0，l，2，3，8，9定理3.7 设A，B，C为任意集合，*代表运算È或Ç，那么 （l）A*AA （等幂律） （2）A*B = B*A （交换律） （3）A*（B*C）= （A*B）*C （结合律）（4）AÈÆ A， AÈU = U AÇÆ = Æ， AÇU = A （5）AÈ(BÇC)=(AÈB) Ç(AÈC) AÇ(

21、BÈC)(AÇB)È(AÇC) （分配律） （6）AÇ( AÈB)=A AÈ(AÇB) =A （吸收律） 证 （1），（2），（3），（5），（6）由逻辑运算，的相应定律立得。现证（4）。 对任意x， xÎAÈÆ Û xÎAxÎÆ Û xÎA（xÎÆ为假）故 AÈÆA 。而 xÎAÇÆ Û xÎAxÎÆ Û

22、xÎÆ（ xÎÆ为假）故 AÇÆ = Æ 。其余两式请读者补证。 定理 3.8 对任意集合 A，B，C， （l） A AÆ， A ÆA， A U = Æ （2） A (BÈC)(A B)Ç(A C) A (BÇC)(A B)È(A C) 证 我们只证（2）中第一式，其余留给读者， 对任意x， xÎ A (BÈC) Û xÎ A(xÎBÈC) Û xÎ A(xÎBx&#

23、206;C) Û xÎ AxÏBxÏC Û (xÎ AxÏB)(xÎ AxÏC) Û (xÎ A B)(xÎ A C) Û xÎ(A B)Ç(A C) 故A (BÈC)(A B)Ç(A C) 。 定理3.9 对任意集合A，B （1） AA , UÆ , ÆU（2） AÈAU , AÇAÆ （3） (AÈB)AÇ B (AÇB)AÈ B（4

24、） A BAÇB 证 （1）,（2）,（4）易证，现证（3）的第一式。 (AÈB)U (AÈB) (U A)Ç(U B) AÇ B 定理3.10 对任意集合A , B , C , D， （1）A Í AÈB （2）AÇB Í A （3）A B Í A （4）A Í B, A B = Æ, AÈB = B , AÇB = A 四命题等价。 （5）若A Í B,则BÍ A 证（1），（2），（3）,（5）易证，我们仅证明（4）。 设（4）中

25、4个命题为P, Q, R, S ，我们来证明PÞQÞRÞSÞP,从而证实4命题等价。 （PÞQ）：设A B ¹ Æ，aÎA B，即aÎA，但aÏB，这与A Í B矛盾故A B = Æ 。得证。 （QÞR）：为证AÈB = B ，需证 1）B Í AÈB 。但由定理3.10之(1)，此已得证。 2）AÈB Í B 。为此设x为AÈB 中任一元素，从而xÎA或xÎB。当xÎB时目的

26、已达到。当xÎA时，若xÏB，则xÎA B，与A B = Æ 矛盾。故xÎB。总之，AÈB中元素x必为B中元素，2）又得证。综合 1）、 2）可知AÈB = B 。 （RÞS）：因AÈB = B，故 AÇB = AÇ(AÈB) =A(吸收律) （SÞP）：设AÇB = A。为证AÍB，又设x为A中任一元素。由此及AÇB = A，可知 xÎ B。故 AÍB得证。 定理3.11 对任意集合A，B若它们满足 （l）A

27、00;BU （2）AÇBÆ 那么BA证 BBÈÆ BÈ (AÇA) (BÈA)Ç (BÈA) UÇ (BÈA) (AÈA)Ç(BÈA) (AÇB)ÈA ÆÈA A本定理的证明使用了集合等式证明的第三种方法（回忆前两种方法:（a）利用谓词演算，（b）自然语言叙述的数学证明），利用已知等式进行推演。这种方法简明，但难度较大。本定理用第二种方法来证较繁锁，但思路清晰，易掌握。先证BÍ A。设xÎB，由于

28、AÇB=Æ，故xÏA,即xÎA，BÍA得证。再证AÍB。设xÎA，则xÏA;由于AÈBU，故必有xÎB，AÍB又得证。因此BA。 幂集运算和广义并、交运算 定义 3.5 对任意集合 A，(A)称为A的幂集（power sets），定义为 (A)x|xÍA即A的全体子集构成A的幂集。由于，ÆÍA, AÍA故必有ÆÎ(A) , AÎ(A)。例3.7 （1）A=a，b时，(A)Æ，a，b，a，b。 （2）A=0，1，2时，(A)Æ，0，1，2，0，1，0，2，1，20，1，2。 我们曾指出，当集合A的基数为n时，A有2n个子集，因此|(A)|= 2n 。 定理3.12 设A,B为任意集合, AÍB当且仅当(A) Í(B) 。 证 先证必要性。设AÍB。为证(A) Í(B)，又设X为(A)中任一元素，从而XÍA。由于AÍB，故XÍB，从而有XÎ(B)。(A)