有限集合的基数

《有限集合的基数》由会员分享，可在线阅读，更多相关《有限集合的基数（45页珍藏版）》请在装配图网上搜索。

1、96 有限集合的基数l集合的基数就是集合中元素的个数这一节介绍有限集合的基数和一些结论无限集合的基数将在以后介绍961 有限集合的基数l定义定义961 如果存在nN，使集合A与集合x|xNx的元素个数相同，就说集合A的基数是n，记作#(A)n或|A|n或card(A)=n空集的基数是0l定义定义962 如果存在nN，使n是集合A的基数就说A是有限集合如果不存在这样的n，就说A是无限集合962 幂集和笛卡儿积的基数l 定理定理961 对有限集合A，l 定理定理962 对有限集合A和B，|AB|A|B|963 基本运算的基数l 定理定理963 对有限集合A1和A2，有l 定理定理964 对有限集合

2、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|下面举例说明定理的应用l 例1 在10名青年中有5名是工人，有7名是学生，其中有3名既是工人又是学生，问有几名既不是工人又不是学生?解 设工人的集合是A，学生的集合是B则 有|A|5，|B|=7，|

3、AB|3，又有|-A-B|+|AUB|=10，于是得|-A-B|=10-|AB|=10-(|A|+|B|-|AB|)=1所以有一名既不是工人又不是学生l对3个有限集合A1，A2和A3，可以推广这个定理，得到|A1A2A3|=|A1|+|A2|+|A3|-|A1A2|-|A2A3|-|A1A3|+|A1A2A3|l 例2 30位同学中，15加体育组，8人参加音乐组，6人参加美术组，其中3人同时参加三个组问至少有多少人没有参加任何小组?解 设A1、A2、A3分别表示体育组、音乐组、美术组成员的集合则有|A1|=15,|A2|=8,|A3|=6,|A1A2A3|=3.因此|A1A2A3|=15+8+

4、6-|A1A2|-|A2A3|-|A1A3|+3=32-|A1A2|-|A2A3|-|A1A3|而|A1A2|A1A2A3|=3|A1A3|A1A2A3|=3|A2A3|A1A2A3|=3所以|A1A2A3|32-3-3-3=23至多23人参加小组，所以至少7人不能参加任何小组.若nN且n1,A1,A2,An是有限集合，则97 集合论公理系统l在913例5中，用谓词定义集合时产生了悖论。的方法是使集合论公理化，也就是建立集合论公理系统，它包括一阶谓词公理系统和几个集合论公理集合论公理系统可以推出一阶谓词的所有定理，也可以推出集合论的概念和定理，它防止了集合论中的悖论l 在一阶谓词公理系统中，公

5、理和定理都是永真公式在集合论公理中，少数公理是描述集合性质的，多数公理是构造合法集合的，也就是判定集合存在性的有的公理构造基本集合，另一些公理由已知集合构造新的集合利用这些公理，可以构造所有的集合(公理系统中的合法集合)，这就是证明定理”，集合论的研究对象只是集合除集合外的其他对象(如有序对、数字、字母)都要用集合定义于是对这些对象的研究也就转化为对集合的研究在定义934中，已经用集合定义了有序对以后将用集合定义自然数其他数字和字母也可以用集合定义因为集合的元素都是集合，例如集合，因此，空集是最基本、最重要的集合97 1 集合论公理l 下面介绍ZF(Zermelo-Fraenkel)公理系统，

