集合及其运算1

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

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

3、现代数学中重要的组成部分。鉴于离散数学学科所要达到的目的，我们不准备引入复杂、抽象的集合论形式系统，但我们将借鉴公理化集合论的思想，以避免悖论；同时将利用已有的形式化知识，使集合论的介绍更加简明、深入。 集合及其运算的有关基础知识，在中学课本上已有介绍，因此我们在第一篇里已经使用了一些集合论术语。但是，为了知识的系统性和完整性，本章仍然要对这些知识作扼要的介绍，有些方面的讨论较之中学数学要更宽广、更深入、更系统, 因而抽象性抽象性和理论性更强。 3.1 集合的基本概念3.1.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)或aA 对任何对象a和任何集合A，或者aA或者aA,两者恰居其

7、一。这正是集合对其元素的“确定性”要求。 集合的规定方式有三种： （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)的对象所组成，即 aA 当且仅当 P(a) 真注意：Ax | P(x)中x为约束变元，它仅仅是集合的符号表示的一部分，没有独立的意义，A中完全可能没有x这个元素。对x可以改名，却不能代入。即x | P(x) =

8、y | P(y)（P中无约束变元y），但5 | P(5)没有意义。 （3）归纳法：在3.3节中详细介绍。在前面几章里，我们已用归纳法定义了公式集合、个体项集合等。 例3.2 （1）0，lxx0xl （2）N = 0，1，2，3， = xx是自然数 I+ = 1，2，3， = xx是正整数 （3）Nn0，1，2，n-1 x xN0xn （4）I ，-3，-2，-l，0，l，2，3， =xx是整数 （5）E = ，-4，-2，0，2，4，xx是偶数 = xxI2x (2x表示2整除x) （6）前n个自然数集合的集合 = 0,0 , 1，0，1，2， = xx= Nn LnI+ = Nn n I+

9、（7）没有任何元素的特定集合（称为空集）记为 xxx 定义3.1 空集和只含有有限多个元素的集合称为有限集（finite sets），否则称为无限集（infinite sets）。集合中成员的个数称为集合的基数（cardinality）（无穷集合的基数概念将在以后重新严格定义）。集合A的基数表示为 | A |。 例3.3 例42之（l）(3)（7）是有限集，其它为无限集。|0，1|=2，| |0，| = 1注意aa，前者为一对象，后者为仅含该对象的单元素集合； ，前者是没有元素的集合，后者是恰含一个元素空集的单元素集。 3.1.2 外延公理、概括公理和正规公理集合论依赖于三大基本原理：外延公理

10、（extensionality axiom）、概括公理（comprehension axiom）和正规公理（regularity axiom）。它们从根本上规定了集合概念的意义。外延公理：两个集合 A和 B相等当且仅当它们具有相同的元素。即对任意集合A，B。 A = B x(xAxB) 例3.4 根据外延公理， 0，l l，0xx(x2 - 2x l) 0 = x x1x0因此，外延公理事实上刻划了集合的下列特性：集合成员的“相异性”、“无序性”，及集合表示形式的不唯一性。 概括公理: 对任意个体域，任一谓词公式都确定一个以该域中的对象为元素的集合。即对给定个体域U，对任意谓词公式P(x)，存

11、在集合s，使得 Sx xUP(x) 概括公理规定了集合成员的确定性,以及集合的描述法表示的理论依据，它还规定了空集的存在性, P(x)永假时集合S为空集。 康脱的朴素集合论不是这样表述概括原理的，他描述如下，并称之为抽象原理（abstraction principle）。 抽象原理: 对任意谓词公式P(x)，均存在集合S，使得 = xP(x) 朴素集合论的问题就出在这里。罗素（Russell）指出；滥用抽象原理导致集合论悖论。 罗素悖论:考虑谓词xx据抽象原理；有集合B，使 Bxxx 现在问；“BB吗？”若回答是，则B满足谓词xx,即BB;若回答否，则B不满足谓词xx，从而有(BB),即BB。

12、于是有 BB BB 因此，在我们今后的讨论中，总是约定有一个个体域作为讨论的基础，它被称为全集，常记为U。虽然我们也用Sx p(x) 表示P（x）所规定的集合（正像先前已指出的那样），但它总被认为是 Sx xUP(x)的简写，因为约定xU恒真，从而从合取式中省略xU。 正规公理：不存在集合A1, A2 , A3 ,，使得 A3 A2 A1正规公理的一个自然推论是：对任何集合A，AA（否则有AAA）。从而规定了集合A与A的不同层次性,因而正规公理也就规定了集合不能是自己的成员3.1.3 子集合 定义3.2 集合A称为集合B的子集合（或子集，subsets），如果A的每一个元素都是B的元素，即 x

