第3章 集合论基础

第二篇集合论•集合论基础•二元关系•函数第三章集合论基础•基本概念及集合的表示方法•集合间的关系•特殊集合•集合的运算•包含排斥原理3-1基本概念1.集合与元素集合是个最基本的概念。集合：由确定的对象(客体)构成的集体。用大写的英文字母表示。这里所谓“确定”是指：论域内任何客体，要么属于这个集合，要么不属于这个集合，是唯一确定的。元素：集合中的对象，称之为元素。∈：表示元素与集合的属于关系。例如，N表示自然数集合，2∈N，而1.5不属于N写成(1.5∈N),或写成1.5N。2.有限集合与无限集合这里对有限集合与无限集合只给出朴素的定义，以后再给出严格的形式定义。有限集合：元素是有限个的集合。如果A是有限集合，用|A|表示A中元素个数。例如，A={1,2,3},则|A|=3。无限集合：元素是无限个的集合。对无限集合的所谓‘大小’的讨论，以后再进行。3.集合的表示方法列举法：将集合中的元素一一列出，写在大括号内。例如，N={1,2,3,4,……}A={a,b,c,d}描述法：用句子(或谓词公式)描述元素的属性。例如，B={x|x是偶数}C={x|x是实数且2≤x≤5}一般地，A={x|P(x)},其中P(x)是描述元素x的特性的谓词公式，如果论域内客体a使得P(a)为真，则a∈A，否则aA。4.说明⑴集合中的元素间次序是无关紧要的，但是必须是可以区分的，即是不同的。例如A={a,b,c,a}，B={c,b,a,}，则A与B是一样的。⑵对集合中的元素无任何限制，例如令A={人，石头，1，Ｂ},B={Φ,{Φ}}⑶本书中常用的几个集合符号的约定：自然数集合N={1,2,3,……}整数集合I，实数集合R，有理数集合Q⑷集合中的元素也可以是集合，下面的集合的含义不同：如a：张书记{a}:党支部(只有一个书记){{a}}：分党委(只有一个支部){{{a}}}：党委(只有一个分党委){{{{a}}}}：市党委(只有一个党委)3-2集合间的关系一.被包含关系(子集)1.定义：A、B是集合，如果A中元素都是B中元素，则称B包含A，A包含于B，也称A是B的子集。记作AB。文氏图表示如右下图。例如，N是自然数集合，R是实数集合，则NR谓词定义：ABx(x∈Ax∈B)AB2.性质：⑴有自反性，对任何集合A有AA。⑵有传递性，对任何集合A、B、C，有AB且BC，则AC。⑶有反对称性，对任何集合A、B，有AB且BA，则A=B。二.相等关系1.定义：A、B是集合，如果它们的元素完全相同，则称A与B相等。记作A=B。定理：A=B，当且仅当AB且BA。证明：充分性，已知AB且BA，假设A≠B，则至少有一个元素a,使得a∈A而aB；或者a∈B而aA。如果a∈A而aB，则与AB矛盾。如果a∈B而aA，则与BA矛盾。所以A=B。必要性显然成立，因为如果A=B，则必有AB且BA。谓词定义：A=BABBAx(x∈Ax∈B)x(x∈Bx∈A)x((x∈Ax∈B)(x∈Bx∈A))x(x∈Ax∈B)2.性质⑴有自反性，对任何集合A，有A=A。⑵有传递性，对任何集合A、B、C，如果有A=B且B=C，则A=C。⑶有对称性，对任何集合A、B，如果有A=B，则B=A。三.真被包含关系(真子集)1.定义：A、B是集合，如果AB且A≠B，则称B真包含A，A真包含于B，也称A是B的真子集。记作AB。谓词定义：ABABA≠Bx(x∈Ax∈B)x(x∈Ax∈B)x(x∈Ax∈B)(x(x∈Ax∈B)x(x∈Bx∈A))(x(x∈Ax∈B)x(x∈Ax∈B))(x(x∈Ax∈B)x(x∈Bx∈A))x(x∈Ax∈B)x(x∈BxA)2.性质有传递性，对任何集合A、B、C，如果有AB且BC，则AC。练习题：设A={a,{a},{a,b},{{a,b},c}}判断下面命题的真值。⑴{a}∈A⑵({a}A)⑶c∈A⑷{a}{{a,b},c}⑸{{a}}A⑹{a,b}∈{{a,b},c}⑺{{a,b}}A⑻{a,b}{{a,b},c}⑼{c}{{a,b},c}⑽({c}A)(a∈Φ)3-3特殊集合一.全集E定义：包含所讨论的所有集合的集合，称之为全集，记作E。实际上，就是论域。它的文氏图如右图。由于讨论的问题不同，全集也不同。所以全集不唯一。例如，若讨论数，可以把实数集看成全集。若讨论人，可以把人类看成全集。E由于论域内任何客体x都属于E，所以x∈E为永真式。所以需要用永真式定义E。E={x|P(x)∨P(x)}性质：对于任何集合A，都有AE。二.空集Φ定义：没有元素的集合，称之为空集，记作Φ。因为论域内如何客体x∈Φ是矛盾式，所以要用一个矛盾式定义Φ。Φ={x|P(x)∧P(x)}性质：1.对于如何集合A，都有ΦA。因为x(x∈Φx∈A)为永真式，所以ΦA。2.空集是唯一的。证明假设有两个空集Φ1、Φ2，则因为Φ1是空集，则由性质1得Φ1Φ2。因为Φ2是空集，则由性质1得Φ2Φ1。所以Φ1=Φ2。三.集合的幂集(PowerSet)定义:A是集合，由A的所有子集构成的集合，称之为A的幂集。记作P(A)或2A。(A)={B|BA}例如，A(A)Φ{Φ}{a}{Φ,{a}}{a,b}{Φ,{a},{b},{a,b}}Ａ＝{a,b,c}则(A)={Φ,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}C33C32C31C30|(A)|＝＋＋＋Cn2＋……Cn0Cn1Cnn＋＋＋Cn2＋…Cn0Cn1Cnn＋＋＋xn-1yxn-2y2xnynCn2＋……Cn0Cn1Cnn＋＋＋性质：1.给定有限集合A，如果|A|=n,则|P(A)|=2n。证明：因为Ａ有n个元素，故(A)中元素个数为而(x+y)n=令x=y=1时得2n=所以|(A)|=2n|2A|=2|A|=2n幂集元素的编码：Ａ＝{a,b,c}则P(A)={Φ,{c},{b},{b,c},{a},{a,c},{a,b},{a,b,c}}A的八个子集分别表示成：B0,B1,B2,B3,B4,B5,B6,B7再将它们的下标写成二进制形式得:B000,B001,B010,B011,B100,B101,B110,B111,Φ{c}{b}{b,c}{a}{a,c}{a,b}{a,b,c}B000B001B010B011B100B101B110B111B0B1B2B3B4B5B6B7子集Bijk编码的写法：Ａ＝{a,b,c}i、j、k的确定：BijkA,如果a∈Bijk,则i=1;b∈Bijk,则j=1;c∈Bijk,则k=1;否则为0。如Ａ＝{a,b,c,d}子集B9=B1001={a,d}{a,c,d}=B1011=B11作业86页(4)(7)练习P86(7)设A={Φ}，B=P(P(A))P(A)={Φ,{Φ}}在求P(P(A))时，一些同学对集合{Φ,{Φ}}难理解，实际上你就将{Φ,{Φ}}中的元素分别看成Φ=a,{Φ}=b,于是{Φ,{Φ}}={a,b}B=P(P(A))=P({a,b})={B0,B1,B2,B3}={B00,B01,B10,B11}={Φ,{b},{a},{a,b}}然后再将a,b代回即可B=P(P(A))=P({Φ,{Φ}})={Φ,{Φ},{{Φ}},{Φ,{Φ}}}以后熟悉后就可以直接写出。a)Φ∈BΦBb){Φ}∈B{Φ}Bc){{Φ}}∈B{{Φ}}Ba)、b)、c)中命题均为真。3-4集合的运算介绍五种运算：∩∪-~一.交运算∩1.定义：A、B是集合，由既属于A，也属于B的元素构成的集合,称之为A与B的交集,记作A∩B。例如A={1,2,3}B={2,3,4}A∩B={2,3}谓词定义：A∩B={x|x∈A∧x∈B}x∈A∩Bx∈A∧x∈B如果A∩B=Φ，则称A与B不相交。ABA∩B2.性质⑴幂等律对任何集合A，有A∩A=A。⑵交换律对任何集合A、B，有A∩B=B∩A。⑶结合律对任何集合A、B、C，有(A∩B)∩C=A∩(B∩C)。⑷同一律对任何集合A，有A∩E=A。⑸零律对任何集合A，有A∩Φ=Φ。⑹ABA∩B=A。前5个公式高中都学过，下面只证明⑹。证明：A∩B=Ax(x∈A∩Bx∈A)x((x∈A∩Bx∈A)∧(x∈Ax∈A∩B))x((xA∩B∨x∈A)∧(xA∨x∈A∩B))x(((x∈A∧x∈B)∨x∈A)∧(xA∨(x∈A∧x∈B))x(((xA∨xB)∨x∈A)∧(xA∨(x∈A∧x∈B)))x(T∧(T∧(xA∨x∈B)))x(xA∨x∈B)x(x∈Ax∈B)AB二.并运算∪1.定义：A、B是集合，由或属于A，或属于B的元素构成的集合,称之为A与B的并集,记作A∪B。例如A={1,2,3}B={2,3,4}A∪B={1,2,3,4}谓词定义：A∪B={x|x∈A∨x∈B}x∈A∪Bx∈A∨x∈BABA∪B2.性质⑴幂等律对任何集合A，有A∪A=A。⑵交换律对任何集合A、B，有A∪B=B∪A。⑶结合律对任何集合A、B、C，有(A∪B)∪C=A∪(B∪C)。⑷同一律对任何集合A，有A∪Φ=A。⑸零律对任何集合A，有A∪E=E。⑹分配律对任何集合A、B、C，有A∩(B∪C)=(A∩B)∪(A∩C)。A∪(B∩C)=(A∪B)∩(A∪C)。⑺吸收律对任何集合A、B，有A∪(A∩B)=AA∩(A∪B)=A。证明A∪(A∩B)=(A∩E)∪(A∩B)(同一)=A∩(E∪B)(分配)=A∩E=A(零律)(同一)⑻ABA∪B=B。三.差运算-(相对补集)1.定义：A、B是集合，由属于A，而不属于B的元素构成的集合,称之为A与B的差集,或B对A的相对补集，记作A-B。例如A={1,2,3}B={2,3,4}A-B={1}谓词定义：A-B={x|x∈A∧xB}x∈A-Bx∈A∧xB2.性质设A、B、C是任意集合，则⑴A-Φ=A⑵Φ-A=Φ⑶A-A=Φ⑷A-BAABA-B⑸ABA-B=Φ⑹(A-B)-C=(A-C)-(B-C)证明：任取x∈(A-C)-(B-C)x∈(A-C)∧x(B-C)(x∈A∧xC)∧(x∈B∧xC)(x∈A∧xC)∧(xB∨x∈C)(x∈A∧xC∧xB)∨(x∈A∧xC∧x∈C)x∈A∧xC∧xBx∈A∧xB∧xC(x∈A∧xB)∧xCx∈A-B∧xCx∈(A-B)-C所以(A-B)-C=(A-C)-(B-C)⑺A-(B∩C)=(A-B)∪(A-C)⑻A-(B∪C)=(A-B)∩(A-C)证明：任取x∈A-(B∪C)x∈A∧x(B∪C)x∈A∧(x∈B∨x∈C)x∈A∧(xB∧xC)(x∈A∧xB)∧(x∈A∧xC)x∈A-B∧x∈A-Cx∈(A-B)∩(A-C)所以A-(B∪C)=(A-B)∩(A-C))⑼A∩(B-C)=(A∩B)-(A∩C)⑽但∪对-是不可分配的，如A∪(A-B)=A而(A∪A)-(A∪B)=Φ注意:这不是分配律四.绝对补集~1.定义：A是集合,由不属于A的元素构成的集合,称之为A的绝对补集,记作~A。实际上~A=E-A。例如，E={1,2,3,4}A={2,3},~A={1,4}谓词定义：~A=E-A={x|x∈E∧xA}={x|xA}x∈~AxA2.性质设A、B、C是任意集合，则⑴~E=Φ⑵~Φ=E⑶~(~A)=A⑷A∩~A=Φ⑸A∪~A=E⑹A-B=A∩~BA~AE⑺~(A∩B)=~A∪~B⑻~(A∪B)=~A∩~B这两个公式称之为底-摩根定律。证明⑺：任取x∈~(A∩B)x∈~(A∩B)xA∩B(x∈A∧x∈B)(xA∨xB)x∈~A∨x∈~Bx∈~A∪~B∴~(A∩B)=~A∪~B⑼AB~B~A证明