1、定理(二)：設S是自然數集N的非空子集，如果0S，且當nSn+1S，則S=N。定理(三)：設S是自然數集N的非空子集，如果0S，且當0,1,2,nSn+1S，則S=N。數學歸納法，有兩種形式：(1)第一數學歸納法要證一個結論對所有自然數都真，只須做兩件事：1)當n=0時，結論成立。2)若當n=k結論成立，則當n=k+1結論也成立。1(2)第二數學歸納法要證一個結論對所有自然數都真，只須做兩件事：當n=0時，結論成立。若當nk結論成立，則當n=k+1結論也成立定理(四)：設P(n)是一個與自然數n有關的結論。若對于自然數0，結論成立；并且當對自然數k結論成立時，對于自然數k+1結論也成立，則該結

2、論對所有自然數都成立。2定理(五)：設P(n)是一個與自然數n有關的結論。若對于自然數0，結論成立；并且當對自然數0,1,2,k結論成立時，對于自然數k+1結論也成立，則該結論對所有自然數都成立。3二、集合的遞歸定義定義4.1:集合A的遞歸(歸納)定義由三部分組成: (1)基礎:設置某些對象是在所要定義的集合A中的 (2)歸納(遞歸):建立一種由集合A的現有元素產生A中新元素的方法。 (3)閉合：除了有限次應用(1)和(2)產生集合A的元素外,A中再沒有其它元素。4例：設整數集Z是全集,非負偶整數集E+=x|x0,且x=2y,yZ,它可以遞歸定義如下:(1)(基礎)0E+。(2)(歸納)如果n

3、E+,則n+2E+。(3)(閉合)除有限次應用(1)和(2)產生的整數外,再沒有其它的整數在E+中。例：下面的歸納定義所給出的是怎樣的集合？ (1)(基礎)3S。(2)(歸納)如果x,yS,則x+yS。(3)(閉合)除有限次應用(1)和(2)產生的整數外,再沒有其它的整數在S中。 3的正整數倍全體。5設是一個有限非空字符集,稱為字母表。從中選取有限個字符組成的串稱為上的字符串或字。設x是上的一個字, x=a1a2an,其中ai,1in,n是正整數,表示字的長度。長度為0的字稱為空串,記為。若x,y是上的兩個字,x=a1a2an, y=b1b2bm,其中ai,bj(1in, 1jm),則由x和y

4、毗連得到新的字記為xy。即:xy=a1a2an b1b2bm。6例:設是一個字母表, 上所有的有限非空字符串集合記為+,遞歸定義如下:(1)(基礎)如果a,則a+。(2)(歸納)如果x+,且a,則ax+(ax表示字符a與字x毗連得到的新的字。(3)(閉合)除有限次應用(1)和(2)產生+中的字外, +中再沒有其它字。集合+包含長度為1,2,3,的字,即+包含無限個字, 但每個字的字符個數是有限的。7例:設是一個字母表, 上所有的有限字符串集合記為*,*包含空串，即*=+,可遞歸定義如下:(1)(基礎)*。(2)(歸納)如果x*,且a,則ax*。(3)(閉合)除有限次應用(1)和(2)產生*中的

5、字外, *中再沒有其它字。例如,若=0,1, 則*=,0,1,00,01, 10,11,000,001,是有限二進制序列的集合, 其中包含空序列。8算術表達式集合是包含整數, 一元運算符+,-, 以及二元運算符+,-,* ,/的符號序列所組成的集合, (3+5)/4),(-5)+6)*3)9算術表達式集合的遞歸定義如下:(1)(基礎)如果D=0,1,2,3,4,5,6,7,8,9和xD+ ,則x是算術表達式。其中D+是D上所有非空數字串的集合。(2)(歸納)如果x和y都是算術表達式, 則(+x)是算術表達式; (-x)是算術表達式;(x+y)是算術表達式; (x-y)是算術表達式;(x*y)是