6、它包括10条集合论公理。下面依次介绍这10条公理，然后重点说明其中几条对每条公理都给出一阶谓词公式，论域包含所有集合(1)外延公理 两个集合相等的充要条件是它们恰好具有同样的元素(x)(y)(xy(z)(zxzy)(2)空集合存在公理 存在不含任何元素的集合(空集)(x)(y)(yx)x是空集这个公理定义了集合论中第一个集合，空集，由外延公理可知，空集是唯一的(3)无序对集合存在公理 对任意的集合x和y，存在一个集合z，它的元素恰好为x和y.(x)(y)(z)(u)(uz(ux)V(uy)在xy时，这个公理构造出恰好有一个元素的集合，如和在xy时，这个公理构造出两个元素的集合，如，和，(4)并

7、集合公理 对任意的集合x，存在一个集合y，它的元素恰好为x的元素的元素，(x)(y)(z)(zy(u)(zuux)这个公理可以由集合，构造集合，它解决了广义并的存在性(集合的广义并是集合)由无序对集合存在公理和并集合公理，可以解决两个集合并集的存在性(并集是集合)(5)子集公理模式(分离公理模式)对于任意的谓词公式P(z)，对任意的集合x，存在一个集合y，它的元素z恰好既是x的元素又使P(z)为真，(x)(y)(z)(zy(zxP(z)对一个具体的谓词(谓词常项)P(z)，子集公理模式就是一条公理，对不同的P(z)，它是不同的公理所以，子集公理模式不是一条公理，而是无限多条有同样模式的公理因此

8、称为公理模式在972节将介绍用子集公理模式解决交集、差集、广义交和笛卡儿积的存在性(集合经这些运算得到的都是集合)，(6)幂集合公理 对任意的集合x，存在一个集合y，它的元素恰好是x的子集，(x)(y)(z)(zy(u)(uzux)公理指出幂集的存在性(集合的幂集是集合)(7)正则公理 对任意的非空集合x，存在x的个元素，它和x不相交(x)(x(y)(yx(xy)正则公理将在973中说明它排除了奇异集合，防止发生悖论(8)无穷公理 存在一个由所有自然数组成的集合(x)(x(y)(yx(yy)x)式中的x是自然数集合N.在974中将说明自然数的定义和无穷公理这个公理构造了第一个无限集合(9)替换

9、公理模式 对于任意的谓词公式P(x,y)，如果对任意的x存在唯一的y使得P(x,y)为真，那么对所有的集合t就存在一个集合s，使s中的元素y恰好是t中元素x所对应的那些y.这也是公理模式，它包括无限多条公理，对一个具体的P(x，y)，就有一条替换公理，(10)选择公理 对任意的关系R，存在一个函数F，F是R的子集，而且F和R的定义域相等也可以简写成(关系R)(函数F)(F Rdom(R)=dom(F)这是有关函数的公理，将在第11章介绍，l 在10条公理中，外延公理和正则公理是描述集合性质的公理，其他公理都是判定集合存在的公理，也就是构造集合的公理，空集合存在公理和无穷公理不以其他集合的存在为

10、前提，是直接构造基本的集合它们称为无条件的存在公理无序对集合存在公理，并集合公理、幂集合公理、子集公理模式、替换公理模式和选择公理是有条件的存在公理这6条公理都是由已知集合构造新集合的公理其中前5条公理构造的集合是唯一的，而选择公理没有给出构造新集合的方法，它只判定了新集合的存在性实际上可能存在多个满足要求的新集合(即存在多个要求的函数)l建立公理系统时，总希望公理是彼此独立的但在这10条公理中，无序对集合存在公理和子集公理模式可以由其它公理推出加入这两条公理是为了使用方便下面给出由其它公理导出这两个公理的简单证明l已知u和v是集合，下面证明u，v也是集合，由空集公理，是集合由幂集公理，P()

11、是集合，P()，也是集合，令集合t=，定义P(x，y)为P(，u)T，P(，v)T，则t和P(x，y)满足替换公理的前提，由替换公理得到，存在由u和v构成的集合su,v，l替换公理模式中，令P(x，y)是(x)(p(x)(x=y)/(z0)(p(z0)/(p(x)/x=y)/(p(x)(x=z0)l显然对任意的x存在唯一的y使p(x)(xy)成立所以替换公理模式的前提成立，则有(t)(s)(u)(us(z)(ztp(z)(z=u)即 (t)(s)(u)(us(utp(u)这就是子集公理模式，因此它是替换公理模式的特例972 子集公理模式l 子集公理模式是(x)(y)(z)(zy(zxp(z)子

12、集公理模式是说，对任意的集合x，存在x的子集y，y的元素z使p(z)为真它主要用于下列情况已知若干满足条件p(z)的元素，但不知这些元素能否组成一个集合这时只要找到一个集合A，使这些满足条件的元素都有zA，这样就可以由A和p(x)用分离公理得到集合x|xAp(x)这就是那些元素组成的集合下面用子集公理模式证明交集、差集、广义交和笛卡儿积的存在性l定理定理971 对任意的集合A和B，交集AB是集合，证明 对集合A，选取xB为子集公理模式中的p(x)由子集公理存在集合A0 x|xAxB，所以，A0AB是集合，l定理定理972 对任意的集合A和B，差集A-B是集合证明 由集合A和谓词公式x B，依据

13、子集公理，存在集合A0=x|xAxB)所以，A0=A-B是集合l 定理定理973 对任意的非空集合A，广义交A是集合，证明 对非空集合A，存在A1A选取公式(y)(yAxy)为p(x)依据子集公理，对集合A1和上述公式，存在集合A0 x|xA1(y)(yAxy)，此外 A=x|(y)(yAxy)由A1A和(y)(yAxy)可以推出xA1，所以A0A，A是集合l 定理定理974 对任意的集合A和B，笛卡儿积AB是集合证明 对任意的，有下面用子集公理证明一个重要结论l 定理定理9.7.5 不存在集合A,使任一集合都是A的元素证明 假设存在集合A，任一集合是A的元素选p(x)为 x x，依据子集公理

14、，存在集合与假设矛盾，定理得证。l下面说明，为什么以前规定不存在?假设是集合，则由广义交的定义，x(y)(yxy)因为y永假，所以右式永真于是左式x对所有x永真，于是是所有集合的集合，与定理975矛盾因此规定不存在，973 正则公理和奇异集合首先定义非空集合的极小元l 定义定义971 对任意的集合A和B，当有AB且AB=，就称A为B的一个极小元l 例如集合B，则A1=是B的极小元，A2=，不是B的极小元l 正则公理是说任一非空集合都有极小元(x)(x(y)(yxxy=)l 正则公理又称为基础公理或限制公理由这个公理可以推出集合的一些重要性质l 定理定理976 对任意的集合A，AA证明 假设存在

15、集合A，使AA，可以构造集合A，有AA由正则公理，A有极小元，这只能是A的唯一元素A，因此，AA=但是，由假设AA，则A与A有公共元A，即AA产生矛盾所以，AAl 定理977 对任意的集合A1和A2有(A1A2A2A1)证明留作思考题，A1,A2违反正则公理。l 定理定理978 对任何非空的传递集合A，有A证明 假设存在非空传递集合A，有A，由正则公理，A中有极小元y，使yA且yA，由假设A，则y由正则公理，非空集合y有极小元z，使zy且zy=，因为A是传递集合，且zy和yA，所以zA，再考虑zy，则yA，产生矛盾结论得证l 由定理结论A，可以进一步推出A=，因而A是传递集合这是定理9.5.1

16、6的结论，下面讨论奇异集合的有关问题l定义定义972 如果集合A中有集合的序列A0A，A1A，AnA，使得，An+lAn，AnAn-1，A1A0，或简写为 An+1AnAn-1 A2A1A0，就称A为奇异集合，l 定理定理979 奇异集合不满足正则公理，证明 设A为奇异集合，则A中的些元素满足An+1AnAn-1 A2A1A0于是可以构造A的非空子集 BA0，A1，An，假设B中有极小元Ai(i0)，则AiB且AiB然而，因为Ai+lAi和Ai+lB，所以AiB，产生矛盾因此B没有极小元，不满足正则公理奇异集合A不是集合l 定理定理9710 若非空集合A不是奇异集合，则A满足正则公理证明 假设

17、A中没有极小元则对任一个A0A，都存在A1，使A1A0且A1AA1也不是A的极小元，应存在A2，使A2A1且A2A依此类推，A中应有元素A0，A1，An,，使得 An+1AnAn-1A1A0因此A是奇异集合，与已知矛盾所以A中有极小元，A满足正则公理l定理指出，若存在奇异集合，则不满足正则公理；若存在正则公理，则不存在奇异集合正则公理是限制性的，它排除了奇异集合的存在，1908年提出的集合论公理中没有正则公理，1917年提出了奇异集合问题1925年提出了正则公理，解决了奇异集合问题。9，74 无穷公理和自然数集合l无穷公理给出自然数集合的存在性下面先定义自然数，再说明无穷公理l定义定义973

18、对任意的集合A，可以定义集合A+=AUA，把A+称为A的后继，A称为A+的前驱l定义定义974 集合0是一个自然数，若集合n是一个自然数，则集合n+1=n+也是一个自然数l 按照这个定义，可以列出各自然数l 0没有元素，1有一个元素，2有两个元素，所以。这样定义自然数是合理的，很容易定义自然数间的大小关系，l定义定义975 对任意的自然数m和n，mmmnmnnml无穷公理是(N)(N(y)(yNy+N)无穷公理给出了自然数集合N的存在性式中的N就是自然数集合，依据外延公理，自然数集合是唯一的，l 下面讨论自然数的三歧性l 定义定义976 对集合A，如果对任意的集合A1A和A2A，使 A1A2,A1=A2和A2A1三式中恰好有一个成立，就称集合A有三歧性。l 例如集合3=0，1，2因为01，02，12，所以3有三歧性，l 定理定理9711 集合N有三歧性每个自然数都有三歧性对任意的自然数m和n，有mn