第八章自然數(shù)和基數(shù)自然數(shù)及數(shù)學(xué)歸納法基數(shù)1§8.1自然數(shù)及數(shù)學(xué)歸納法1.用集合定義自然數(shù)定義8.1 0N,且0對(duì)應(yīng)空集,0=.定義8.2 對(duì)于任意集合A,其后繼集合A+=A{A}.定義8.3 自然數(shù)集N的歸納定義如下：

⑴基礎(chǔ)語(yǔ)句:N(=0) ⑵歸納語(yǔ)句:若nN,則n+=n{n}N ⑶權(quán)限語(yǔ)句:若SN且S滿足⑴⑵,則S=N自然數(shù)是“計(jì)數(shù)”的抽象?！皵?shù)”可以定義為集合的性質(zhì)，而其外延即是具有該性質(zhì)的對(duì)象集合。2N0 1 {

}2 {,{}}3 {,{},{,{}}}4 {,{},{,{}},{,{},{,{}}}} 0,1,2,3… ……n={0,1,2,…,n-1}由于n+=n{n},所以有

01234… 01234…3自然數(shù)公理(Peano)⑴0是自然數(shù),即0N⑵若nN,則恰存在一個(gè)自然數(shù)n+,稱為n的后繼數(shù)⑶沒(méi)有這樣的nN,使得n+=0⑷如果n+=m+,則n=m⑸若子集SN，且具有性質(zhì)

a.0S b.如果nS,那么n+S

則S=N用集合方法定義的自然數(shù)集N也滿足上述公理。4性質(zhì)8.1作集合方法定義的N還滿足：⑴傳遞性：若n1n2,n2n3,則n1n3.⑵三岐性：任意自然數(shù)n1,n2,則

n1n2

n1=n2

n2n1

恰有一個(gè)成立.⑶良基性：01234… 01234…

對(duì)于每一個(gè)自然數(shù)，比它小的自然數(shù) 總是有窮個(gè).52.數(shù)學(xué)歸納法第一歸納法： 設(shè)P(n)是自然數(shù)集合上的性質(zhì)，如果能證明

a.P(0)為真,

b.對(duì)任何mN,P(m)P(m+1).

則對(duì)所有nN,P(n)為真。

P(0)

m(P(m)

P(m+1))

nP(n)第二歸納法：

假設(shè)對(duì)所有k<m,P(k)為真,能推出P(m)為真,

則對(duì)所有nN,P(n)為真。

m(k(k<mP(k))

P(m))

nP(n)這里隱含了P(0)為真：

k(k<0P(k))

P(0)為真推P(m)為真時(shí)的前提“多”6超窮歸納法---將第二歸納法推廣到良序集合上： 設(shè)<X,<>為良序關(guān)系，則

x(y(y<xP(y))

P(x))

xP(x)歸納法的好處：

(1)有了“綠色”前提，證“黃色”P(pán)(x)更容易；

(2)需證的P(x)中x已是上限。推導(dǎo)式的正確性：假設(shè)

xP(x)不為真,即X中存在使P(x)為假的元素,構(gòu)造X的子集A={x|xXP(x)}.

由于X是良序,它的任何子集都有最小元,設(shè)A的最小元為a,即a為使P(x)為假的最小元素.

則所有y<a都有P(y)為真,而根據(jù)前提

y(y<aP(y))

P(a)

可見(jiàn)與P(a)為假矛盾。所以xP(x)為真。7§8.2基數(shù)有窮集合的基數(shù)為一自然數(shù)n，而n可定義為集合{0,1,2,…,n-1}，即有窮集合中的元素可與n中的元素一一對(duì)應(yīng)。1.等勢(shì)定義8.5 集合A和B是等勢(shì)的,當(dāng)且僅當(dāng)A和B的元 素一一對(duì)應(yīng)(雙射函數(shù))，記作A~B.例8.5 設(shè)N={0,1,2,3,…},E={0,2,4,6,…}

定義f:NE,f(n)=2n,是雙射函數(shù).

所以N~E.8例8.5 集合NN與集合N等勢(shì).斜行0

0112234536789…序偶<m,n>位于第(m+n)斜行上的第m個(gè)位置： 此前的(m+n)行共有(m+n)(m+n+1)/2個(gè)序偶,

當(dāng)前本行到此又有m個(gè)序偶.所以

f(<m,n>)=[(m+n)2+3m+n]/2

顯然，這是一個(gè)NN到N的雙射.N(m)N(n)?0?1?2?31?2?3??????????<m,n>01234567899例8.6自然數(shù)集N與有理數(shù)集Q等勢(shì)。例8.7單位開(kāi)區(qū)間(0,1)與實(shí)數(shù)集R等勢(shì)。由此可見(jiàn)： 無(wú)窮集合可與其真子集等勢(shì)。 “整體大于部分”對(duì)無(wú)窮集而言并不成立。等勢(shì)關(guān)系是一個(gè)等價(jià)關(guān)系：⑴自反性：A~A

可構(gòu)成恒等函數(shù)⑵對(duì)稱性：若A~B,則B~A.

雙射的反函數(shù)仍是雙射⑶傳遞性：若A~B,B~C,則A~C.

雙射的合成仍是雙射將Q看成是分?jǐn)?shù)n/m,跳過(guò)已計(jì)數(shù)，如1/2,2/4,3/6,…將(0,1)彎成半園映射到R，或tg(2x-1)/2，或(1/2-x)/x(1-x)102.有窮集定義8.6 集合是有窮的，當(dāng)且僅當(dāng)它與某個(gè)自然 數(shù)等勢(shì)。否則就是無(wú)窮集。鴿巢原理(抽屜原理)：

