離散數學5枚舉定義:N的一個初始段{0,1,…,n-1}到(非空)有限集A的一個滿射函數f:

{0,1,…,n-1}

A稱為A的一個有限枚舉;若f是雙射則稱為有限無重復枚舉.定理:集A為非空有限集當且僅當存在A的一個有限無重復枚舉.注:N到集A的一個滿射函數f:

N

A

稱為A的一個無限枚舉.基數一般概念(有限集元素數的推廣)對任意集合A,B,如果存在A到B的雙射(表示為AB)),則稱A和B等勢,或有相同基數,記為|A|=|B|;如果A與B的一個子集等勢(即存在A到B的單射),則|A||B|,特別AB

|A||B|;如果存在A到B的單射但不存在A到B的雙射,則|A|<|B|;如果|A||B|且|B||A|,則|A|=|B|(Berstein定理—定理5.2-3).集合上的等勢關系是等價關系,同一等價類中的集合有相同基數.(恒等映射為雙射,雙射的逆,合成仍為雙射)可數無限集的概念

記|N|=0,基數為0的集,即與

N

等勢的集,稱為可數無限集;有限集(包含空集)與可數無限集統(tǒng)稱為可數集.(與N的子集等勢的集合稱為可數集)

例非負偶數的集:A={0,2,4,6,…}={2k|kN}是可數無限集.f:NA,f(x)=2x為雙射

A為可數集

|A|0

存在A到N的單射

因恒等函數是可數集A的任意子集到A的單射,故可數集的任意子集是可數集.可數集的性質①A為可數集當且僅當A的元素可列成表(可按{0,1,…,n-1}或N與A元素間的一一對應關系列表),或說A是可枚舉的.②A,B為可數集,則AB為可數集.證:若A或B為空集,則|AB|=||=0,結論成立.當A∧B時,AB的元素可列成表(見下兩張幻燈片).注:

由歸納法易見:對任意正整數n,A1,,An為可數集A1An為可數集.1,11,21,31,n

2,12,22,32,nm-1,1m-1,2m-1,3m-1,nm,1m,2m,3m,n1,11,21,31,41,5

2,12,22,32,42,53,13,23,33,43,54,14,24,34,44,55,15,25,35,45,5可數集的性質續(xù)③可數集A的任意子集B都是可數集.(把A列成表后再劃去表中A-B的所有元素即得B的列表)特別,任意二可數集的交集都是可數集.或|B||A|0

④可數個可數集Ai的并集

A=∪iS

Ai都是可數集(∵此并集的雙射象是可數集NN的子集).⑤若A為有限集,B為可數集,則

A

到

B的所有函數的集

BA

是可數集.⑤的證明⑤若A為有限集,B為可數集,則

A

到

B

的所有函數的集

BA

是可數集.證:令

A={a1,…,an};

fBA.易見:

f與(f(a1),…,f(an))B…B=Bn一一對應,從而,BA

Bn

是可數集(②的注).可數無限集的性質及0的算術對每個正整數n,n個兩兩不交的可數無限集的并集是可數無限集,n0=0.可數無限集與其任意n元子集的差集是可數無限集,0-n=0(存在雙射

f:N-{0,1,…,n-1}N,其中

f(i)=i-n,iN)對任意正整數n成立：0

n=0NN…NN,(0)n=0,nI+推論:N到m元有限集A的全體函數構成可數無限集AN(∵|AN||N|m=(0)m=0);可數集到有限集的全體函數構成可數集.今后將證:|(N)|=20

>

0,即

N的冪集不是可數的無限集(見定理5.2-9).定理5.2-7:可數無限集是最小無限集:A為無限集|A|0證:只需證任意無限集A中一定存在可數無限子集即可.這一結論可推導如下:A不是有限集

a0(a0A);

A1=A-{a0}不是有限集

a1(a1A1A);

A2=A1-{a1}不是有限集

a2(a2A2A);