6、算術表達式; (x/y)是算術表達式。 (3)(閉合)一個符號序列是一個算術表達式當且僅當它能通過有限次應用(1)和(2)而得到。10后繼集合的概念: 設A是任一給定集合,AA稱為A的后繼集合, 簡稱后繼, 記為A+。定義4.2:設N為自然數集, 它的遞歸定義如下:(1)(基礎)N。(2)(歸納)如果nN, 則n+N(這里n+=nn)。(3)(閉合)如果SN,且S滿足(1)、(2)則S=N。11自然數集的元素為: ,+,(+)+,(+)+)+,即為: ,可以簡化為: ,用記號:=給這些集合命名例如命名為0,記為0:=0:=; 1:=0+=0; 2:=1+=,=0,1; 3:=2+=,=0,1,

7、2 若已給出n, 則n+1:=n+=0,1,2,n12定理4.1:(1)0不是任何自然數的后繼。(2)任何自然數的后繼是唯一的。(3)如果n+=m+,則n=m。貝安諾(Peano)公理(1)0N;(2)對每一個nN,恰存在一個n+N(稱n+為n的后繼);(3)不存在一個nN,使n+=0;(4)如果n+=m+, 則n=m;(5)如果SN,且0S;如果nS,有n+S, 則S=N。134.2 基數一、基數概念在棋盤的第一個方格內放一粒米，以后每一小格內都比前一小格加一倍，最后擺滿所有64格1+2+22+263=264-1約合140億升所有整數的個數，一條線上所有幾何點個數(即區間a,b上 個數)14

8、比較一堆珠子和一堆銅幣哪個多，把珠子和銅幣逐個比較，最后看哪堆有多余，若同時沒有則兩者相同。定義4.3：設A,B是任意兩個集合,若存在一個雙射f:AB,則稱A和B對等(或等勢),記為 AB;或稱A和B的基數相同。A的基數記為|A|;A和B的基數相同記為|A|=|B|15二、無限集定義4.4：設A為一個集合, 若A為空集或與集合0,1,2,n-1的基數相同, 則稱A為有限集,且|A|=nN。若集合A不是有限集, 則稱A為無限集。定理4.2:自然數集N是無限集。沒有一個自然數能作為N的基數,因此今后將記|N|為0,讀作阿列夫零。 16定理4.2:自然數集N是無限集。即證明N不是有限集.關鍵證明對任

9、何nN，不存在從0,1,2,n-1到N的雙射。證明：設n是N中任一元素，f是從0,1,2,n-1到N的任一函數，沒有一個自然數能作為N的基數,因此今后我們將記|N|為0,讀作阿列夫零。 17例:設N與Z之間有如下一一對應:N: 0,1, 2,3, 4,5, 6,Z: 0,1,-1,2,-2,3,-3,即存在雙射f:NZ,使對nN,所以|Z|=0。18例:設E=0,2,4, 因為存在f: NE,對任何nN有f(n)=2n , 顯然f是NE的雙射。這里E是N的真子集,然而|E|=|N|=0。這一事實揭示了無限集的一個重要特征:即無限集可以與它的一個真子集對等。19定理4.3:無限集必與它的一個真子

10、集對等。證明：基本思路A是構造一個真子集,然后證明兩者之間存在雙射推論:凡不能與自身的任一真子集對等的集合為有限集。凡能與自身的某一真子集對等的集合稱為無限集,否則稱為有限集。前面的例子和定理說明了這樣的事實：在無窮大的世界里，部分可能等于全部。那么是否無窮大數都是相等的？204.3 可列集與不可列集定義4.5：若存在從N到A的雙射, 則稱A為可列無限集, 簡稱可列集或可數集, |A|=0。定理(一)：設A是可列集, 若存在從A到B的雙射,則B也是可列集。目標證明存在N到A的雙射.21定理(二)：集合A是可列集的充要條件是集合A中的元素可以排成一個無窮序列的形式:a0,a1,a2,a3,a4,。利用自然數有序性目標證明存在N到A的雙射。定理4.4：任何無限集必含有一個可列子集。采用構造方法,從無限集中構造一個無窮序列22定理4.5：可列集的任何無限子集必為可列集。定理4.6：可列集中加入有限個元素(或刪去有限個元素), 仍為可列集。23作業:P76 1,補充:證明定理(五)：設P(n)是一個與自