m只鴿子放入n個(gè)巢中，如果m>n，則某個(gè)巢內(nèi)必有兩只以上的鴿子。若A,B為有窮集合,#A>#B,則不存在A到B的單射.任何有窮集合都不會(huì)與它本身的真子集等勢(shì)。

---有窮集與無(wú)窮集之間的區(qū)別.113.可數(shù)無(wú)窮集定義8.9 任何與自然數(shù)集N等勢(shì)的集合,稱為可數(shù)

無(wú)窮集。其基數(shù)記作

0(阿列夫零)。自然數(shù)集N,整數(shù)集I,有理數(shù)集Q都是可數(shù)無(wú)窮集?？蓴?shù)集合包括：有窮集、可數(shù)無(wú)窮集。定理8.2 任何無(wú)窮集合必含有可數(shù)無(wú)窮子集。I~N:建立I和N之間的對(duì)應(yīng)關(guān)系，也就是用一個(gè)雙射函數(shù)f：NI來(lái)表示：

n/2,n是偶數(shù)

-(n+1)/2,n是奇數(shù)f(n)=12定理8.3 可數(shù)集合的無(wú)窮子集是可數(shù)無(wú)窮的。證明設(shè)S是給定可數(shù)集合A的無(wú)窮子集，顯然A~N。因此有函數(shù)f:NA，它由f(n)=x,xA給定，它是雙射函數(shù)。這樣，A的元素可以排列為f(1)、f(2)、、、，現(xiàn)在，可以把那些不在S中的元素從這序列中去掉，由于S是無(wú)窮集合，所以余下的元素仍然是無(wú)窮的，并用f(i1)、f(i2)、、、來(lái)表示余下的元素，然后，確定一個(gè)函數(shù)g:NS，使得g(n)=f(in)，則g是一對(duì)一滿射的映射，因此S是可數(shù)無(wú)窮的。證畢。134.不可數(shù)無(wú)窮集定理8.4 實(shí)數(shù)集R是不可數(shù)的。證： 只需證S=(0,1)是不可數(shù)的.(用康托爾對(duì)角線法)

假設(shè)S可數(shù)，則S中所有的元素可排列如下：

s1=0.a11

a12a13… (如0.5=0.49999……)

s2=0.a21a22a23… s3=0.a31a32

a33… ……… 1,若ajj1

現(xiàn)構(gòu)造實(shí)數(shù)r=0.b1b2b3…

值bj=

2,若ajj=1

則r與所有的si都不同,即rS,矛盾。 所以S是不可數(shù)的。實(shí)數(shù)集R的基數(shù)用C表示---稱為連續(xù)統(tǒng)的勢(shì)。145.勝過(guò)(領(lǐng)先于)定義8.11 對(duì)于集合A和B,B勝過(guò)A(或A領(lǐng)先于B),當(dāng)且僅當(dāng)有一個(gè)從A到B的單射f,即A與B的子集等勢(shì)(ran(f)B).記為A?B. (此時(shí)稱#A≤#B)定義8.12 對(duì)于集合A和B,若A?B且A不等勢(shì)B,則稱B嚴(yán)格勝過(guò)A,記為A?B. (此時(shí)稱#A<#B)

勝過(guò)?是偏序,也是全序：或者A?B,或者B?A.N是R的真子集,所以N?R,即

0<C.

任何無(wú)窮集A都包含一個(gè)可數(shù)無(wú)窮子集,N?A.

對(duì)于任意集合A,A?(A).

可知N的冪集

(N)的基數(shù)是C,即C=20.

連續(xù)統(tǒng)假設(shè):不存在k,使得0<k<C.15第五章集合的基本概念及其運(yùn)算第二篇集合論第六章關(guān)系第七章函數(shù)第八章自然數(shù)和基數(shù)16第五章集合的基本概念及其運(yùn)算集合與元素集合間的關(guān)系冪集集合運(yùn)算A–B=A~B，A+B=(A–B)(B–A)有窮集的計(jì)數(shù)集合的歸納定義基礎(chǔ)語(yǔ)句：規(guī)定集合的生成元； (非空、原子)

歸納語(yǔ)句：規(guī)定集合的生成算法；權(quán)限語(yǔ)句：限定了集合的范圍。 (有時(shí)省略)有序偶和笛卡爾乘積17第六章關(guān)系關(guān)系及其性質(zhì)從集合X到Y(jié)的關(guān)系R滿足RXY關(guān)系的五種性質(zhì)：自反性、反自反性、對(duì)稱性、反對(duì)稱性、傳遞性。關(guān)系的運(yùn)算

x(RS)y

xRy

xSy x(RS)y

xRy

xSy x(R–S)y

xRy

xSy x(~R)y

xRy ~R=Ux

–R=XY–RR?S={<x,z>|y(xRy

ySz)}

(R?S)?P=R?(S?P)R-1={<y,x>|xRy}(R?S)-1=S-1?R-118次序關(guān)系偏序關(guān)系、全序關(guān)系、嚴(yán)格偏序、良序良序集合

全序集合有窮的全序集合

良序集合最大(小)元、極大(小)元、上(小)界、上(小)確界等價(jià)關(guān)系與劃分覆蓋與劃分R是自反的、對(duì)稱的和可傳遞的，則稱R是等價(jià)關(guān)系。等價(jià)類：等價(jià)類[x]R是由X中與x有關(guān)系R的元素構(gòu)成第六章關(guān)系19第七章函數(shù)基本概念關(guān)系到函數(shù)的要求：處處有定義(定義的全域性)

單值(值的唯一性)函數(shù)的復(fù)合g?f={<x,z>|y(y=f(x)z=g(y))}稱為f和g的復(fù)合，寫(xiě)成g(f(x))特殊性質(zhì)的函數(shù)滿射、單射、雙射：#X=#Y集合的特征函數(shù)A的特征函數(shù)A:U{