1、第9章 集 合,第9章到第12章介绍集合论包含集合、关系、函数和基数对概念和定理的介绍将以数理逻辑的谓词逻辑为工具来描述，体现了这两个数学分支之间的联系，且可使集合论的研究既简练又严格，还将简要介绍集合论公理系统这个公理系统又称公理集合论，是数理逻辑的一个分支,9 1 集合的概念和表示方法91 1 集合的概念,一个模糊定义：集合是一些确定的、可以区分的事物汇聚在一起组成的一个整体，组成个集合的每个事物称为该集合的一个元素或简称个元(集合论公理系统的一个基本思想是将集合中的元素也描述为集合，这样集合论就可以只关心集合了。)如果a是集合A的一个元素，就说a属于A，或者说a在A中，记作aA，如果b不
2、是集合A的个元素，就说b不属于A或者说b不在A中,记作bA,朴素的集合论简单但存在多种悖论，例如例5的罗素悖论。为避免悖论，准确理解，特别应注意以下约束：,(1)不自吞：集合的元素可以是任何事物，也可以是另外的集合(以后将说明，集合的元素不能是该集合自身，正则公理指出集合不能自吞p153-154)(2)不重复：一个集合的各个元素是可以互相区分开的这意味着，在一个集合中不会重复出现相同的元素(3)无次序：组成一个集合的各个元素在该集合中是无次序的(注：有序对也可由集合来表达p135)(4)确定性：任事物是否属于一个集合，回答是确定的，也就是说。对一个集合来说，任一事物或者是它的元素或者不是它的元
3、素，二者必居其一而不可兼而有之，且结论是确定的。(例5的罗素悖论违反了这一性质p131),912 集合的表示方法,约定1：我们般用不同的大写字母表示不同的集合并用不同的小写字母表示集合中不同的元素，但是因为某个集合的一个元素可能是另个集合所以这种约定不是绝对的约定2：用几个特定的字母表示几个常用的集合约定N表示全体自然数组成的集合(本书中,规定0是自然数,即0N但在另一些书中,规定0不是自然数),Z表示全体整数组成的集合，Q表示全体有理数组成的集合，R表示全体实数组成的集合，C表示全体复数组成的集合,两种表示集合的方法(另外还有运算式子表达法9.3、图形表达法9.4)：一种方法是外延表示法(列
4、举)这种方法一一列举出集合的全体元素例如A=7，8，9，N=0，1，2，3，表示集合A有三个元素7，8，9集合N的元素是0，1，2，3，集合N就是自然数的集合，N的表示式中使用了省略符号，这表示N中有无限多个元素4，5，6，7等有限集合中也可以使用省略符号，例如a，b，c,，y，z表示由26个小写英文字母组成的集合,另一种方法是内涵表示法(谓词描述)：这种方法是用谓词来描述集合中元素的性质上述的集合A和N可以分别表示为Ax|x是整数且6xl0，Nx|x是自然数，一般情况，如果P(x)表示一个谓词，那么就可以用x|P(x)或x:P(x)表示一个集合.x|P(x)是使P(x)为真的所有元素组成的集
5、合也就是说，若P(a)为真，则a属于该集合；若P(a)为假，则a不属于该集合在表示式中的|和：是一个分隔符号在它前向的x是集合中元素的形式名称(如集合A中元素的形式名称是x，但实际名称是7，8，9.常用x，y，z表示形式名称)在分隔符号后面的P(x)是仅含自由变元x的谓词公式,913 集合的实例,例1(外延表示法) B=9，8，8，7(约束2)，集合B中的两个8应看作B中的同一个元素，所以B中只有三个元素集合B就是9，8，7它与上述的集合A=7,8,9是同样的集合，因为元素之间没有次序,例2(内涵表示法) Dx |xB集合D是用集合B来定义的若xB，则xD：若xB，则xD集合D中的元素是除7，
6、8，9外的一切事物,例3 (外延表示法，有层次) F=7，8，9集合F和集合B不同。7F，但8F，9F只有88，9和99集合F仅含有两个元素7和8，9，这两个元素由表示F的最外层花括号包围，并由逗号分隔开对于以集合为元素的集合(即有多层花括号的集合)，应注意集合的层次,例4 (内涵表示法，递归) Gx|x1 V(y)(yG x=y)集合G是用递归方法定义的这个定义是构造性的，可以由该定义求G的每个元素，从而构造出G构造G的过程是由1G，有1 G，由1 G，有1 G，这个构造过程是无止境的，因此G的元素有无限多个,例5 (内涵表示法) 罗素悖论Hx|x是一个集合 x x (所有不自吞集合的集合，
7、违反约束4)可用反证法证明集合H是不存在的假设存在这样的集合H，下面将证明，对某一具体事物y，无法确定y是否属于H我们以H本身作为这个具体事物y，证明中y就是H.对于集合H，必有yH或yH，下面分别考虑之(1)若yH由于y是H的元素,y就具有H中元素的性质yy.考虑到y就是H，所以yH这与yH矛盾(2)由于y不是H的元素，y就没有H中元素的性质，因此yy又因y就是H，则yH这与yH矛盾两种情况都存在矛盾，所以yH和yH都不成立，集合H不存在问题的根源在于，集合论不能研究“所有集合组成的集合”(由子集公理和罗素悖论推出，见定理9.7.5)这是集合论中的一个悖论，称为Rusell悖论,92 集合间
8、的关系和特殊集合921 集合间的关系,本小节，介绍几种集合关系符，可以用来构造命题(构造集合、命题、复合命题、描述命题关系时，使用符号的优先权问题：集合运算符优于集合关系符优于逻辑联结词优于逻辑关系词，见9.3.5）在实数之间可以定义关系=、类似地，在集合之间可以定义关系符、 、 、 、 . 注意也是集合关系符。,1、相等关系：定义921 () 两个集合是相等的，当且仅当它们有相同的元素若两个集合A和B相等，则记作AB；若A和B不相等，则记作AB，这个定义也可以写成A=B (x)(xAxB)，(注意左边由集合关系符产生命题；右边由逻辑联结词产生复合命题；左右两边命题由逻辑关系词衔接)AB (x
9、)(xA xB) (注意同上),这个定义就是集合论中的外延公理(集合论公理1)，也叫外延原理它实质上是说“一个集合是由它的元素完全决定的”因此，可以用不同的表示方法(外延的或内涵的)，用不同的性质、条件和内涵表示同一个集合例如7，8，9，x|x是整数 6xA=B(3)(AB BC)=AC在这个定理中，(1)是自反性，(2)是反对称性(这是定理921的一部分)，(3)是传递性定理922说明包含关系具有这3个性质(实数间的关系也有这3个性质)。应该指出，没有这3个性质。见9.7.3：(1)以后将证明，对任意的集合A，AA(2)以后将证明，对任意的集合A和B，(AB BA)(3)对任意的集合A、B和
10、C，当AB和BC时，不一定有AC以后将指出，C为传递集合时才能推出AC,4、定义923 对任意两个集合A和B，若AB且AB，就称A为B的真子集，或称B真包含A，或称B是A的真超集合，记作AB或BA，这个定义也可以写成AB(AB AB),5、定义924 若两个集合A和B没有公共元素，就称A和B是不相交的这个定义也可以写成A和B不相交(x)(xA xB)若A和B不是不相交的，就称A和B是相交的例如1，2 1，2，3，1，2 1，2，1，2和3，4，5不相交，1，2和2，3，4相交。,922 特殊集合,空集和全集是两个特殊集合它们的概念简单，但在集合论中的地位却很重要下面介绍这两个集合定义925 不
11、含任何元素的集合称为空集(集合论公理2)，记作空集的定义也可以写成x|xx)显然，(x)(x)为真下面介绍有关空集的两个重要结论,定理923 对任意的集合A， A证明 假设存在集合A，使 A，则存在x，使x且xA这与空集的定义矛盾，所以定理得证推论921 空集是唯一的，证明留作思考题(只要假设有两个空集和，证明，即可)，,定义926 在给定的问题中，所考虑的所有事物的集合称为全集，记作E.全集的定义也可以写成Ex|xx全集的概念相当于谓词逻辑的论域对不同的问题，往往使用不同的论域，例如在研究有关实数的问题时，就以R为全集,93集合的运算,运算是数学上常用的手段两个实数进行加法运算可以得到一个新
12、的实数类似地，两个集合也可以进行运算，得到交集、并集等新的集合集合的运算是由已知集合构造新集合的一种方法这类似于用逻辑联结词构造出大量合式公式集合的运算式子是表示集合的第三种方法。这种表示方法不仅简捷，而且可利用运算的性质简化一些证明问题,本小节，介绍几种集合运算符，可以用来构造集合。,931 集合的基本运算,下面介绍的5种运算是集合论中的基本运算，定义931 对集合A和B，(1)并集AUB定义为AUBx|xAVxB，(2)交集AB定义为A B=x|xA xB(3)差集(又称B对A的相对补集，补集)A-B定义为A-Bx|xA xB(4)余集(又称A的绝对补集)-A定义为(一元运算符)-A=E-
13、Ax|xA，(其中E为全集A的余集就是A对E的相对补集)(5)对称差AB定义为AB(AB)U(BA)x|xA xB(参考p10),例1 已知集合A，B和全集E为Aa，b，c，d，Be, f，a, d，Ea，b，c，d，e，f，g，则有A UBa，b，c ，d，e ，fBUA，A Ba，dB A，ABb，c，BAe，f，一Ae，f，g，Bb,c，g)，ABb，c，e，f=BA并集AUB中的元素是A和B中所有的元素，公共元素只出现一次交集A B中的元素是A和B占所有的公共元素差集AB中的元素是在A中但不在B中的那些元素，余集A中的元素是在全集中但不在A中的那些元素对称差AB中的元素即由AB的元素和
14、BA的元素组成,932 广义并和广义交,广义并和广义交是一元运算，是对一个集合的集合A进行的运算它们分别求A中所有元素的并和交，A中可以有任意多个元素，它们就可以求任意个元素的并和交A中若有无限多个元素，它们就可以求无限多个元素的并和交广义并和广义交是并集和交集的推广,定义932 若集合A的元素都是集合(集合论公理体系的一个基本思想是把所有元素都描述为集合)，则把A的所有元素的元素组成的集合称为A的广义并，记作UA；把A的所有元素的公共元素组成的集合称为A的广义交，记作 A这个定义也可以写成UAx|(z)(zAxz)， Ax|(z)(zAxz)，此外，规定U，规定 无意义(p153通过子集公理
15、佐证),例2 已知集合A为Aa，b，c，a，b，b，c，d，则有U Aa，b，c，d， Ab可以用广义并和广义交分别定义并集和交集AU BUA，B，A B A，B广义并和并集的运算符都是U但因广义并是一元运算，并集是二元运算，所以对U的含义不会产生误解,933 幂集,集合的幂集是该集合所有子集组成的集合，幂集是由个集合构造的新集合，它也是集合的一元运算，但是幂集与原集合的层次有所不同定义933 若A是集合，则把A的所有子集组成的集合称为A的幂集，记作P(A)若A有a个元素，则P(A)有2a个元素。这个定义也可以写成P(A)x|xA例3 P()，P()，P(a，b) ，a，b，a，b.对任意的集
16、合A，有 A和A A，因此有P(A)和AP(A),934 笛卡儿积用集合定义有序对，用有序对定义笛卡儿积,1、笛卡儿积的描述：笛卡儿积也是一种集合二元运算，两个集合的笛卡儿积是它们的元素组成的有序对的集合，笛卡儿积是与原集合层次不同的集合笛卡儿积是下一章介绍关系概念的基础下面先介绍有序对，再介绍笛卡儿积2、有序对的描述：两个元素x和y(允许xy)按给定次序排列组成的二元组合称为一个有序对，记作其中x是它的第一元素，y是它的第二元素,有序对应具有下列基本性质：(1)xy=，(2)xu /yv例如：在平面直角坐标系上一个点的坐标就是一个有序对定义934 通过集合定义有序对：x，x，y,定理931(
17、有序对两条基本性质的证明)(1) x=u / yv(2)xy = 证明 (1)设xu/yv，则显然有x，x，yu，u，v，于是设，则有x,x，yu，u，v分别考虑xy和xy两种情况当xy时，x，于是xuu，v，则 xuvy当xy时，显然ux，y于是 u=x且x，yu，v则 x=u显然yu，于是yv两种情况都可得到xu / y=v (2)其证明留作思考题。,3、 有序的n元组：可以推广有序对的概念，定义由有序的n个元素组成的n元组有序的n元组是用递归方法定义的定义9.3.5 若nN且n1，x1，x2，xn是n个元素，则n元组定义为当n2时，二元组是有序对，当n2时，=，xn,例4 =，c，d按照
18、这个定义，有序对就是二元组，n元组就是多重有序对,4、定义9.3.6 通过有序对定义笛卡儿积：集合A和B的笛卡儿积(又称卡氏积、乘积、直积)AB定义为ABz|xA / yB / z或简写为AB=|xA / yB例5 已知集合A和B为Aa，b，B0，1，2则有AB=，、BA，AA，在A=B时，可把AA简写为A2,5、用n元组定义n阶笛卡儿积： 定义937 若nN且n1，而A1，A2,，An是n个集合，它们的n阶笛卡儿积记作 A1A2An，并定义为A1A2An =| x1 A1 / / xn An当A1 A2 = An =A时，它们的n阶笛卡儿积可以简写为An,部分集合论公理(参考9.7)1. 外
19、延公理指出什么是两个集合相等；2. 空集合存在公理指出空集合的存在性；3. 并集合公理指出了广义并的存在性；4. 并集合公理和无序对集合存在公理指出了并集的存在性；5. 子集公理指出了交集、广义交、差集、笛卡儿积的存在性；6. 幂集合公理指出了幂集的存在性。,935 优先权,集合可以由集合运算符连接构成新集合，如AB和-A两个集合可以由集合关系符连接，构成一个命题，如ABA和AB这种命题可以由逻辑联结词连接，构成复合命题，如(AB / AB)两个命题可以由逻辑关系符连接，如AB=AB在集合论中，当描述问题和证明问题时，往往在一个式子中同时使用上述四类连接符号为了简单、确定地表示各类连接符号的优
20、先次序，下面规定各类连接符号的优先权，,集合运算符：一元运算符(-A，P(A)，A，A)优先于 集合运算符：二元运算符(-，)优先于 集合关系符：(，)优先于 逻辑联结词：一元联结词()优先于 逻辑联结词：二元联结词(， )优先于 逻辑关系符：(，) 此外，还使用数学上惯用的括号表示优先权方法、从左到右的优先次序规定(1)括号内的优先于括号外的；(2)同一层括号内，按上述优先权，(3)同一层括号内，同一优先级的，按从左到右的优先次序,94 集合的图形表示法,前面已介绍了表示集合的三种方法：外延(列举)表示法，内涵(谓词描述)表示法和使用运算的表示法，图形表示法是第四种表示法图形表示法是数学上常
21、用的方法，它的优点是形象直观、易于理解，缺点是理论基础不够严谨，因此只能用于说明，不能用于证明：文氏图：首创于瑞士数学家欧拉。十九世纪末，英国逻辑学家venn重新采用了这种办法。幂集图示: 参考描述偏序关系的(二战德国)哈斯图(平面的)。笛卡尔积图示：使用直角坐标系。,941 文氏图,在文氏图中，矩形内部的点表示全集的所有元素在矩形内画不同的圆表示不同的集合，用圆内部的点表示相应集合的元素图941中各图表示集合的关系图942中各图表示5种基本运算,942 幂集的图示法,可以用一个网络图中的各结点表示幂集的各元素设A=0，1，2，则P(A)的各元素在图943中表示图中结点间的连线表示二者之间有包
22、含关系这种图就是下一章介绍的哈斯图,943 笛卡儿积的图示法,在平面直角坐标系上，如果用x轴上的线段表示集合A，并用y轴上的线段表示集合B，则由两个线段画出的矩形就可以表示笛卡儿积AB，如图9.4.4所示，,95 集合运算的性质和证明9 51 基本运算的性质,集合的三种运算AUB，AB，-A分别是用逻辑连接词/ ，/，定义的，因此它们具有和/ ，/， 类似的性质1、集合运算符基本规律,下面仅证（3）和（5）,这里采用了两种证明方法种是利用谓词演算(3)的证明)的方法，另一种是利用已知的集合恒等式(5)的证明) 可以用文氏图说明集合恒等式图951用文氏图说明A-(BC)(A-B)(A-C)从图中
23、看出，等式两边对应图中同一个区域，因此应该相等这种图形表示法只能说明问题，不能证明问题，,2、差集的性质定理952 对任意的集合A，B和C，有(1)A-BA-(AB)(2)A-BA-B，(3)A(B-A)AB(4)A(B-C)(AB)-C证明,定理中的(2)是很有用的结论，它可以用AB代入式中的A-B，从而消去差集算符，利用定理9.5.1的规律这类似于命题逻辑中消去联结词“”,3、对称差的性质类似于并集定理953 对任意的集合A，B和C，有,证明(3)如下,4、集合间的关系类似于实数间的关系（偏序）,例1(谓词演算) 对任意的集合A和B，有(AUB=B)(AB)(ABA)(A一B=)证明 本例
24、要求证明4个命题互相等价设命题(1)是AUB=B ，命题(2)是AB ，命题(3)是ABA ，命题(4)是A一B= 。只要证明(1)=(2)，(2)=(3)，(3)=(4)，(4)=(1)即可，(1)=(2):已知AUB=B对任意的x，得xA=xAxBxABxB因此AB,(2)=(3):已知AB对任意的x，得xABxAxB=xA，xAxAxA=xAxBxAB.因此ABA,(3)=(4)：已知ABA，故A-BA-B(AB)-B=A(B-B)=(4)=(1)：已知A-B，故ABBAB(A-B)(由定理952)=B=B,例2(集合等式运算) 对任意的集合A，B和C，有ABAC，ABAC=BC证明 方
25、法1：BB(AB)=B(AC)=(BA)(BC) (AC)(BC)=(AB)C=(AC)C=C方法2（反证法，简洁的好办法）：假设BC不妨设存在x，使xBxC如果xA，则xAB且xAC与已知矛盾如果xA，则xAB且xAC,也与已知矛盾因此B=C由ABAC能否推出BC呢?能否由AB=AC推出B=C呢? 请思考,例3 对任意的集合A，B和C，给出(A-B)(A-C)=成立的允要条件(理解)解 (A-B)(A-C)=(A-B)-(A-C)(A-C)-(A-B)=(A-B)-(A-C)(A-C)-(A-B)=(A-B)(A-C)(A-C) (A-B) (例1)A-B=A-C.于是，充要条件是A-BA-
26、C,952 幂集合的性质和传递集合,1、幂集合(集合的集合)定理955 对任意的集合A和B有,定理95，6 对任意的集合A和B，有(1)P(A)P(B)P(AB)(2)P(A)P(B) P(AUB)证明(1)对任意的x，可得xP(A) P(B)xP(A) xP(B)xAxB(y)(yxyA) (y)(yxyB)(y)(yx(yAyB)xABxP(AB),(2)对任意的x，可得xP(A)UP(B)xP(A)V xP(B)xAV xB(y)(yxyA)V(y)(yxyB)=(y)(yxyA)V(yxyB)(y)(yx(yAB)xAUBxP(AUB)注意，结论(2)不能写成等式例如，令A=a，Bb则
27、P(AUB)，a，b，a，b，P(A)UP(B)，a，b,定理958 对任意的集合A和B有P(A-B) (P(A)-P(B)U 证明 对任意的x,若x，则有 xP(A-B)xA-B (y)(yxyA-B) (y)(yxyA) (y)(yxyB) =(y)(yxyA)xA此外 xP(A-B) x xA-B(y)(yx) (y)(yx(yAyB) (y)(yx) =(y)(yxyB)(用推理规则),x B于是xP(A-B) x=xAx BxP(A) xP(B)x(P(A)-P(B)= P(A-B) (P(A)-P(B)U若x=,有 P(A-B)且(P(A)-P(B)U,2、传递集合(集合的集合)下
28、面给出传递集合的定义，并讨论它和幂集的关系，定义951 如果集合的集合A的任一元素的元素都是A的元素，就称A为传递集合这个定义也可以写成A是传递集合(x)(y)(xyyA) xA)，,例4 A=，是传递集合A的元素的元素有和，这些都是A的元素B=，不是传递集合，B的元素的元素有和，但是不是B的元素,定理959 对集合的集合A，A是传递集合AP(A)证明 先设A是传递集合则对任意的yA，若y则yP(A)若y，对(x)(xy)，有xA(A是传递集合)，则有yA，于是yP(A)总之，由yAyP(A)，有AP(A)再设AP(A)，则对任意的x和y，有xyyA=xyyP(A) (由已知)xyyA=xA因
29、此，A是传递集合,幂集运算对于传递集合的封闭性定理9510 对集合的集合A，A是传递集合P(A)是传递集合证明 先设A是传递集合对任意的x和y，有 xyyP(A)xyyA=xA =xA (因为A是传递集合) xP(A)所以P(A)是传递集合(证明中利用了传递集合的性质，它的元素一定是它的子集)再设P(A)是传递集合对任意的x和y,有 xyyAxyy A xy yy y P(A) =xyyP(A) (P(A)是传递集合) xyyA=xA所以A是传递集合,953 广义并和广义交的性质,定理9511 对集合的集合A和B，有 (1)AB=AB， (2)AB=BA，其中A和B非空 证明 (1)设AB对任
30、意的x可得 xA(y)(xyyA) =(y)(xyyB)xB所以，AB (2)设AB.对任意的x，可得 xB(y)(yBxy) =(y)(yAxy)(由AB) xA所以，BA,1、基本性质,定理9512 对集合的集合A和B，有 (1)U(AUB)=(UA)U(UB)， (2)(AUB)(A)(B)，其中A和B非空 证明 (1)对任意的x，可得 xU(AUB)(y)(xyyAUB) (y)(xy(yA VyB) (y)(xyyA)V(y)(xyyB) xUA V xUBx(UA)U(UB) 所以，U(AUB)=(UA)U(UB),(2)对任意的x，可得 x(AUB)(y)(yAUBxy) (y)
31、(yA V yB) xy) (y)(yAxy) (y)(yBxy) xAxBx (A) (B) 所以，(AUB)(A)(B),定理9513 对任意的集合A，有 (P(A)A 证明 对任意的x，可得 xU(P(A)(y)(xyyP(A) (y)(xyyA)xA所以，(P(A)A定理说明，广义并是幂集的逆运算例如，当Aa，b有P(A)=，a，b，a，b， 有P(A)a，b但是次序不能颠倒，即P(A)A，只有AP(A)例如，当A=a,有A=a，有P(A)，a,2、广义并和广义交对于传递集合的封闭性(两对定理)定理9514 若集合A是传递集合，则UA是传递集合证明 对任意的x和y，有 xyyAxy (
32、z)(yzzA) =xyyA (A是传递集合) xU A所以UA是传递集合,定理9515 若集合A的元素都是传递集合，则UA是传递集合证明 对任意的x和y，有 xyyAxy(z)(yzzA) =(z)(xzzA) (z是传递集合) xUA 所以UA是传递集合,定理9，516 若非空集合A是传递集合，则A是传递集合，且A这个定理的证明要使用正则公理，这里不给出证明参见定理9.7.8。,定理9517 若非空集合A的元素都是传递集合，则A是传递集合证明 对任意的x和y，可得所以A是传递集合,954 笛卡儿积的性质,笛卡儿积具有下列基本性质 (1)A=B， (2)若A，B且AB，则ABBA， (3)A (B C) (AB) C 结论表明，笛卡儿积不满足交换律和结合律结论(3)是因为 A (B C)|aAbBcC (A B) C，c|aAbBcC 其中，c是三元组，但不是三元组，c,定理9518 若A是集合，xA,yA，则PP(A)(PP(A)表P(P(A).),定理9519 对任意的集合A，B和C，有,笛卡尔积对并、交的分配律,证明 只证(1)，其余留作思考题,定理9.5.20 对任意的集合A，B和C，若C，则,定理9521 对任意的非空集合A，B，C和D，,
