離散數(shù)學(xué)鄭版watched05無限集合

1有限集合可數(shù)無限集合不可數(shù)無限集合基數(shù)及其比較無限集合2有限和無限集合給定兩個集合P和Q，如果對P中每個不同元素，與Q中每個不同元素，可以分別兩兩成對，則稱P的元素和Q的元素間存在著一一對應(yīng)。 如：奇數(shù)集合和偶數(shù)集合之間有一一對應(yīng)。當(dāng)且僅當(dāng)集合A的元素和集合B的元素之間存在著一一對應(yīng)，集合A和集合B稱為是等勢的（同濃的），記作A~B。 如，自然數(shù)集合N和非負(fù)偶數(shù)集合M是等勢的。在集合族上等勢關(guān)系是一個等價關(guān)系。3有限和無限集合N的初始段是前n個（包括0個）自然數(shù)的集合{0,1,...,n-1}或N自身。如果有從N的初始段{0,1,...,n-1}到A的雙射函數(shù)，則稱集合A是有限的，具有基數(shù)n。如果集合A不是有限的，則稱它是無限的。自然數(shù)集合N是無限的。證明：設(shè)n是N的任意元素，f是任意的從{0,1,2,...,n-1}到N的函數(shù)。設(shè)k=1+max{f(0),f(1),...,f(n-1)}，則k是自然數(shù)，但對于每一個x∈{0,1,2,...,n-1}，有f(x)≠k，因此f不可能是滿射函數(shù)，也就不是雙射函數(shù)。又因為f和n是任意的，故N不是有限的，即是無限的。4有限和無限集合有限集合的每一子集是有限的。 證明：設(shè)S是有限集T的任一子集。如果S是空集，那么存在空集到S的雙射函數(shù)－空函數(shù)，則S是有限的；如果S是非空集，則T也是非空集。因為T是有限的，所以存在雙射函數(shù)使T的每一元素和某個N的初始段中的數(shù)對應(yīng)。把和i對應(yīng)的元素記為ai，于是T的元素是a0,a1,a2,...,an-1?，F(xiàn)構(gòu)造一個雙射函數(shù)g，使某一N的初始段和S的元素相對應(yīng)。5有限和無限集合開始結(jié)束置i=0,j=0ai在S中g(shù)(j)=ai,j++,i++i<ni++YNYN按左圖方法構(gòu)造函數(shù)g，則為從初始段{0,1,...,j-1}到S的雙射函數(shù)。所以S是有限集。設(shè)S是T的子集，如果S是無限集，則T是無限集。6可數(shù)集合度量集合大小的數(shù)稱為基數(shù)或勢。 有限集合A的大小通過構(gòu)造從N的初始段{0,1,...,n-1}到A的雙射函數(shù)進行比較。有限集合的基數(shù)就是該集合的元素個數(shù)，那么無限集合呢？如自然數(shù)如果存在一個從自然數(shù)集合N到A的雙射函數(shù)，那么集合A的基數(shù)是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+構(gòu)造雙射函數(shù)f(x)=x+1。7可數(shù)集合如果存在從N的初始段到集合A的雙射函數(shù)，則稱集合A是可數(shù)的或可列的；如果|A|=s\s0，則稱集合A是可數(shù)無限的；如果集合A不是可數(shù)的，則稱集合A是不可數(shù)的，或不可數(shù)無限的。一個集合A,如果它的元素可列成表,我們說這個集合是可枚舉的。這個表可以是有限的也可以是無限的,A的元素也可以在表中重復(fù)出現(xiàn),即不要求表中的所有項都是不同的。如果一張表列出集合A,那么表的每一項是A的一個元素,而A的每一元素是表的一項。設(shè)A是一集合,A的枚舉是從N的初始段到A的一個滿射函數(shù)f。如果f也是單射的(所以是雙射的),那么f是一個無重復(fù)枚舉;如果f不是單射的,那么f是重復(fù)枚舉。枚舉函數(shù)f通常是用給出序列〈f(0),f(1),f(2),…〉含蓄地指定。8可數(shù)集合(a)如果A=Φ,僅有一個A的枚舉－空函數(shù)。(b)如果A={x,y},那么〈x,y,x〉和〈y,x〉都是A的有限枚舉,第一個是重復(fù)枚舉,第二個是無重復(fù)枚舉。(c)設(shè)A是非負(fù)的3的整倍數(shù)集合,那么〈0,3,6,…〉和〈3,0,9,6,15,12,…〉都是A的無重復(fù)枚舉,后者的枚舉函數(shù)是9例:

正有理數(shù)集合Q+是無限可數(shù)集合。顯然Q+不是有限的,因為其真子集正整數(shù)集合I+是無限的?？扇鐖D5.1-1那樣,對Q+進行重復(fù)枚舉,枚舉的次序用有向路徑指出。所以,Q+是可數(shù)無限的?？蓴?shù)集合10圖5.1-1可數(shù)集合11可數(shù)集合一個集合A是可數(shù)的當(dāng)且僅當(dāng)存在A的枚舉。A為可數(shù)集的充要條件是可以排列成{a1,a2,...,an,...}的形式。任一無限集，必含有可數(shù)（有限/無限）子集。

