離散數(shù)學(xué)第五章無限集合

離散數(shù)學(xué)第五章無限集合第一頁，共六十二頁，編輯于2023年，星期日5.1可數(shù)和不可數(shù)集合5.1.1有限和無限集合

定義5.1-1

N的初始段是前n個(?包括0個)自然數(shù)的集合{0,1,…,n-1}或N自身。

定義5.1-2

如果有從N的初始段{0,1,…,n-1}到A的雙射函數(shù),那么集合A是有限的,具有基數(shù)n∈N。如果集合A不是有限的,那么它是無限的。第二頁，共六十二頁，編輯于2023年，星期日

定理5.1-1

自然數(shù)集合N是無限的。;

證為了證明N不是有限的,我們必須證明沒有n∈N使從{0,1,2,…,n-1}到N的雙射函數(shù)存在。設(shè)n是N的任意元素,f是任意從{0,1,…,n-1}到N的函數(shù),?令k=1+max｛f(0),f(1),…,f(n-1)｝那么k∈N,但對每一x∈{0,1,2,…,n-1},f(x)?≠k。這說明,f不是一個滿射函數(shù),所以f不是一個雙射函數(shù)。因為n和f都是任意選取的,我們得出N是無限的。證畢。第三頁，共六十二頁，編輯于2023年，星期日

定理5.1-2

有限集合的每一子集是有限的。

證設(shè)S是有限集T的任一子集,(i)如果S是空集,那么存在到S的雙射函數(shù)——空函數(shù),根據(jù)定義5.1-2,S是有限的。

(ii)如果S是非空集,那么T也是非空集。因為T是有限的,所以存在雙射函數(shù)使T的每一元素和某個N的初始段中的數(shù)對應(yīng)。我們把和數(shù)i對應(yīng)的元素就記為ai,于是T的元素是a0,a1,a2,…,an-1第四頁，共六十二頁，編輯于2023年，星期日

現(xiàn)在我們要造出一個雙射函數(shù)g,使某一N的初始段和S的元素對應(yīng)。構(gòu)造方法如下:(1)置i=0,j=0。

(2)先檢查ai是否在S中,如果在S中,轉(zhuǎn)第3步。否則轉(zhuǎn)第4步。

(3)使g(j)=ai,把j的值加1,把i的值加1,加1后如果i＜n轉(zhuǎn)第(2)步,否則結(jié)束。

(4)把i的值加1,加1后如果i＜n轉(zhuǎn)第(2)步,否則結(jié)束。容易看出這樣構(gòu)造的函數(shù)g是從初始段{0,1,2,…,j-1}到S的雙射函數(shù)。按定義5.1-2,S是有限集。第五頁，共六十二頁，編輯于2023年，星期日

推論5.1-2

設(shè)S是T的子集,如果S是無限集,那么T是無限集。本推論是上一定理的逆反。

例1

設(shè)A表示永不停機(jī)的ALGOL程序集合,我們通過構(gòu)造永不停機(jī)的程序集合A的一個子集A′,證明A是無限集合。begin;B:gotoB;end

這個程序我們記作p0是A的一個元素。在緊接于begin的后邊,我們插入語句

gotoB第六頁，共六十二頁，編輯于2023年，星期日

5.1.2可數(shù)集合

度量集合大小的數(shù)叫基數(shù)或勢。為確定有限集的大小,我們把稱作N的初始段的集合{0,1,…,n-1}作為“標(biāo)準(zhǔn)集合”,用雙射函數(shù)做工具,對它們進(jìn)行比較。當(dāng)且僅當(dāng)從{0,1,2,…,n-1}到集合A存在一雙射函數(shù)時,稱集合A具有基數(shù)n,記為|A|=n,記為|A|=n,這就是日常生活中的數(shù)數(shù)的概念。現(xiàn)在我們將這種想法加以推廣。通過選取一些新的“標(biāo)準(zhǔn)集合”,建立無限集合的基數(shù)的概念。第七頁，共六十二頁，編輯于2023年，星期日

定義5.1-3

如果存在一個從N到A的雙射函數(shù),那么集合A的基數(shù)是,記為。顯然,存在從N到N的雙射函數(shù),所以,,讀做阿列夫零,是希伯來文第一個字母。第八頁，共六十二頁，編輯于2023年，星期日例2函數(shù)f:N→I+,f(x)=x+1是一雙射函數(shù)。函數(shù)f:N→I,當(dāng)x是偶數(shù)時當(dāng)x是奇數(shù)時是一雙射函數(shù)。第九頁，共六十二頁，編輯于2023年，星期日

