![離散數(shù)學(xué)鄭版watched05無限集合_第1頁](http://file4.renrendoc.com/view/c4a58a680dc536963c2d519578eb6e4a/c4a58a680dc536963c2d519578eb6e4a1.gif)
![離散數(shù)學(xué)鄭版watched05無限集合_第2頁](http://file4.renrendoc.com/view/c4a58a680dc536963c2d519578eb6e4a/c4a58a680dc536963c2d519578eb6e4a2.gif)
![離散數(shù)學(xué)鄭版watched05無限集合_第3頁](http://file4.renrendoc.com/view/c4a58a680dc536963c2d519578eb6e4a/c4a58a680dc536963c2d519578eb6e4a3.gif)
![離散數(shù)學(xué)鄭版watched05無限集合_第4頁](http://file4.renrendoc.com/view/c4a58a680dc536963c2d519578eb6e4a/c4a58a680dc536963c2d519578eb6e4a4.gif)
![離散數(shù)學(xué)鄭版watched05無限集合_第5頁](http://file4.renrendoc.com/view/c4a58a680dc536963c2d519578eb6e4a/c4a58a680dc536963c2d519578eb6e4a5.gif)
版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)
文檔簡介
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ù)進(jìn)行比較。有限集合的基數(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+進(jìn)行重復(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]都表示為無限十進(jìn)制小數(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ū)間的兩端點(diǎn);構(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
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 7多元文化 多樣魅力《多彩的世界文化》(說課稿)-統(tǒng)編版道德與法治六年級下冊
- 2025合同模板承包合同書(車輛)范本
- 2025中外合資公司勞動合同協(xié)議書
- 2024年春七年級語文下冊 第4單元 13 葉圣陶先生二三事說課稿 新人教版
- 《1 信息并不神秘》說課稿-2023-2024學(xué)年華中師大版信息技術(shù)三年級上冊
- Unit 2 Expressing yourself Part A Lets spell(說課稿)-2024-2025學(xué)年人教PEP版(2024)英語三年級下冊001
- 2024年01月浙江2024年中國工商銀行杭州金融研修學(xué)院社會招考筆試歷年參考題庫附帶答案詳解
- 2《學(xué)會溝通交流》第2課時說課稿-2024-2025學(xué)年道德與法治五年級上冊統(tǒng)編版
- 以工代賑項目用工合同范例
- 農(nóng)業(yè)培訓(xùn)合同范例
- 如何當(dāng)好學(xué)校的中層干部
- SWITCH塞爾達(dá)傳說曠野之息-1.6金手指127項修改使用說明教程
- 2022-2023學(xué)年廣東省佛山市順德區(qū)高三(下)模擬英語試卷
- 節(jié)后復(fù)工培訓(xùn)內(nèi)容五篇
- GB/T 33322-2016橡膠增塑劑芳香基礦物油
- GA 1051-2013槍支彈藥專用保險柜
- 某水毀公路維修工程施工方案
- 家庭病房工作制度和人員職責(zé)
- 建設(shè)工程監(jiān)理合同示范文本GF-2018-0202
- 2022質(zhì)檢年終工作總結(jié)5篇
- 江蘇省中等職業(yè)學(xué)校學(xué)業(yè)水平考試商務(wù)營銷類(營銷方向)技能考試測試題
評論
0/150
提交評論