,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,*,9,6,有限集合的基数,集合的基数就是集合中元素的个数这一节介绍有限集合的基数和一些结论无限集合的基数将在以后介绍,96 有限集合的基数集合的基数就是集合中元素的个数这一,9,6,1,有限集合的基数,定义,9,6,1,如果存在,nN,,使集合,A,与集合,x|xNx,的元素个数相同,就说集合,A,的基数是,n,,记作,#(A),n,或,|A|,n,或,card(A)=n,空集,的基数是,0,定义,9,6,2,如果存在,nN,,使,n,是集合,A,的基数就说,A,是有限集合如果不存在这样的,n,,就说,A,是无限集合,961 有限集合的基数定义961 如果存在nN,9,6,2,幂集和笛卡儿积的基数,定理,9,6,1,对有限集合,A,,,962 幂集和笛卡儿积的基数定理961 对有限集,定理,9,6,2,对有限集合,A,和,B,,,|AB|,|A|B|,公理系统构造的第一个集合就是空集课件,9,6,3,基本运算的基数,定理,9,6,3,对有限集合,A1,和,A2,,有,963 基本运算的基数定理963 对有限集合A1,下述定理通常称为包含排斥原理,它有更多的用途,比较上面定理的第,(4),项与包含排斥原理的形式。,定理,9,6,4,对有限集合,A1,和,A2,,有,|A1A2|=|A1|+|A2|-|A1A2|,证明,(1),若,A1,与,A2,不相交,则,A1A2,,而且,|A1A2|=0,,这时显然成立,|A1A2|,|A1|+|A2|,,,(2),若,A1,与,A2,相交,则,A1A2,,但有,|A1|=|A1-A2|+|A1A2|,|A2|=|-A1A2|+|A1A2|,,,此外,|A1A2|=|A1-A2|+|-A1A2|+|A1A2|,,,所以,|A1A2|=|A1|+|A2|-|A1A2|,下述定理通常称为包含排斥原理,它有更多的用途,下面举例说明定理的应用,例,1,在,10,名青年中有,5,名是工人,有,7,名是学生,其中有,3,名既是工人又是学生,问有几名既不是工人又不是学生,?,解 设工人的集合是,A,,学生的集合是,B,则有,|A|,5,,,|B|=7,,,|AB|,3,,又有,|-A-B|+|AUB|=10,,于是得,|-A-B|=10-|AB|=10-(|A|+|B|-|AB|),=1,所以有一名既不是工人又不是学生,下面举例说明定理的应用,对,3,个有限集合,A1,,,A2,和,A3,,可以推广这个定理,得到,|A1A2A3|=|A1|+|A2|+|A3|-|A1A2|-|A2A3|-|A1A3|+|A1A2A3|,对3个有限集合A1,A2和A3,可以推广这个定理,得到,例,2 30,位同学中,,15,加体育组,,8,人参加音乐组,,6,人参加美术组,其中,3,人同时参加三个组问至少有多少人没有参加任何小组,?,解 设,A1,、,A2,、,A3,分别表示体育组、音乐组、美术组成员的集合则有,|A1|=15,|A2|=8,|A3|=6,|A1A2A3|=3.,因此,|A1A2A3|=15+8+6-|A1A2|-|A2A3|-|A1A3|+3=32-|A1A2|-|A2A3|-|A1A3|,例2 30位同学中,15加体育组,8人参加音乐组,6人参加,而,|A1A2|,|A1A2A3|=3,|A1A3|,|A1A2A3|=3,|A2A3|,|A1A2A3|=3,所以,|A1A2A3|,32-3-3-3=23,至多,23,人参加小组,所以至少,7,人不能参加任何小组,.,而|A1A2|A1A2A3|=3,包含排斥原理的推广,若,n,N,且,n1,A1,A2,An,是有限集合,则,包含排斥原理的推广,9,7,集合论公理系统,在,9,1,3,例,5,中,用谓词定义集合时产生了悖论。,防止悖论,的方法是使集合论公理化,也就是建立集合论公理系统,集合论公理系统是一阶谓词公理系统的扩展,,它包括一阶谓词公理系统和几个集合论公理集合论公理系统可以推出一阶谓词的所有定理,也可以推出集合论的概念和定理,它防止了集合论中的悖论,97 集合论公理系统在913例5中,用谓词定义集合,在一阶谓词公理系统中,公理和定理都是永真公式在集合论公理中,少数公理是描述集合性质的,多数公理是构造合法集合的,也就是判定集合存在性的有的公理构造基本集合,另一些公理由已知集合构造新的集合利用这些公理,可以构造所有的集合,(,公理系统中的合法集合,),,这就是证明定理,在公理系统中的集合,都是由公理得到的合法集合,以前介绍的外延法和内涵法都不能构造出集合可以说,集合论公理系统的主要目的是构造出所有合法的集合,即判定集合的存在性、合法性,在一阶谓词公理系统中,公理和定理都是永真公式在集合论公理中,集合论公理系统的一个基本思想是认为“任一集合的所有元素都是集合,”,集合论的研究对象只是集合除集合外的其他对象,(,如有序对、数字、字母,),都要用集合定义于是对这些对象的研究也就转化为对集合的研究在定义,9,3,4,中,已经用集合定义了有序对以后将用集合定义自然数其他数字和字母也可以用集合定义因为集合的元素都是集合,,所以集合最内层的元素只能是空集,例如集合,,,,,,,,因此,空集是最基本、最重要的集合,公理系统构造的第一个集合就是空集,集合论公理系统的一个基本思想是认为“任一集合的所有元素都是集,9,7,1,集合论公理,下面介绍,ZF(Zermelo-Fraenkel),公理系统,它包括,10,条集合论公理。下面依次介绍这,10,条公理,然后重点说明其中几条对每条公理都给出一阶谓词公式,论域包含所有集合,(1),外延公理 两个集合相等的充要条件是它们恰好具有同样的元素,(,x)(,y)(x,y(,z)(zxzy),(2),空集合存在公理 存在不含任何元素的集合,(,空集,),(,x)(,y)(y,x)x,是空集,这个公理定义了集合论中第一个集合,空集,由外延公理可知,空集是唯一的,97 1 集合论公理下面介绍ZF(Zermelo-Fr,(3),无序对集合存在公理 对任意的集合,x,和,y,,存在一个集合,z,,它的元素恰好为,x,和,y.,(,x)(,y)(,z)(,u)(uz(u,x)V(u,y),在,x,y,时,这个公理构造出恰好有一个元素的集合,如,和,在,xy,时,这个公理构造出两个元素的集合,如,,,和,,,,,(3)无序对集合存在公理 对任意的集合x和y,存在一个集,(4),并集合公理 对任意的集合,x,,存在一个集合,y,,它的元素恰好为,x,的元素的元素,,(,x)(,y)(,z)(zy(,u)(zuux),这个公理可以由集合,,,,,,,构造集合,,,,,它解决了广义并的存在性,(,集合的广义并是集合,),由无序对集合存在公理和并集合公理,可以解决两个集合并集的存在性,(,并集是集合,),(4)并集合公理 对任意的集合x,存在一个集合y,它的元,(5),子集公理模式,(,分离公理模式,),对于任意的谓词公式,P(z),,对任意的集合,x,,存在一个集合,y,,它的元素,z,恰好既是,x,的元素又使,P(z),为真,,(,x)(,y)(,z)(zy(zxP(z),对一个具体的谓词,(,谓词常项,)P(z),,子集公理模式就是一条公理,对不同的,P(z),,它是不同的公理所以,子集公理模式不是一条公理,而是无限多条有同样模式的公理因此称为公理模式在,9,7,2,节将介绍用子集公理模式解决交集、差集、广义交和笛卡儿积的存在性,(,集合经这些运算得到的都是集合,),,,(5)子集公理模式(分离公理模式)对于任意的谓词公式P(,(6),幂集合公理 对任意的集合,x,,存在一个集合,y,,它的元素恰好是,x,的子集,,(,x)(,y)(,z)(zy(,u)(uzux),公理指出幂集的存在性,(,集合的幂集是集合,),(6)幂集合公理 对任意的集合x,存在一个集合y,它的元素,(7),正则公理 对任意的非空集合,x,,存在,x,的,个元素,它和,x,不相交,(,x,)(x,(,y,)(yx(xy,),正则公理将在,9,7,3,中说明它排除了奇异集合,防止发生悖论,(7)正则公理 对任意的非空集合x,存在x的个元素,它和,(8),无穷公理 存在一个由所有自然数组成的集合,(,x)(,x(,y)(yx(yy)x),式中的,x,是自然数集合,N.,在,9,7,4,中将说明自然数的定义和无穷公理这个公理构造了第一个无限集合,(8)无穷公理 存在一个由所有自然数组成的集合,(9),替换公理模式 对于任意的谓词公式,P(x,y),,如果对任意的,x,存在唯一的,y,使得,P(x,y),为真,那么对所有的集合,t,就存在一个集合,s,,使,s,中的元素,y,恰好是,t,中元素,x,所对应的那些,y.,这也是公理模式,它包括无限多条公理,对一个具体的,P(x,,,y),,就有一条替换公理,,(9)替换公理模式 对于任意的谓词公式P(x,y),如果对,(10),选择公理 对任意的关系,R,,存在一个函数,F,,,F,是,R,的子集,而且,F,和,R,的定义域相等,也可以简写成,(,关系,R)(,函数,F)(F,Rdom(R)=dom(F),这是有关函数的公理,将在第,11,章介绍,,(10)选择公理 对任意的关系R,存在一个函数F,F是R的,在,10,条公理中,外延公理和正则公理是描述集合性质的公理,其他公理都是判定集合存在的公理,也就是构造集合的公理,空集合存在公理和无穷公理不以其他集合的存在为前提,是直接构造基本的集合它们称为无条件的存在公理无序对集合存在公理,并集合公理、幂集合公理、子集公理模式、替换公理模式和选择公理是有条件的存在公理这,6,条公理都是由已知集合构造新集合的公理其中前,5,条公理构造的集合是唯一的,而选择公理没有给出构造新集合的方法,它只判定了新集合的存在性实际上可能存在多个满足要求的新集合,(,即存在多个要求的函数,),在10条公理中,外延公理和正则公理是描述集合性质的公理,其他,建立公理系统时,总希望公理是彼此独立的但在这,10,条公理中,无序对集合存在公理和子集公理模式可以由其它公理推出加入这两条公理是为了使用方便下面给出由其它公理导出这两个公理的简单证明,建立公理系统时,总希望公理是彼此独立的但在这10条公理中,,已知,u,和,v,是集合,下面证明,u,,,v,也是集合,由空集公理,,是集合由幂集公理,,P(,),是集合,,P(,),,,也是集合,令集合,t=,,,,定义,P(x,,,y),为,P(,,,u),T,,,P(,,,v),T,,则,t,和,P(x,,,y),满足替换公理的前提,由替换公理得到,存在由,u,和,v,构成的集合,s,u,v,,,已知u和v是集合,下面证明u,v也是集合,由空集公理,,替换公理模式中,令,P(x,,,y),是,(,x,)(p(x)(x=y)/,(,z,0,)(p(,z,0,)/(p(x)/x=y)/(p(x)(x=,z,0,),显然对任意的,x,存在唯一的,y,使,p(x)(x,y),成立所以替换公理模式的前提成立,则有,(,t)(,s)(,u)(us(,z)(ztp(z)(z=u),即,(,t)(,s)(,u)(us(utp(u),这就是子集公理模式,因此它是替换公理模式的特例,替换公理模式中,令P(x,y)是,9,7,2,子集公理模式,子集公理模式是,(,x)(,y)(,z)(zy(zxp(z),子集公理模式是说,对任意的集合,x,,存在,x,的子集,y,,,y,的元素,z,使,p(z),为真它主要用于下列情况已知若干满足条件,p(z),的元素,但不知这些元素能否组成一个集合这时只要找到一个集合,A,,使这些满足条件的元素都有,zA,,这样就可以由,A,和,p(x),用分离公理得到集合,x|xAp(x),这