定義5.1-4

如果存在從N的初始段到集合A的雙射函數(shù),則稱集合A是可數(shù)的或可列的如果,則稱集合A是可數(shù)無限的;如果集合A不是可數(shù)的,則稱集合A是不可數(shù)的或不可數(shù)無限的。

一個集合A,如果它的元素可列成表,我們說這個集合是可可枚舉的。這個表可以是有限的也可以是無限的,A的元素也可以在表中重復(fù)出現(xiàn),即不要求表中的所有項都是有別的。如果一張表列出集合A,那么表的每一項是A的一個元素,而A的每一元素是表的一項。第十頁，共六十二頁，編輯于2023年，星期日

定義5.1-5

設(shè)A是一集合,A的枚舉是從N的初始段到A的一個滿射函數(shù)f。如果f也是單射的(所以是雙射的),那么f是一個無重復(fù)枚舉;如果f不是單射的,那么f是重復(fù)枚舉。枚舉函數(shù)f通常是用給出序列〈f(0),f(1),f(2),…〉含蓄地指定。第十一頁，共六十二頁，編輯于2023年，星期日

例3

(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ù)是第十二頁，共六十二頁，編輯于2023年，星期日

定理5.1-3

一個集合A是可數(shù)的當(dāng)且僅當(dāng)存在A的枚舉。

證必要性。如果A是可數(shù)的,那么根據(jù)定義,存在一從N的初始段到A的雙射函數(shù),這證明了存在A的枚舉。充分性。我們考慮兩種情況:

情況1

如果A是有限的,那么根據(jù)有限集合的定義和可數(shù)集合的定義,A是可數(shù)的。

情況2

假設(shè)A不是有限的而f是A的枚舉。枚舉f必須以N的全集作為它的前域。如果f是雙射函數(shù),那么根據(jù)可數(shù)無限集合的定義,A的基數(shù)是而A是可數(shù)的。如果f不是雙射函數(shù)。利用下述辦法,根據(jù)枚舉f構(gòu)造一個從N到A的雙射函數(shù)g,以證明A是可數(shù)的。第十三頁，共六十二頁，編輯于2023年，星期日(1)置g(0)=f(0),i=1,j=1。

(2)檢查f(i)是否已出現(xiàn)在S={g(0),g(1),…,g(j-1)}中,如果f(i)不在S中,轉(zhuǎn)第(3)步,否則轉(zhuǎn)第(4)步。

(3)置g(j)=f(i),把j的值加1,把i的值加1,然后轉(zhuǎn)第2步。

(4)把i的值加1,再轉(zhuǎn)第(2)步。如此地進(jìn)行下去,就可得出任意n∈N的g(n)值。因為A的每一元素是某整數(shù)i的對應(yīng)值f(i),這得出A的這個元素是函數(shù)g對某自變元j的值g(j),這里j≤i。因此g是滿射的。又根據(jù)構(gòu)造方法,g(0)、g(1)、g(2)…中無重復(fù)的,另外,因為A是無限的,g的前域?qū)⑹钦麄€集合N。所以g是N到A的雙射函數(shù)。這證明了和A是可數(shù)的。第十四頁，共六十二頁，編輯于2023年，星期日

例4(a)設(shè)Σ={a,b},則Σ*是可數(shù)無限的。不妨設(shè)a≤b,這樣,Σ*的元素能用標(biāo)準(zhǔn)序列出,Σ*的枚舉是〈Λ,a,b,aa,ab,ba,bb,aaa,aab,…〉所以,Σ*是可數(shù)無限的。對任何有限字母表Σ,以上結(jié)論均成立。但注意,如果｜Σ｜＞1,那么Σ*不能按詞典序枚舉。

(b)正有理數(shù)集合Q+是可數(shù)無限的。顯然Q+不是有限的,因為其真子集正整數(shù)集合I+是無限的?？扇鐖D5.1-1那樣,對Q+進(jìn)行重復(fù)枚舉,枚舉的次序用有向路徑指出。所以,Q+是可數(shù)無限的。第十五頁，共六十二頁，編輯于2023年，星期日圖5.1-1第十六頁，共六十二頁，編輯于2023年，星期日圖5.1-2第十七頁，共六十二頁，編輯于2023年，星期日

定理5.1-4

