离散数学-4-6基数的比较.ppt

《离散数学-4-6基数的比较.ppt》由会员分享，可在线阅读，更多相关《离散数学-4-6基数的比较.ppt（9页珍藏版）》请在三一办公上搜索。

1、第三章 集合与关系,4-6 基数的比较授课人：李朔,1 基数的大小,在上一节我们论述了可数集和一些不可数集的基数概念。为了证明两个集合的基数相等，我们必须构造两个集合之间的双射函数，这常常是非常困难的工作。下面将介绍证明基数相等的一个较为简单的方法，为此先说明基数是如何比较大小的。定义4-6.1 若从集合A到集合B存在一个入射，则称A的基数不大于B的基数，记作KAKB。若从A到B存在一个入射，但不存在双射，则称A的基数小于B的基数，记作KAKB。,2 性质,定理4-6.1(Zermelo定理)令A和B是任意集合，则以下三条中恰有一条成立。a)KAKBb)KBKAc)KAKB定理4-6.2(Ca

2、ntor-Schroder-Bernstein定理)设A和B是集合，如果KAKB，KBKA，则KAKB这个定理对证明集合有相同的基数提供了有效方法，如果我们能够构造一入射函数f：AB，即说明有KAKB，另外，如能够构造入射函数g：BA，即有KBKA，因此根据本定理就得到KAKB。,2 性质,例题1 证明0，1与(0，1)有相同的基数。证明 作入射函数：f：(0，1)0，1，f(x)xg：0，1(0，1)。g(x)x/2+1/4例题2 设AN，B(0，1)，KA0，KB，求证KAB 证明 定义一个从AB到正实数的函数f。f：ABx|xR+f(n，x)n+x因为f是入射函数，且KR+。所以KAB。

3、此外，作映射g：(0，1)ABg(x)因为g是入射的，故 KAB。因此 KAB,2 性质,定理4-6.3 设A是有限集合，则KA 0.证明:设KAn，则A0，1，2，n-1。定义函数f：0，1，2，n-1N，f(x)x；f是入射函数，故KAKN 在定理4-4.2中已证得N到A之间不存在双射函数，所以KAKN故KAKN，即KA 0又作映射g：N0，l，g(n)1/(n+1)，g是入射函数，故，0。因为N与0，1间不能一一对应，故0，因此0。,2 性质,定理4-6.4 如果A是无限集，那么0KA。证明 因为A是无限集合，故A必包含一个可数无限子集A，作函数f：AA，使得f(x)x，对xA，f是入射

4、函数，故KAKA。但KA0，因此0KA。*尽管我们证明了0，以及 0 KA。但是直到目前为止还没有人能够证明是否有一无限集，其基数严格介于0 与 之间。*假定 是大于0 的最小基数，即不存在任何基数KS，使0KS 成立，这就是著名的连续统假设。,2 性质,定理4-6.5(Cantor定理)设M是一个集合，T P(M)则 KMKT 证明 a)首先证明KMKT。为此作函数f：MP(M)，使得 f(a)a，则f是入射函数，故KMKT。b)其次我们证明KMKT。反之，若KMKT，则必有函数：MT是双射函数。对于任意mM，必有T中唯一的(m)与之对应，即m(m)。若m(m)称m为M的内部元素，若m(m)称m为M的外部元素。设Sx|xM，x(x)，即S为M的外部元素集合，则有S M，故ST。因为 是双射函数，故必有一个元素bM，使(b)S若bS，因为(b)S，此时b为M的内部元素，得出矛盾。若b S，因为(b)S，此时b为M的外部元素，也得出矛盾。故KMKT，由a)，b)得到KM KT。,本课小结,基数基数的诸性质,作业,P173（2）,