證明：設(shè)A是無限集，從A中取一元素a1，取后A-{a1}非空，再從A-{a1}中取一元素a2，A-{a1,a2}也非空，于是又可以取一元素a3，如此繼續(xù)下去，就可以得到A的可數(shù)子集。12可數(shù)集合任一無限集合必與其某一真子集等勢。 證明：設(shè)任一無限集合M，其必含有可數(shù)子集，設(shè)為A＝{a1,a2,...,an,...}，令B＝M-A，可以定義集合M到其一個真子集的函數(shù)f：M→M-{a1}，使得f(an)＝f(an+1)(n=1,2,…)且對于任一b∈B，有f(b)＝b。該函數(shù)為雙射函數(shù)?？蓴?shù)集的任何無限子集是可數(shù)的。 證明：設(shè)A為任一可數(shù)集合，B為A的一個無限子集，如將A的元素排列成a1,a2,...,an,...，從a1開始向后檢查，不斷的刪除不在B中的元素，則得到新的一列ai1,ai2,...,ain,...，與自然數(shù)一一對應(yīng)，所以B是可數(shù)的。13可數(shù)集合可數(shù)個兩兩不相交的可數(shù)集的并集是可數(shù)的。14可數(shù)集合設(shè)A和B是可數(shù)集合，則A×B是可數(shù)集合。 如N×N有理數(shù)的全體組成的集合是可數(shù)的。A={a0,a1,a2,…},B={b0,b1,b2,…}b0,b1,b2,…a0<a0,b0><a0,b1><a0,b2>…a1<a1,b0><a1,b1><a1,b2>…a2<a2,b0><a2,b1><a2,b2>……15不可數(shù)無限集不是所有無限集都是可數(shù)無限集，如實數(shù)的子集[0,1]是不可數(shù)無限集。 證明：設(shè)f是從N到[0,1]的任一函數(shù),我們將證明f不是滿射函數(shù),從而證明不存在從N到[0,1]的雙射。我們把每一x∈[0,1]都表示為無限十進制小數(shù),于是f(0)，f(1)，f(2)…可表示為16不可數(shù)無限集

這里xni是f(n)小數(shù)展開式的第i個數(shù)字?，F(xiàn)在我們指定實數(shù)y∈［0,1］如下:如果xii≠1如果xii=1數(shù)y是決定于數(shù)組對角線上的數(shù)字。顯然,y∈［0,1］,然而,y與每一f(n)的展開式至少有一個數(shù)字(即第n個數(shù)字)不同。因此,對一切n,y≠f(n)。我們得出映射f:N→［0,1］不是一個滿射函數(shù)。所以f不是雙射。因為f是任意的,這證明［0,1］不是可數(shù)的。這個定理和證明是康脫給出的。這種證明方法叫“康脫對角線法”,被廣泛地應(yīng)用于可計算理論。17不可數(shù)無限集

不是所有無限集都是可數(shù)無限集，如實數(shù)的子集[0,1]是不可數(shù)無限集，如果有從［0,1］到集合A的雙射函數(shù),那么A的基數(shù)是c，也稱為連續(xù)統(tǒng)的勢，因為集合[0,1]常稱為連續(xù)統(tǒng)。|[a，b]|=c。這里［a，b］是R中的任意閉區(qū)間,a＜b?？梢詮模?,1］到［a,b］構(gòu)造雙射函數(shù)f(x)=(b-a)x+a。｜(0,1)｜=｜［0,1］｜。這兩個集合的不同僅在于區(qū)間的兩端點;構(gòu)造從［0,1］到(0,1)的一個雙射函數(shù)。18不可數(shù)無限集

定義集合A是

,定義映射f如下:19不可數(shù)無限集全體實數(shù)構(gòu)成的集合R是不可數(shù)的，即K[R]=c定義一個從(0,1)到R的雙射函數(shù)如下:因為前例中的f是從［0,1］到(0,1)的雙射函數(shù),而g是(0,1)到R的雙射函數(shù),合成函數(shù)gf是從［0,1］到R的雙射函數(shù)。20基數(shù)的比較

現(xiàn)在已知可數(shù)集和某些不可數(shù)集的基數(shù)，為了證明兩個集合基數(shù)相等，必須構(gòu)造兩個集合之間的雙射函數(shù)，這通常是非常困難的。為此，引入基數(shù)的比較。如果A和B是有限集，|A|=n，|B|=m，則若從集合A到集合B存在一個雙射，則n=m;若從集合A到集合B存在一個單射，則n≤m;若從集合A到集合B存在一個單射，但不存在雙射，則n<m。21基數(shù)的比較設(shè)A和B是任意集合，則若從集合A到集合B存在一個雙射，則稱A和B有相同的基數(shù)（或等勢），記為|A|=|B|;若從集合A到集合B存在一個單射，則稱A的基數(shù)小于等于B的基數(shù)，記為|A|≤|B|;若從集合A到集合B存在一個單射，但不存在雙射，則稱A的基數(shù)小于B的基數(shù)，記為|A|<|B|。22基數(shù)的比較Zermelo定理：設(shè)A和B是任意集合，則以下三條中恰有一條成立。|A|<|B||A|>|B||A|=|B|Cantor-Schroder-Bernstein定理：設(shè)A和B是集合，如果|A|≤|B|，|B|≤|A|，則|A|=|B|。 這樣，如果我們能夠構(gòu)造一個從A到B的單射函數(shù)，說明有|A|≤|B|；還能夠構(gòu)造一個從B到A的單射函數(shù)，說明|B|≤|A|，則有|A|=|B|。23基數(shù)的比較24基數(shù)的比較設(shè)A是有限集合，則|A|<s\s0<c。

證明：假定|A|=n。 現(xiàn)證明對每一n，有|{0,1,...,n-1}|<|N|<|[0,1]|。25無限集合的特性s\s0是最小的無限集合的基數(shù)。即對于任何無限集A，有s\s0≤|A|。 證明：如果A是無限集合,那么A包含一可數(shù)無限子集B。因為映射

f:B→A,f(x)=x,x∈B 是從B到A的單射函數(shù),這得出|B|≤|A|,而|B|=s\s0，所以s\s0