可數(shù)個可數(shù)集合的并是可數(shù)的。

證設(shè)S是N的初始段,集合這里每一Ai是可數(shù)的。如果S=或?qū)γ恳籭∈S,Ai=,那么A=,結(jié)果成立?，F(xiàn)在假定S≠且至少有一非空集合Ai;不失一般性,我們假定A0≠。我們用非空集合的枚舉構(gòu)造一無限數(shù)組。如果Ai≠,那么數(shù)組第i行是Ai的枚舉;如果Ai是有限的我們用無限重復(fù)枚舉。如果Ai=,我們置第i行等于第i-1行。這樣,數(shù)組包含所有A的元素而無其它元素。A元素的一個枚舉由圖5.1-3中的有向路徑指定。從定理5.1-3得出A是可數(shù)的,于是定理得證。第十八頁，共六十二頁，編輯于2023年，星期日圖5.1-3第十九頁，共六十二頁，編輯于2023年，星期日

例5

上述定理能用來證明下列每一個集合都是可數(shù)無限的。

(a)N2={〈n1,n2〉|ni∈N}。;(b)In={〈x1,x2,…,xn〉|xi∈I}(整數(shù)分量的n重組集合)。

(c)Qn={〈x1,x2,…,xn〉|xi∈Q}。;(d)有理系數(shù)的所有n次多項式集合。;(e)有理系數(shù)的所有多項式集合。;(f)以有理數(shù)為元素的所有n×m矩陣集合。;(g)以有理數(shù)為元素的任意有限維的所有矩陣集合。第二十頁，共六十二頁，編輯于2023年，星期日

定理5.1-6

如果A是有限集合,B是可數(shù)集合,那么BA是可數(shù)的。

證若A是空集,則|BA|=1,是可數(shù)的;若A非空,而B有限(包括是?空集),則|BA|=|B||A|有限,因而是可數(shù)的。剩下只需證明｜A｜=n＞0,且B是可數(shù)無限的情況。設(shè)B的無重復(fù)枚舉函數(shù)是g:N→B,對每一正整數(shù)k∈N定義集合Fk如下:那么Fk包括所有這樣的函數(shù),其象是包含在B的枚舉的前k個元素組成的集合中;|Fk|=kn。因為A是有限的,對每一函數(shù)f:A→B存在某m∈N,如果取k＞m,那么f∈Fk;所以。但每一集合Fk是有限的因而BA是可數(shù)的。證畢。第二十一頁，共六十二頁，編輯于2023年，星期日5.1.3基數(shù)c

不是所有無限集都是可數(shù)無限的,下一定理說明需要新的無限集基數(shù)。

定理5.1-7

實數(shù)的子集［0,1］不是可數(shù)無限。

證設(shè)f是從N到［0,1］的任一函數(shù),我們將證明f不是滿射函數(shù),從而證明了對［0,1］沒有枚舉存在。我們把每一x∈［0,1］都表示為無限十進(jìn)制小數(shù),于是f(0),f(1),f(2)…可表示為第二十二頁，共六十二頁，編輯于2023年，星期日第二十三頁，共六十二頁，編輯于2023年，星期日

