离散数学之集合论

69第二篇集合与关系集合论是现代各科数学的基础，它是德国数学家康托（GeogCantor,1845～1918）于1874年创立的，1876～1883年康托一系列有关集合论的文章，对任意元的集合进行了深入的探讨，提出了关于基数、序数和良序集等理论，奠定了集合论深厚的基础，19世纪90年代后逐渐为数学家们采用，成为分析数学、代数和几何的有力工具。随着集合论的发展，以及它与数学哲学密切联系所作的讨论，在1900年前后出现了各种悖论，使集合的发展一度陷入僵滞的局面。1904～1908年，策墨罗（Zermelo）列出了第一个集合论的公理系统，它的公理，使数学哲学中产生的一些矛盾基本上得到了统一，在此基础上以后就逐渐形成了公理化集合论和抽象集合论，使该学科成为在数学中发展最为迅速的一个分支。现在，集合论已经成为内容充实、实用广泛的一门学科，在近代数学中占据重要地位，它的观点已渗透到古典分析、泛函、概率、函数论、信息论、排队论等现代数学各个分支，正在影响着整个数学科学。集合论在计算机科学中也具有十分广泛的应用，计算机科学领域中的大多数基本概念和理论几乎均采用集合论的有关术语来描述和论证，成为计算机科学工作者必不可少的基础知识。集合论可作为数学学科的通用语言，一切必要的数据结构都可以利用集合这个原始数据结构而构造出来，计算机科学家或许也可以利用这种方法。本篇介绍集合论的基础知识，主要内容包括集合及其运算、性质、序偶、关系、映射、函数、基数等。第2-1章集合及其运算§2-1-1集合的概念及其表示一、集合的概念“集合”是集合论中的一个原始的概念，因此它不能被精确地定义出来。一般地说，把具有某种共同性质的许多事物，汇集成一个整体，就形成一个集合。构成这个集合的每一个事物称为这个集合的一个成员（或一个元素），构成集合的这些成员可以是具体东西，也可以是抽象东西。例如：教室内的桌椅；图书馆的藏书；全国的高等学校；自然数的全体；程序设计语言C的基本字符的全体等均分别构成一个集合。通常用大写的英文字母表示集合的名称；用小写的英文字母表示元素。若元素a属于集合A记作70Aa，读作“a属于A”。否则，若a不属于A，就记为Aa，读作“a不属于A”。一个集合，若其组成集合的元素个数是有限的，则称作“有限集”，否则就称作“无限集”。集合的表示方法有两种：一种是列举法又称穷举法，它是将集合中的元素全部列出来，元素之间用逗号“，”隔开，并用花括号“{}”在两边括起来，表示这些元素构成整体。例2-1-1.1A＝｛a,b,c,d｝；B＝｛1，2，3，…｝；D＝｛桌子，台灯，钢笔，计算机，扫描仪，打印机｝；},,,{32aaaE。集合的另一种表示方法叫做谓词法又叫叙述法，它是利用一项规则，概括集合中元素的属性，以便决定某一事物是否属于该集合的方法。设x为某类对象的一般表示，)(xP为关于x的一个命题，我们用})({xPx表示“使)(xP成立的对象x所组成的集合”，其中竖线“|”前写的是对象的一般表示，右边写出对象应满足（具有）的属性。例2-1-1.2全体正奇数集合表示为}{1是正奇数xxS，所有偶自然数集合可表示为}2{NmmmE且其中2|m表示2能整除m。[0,1]上的所有连续函数集合表示为}]10[)()({]1,0[上连续，在xfxfC集合的元素也可以是集合。例如}}{,,}2,1{,{qpaS，但必须注意：}{qq，而Sq，同理}2,1{1，S}2,1{，而S1。两个集合相等是按下述原理定义的。外延性原理：两个集合相等，当且仅当两个集合有相同的元素。两个集合A，B相等，记作BA，两个集合不相等，记作BA。集合中的元素是无次序的，集合中的元素也是彼此不相同的。例如：},4,2,2,1{}4,2,1{},2,4,1{}4,2,1{}{},5,3,1{},4,2,1{}4}2,1{{是正奇数，xx。集合中元素可以是任何事物（如例2-1-1.1）。不含任何元素的集合称为空集，记为Φ。例如，方程012x的实根的集合是空集。二、集合与集合间的关系Sa{q}{1，2}p12q71“集合”、“元素”、元素与集合间的“属于”关系是三个没有精确定义的原始概念，对它们仅给出了直观的描述，以说明它们各自的含义。现利用这三个概念定义集合间的相等关系，集合的包含关系，集合的子集和幂集等概念。定义2-1-1.1设A，B是任意两个集合，如果A中的每一个元素都是B的元素，则称A是B的子集，或A包含于B内，或B包含A。记作BA，或AB。即)(BxAxxBA可等价地表示为)(AxBxxBA。例2-1-1.3设N为自然数集合，Q为一切有理数组成的集合。R为全体实数集合，C为全体复数集合，则CRQN，RQN},2{,}9.9,2.1,1{,}1{。如果A不是B的子集，则记为BA（读作A不包含在B内），显然，))()((BxAxxBA。集合间的包含关系“”具有下述性质：2-1-1.自反性AA；2.传递性)()()(CACBBA。证明：采用逻辑演绎的方法证明。⑴BAP⑵))()((BxAxxT(1)E⑶)()(BaAaUS(2)⑷CBP⑸))()((CxBxxT(4)E⑹)()(CaBaUS(5)⑺)()(CaAaT(3)(6)I⑻))()((CxAxxUG(8)⑼CAT(8)E72定义2-1-1.2如果集合A的每一元素都属于集合B，而集合B中至少有一元素不属于A，则称A为B的真子集，记作BA。即))()(())()((AxBxxBxAxxBA例如：},{ba是},,{cba的真子集；N是Q的真子集，Q是R的真子集；R是C的真子集。注意符号“∈”和“”在概念上的区别，“∈”表示元素与集合间的“属于”关系，“”表示集合间的“包含”关系。定理2-1-1.1集合A＝B的充分必要条件是：BA且AB。（外延性原则）证明：必要性，即证：)()(ABBABA)()()))()((()))()(((ABBAAxBxxBxAxxBA充分性，即证：BAABBA)()(FBABABABxAxxBA)()())()((或FABABABAxBxxBA)()())()((#定理2-1-1.2对于任一集合A，A，且空集是唯一的。证明：假设A为假，则至少存在一个元素x，使x且Ax，因为空集不包含任何元素，所以这是不可能的。设与都是空集，由上述可知，且，根据定理2-1-1.1知，所以，空集是唯一的。注意：}{，})()({xPxPxP(x)是任一谓词。例2-1-1.4设BA},3,2{为方程0652xx的根组成的集合，则A＝B。定理2-1-1.1指出了一个重要原则：要证明两个集合相等，即要证明每一个集合中的任一元素均是另一集合的元素。这种证明是靠逻辑推理理论，而不是靠直观。证明两个集合相等是应该掌握的方法。定义2-1-1.3在一定范围内，如果所有集合均为某一集合的子集，则称该集合为全73集，记作E。对于任一Ax，因EA，所以Ex，也即)(Exx恒为真故})()({xPxPxE，)(xP为任一谓词。注意：全集的概念相当于论域，只包含与讨论有关的所有对象，并不一定包含一切对象与事物。例如：在初等数论中，全体整数组成了全集；方程012x的解集合，在全集为实数集时为空集，而全集为复数集时解集合就不再是空集，此时解集合为1},{2iii，。三、幂集定义2-1-1.4给定集合A，由集合A的所有子集为元素组成的集合，称为集合A的幂集。记为P(A)（或记为A2）。即P(A)＝{X|XA}。例2-1-1.5A={0,1,2}，则P(A)＝{Φ,{0},{1},{2},{0,1},{0,2},{1,2},{0,1,2}}；P(Φ)＝{Φ}；P({a})={Φ,{a}}；P({Φ})={Φ,{Φ}}。定理2-1-1.3设},,,{21naaaA，则|P(A)|＝n2。其中：|P(A)|表示集合P(A)中元素的个数。证明：集合A的m(m=0,1,2,…,n)个元素组成的子集个数为从n个元素中取m个元素的组合数，即mnC，故P(A)的元素个数为：|P(A)|＝nmmnnnnnCCCC010根据二项式定理nmmnmmnnyxCyx0)(令x=y=1得nmmnnC02故|P(A)|＝n2。四、集合的数码表示在中学学习集合时，特别强调了集合中元素的无序性，但是，为了用计算机表示集合及其幂集，需要对集合中元素规定次序，即给集合中元素附上排列指标，以指明一个元素关于集合中其他元素的位置。如A2={计算机，打印机}是二个元素的集合，令“计算机”为集合A的第一个元素，“打印机”为集合A2的第二个元素。改记为A2={x1,74x2}，则P(A2)的四个元素，可记为，00S，101}{Sx，012}{Sx，1121},{Sxx，其中S的下标，从左到右分别记为第一位，第二位，它们的取值是1还是0由第一个和第二个元素是否在该子集中出现来决定，如果第i个元素出现在该子集中，那么S下标的第i位取值为1，否则取值为0（i=0,1）。即令J={00,01,10,11}={i|i是二位二进制数，00≤i≤11}，则P(A2)＝{Si|i∈J}。类似地，三个元素集合A3={x1,x2,x3}的幂集P(A3)＝{Si|i∈J,J={i|i二进制数，000≤i≤111}}，因此，S010={x2}，S101={x1,x3}。上述幂集中元素表示法实际上是一种编码，可以推广到n个元素的集合An的幂集上，P(An)的2n个元素可以表示为Si，i∈J={i|i是二进制数，00…0≤i≤11…1}如果},,,,,{6543216xxxxxxA，P(A6)的62个元素记为12106,,,SSS，此时S的下标是十进制整数，如何求出127,SS是A6的那些元素组成的子集呢？将下标转换为二进制的整数，不足六位的在左边补入需要个数的零，使之成为六位的二进制整数，由排列的六位二进制整数推断出，含有那些元素。凡第i位为0，表示xi不在此子集中，凡第i位为1表示xi在此子集中，故},,{6540001111117xxxBBB，},{4300110012xxBB。这种方法可以推广到一般情况，即将十进制整数转换为二进制整数，在左边补入需要个数的零使之成为n位的二进制数，若第i位为0，表示xi不在此子集中，若第i位为1表示xi在此子集中。子集的这种编码法，不仅给出了一个子集含那些元素的判别方法，还可以用计算机表示集合、存贮集合以供使用。§2-1-2集合的基本运算集合的运算，就是以集合为对象，按照确定的规则得到另外一些新集合的过程。给定集合A，B，可以通过集合的并（∪）、交（∩）、相对补（－）、绝对补（¯）和对称差（⊕）等运算产生新的集合。一、集合并（∪）运算定义2-1-2.1设A，B为任意两集合，所有属于集合A或属于集合B的元素组成nn75的集合，称为集合A和B的并集。记作A∪B})()({BxAxxBA并集的文氏（英国数学家JohanWenn(1834~1883)）图例2-1-2.1设A={1,2,3,4}，B={2,4,5,6}则A∪B={1,2,3,4,5,6}。注意：集合是由互不相同元素组成的，在A∪B中2，4各写一次，不能重写。由集合并运算的定义知，并运算具有如下性质：定理2-1-2.1设A，B，C为任意三个集合，则⑴幂等律A∪A=A；⑵交换律A∪B=B∪A；⑶结合律(A∪B)∪C=A∪(B∪C)；⑷同一律A∪Φ=A；⑸零律A∪E=E；⑹AA∪B，BA∪B；⑺A∪B=BAB。证明：性质⑴，⑵，⑷，⑸，⑹由定义2-1-2.1立即可以得到。⑶的证明(A∪B)