第三章集合及其运算(精)

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

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

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

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

5、级组成一集合，其组成对象是班级，而不是学生，因为集合中对象是整体识别的。（ 5）“好书”的全体不构成集合，因为难以对每一本书的好坏作出确定的判断。（ 6）方程 x(x 2-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 ，记为a

7、A当对象a 不是集合A 的成员时，称a 不属于 A ，记为(a A) 或 aA对任何对象a 和任何集合A ，或者 a A 或者 a A , 两者恰居其一。 这正是集合对其元素的定性 ”要求。集合的规定方式有三种：（ l）列举法：规定一个集合A 时，将 A 中元素 一列举，或列出足够多的元素以反映中成员的特征，表示形如“确AA a1，a2， ， an或 A = a1， a2， a3, （ 2）描述法；规定一个集合 A 时，将 A 中元素的特征用一个谓词公式来描述，表示形如A = xP(x) 或A = x : P(x)其意义为：集合A 由且仅由满足谓词公式P(x) 的对象所组成，即a A当且仅当P

8、(a) 真注意： A xP(x) 中 x 为约束变元， 它仅仅是集合的符号表示的一部分，没有独立的意义，A 中完全可能没有x 这个元素。对x 可以改名，却不能代入。即xP(x) = yP(y) （ P 中无约束变元y），但 5P(5) 没有意义。（ 3）归纳法：在 3.3 节中详细介绍。在前面几章里，我们已用归纳法定义了公式集合、个体项集合等。例 3.2 （ 1） 0 ， l xx0 x l（ 2） N = 0 ， 1， 2，3， = xx 是自然数 I+ = 1 ， 2， 3， = xx 是正整数 （ 3） Nn 0 ， 1， 2， ， n-1 xxN 0 x n（ 4） I ， -3， -

9、2，-l ， 0， l ， 2， 3， = x x 是整数（ 5） E = ， -4， -2， 0， 2，4， xx 是偶数 （ 6）前= xxI 2 x(2 x 表示n 个自然数集合的集合2 整除x)= 0,0 , 1= xx= N n= N nn， 0，1，2 ， nI+ I +（ 7）没有任何元素的特定集合（称为空集 ）记为 xx x定义 3.1空集和只含有有限多个元素的集合称为有限集 （ finite sets），否则称为 无限集（ infinite sets）。集合中成员的个数称为集合的基数 （ cardinality ）（无穷集合的基数概念将在以后重新严格定义）。集合 A 的基数表

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

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

12、:对任意谓词公式P(x) ，均存在集合S，使得 = x P(x)朴素集合论的问题就出在这里。罗素（Russell ）指出；滥用抽象原理导致集合论悖论。罗素悖论 : 考虑谓词x x据抽象原理；有集合B，使B x xx现在问；“BB 吗？”若回答是，则B 满足谓词xx,即 BB; 若回答否，则B 不满足谓词x x，从而有 (B B),即 B B。于是有BB BB因此，在我们今后的讨论中，总是约定有一个个体域作为讨论的基础，它被称为全集，常记为 U。虽然我们也用 S xp(x) 表示 P（ x）所规定的集合 （正像先前已指出的那样） ，但它总被认为是S x xU P(x)的简写，因为约定 x U 恒

13、真，从而从合取式中省略x U 。正规公理 ：不存在集合 A 1, A2 , A3 , ，使得A3 A2 A1正规公理的一个自然推论是：对任何集合A ，AA（否则有 AAA）。从而规定了集合 A 与 A 的不同层次性, 因而正规公理也就规定了集合不能是自己的成员子集合定义 3.2集合 A 称为集合B 的子集合 （或子集， subsets），如果 A 的每一个元素都是B 的元素，即x(xAxB)A 是 B 的子集，表示为AB（或 BA），读作“ A 包含于 B”（或“ B 包含 A ”）。集合之间的子集关系或包含关系是集合之间最重要的关系之一。读者必须彻底弄清子集关系和隶属关系这两个完全不同的概念

14、。例 3.5 a ，ba ，c，b，d ，a ，b，ca， b，c ，aa ， b ，但 aa ，b ，只有 aa ， b。不过存在这样两个集合，其中一个既是另一个的子集、又是它的元素。例如， l 1， l ，且 1 1， l 。关于子集关系我们有以下定理和定义（以下表示术语“当且仅当” ）。定理 3.1对任意集合 A ， B， A B 当且仅当 AB 且 BA 。特别地，对任意集合A,AA 。证A Bx (xAxB)x (xA xB) (x B x A)x(xA xB) x (x B xA)ABBA定理 3.2对任意集合A， AU 。证 因 xU 恒真，因而x(xAxU)恒真，故 AU。定理

15、 3.3设 A， B， C 为任意集合，若 AB , BC，则 AC。证 设 x 为 A 中任一元素由于AB ，因此 xB; 又因为 BC，故 xC。这就是说，A 的所有元素都是 C 的成员，故 AC。定理 3.l和定理3.3 的证明方法、 形式完全不同， 前者利用谓词演算知识， 后者为通常数学证明，两者各有利弊，读者都应熟悉之。定理 3.4对任何集合 A ，A。证 因 x恒假，故x(xxA) 恒真，即A 恒真。定理 3.5空集是唯一的。证 设有空集1, 2据定理3.4，应有 12 和21，从而由定理3.1 知 1=2。定理 3.6设 A为一有限集合，An，那么A 的子集个数为 2n。证 A

16、有子集：没有元素的子集，计 C n0个（ Cn0 1）; 恰含 A 中一个元素的子集计Cn1个 ,恰含 A 中两个元素的子集计Cn2个 ,恰含 A 中 n 个元素的子集计Cnn 个。因此 A的子集个数为Cn0+Cn1 C nn =2 n设集合 A=1， ,1,3,则 A 有 23 = 8 个子集，分别为：，1 ， ，1 ，3，1， ，1 ，1 ，3 ，1， 3 ，1，1，3 。定义 3.3集合 A 称为集合B 的真子集 ，如 AB 且 AB。“A 是 B 的真子集”记为AB。显然，是所有非空集合的真子集。3.2集合运算集合运算指以集合为运算对象、以集合为值的运算。并、交、差、补运算定义 3.4

17、 设 A ，B 为任意集合 。（ l） A B 称为 A 与 B 的并集（ union set），定义为A B x x A x B称为 并运算 。（ 2） A B 称为 A 与 B 的交集 （ intersection set），定义为A B =x x A x B称为 交运算 。（ 3） A- B 称为 A 与 B 的差集 （ difference set），定义为A- B x x A xB- 称为 差运算 。（ 4）A 称为 A 的补集 （complement set），定义为A =U - A = xxA 称为补运算 ，它是一元运算，是差运算的特例。例 3.6 设 U0, 1 ，2，3， ，

18、 9，A = 2 ， 4，B = 4, 5, 6 ,7 ， C = 0 ，8， 9，D l, 2, 3 ：AB 2，4，5， 6，7， ABCDUAB 4，AC=A-B=2，B- A =5，6，7，A-C = 2，4A =0， l， 3， 5，6， 7， 8， 9， B 0， l， 2， 3， 8， 9定理 3.7设 A， B， C 为任意集合， * 代表运算或，那么（ l） A*A A（等幂律）（ 2） A*B = B*A（交换律）（3）A* （B*C ）=（A*B ）*C（结合律）（4）AA，A U=UA= ，AU = A（5）A( BC)=(AB)( AC)A (B C) (AB) (A

19、 C)（分配律）（6）A( AB)=AA(AB) =A（吸收律）证 （ 1），（ 2），（ 3），（ 5），（6）由逻辑运算，的相应定律立得。现证（4）。对任意 x，xAxA xxA （ x为假）故AA。而xAxA xx（x为假）故 A=。其余两式请读者补证。定理 3.8对任意集合 A ，B， C，（ l）AA ， A A， AU=（ 2）A (BC) (A B)(A C)A (BC) (A B)(A C)证 我们只证（ 2）中第一式，其余留给读者，对任意x，xA (BC)xA (xBC)xA (xB xC)xA xB xC(xA xB) (xA xC)(xA B) (xA C)x (A B)

20、 (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(AB) A B（ 4） A BA B证 （ 1） ,（ 2） ,（ 4）易证，现证（3）的第一式。(AB) U (AB) (U A) (U B)AB定理 3.10 对任意集合A,B,C,D，（1）AAB（2）ABA（3）A BA（4）AB, A B =,AB=B,AB =A 四命题等价。（5）若 AB,则 BA证（ 1），（ 2），（ 3）,（ 5）易证，我们仅证明（4）。设（ 4）中 4 个命题为 P, Q, R,

21、 S ，我们来证明PQR SP,从而证实 4 命题等价。（ PQ）：设 A B，a A B ，即 a A ，但 aB，这与 AB矛盾故 AB= 。得证。（ QR）：为证 AB=B ，需证1） BAB 。但由定理 3.10 之 (1) ，此已得证。2）ABB 。为此设 x 为 AB中任一元素，从而 xA 或 x B。当 x B 时目的已达到。当 xA 时，若 x B，则 x AB，与 A B =矛盾 。故 xB 。总之， A B 中元素 x必为 B 中元素， 2）又得证。综合1）、 2）可知 AB = B。（ RS）：因 A B=B，故AB = A(AB) =A( 吸收律 )（ SP）：设 A

22、B = A。为证 AB ，又设 x 为 A 中任一元素。 由此及 A B = A ，可知 xB。故 AB 得证。定理 3.11 对任意集合 A， B若它们满足（ l） A B U （ 2） A B那么 BA证BBB(AA)(BA)(BA)U(BA)(AA)(BA) (AB)A A A 本定理的证明使用了集合等式证明的第三种方法（回忆前两种方法（: a）利用谓词演算，（b）自然语言叙述的数学证明），利用已知等式进行推演。这种方法简明，但难度较大。本定理用第二种方法来证较繁锁，但思路清晰， 易掌握。 先证 BA 。设 xB ，由于 AB=，故 xA, 即 xA ，BA 得证。再证A B 。设 xA

23、 ，则 xA; 由于AB U ，故必有 xB ，AB 又得证。因此B A。幂集运算和广义并、交运算定义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，2 0，1， 2。我们曾指出，当集合 A 的基数为 n 时， A 有 2n 个子集，因此 | (A) |=2n 。定理 3.12 设 A,B 为任意集合 , A

24、 B 当且仅当 (A) (B)。证先证必要性。 设 AB。为证 (A) (B) ，又设 X 为 (A) 中任一元素， 从而 XA 。由于 AB，故 X B，从而有X (B) 。 (A) (B) 得证再证充分性。设 (A) (B) ，反设 AB 不成立，那么至少有一元素a A ，但 aB 。考虑单元素集合 a， a (A) ，但 a (B) ，与 (A) (B) 矛盾， A B 得证。为了讨论广义的并、交运算，需要以下术语。定义 3.6 若集合 C 的每个元素都是集合，则称 C 为集合族 （ collections）。若集合族 C 可表示为C = Sd|d D 则称 D 为集合族的 标志集 （ index set）。例 3.8 C = 0， 0， 1，0，