13、(xAxB)A是B的子集，表示为AB（或BA），读作“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 。不过存在这样两个集合，其中一个既是另一个的子集、又是它的元素。例如，l 1，l，且1 1，l。 关于子集关系我们有以下定理和定义（以下 表示术语“当且仅当”）。 定理3.1对任意集合A，B，AB当且仅当A B且B A 。特别地，对任意集合A, A A 。 证 AB x (xAxB) x (xAxB

14、)(xBxA) x(xAxB)x (xBxA) ABBA定理3.2 对任意集合A，A U。证 因xU恒真，因而x(xAxU)恒真，故A U。 定理3.3 设A，B，C为任意集合，若A B , B C，则A C。 证 设x为A中任一元素由于A B，因此xB;又因为B C，故xC。这就是说，A的所有元素都是C的成员，故A C。定理3.l和定理3.3的证明方法、形式完全不同，前者利用谓词演算知识，后者为通常数学证明，两者各有利弊，读者都应熟悉之。 定理3.4 对任何集合A， A。证 因x恒假，故x(x xA)恒真，即 A恒真。定理3.5 空集是唯一的。证 设有空集1, 2据定理3.4，应有1 2和2

15、 1，从而由定理3.1知1= 2。 定理 3.6 设 A 为一有限集合，| A | = n，那么 A的子集个数为2n。 证 A有子集：没有元素的子集 ，计 个（ 1）; 恰含A 中一个元素的子集计 个,恰含A中两个元素的子集计 个, , 恰含A中n个元素的子集计 个。因此A的子集个数为 +=2n 设集合A = 1，, 1, 3 , 则A有23 = 8个子集，分别为：，1，1，3，1，1，1，3，1，3，1，1，3。 定义3.3 集合 A称为集合 B的真子集，如 AB且A B。“A是B的真子集”记为AB。显然，是所有非空集合的真子集。3.2 集合运算集合运算指以集合为运算对象、以集合为值的运算。

16、3.2.1 并、交、差、补运算定义3.4 设A，B为任意集合。 （l） AB称为A与B的并集（union set），定义为 ABxxAxB称为并运算。 （2） AB称为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 | xA称为补运算，它是一元运算，是差运算的特例。 例3.6 设U0, 1，2，3，9，A = 2，4，B = 4, 5, 6 ,7， C = 0，8，

17、9，Dl, 2, 3： AB2，4，5，6，7， ABCDU AB 4，AC= 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， AU = U A = ， AU = A （5）A(BC)=(AB) (AC) A(BC)(AB)(AC) （分配律） （6）A( AB)=A A(AB) =A （吸收律） 证 （1），（2），（3），（5），（6

18、）由逻辑运算，的相应定律立得。现证（4）。 对任意x， xA xAx xA（x为假）故 AA 。而 xA xAx x（ x为假）故 A = 。其余两式请读者补证。 定理 3.8 对任意集合 A，B，C， （l） A A， A A， A U = （2） A (BC)(A B)(A C) A (BC)(A B)(A C) 证 我们只证（2）中第一式，其余留给读者， 对任意x， x A (BC) x A(xBC) x A(xBxC) x AxBxC (x AxB)(x AxC) (x A B)(x A C) x(A B)(A C) 故A (BC)(A B)(A C) 。 定理3.9 对任意集合A，B

19、 （1） AA , U , U（2） AAU , AA （3） (AB)A B (AB)A B（4） A BAB 证 （1）,（2）,（4）易证，现证（3）的第一式。 (AB)U (AB) (U A)(U B) A B 定理3.10 对任意集合A , B , C , D， （1）A AB （2）AB A （3）A B A （4）A B, A B = , AB = B , AB = A 四命题等价。 （5）若A B,则B A 证（1），（2），（3）,（5）易证，我们仅证明（4）。 设（4）中4个命题为P, Q, R, S ，我们来证明PQRSP,从而证实4命题等价。 （PQ）：设A B ，aA

20、 B，即aA，但aB，这与A B矛盾故A B = 。得证。 （QR）：为证AB = B ，需证 1）B AB 。但由定理3.10之(1)，此已得证。 2）AB B 。为此设x为AB 中任一元素，从而xA或xB。当xB时目的已达到。当xA时，若xB，则xA B，与A B = 矛盾。故xB。总之，AB中元素x必为B中元素，2）又得证。综合 1）、 2）可知AB = B 。 （RS）：因AB = B，故 AB = A(AB) =A(吸收律) （SP）：设AB = A。为证AB，又设x为A中任一元素。由此及AB = A，可知 x B。故 AB得证。 定理3.11 对任意集合A，B若它们满足 （l）AB

21、U （2）AB 那么BA证 BB B (AA) (BA) (BA) U (BA) (AA)(BA) (AB)A A A本定理的证明使用了集合等式证明的第三种方法（回忆前两种方法:（a）利用谓词演算，（b）自然语言叙述的数学证明），利用已知等式进行推演。这种方法简明，但难度较大。本定理用第二种方法来证较繁锁，但思路清晰，易掌握。先证B A。设xB，由于AB=，故xA,即xA，BA得证。再证AB。设xA，则xA;由于ABU，故必有xB，AB又得证。因此BA。 3.2.2 幂集运算和广义并、交运算 定义 3.5 对任意集合 A，(A)称为A的幂集（power sets），定义为 (A)x|xA即A的全体子集构成A的幂集。由于，A, AA故必有(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为任意集合, AB当且仅当(A) (B) 。 证 先证必要性。设AB。为证(A)