05无限集合.ppt

有限集合可数无限集合不可数无限集合基数及其比较无限集合1有限和无限集合给定两个集合P和Q,如果对P中每个不同元素,与Q中每个不同元素,可以分别两两成对,则称P的元素和Q的元素间存在着一一对应。 如:奇数集合和偶数集合之间有一一对应。当且仅当集合A的元素和集合B的元素之间存在着一一对应,集合A和集合B称为是等势的(同浓的),记作A~B。 如,自然数集合N和非负偶数集合M是等势的。在集合族上等势关系是一个等价关系。2有限和无限集合N的初始段是前n个(包括0个)自然数的集合{0,1,...,n-1}或N自身。如果有从N的初始段{0,1,...,n-1}到A的双射函数,则称集合A是有限的,具有基数n。如果集合A不是有限的,则称它是无限的。自然数集合N是无限的。证明:设n是N的任意元素,f是任意的从{0,1,2,...,n-1}到N的函数。设k=1+max{f(0),f(1),...,f(n-1)},则k是自然数,但对于每一个x∈{0,1,2,...,n-1},有f(x)≠k,因此f不可能是满射函数,也就不是双射函数。又因为f和n是任意的,故N不是有限的,即是无限的。3有限和无限集合有限集合的每一子集是有限的。 证明:设S是有限集T的任一子集。如果S是空集,那么存在空集到S的双射函数-空函数,则S是有限的;如果S是非空集,则T也是非空集。因为T是有限的,所以存在双射函数使T的每一元素和某个N的初始段中的数对应。把和i对应的元素记为ai,于是T的元素是a0,a1,a2,...,an-1。现构造一个双射函数g,使某一N的初始段和S的元素相对应。4有限和无限集合开始结束置i=0,j=0ai在S中g(j)=ai,j++,i++i<ni++YNYN按左图方法构造函数g,则为从初始段{0,1,...,j-1}到S的双射函数。所以S是有限集。设S是T的子集,如果S是无限集,则T是无限集。5可数集合度量集合大小的数称为基数或势。 有限集合A的大小通过构造从N的初始段{0,1,...,n-1}到A的双射函数进行比较。有限集合的基数就是该集合的元素个数,那么无限集合呢?如自然数如果存在一个从自然数集合N到A的双射函数,那么集合A的基数是s\s0,记为|A|=s\s0。 显然,|N|=s\s0。 例:A={0,1,4,9,16,...,n2,...}, B={0,3,12,27,...,3n2...} |I+|=s\s0。因为可从N到I+构造双射函数f(x)=x+1。6可数集合如果存在从N的初始段到集合A的双射函数,则称集合A是可数的或可列的;如果|A|=s\s0,则称集合A是可数无限的;如果集合A不是可数的,则称集合A是不可数的,或不可数无限的。一个集合A,如果它的元素可列成表,我们说这个集合是可枚举的。这个表可以是有限的也可以是无限的,A的元素也可以在表中重复出现,即不要求表中的所有项都是不同的。如果一张表列出集合A,那么表的每一项是A的一个元素,而A的每一元素是表的一项。设A是一集合,A的枚举是从N的初始段到A的一个满射函数f。如果f也是单射的(所以是双射的),那么f是一个无重复枚举;如果f不是单射的,那么f是重复枚举。枚举函数f通常是用给出序列〈f(0),f(1),f(2),…〉含蓄地指定。7可数集合(a)如果A=Φ,仅有一个A的枚举-空函数。(b)如果A={x,y},那么〈x,y,x〉和〈y,x〉都是A的有限枚举,第一个是重复枚举,第二个是无重复枚举。(c)设A是非负的3的整倍数集合,那么〈0,3,6,…〉和〈3,0,9,6,15,12,…〉都是A的无重复枚举,后者的枚举函数是8例:正有理数集合Q+是无限可数集合。显然Q+不是有限的,因为其真子集正整数集合I+是无限的。-1那样,对Q+进行重复枚举,枚举的次序用有向路径指出。所以,Q+是可数无限的。-1可数集合10