n(nI+

An

-{a1,…,an}不是有限集)(否則,An-1,,A1,A是有限集,矛盾)得證:A中含可數無限集{a1,…,an,…,}.§5.1和§5.2的作業(yè)布置5.1習題#2;#5(b);提示:I是無限可數的.#7(d).5.2習題#4(a);提示:證明A與(A)的一個子集等勢.#10(a);提示:正有理數集合的基數是0.#11(a).提示:利用定理5.1-7和#10(a)的結果.可數無限集的若干實例①一元字母集{a}的所有字符串集A={a}*={an|nN}(∵

令an對應n可證ANA為可數無限集).②正有理數集合Q+是可數無限集(圖5.1-1).有理數集合Q是可數無限集:|Q|=2|Q+|+1=20+1=0;同理可證,I為可數無限集.③在平面直角坐標下所有整坐標點集:(A={(x,y)|x,yI}=II)(|I|=2|N|-1=20-1=0-1=0)

|A|=|II|=(0)2=0

④所有整系數一次多項式的集

A={ax+b|aI-{0},bI}

是可數無限集.證

ax+b與a,b一一對應,故

A(I-{0})I,|A|=|I-{0}||I|=00=0.⑤具有可數數結點的所有關系的集A為可數無限集(∵對nN,具有n個結點的所有關系集An的基數等于n元集的叉積的冪集的元數,即|An|=2n2為有限集,故A=∪nNAn為可數集,又A顯然不是有限集.)作業(yè)中出現(xiàn)的問題§3.5#9由對稱和傳遞性推不出自反性因R對稱:x,yRy,xR;因R傳遞:x,yR∧y,xRx,xR.注意:如果沒有x,yR或y,xR,便得不到x,xR.所以,上面的推導得不出自反律:x(x,xR).反例:A={0,1,2},R={0,1,1,0,0,0,1,1}.易見,R是對稱的和傳遞的,但不是自反的(因2,2R,即2R2不成立).§4.3#1

下列函數是否滿,單,雙射?求集合S的逆象;求函數誘導的等價關系.(i)f:RR+,f(x)=2x,S={1,2}.解:∵f是連續(xù)函數且f(-)=0;f()=,

f是滿射.

∵f(x)>0(或f(x)=f(y)2x=2yx=y)

f也是單射,從而f是雙射.由上式也看出函數f誘導的等價關系是相等關系:1R.f-1({1,2})={0,1}.§4.3#1下列函數是否滿,單,雙射?求集合S的逆象;求函數誘導的等價關系.(ii)f:IN,f(x)=|x|,S={0,1}.解:f是滿射但不是單射(反例:|-1|=|1|).

f誘導的等價關系R是:xRy

f(x)=f(y)

|x|=|y|f-1({0,1})={0,1,-1}.(iii)f:RR+,f(x)=3,S=N.解:函數f顯然不是滿射(f(R)={3}R+);函數f也不是單射(f(0)=3=f(1));f-1(S)=R.因xy(x,yRf(x)=3=f(y)),故f誘導的等價關系是全域關系:RR.[0,1]不是可數集|[0,1]|=|(N)|>0證:每個數x[0,1]都可唯一表示為無限二進制數:x=0.x1x2

xn其中xn{0,1},nI+.(x1=2x;x2=4(x-x1);x3=23(x-x1-x2);

,x表示不大于x的最大整數).因(N)的每個元A一一對應于無限二進制串(特征函數):x1x2

xn,(若nA,xn=1;否則xn=0),故存在雙射f:[0,1](N).下面用反證法證上述雙射f不是[0,1]的枚舉(從而推出[0,1]不是可數集].若f是枚舉,則[0,1]的全部元素可枚舉為x1=0.x11x12

x1n

x2=0.x21x22

x2n………xn=0.xn1xn2

xnn………作無限二進制數:y=0.y1y2yn其中nI+(yn=1,若xnn=0;

yn=0,若xnn=1)則nI+(yxn),從而,與y[0,1]相矛盾.

|[0,1]|=|(N)|>0

