集合及其运算1

第三章集合及其运算集合论产生于16世纪末。当时，只是由于微积分学的需要，人们只对数集进行了研究。19世纪末，即1876一1883年间，康托尔（GaorgeCantor1845一1918年,德国数学家）对任意元素的集合进行了系统的研究，提出了无限集的势、序型等概念，奠定了集合论的基础。康托尔被公认为集合论的创始人。集合论是一门研究数学基础的学科，它试图从一个比“数”更简单的概念——集合（sets）出发，定义数及其运算，进而发展到整个数学。在这一点上它取得了极大的成功。我们介绍集合论则不仅因为此，而且因为计算机科学及应用的研究，也和集合论理论有着极密切的关系。集合不仅可用来表示数及其运算，更可以用于非数值信息的表示和处理。像数据的删节、插入、排序，数据间关系的描述，数据的组织和查询都很难用传统的数值计算来处理，但却可以用集合运算来实现。德国数学家康托尔（cantor）开创的集合论被称为朴素集合论，因为他没有对集合论作完全形式的刻划，从而导致了理论的不一致（产生了悖论，见3.1.2节）。为弥补朴素集合论的不足，本世纪初出现了各种公理化的集合论体系。1904--1908年间，策墨罗（Zormelo）给出了第一个集合论的公理系统。之后，集合论迅速发展，逐步形成公理化集合论和抽象集合论；并且在集合论的基础上,实变函数论、泛函分析、概率论和信息论等许多数学学科，先后建立起来。集合论已成为现代数学中重要的组成部分。鉴于离散数学学科所要达到的目的，我们不准备引入复杂、抽象的集合论形式系统，但我们将借鉴公理化集合论的思想，以避免悖论；同时将利用已有的形式化知识，使集合论的介绍更加简明、深入。集合及其运算的有关基础知识，在中学课本上已有介绍，因此我们在第一篇里已经使用了一些集合论术语。但是，为了知识的系统性和完整性，本章仍然要对这些知识作扼要的介绍，有些方面的讨论较之中学数学要更宽广、更深入、更系统,因而抽象性抽象性和理论性更强。3.1集合的基本概念3.1.1集合及其元素集合是作为整体识别的、确定的、互相区别的一些对象的总体。严格地说这算不得集合的定义，因为“总体”只是“集合”一词的同义反复。在集合论中，集合是一个不作定义的原始概念（就像几何学中的点、线、面等概念）。不过，上述关于集合概念的描述，有益于对它的内涵作直观的理解和认识。例3.1（1）“南京大学全体学生”为一集合，其组成对象是学生。（2）“全体自然数0，1，2，3，…”为一集合，其组成对象是各自然数。（注意，我们所说的自然数与中学课本定义的自然数略有不同,这是计算机界目前的一个流行做法,让自然数有别于正整数,包括数0。）（3）获1988年诺贝尔文学奖的作家构成一个集合，尽管它只有一个对象——埃及作家纳吉布•马夫兹。（4）育才中学的所有班级组成一集合，其组成对象是班级，而不是学生，因为集合中对象是整体识别的。（5）“好书”的全体不构成集合，因为难以对每一本书的好坏作出确定的判断。（6）方程x(x2-2x+1)=0的所有根组成一个集合，它只有一个对象0和一个（而不是两个）对象1，因为集合中对象是相互区别的。（7）方程x2+x+1=0的根组成一个集合。当讨论复数时，它由两个对象组成；当讨论实数时，它是一个没有任何对象的特定集合。组成集合的对象称为集合的成员（members）或元素（elements）请注意，这里“对象”的概念是相当普遍的，可以是任何具体的或抽象的客体，还可以是集合，因为人们有时以集合为其讨论的对象，而又需涉及它们的一个总体——以集合为其元素的集合。例如，育才中学所有班级的全体构成的集合，以学生班级集体为其元素;又如集合{1，{1，2}，{1}，2},其中成员有１，２，又有以１，２为元素的集合。因此，尽管集合与其成员是两个截然不同的概念，但一个集合完全可以成为另一个集合的元素。通常用大写拉丁字母A，B，C等表示集合，用小写字母a,b,c等表示集合的元素。但是，这种表示形式不是绝对的。a作为A的元素时，并不排斥a作为集合的可能性。同样，集合A也可能是别的集合的元素。元素对于集合的隶属关系是集合论的另一基本概念。当对象a是集合A的成员时，称a属于A，记为a∈A当对象a不是集合A的成员时，称a不属于A，记为(a∈A)或aA对任何对象a和任何集合A，或者aA或者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)真注意：A＝{xP(x)}中x为约束变元，它仅仅是集合的符号表示的一部分，没有独立的意义，A中完全可能没有x这个元素。对x可以改名，却不能代入。即{xP(x)}={yP(y)}（P中无约束变元y），但{5P(5)}没有意义。（3）归纳法：在3.3节中详细介绍。在前面几章里，我们已用归纳法定义了公式集合、个体项集合等。例3.2（1）{0，l}＝{xx＝0∨x＝l}（2）N={0，1，2，3，…}={xx是自然数}I+={1，2，3，…}={xx是正整数}（3）Nn＝{0，1，2，…，n-1}＝{xxN∧0≤x＜n}（4）I＝{…，-3，-2，-l，0，l，2，3，…}=｛xx是整数｝（5）E={…，-4，-2，0，2，4，…}＝{xx是偶数}={xxI∧2x}(2x表示2整除x)（6）前n个自然数集合的集合={{0},{0,1}，{0，1，2}，…}={xx=NnnI+}={NnnI+}（7）没有任何元素的特定集合（称为空集）记为＝{}＝{xxx}定义3.1空集和只含有有限多个元素的集合称为有限集（finitesets），否则称为无限集（infinitesets）。集合中成员的个数称为集合的基数（cardinality）（无穷集合的基数概念将在以后重新严格定义）。集合A的基数表示为A。例3.3例4．2之（l）(3)（7）是有限集，其它为无限集。{0，1}=2，＝0，{}=1．注意a{a}，前者为一对象，后者为仅含该对象的单元素集合；{}，前者是没有元素的集合，后者是恰含一个元素——空集的单元素集。3.1.2外延公理、概括公理和正规公理集合论依赖于三大基本原理：外延公理（extensionalityaxiom）、概括公理（comprehensionaxiom）和正规公理（regularityaxiom）。它们从根本上规定了集合概念的意义。外延公理：两个集合A和B相等当且仅当它们具有相同的元素。即对任意集合A，B。A=Bx(xAxB)例3.4根据外延公理，{0，l}＝{l，0}＝{x∣x(x2-2x＋l)＝0}={xx＝1∨x＝0}因此，外延公理事实上刻划了集合的下列特性：集合成员的“相异性”、“无序性”，及集合表示形式的不唯一性。概括公理:对任意个体域，任一谓词公式都确定一个以该域中的对象为元素的集合。即对给定个体域U，对任意谓词公式P(x)，存在集合s，使得S＝{xxU∧P(x)}概括公理规定了集合成员的确定性,以及集合的描述法表示的理论依据，它还规定了空集的存在性,P(x)永假时集合S为空集。康脱的朴素集合论不是这样表述概括原理的，他描述如下，并称之为抽象原理（abstractionprinciple）。抽象原理:对任意谓词公式P(x)，均存在集合S，使得Ｓ={xP(x)}朴素集合论的问题就出在这里。罗素（Russell）指出；滥用抽象原理导致集合论悖论。罗素悖论:考虑谓词xx．据抽象原理；有集合B，使B＝{xxx}现在问；“BB吗？”若回答是，则B满足谓词xx,即BB;若回答否，则B不满足谓词xx，从而有(BB),即BB。于是有BBBB因此，在我们今后的讨论中，总是约定有一个个体域作为讨论的基础，它被称为全集，常记为U。虽然我们也用S＝{xp(x)}表示P（x）所规定的集合（正像先前已指出的那样），但它总被认为是S＝{xxU∧P(x)}的简写，因为约定xU恒真，从而从合取式中省略xU。正规公理：不存在集合A1,A2,A3,…，使得…A3A2A1正规公理的一个自然推论是：对任何集合A，{A}A（否则有…AAA）。从而规定了集合{A}与A的不同层次性,因而正规公理也就规定了集合不能是自己的成员3.1.3子集合定义3.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}。不过存在这样两个集合，其中一个既是另一个的子集、又是它的元素。例如，{l}{1，{l}}，且{1}{1，{l}}。关于子集关系我们有以下定理和定义（以下表示术语“当且仅当”）。定理3.1对任意集合A，B，A＝B当且仅当AB且BA。特别地，对任意集合A,AA。证A＝Bx(xAxB)x((xA→xB)∧(xB→xA))x((xA→xB)∧x(xB→xA)AB∧B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.l和定理3.3的证明方法、形式完全不同，前者利用谓词演算知识，后者为通常数学证明，两者各有利弊，读者都应熟悉之。定理3.4对任何集合A，A。证因x恒假，故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有子集：没有元素的子集，计0nC个（0nC＝1）;恰含A中一个元素的子集计1nC个,恰含A中两个元素的子集计2nC个,…,恰含A中n个元素的子集计nnC个。因此A的子集个数为0nC+1nC＋…＋nnC=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.2.1并、交、差、补运算定义3.4设A，B为任意集合。（l）A∪B称为A与B的并集（unionset），定义为A∪B＝｛x∣x∈A∨x∈B｝∪称为并运算。（2）A∩B称为A与B的交集（intersectionset），定义为A∩B=｛x∣x∈A∧x∈B｝∩称为交运算。（3）A-B称为A与B的差集（differenceset），定义为A-B＝｛x∣x∈A∧xB｝-称为差运算。（4）A–称为A的补集（complementset），定义为A–=U-A=｛xxA｝–称为补运算，它是一元运算，是差运算的特例。例3.6设U＝{0,1，2，3，…，9}，A={2，4}，B={4,5,6,7}，C={0，8，9}，D＝{l,2,3}：AB＝｛2，4，5，6，7｝，ABCD＝UAB＝｛4｝，