這里xni是f(n)小數(shù)展開式的第i個數(shù)字。現(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不是［0,1］的枚舉。因為f是任意的,這證明。這個定理和證明是康脫給出的。這種證明方法叫“康脫對角線法”,被廣泛地應(yīng)?用于可計算理論。第二十四頁，共六十二頁，編輯于2023年，星期日

定義5.1-6

如果有從［0,1］到集合A的雙射函數(shù),那么A的基數(shù)是c。選用字母c是根據(jù)集合［0,1］常叫做連續(xù)統(tǒng)(Continuum)這個事實。第二十五頁，共六十二頁，編輯于2023年，星期日

例6(a)｜［a,b］｜=c。這里［a,b］是R中的任意閉區(qū)間,a＜b。注意到f(x)=(b-a)x+a是從［0,1］到［a,b］的雙射函數(shù),即可證明。

(b)｜(0,1)｜=｜［0,1］｜。這兩個集合的不同僅在于區(qū)間的兩端點;為了構(gòu)造從［0,1］到(0,1)的一個雙射函數(shù),我們必須在(0,1)中找出0和1的象而保持映射是滿射的。定義集合A是

,定義映射f如下:第二十六頁，共六十二頁，編輯于2023年，星期日圖5.1-4第二十七頁，共六十二頁，編輯于2023年，星期日(c)｜R｜=c。我們定義一個從(0,1)到R的雙射函數(shù)如下:因為前例中的f是從［0,1］到(0,1)的雙射函數(shù),而g是(0,1)到R的雙射函數(shù),合成函數(shù)gf是從［0,1］到R的雙射函數(shù)。因此｜R｜=c。第二十八頁，共六十二頁，編輯于2023年，星期日5.2基數(shù)的比較5.2.1基數(shù)比較我們知道,如果A和B是有限集,|A|=n,|B|=m,那么

(a)如果存在一個從A到B的雙射函數(shù),那么n=m。

(b)如果存在一個從A到B的單射函數(shù),那么n≤m。

(c)如果存在一個從A到B的單射函數(shù),但不存在雙射函數(shù),那么n＜m。第二十九頁，共六十二頁，編輯于2023年，星期日

定義5.2-1設(shè)A和B是任意集合。

(1)如果有一個從A到B的雙射函數(shù),那么稱A和B有相同的基數(shù)(或等勢),記為|A|=|B|。

(2)如果有一個從A到B的單射函數(shù),那么稱A的基數(shù)小于等于B的基數(shù),記為|A|≤|B|。

(3)如果有一個從A到B的單射函數(shù),但不存在雙射函數(shù),那么稱A的基數(shù)小于B的基數(shù),記為|A|＜|B|。第三十頁，共六十二頁，編輯于2023年，星期日(i)等勢是集合族上的等價關(guān)系,它把集合族劃分成等價類,在同一等價類中的集合有相同的基數(shù)。因此可以說“基數(shù)是在等勢關(guān)系下集合的等價類的?特征”,或者干脆說“基數(shù)是在等勢關(guān)系下集合的等價類的名稱”,這實際上就是基數(shù)的一般定義。例如,3是等價類{{a,b,c},{0,1,2},{r,s,t},…}的名稱(或特征),是N所屬等價類的名稱。(ii)要證明一個集合S有基數(shù)α,只需選基數(shù)為α的任意集合S′,證明從S到S′或從S′到S存在一雙射函數(shù)。選取集合S′的原則是使證明盡可能容易。第三十一頁，共六十二頁，編輯于2023年，星期日

例1(a)設(shè)E是正偶數(shù)集合,考慮E的基數(shù)。因為f:I+→E,f(x)=2x是從I+到E的雙射函數(shù),所以,|E|=|I+|=。

(b)設(shè)Σ={a,b},S是Σ上以a帶頭的有限串集合,考慮S的基數(shù)。因為f:Σ*→S,f(x)=ax是一個雙射函數(shù)。所以,|S|=|Σ*|=。第三十二頁，共六十二頁，編輯于2023年，星期日

第一個定理叫做三歧性定律。

定理5.2-2(Zermelo)設(shè)A和B是集合,那么下述情況恰有一個成立:(a)|A|＜|B|,(b)|B|＜|A|,(c)|A|=|B|。第二個定理斷言關(guān)系≤是反對稱的。第三十三頁，共六十二頁，編輯于2023年，星期日

定理5.2-3(Cantor-Schroder-Bernstein)設(shè)A和B是集合,如果|A|≤|B|和|B|≤A,那么,|A|=|B|。這個定理對證明兩個集合具有相同的基數(shù)提供了有效方法。如果我們能夠構(gòu)造一單射函數(shù)f:A→B,以證明|A|≤|B|;構(gòu)造另一單射函數(shù)g:B→A,以證明|B|≤|A|,則按照定理即可得出|A|=|B|。注意f和g不必是滿射的。這樣,定理5.2-3實際上等價于“若存在從A到B和從B到A的單射函數(shù),則存在從A到B的雙射函數(shù)”。通常構(gòu)造這樣的兩個單射函數(shù)比構(gòu)造一個雙射函數(shù)要容易。有了以上兩個定理,就容易得出:;

定理5.2-4

設(shè)S是一基數(shù)集合,S上的次序關(guān)系≤是一線序。S上的次序關(guān)系＜是一擬序。證明留作練習(xí)。第三十四頁，共六十二頁，編輯于2023年，星期日

例2(a)證明｜(0,1)｜=｜［0,1］｜。證因為f:(0,1)→［0,1］,f(x)=x是單射函數(shù),｜(0,1)｜≤｜［0,1］｜。又g:［0,1］→(0,1),g(x)=是單射函數(shù),所以,|［0,1］|≤｜(0,1)｜。故｜(0,1)｜=｜［0,1］｜。

(b)證明｜(0,1］｜=c。

證作函數(shù)f:(0,1)→(0,1］,f(x)=x,這是單射函數(shù),所以,c≤|(0,1］|。作函數(shù)g:(0,1］→［0,1］,g(x)=x,也是單射函數(shù),所以,|(0,1］|｜≤c。故|(0,1］|=c。第三十五頁，共六十二頁，編輯于2023年，星期日

定理5.2-5

設(shè)A是有限集合,那么。

證假定|A|=n。我們證明對每一n,有|{0,1,2,…,n-1}|＜|N|＜|［0,1］|。作函數(shù)f:{0,1,2,…,n-1}→N,f(x)=x。這是一單射函數(shù),所以,|{0,1,2,…,n-1}|≤|N|。定理5.1-1已證明沒有從N到{0,1,2,…,n-1}的雙射函數(shù),所以,|{0,1,2,…,n-1}|≠|(zhì)N|,故|{0,1,2,…,n-1}|＜|N|,即。作函數(shù)g:N→［0,1］,,這也是一單射函數(shù),所以,|N|≤|［0,1］|。定理5.1-7已證明|N|≠|(zhì)［0,1］｜,所以,|N|≤|［0,1］|,即。第三十六頁，共六十二頁，編輯于2023年，星期日*5.2.2應(yīng)用舉例

例3

證明|ρ(N)｜=c。

證

(i)作函數(shù)h:ρ(N)→［0,1］。h的變換規(guī)則是:對每一子集,第三十七頁，共六十二頁，編輯于2023年，星期日

例如,h(N)=0.111…

h({1,4,5})=0.010011h是單射的,所以,｜ρ(N)｜≤｜［0,1］｜。(ii)作函數(shù)k:［0,1］→ρ(N),設(shè)x=.x0x1x2…是x∈［0,1］的二進(jìn)制表示(如果x沒有唯一表示,可任意選取其中之一)。k的變換規(guī)則是第三十八頁，共六十二頁，編輯于2023年，星期日

例如,

則k是單射的(注意不滿射,例如如果用0.1表達(dá),則其象是{0},如果用0.0111…表達(dá),則其象是{1,2,3,…},兩者不能兼得),所以,c≤｜ρ(N)｜。由(i)和(ii)得ρ(N)=c。第三十九頁，共六十二頁，編輯于2023年，星期日

例4

證明｜ρ(Σ*)｜=c,這里Σ={a,b}。

證上例已證明|ρ(N)|=c,我們只需證明｜ρ(Σ*)|=ρ(N)｜。;(i)作函數(shù)f:Σ*→N,f的變換規(guī)則是把Σ*中的字符串變?yōu)閧1,2}*中的字符串,串中的a變1,b變2,然后將所得串作為N中的自然數(shù)。例如f(aab)=112,f(abab)=1212,…另外定義f(Λ)=0。

f把Σ*中不同字符串映射到N中不同自然數(shù),f是單射的。因而f誘導(dǎo)的函數(shù)(仍記為f)f:ρ(Σ*)→ρ(N)也是單射的,所以|ρ(Σ*)|≤|ρ(N)|。第四十頁，共六十二頁，編輯于2023年，星期日(ii)作函數(shù)g:N→Σ*,設(shè)n∈N用二進(jìn)制表示,表示式中除0外均由1打頭,例如5寫成101不能寫成0101等。g的變換規(guī)則是:把n看作{0,1}上的字符崐串,再把串中的0變a、1變b,得出Σ上的字符串。例如g(0)=a,g(101)=bab。

g把N中不同的自然數(shù)變?yōu)棣?中不同的串,g是單射的,因而g誘導(dǎo)的函數(shù)(仍記為g)g:ρ(N)→ρ(Σ*)也是單射的,所以｜ρ(N)｜≤|ρ(Σ*)|。由(i)和(ii)得出|ρ(Σ*)|=|ρ(N)|。第四十一頁，共六十二頁，編輯于2023年，星期日

例5

證明｜NN｜=c。

證

(i)作函數(shù)F:NN→(0,1),設(shè)f是NN的元素,對每一變元i∈N,f(i)=xi,這里xi是二進(jìn)制數(shù),應(yīng)用數(shù)字“2”作函數(shù)值的間隔符,我們定義F(f)=.x02x12x22…并解釋F(f)為對應(yīng)于自變元f的三進(jìn)制小數(shù)。例如,若h:N→N,h(x)=2x,那么h∈NN而F(h)=.0210210021102……F是入射函數(shù),所以,|NN|≤c。第四十二頁，共六十二頁，編輯于2023年，星期日(ii)作函數(shù)G:(0,1)→NN,設(shè)x是(0,1)的一個元素,x=.

x0x1x2…是x的無限十進(jìn)制展開式,定義G(x)=f其中f∈NN,f(0)=x0,f(1)=x1,…,f(n)=xn,…。G是從(0,1)到NN的入射函數(shù)。所以c≤｜NN｜。由(i)和(ii)得出｜NN｜=c。第四十三頁，共六十二頁，編輯于2023年，星期日

例6

對一個數(shù)x∈(0,1),如果存在一個ALGOL(或PL／1,或FORTRAN等等)程序P,當(dāng)給出任一非負(fù)整數(shù)i(作為輸入),經(jīng)過有限但可任意長的時間,它恰好輸出x的十進(jìn)制展開式的第i個數(shù)字后停機(jī),則稱x是可計算的。所謂數(shù)x=.x0x1x2…是可計算的,意指存在程序P能用來確定x到任意精確度,或產(chǎn)生x的展開式的任意一位數(shù)字。反之,則稱數(shù)x∈(0,1)是不可計算的。例如,循環(huán)小數(shù)5141414…是可計算的,因為存在以下計算它的過程。ProcedureComp(i);ifi=1thenreturn5;else;ifi≡0(mod2)thenreturn1;elsereturn4第四十四頁，共六十二頁，編輯于2023年，星期日

證明區(qū)間(0,1)中存在不可計算的數(shù)。所用的證明方法叫基數(shù)論證,是非構(gòu)造性的,將涉及以下集合:Σ:ALGOL的字符集合,;A:所有ALGOL程序集合,;C:計算(0,1)中某個數(shù)的ALGOL程序集合,;S:在(0,1)中能被某ALGOL程序計算的數(shù)的集合。第四十五頁，共六十二頁，編輯于2023年，星期日

因為Σ是一有限集合,字母表Σ上非空串的集合有基數(shù),即。因為任何ALGOL程序是Σ上的有限串,所以|A|≤|Σ+|。因為C是A的真子集,所以|C|≤|A|。任一程序P至多能計算S的一個元素的數(shù)字,但不同程序能計算同樣數(shù)的數(shù)字。這得出|S|≤|C|。這樣,我們有第四十六頁，共六十二頁，編輯于2023年，星期日5.2.3無限集合的特性

定理5.2-6

每一無限集合包含一可數(shù)無限集合。

證設(shè)A是無限集合,應(yīng)用選擇公理于A的子集的序列，我們構(gòu)造一無限序列〈a0,a1,a2,…〉如下:從A中 選取a0

從A-{a0}中 選取a1

從A-{a0,a1}中 選取a2

從A-{a0,a1,a2}中 選取a3

第四十七頁，共六十二頁，編輯于2023年，星期日

集合A-{a0,a1,a2,…,an}的每一個都是無限的。若不然,A將等于兩個有限集合A-{a0,a1,…,an}和{a0,a1,…,an}的并,而兩個有限集合的并是有限集合,與A是無限集合矛盾。這樣,我們能從A-{a0,a1,…,an}中選取一個新元素an+1,從而能夠構(gòu)造一無限序列a0,a1,a2,…而沒有重復(fù)。這個序列的元素組成一個A的可數(shù)無限子集B。于是定理得證。第四十八頁，共六十二頁，編輯于2023年，星期日

定理5.2-7是最小的無限集基數(shù)。

證根據(jù)定理5.2-6,如果A是無限集合,那么A包含一可數(shù)無限子集B。因為映射f:B→A,f(x)=x,x∈B是從B到A的單射函數(shù),這得出|B|≤|A|,而,我們得。證畢。第四十九頁，共六十二頁，編輯于2023年，星期日

定理5.2-8

集合A是無限集合,當(dāng)且僅當(dāng)存在一單射函數(shù)f:A→A,使f(A)是A的真子集。

證必要性。為減少敘述,我們應(yīng)用定理5.2-6的符號和結(jié)果。記A′=A-{a0}。作函數(shù)f:A→A′,f(x)=x,當(dāng)時;f(xi)=xi+1,當(dāng)x∈B時,顯然,A′是A的真子集,f是A到真子集A′的單射函數(shù)。充分性。我們要證明“如果存在單射函數(shù)f:A→A,使f(A)是A的真子集,那么A是無限集”。用逆反證明法,即要證明“如果A是有限集,那么不存在單射函數(shù)f:A→A,使f(A)是A的真子集”。但這是顯然的,因為A的元素個數(shù)多于真子集f(A)的元素個數(shù),函數(shù)f至少要把A的兩個元素映到f(A)的同一元素,所以f不是單射函數(shù)。證畢。第五十頁，共六十二頁，編輯于2023年，星期日

例7(a)證明N是無限集。;

函數(shù)f:N→N,f(x)=2x是單射函數(shù),它的象是偶數(shù)集合,是N的真子集,所以N是無限集。;(b)證明Σ*是無限集,這里Σ={a,b}。函數(shù)f:Σ*→Σ*,f(x)=ax是單射函數(shù),它的象是以字母a開頭的所有有限串,它是Σ*的真子集,所以Σ*是無限集。第五十一頁，共六十二頁，編輯于2023年，星期日5.2.4基數(shù)的無限性和連續(xù)統(tǒng)假設(shè)定理5.2-9(Cantor)設(shè)A是一集合,那么|A|＜|ρ(A)|。證容易看出,函數(shù)f:A→ρ(A),f(a)={a}是單射的。所以,|A|≤|ρ(A)|。;

下面我們證明|A|≠|(zhì)ρ(A)|。;

設(shè)g:A→ρ(A)是任意函數(shù),我們要證明g不是滿射的,因而不是雙射的。函數(shù)g映射A的每一元素x到A的子集g(x),元素x可能在子集g(x)中,即x∈g(x),也可能。定義集合S是A的子集。第五十二頁，共六十二頁，編輯于2023年，星期日

現(xiàn)在證明對任一a∈A,g(a)≠S。用反證法,假設(shè)g(a)=S,則 根據(jù)S的定義;

根據(jù)定義S的謂詞;

根據(jù)假設(shè)g(a)=S

這是一個矛盾,所以g(a)=S是假。因為a是任意的,這得出g不是滿射函數(shù),因此不是雙射函數(shù)。又g是任意函數(shù),這證明了沒有雙射函數(shù)存在,所以|A|≠|(zhì)ρ(A)|。證畢。應(yīng)用本定理我們能夠構(gòu)造一個可數(shù)無限的無限基數(shù)的集合。其中每一個都大于它前邊的一個。|N|＜|ρ(N)|＜|ρ(ρ(N))|＜…第五十三頁，共六十二頁，編輯于2023年，星期日

如果集合A有n個元素,則ρ(A)有2n個元素,本節(jié)例3證明了｜ρ(N)｜=c,于是人們認(rèn)為。A是有限集時,|A|和|ρ(A)|之間存在著其它基數(shù),于是康脫提出和c之間是否也存在其它基數(shù)連續(xù)統(tǒng)假設(shè)斷言不存在這樣的基數(shù)。從前已經(jīng)知道連續(xù)統(tǒng)假設(shè)和集合論公理是一致的。但1963年科恩(PaueCohen)證明連續(xù)統(tǒng)假設(shè)的反命題也和集合論公理一致，即連續(xù)統(tǒng)假設(shè)和集合論公理是獨立的。這就給我們帶來一個問題,例如,我們要證明所給集合A有基數(shù)c,如果接受連續(xù)統(tǒng)假設(shè),那么我們只需證明|A|≤c和。如果拒絕這一假設(shè),那么這樣的證明是不充分的,可能有。我們應(yīng)避開使用這一假設(shè)。第五十四頁，共六十二頁，編輯于2023年，星期日*5.3基數(shù)算術(shù)

定義5.３-1

設(shè)a和b是基數(shù),A和B是使|A|=a和|B|=b的兩不相交集合。a和b之和定義為a+b=|A∪B|

定理5.3-1

基數(shù)的加法是可交換的和可結(jié)合的。

證根據(jù)和的定義和集合并的性質(zhì)直接得出。第五十五頁，共六十二頁，編輯于2023年，星期日

定理5.3-2

設(shè)a、b、d和e是基數(shù),那么

(a)如果a≤b和d≤e,則a+d≤b+e。

(b)如果a＜b和d＜e,則a+d＜b+e。

證