20>0,§5.1#9與連續(xù)統(tǒng)[0,1]等勢的集的基數記為c基數是c的集合例子(1)對任意實數a<b,|[a,b]|=c.證:令f:[0,1][a,b],f(x)=(b-a)x+a,x[0,1],則f(x)為單調增加連續(xù)函數,并且f(0)=a;f(1)=b,由此推出

f(x)為雙射.

(2)|(0,1)|=|[0,1]|=c=|(0,1]|=|[0,1)|證:無限集(0,1)中有可數無限子集A={1/n|n=1,2,…}N,B={0,1}∪A為[0,1]的可數無限子集,故有雙射g:BA.令f:[0,1](0,1),f(x)=g(x),當xB;f(x)=x,當x[0,1]-B.則f是雙射,得證|[0,1]|=|(0,1)|=c.(3)

由①的證明和②又得:任何長度大于0的(有限)閉,開,半開半閉區(qū)間的基數都是

c.(4)

單位圓周的基數也是

c(§5.1#7)

A={x,y|x,yR∧x2+y2=1}|A|=

c證:令f:[0,2)A,f()=sin

,cos

A,易見f(x)為雙射函數,從而|A|=|[0,2)|=

c.

(5)

實數集的基數也是c:|R|=c.證:

作函數g:(0,1)R,g(x)=則g為區(qū)間(0,1)上的單調減少的連續(xù)函數,滿足g(0)=+;g(1)=-;和x(x(0,1)g(x)<0).所以g是雙射函數,|R|=|(0,1)|=c.基數c的集合的有限重叉積基數也是c證:只須證[0,1][0,1][0,1](§5.2#9)即可.我們知道,[0,1]上的每個數x與無限十進制小數一一對應:

x0.x1x2

xn,xn{0,1,…,9},nI+.叉積[0,1][0,1]的元素可表為

a,b,其中a0.a1a2

an,b0.b1b2

bn為無限十進制小數.令

f:[0,1][0,1][0,1],f(x)=a,b,其中

x0.x1x2

xn,a0.x1x3

x2k-1

,b0.x2x4

x2k

易見f為雙射函數,從而得證:

c2=c.集合A是無限集有單射f:AA,f(A)A證:必要性

令

B

={a0,a1,

an}為A的一個可數無限子集,作函數

f:

AA-{a0},f(x)=x,xB;f(an)=an+1,nN,則f顯然為雙射,且f(A)=A-{a0}是A真子集.充分性若

f:AA為單射,且f(A)為A真子集,則

A

不能為有限集.不然的話,便出現(xiàn)一個有限集的元素個數與它的一個真子集的元素個數相等的矛盾.例:

N是無限集,原因是A={2x|xN}為N的真子集;

Q是無限集,因為N為Q的真子集.Cantor定理:對任意集A成立|A|<|(A)|證:只須證明:從A到(A)存在單射但不存在雙射即可.易見:A(A),f(a)={a},aA是單射.下證:若任何函數

g:

A(A)是雙射都會導致矛盾.令S={x|xg(x)},則

S

是

A

的子集.若對某aA,g(a)=S,則aS

a{x|xg(x)}

ag(a)

aS上述矛盾證明:對任意aA都有g(a)S.這又與

g:A(A)是滿射的假設矛盾.所以,從A到(A)不存在雙射.證畢.存在可數無限個無限基數;連續(xù)統(tǒng)假設利用Cantor定理可證:存在可數無限個無限基數集:0=|N|<|(N)|(=c)<|((N))|<若A為有限集|A|=n>1,則在|A|和|(A)|之間存在其它基數.Cantor提出連續(xù)統(tǒng)假設:在0=|N|和c=|(N)|之間不存在別的基數.連續(xù)統(tǒng)假設為無數事實所證明,并且已成功地用于解決許多理論問題.特別由這個假設推出:若無限集

A

滿足

0<|A|c，則|A|=c.連續(xù)統(tǒng)假設的一個推論

我們證明過:任何長度大于

0

的有限閉,開,半開半閉區(qū)間的基數都是

c.

現(xiàn)在任何長度大于

0

的無限(閉,開,