集合論與圖論-第9講基數(shù)上

自然數(shù)的兩個基本性質(zhì)匹配(matching):多少,大小(基數(shù))----雙射{a}

{0}=1{a,b}

{0,1}=2{a,b,c}

{0,1,2}=3…計數(shù)(counting):首尾,先后(序數(shù))----良序0123…ababc……2008-10-9《集合論與圖論》第9講22008-10-9《集合論與圖論》第9講3等勢集合A與B等勢(same

cardinality)

雙射f:AB記作AB2008-10-9《集合論與圖論》第9講4例5.1N

N偶={n

|

n

N

n為偶數(shù)}f:NN偶,f(n)=2nN

N奇={n

|

n

N

n為奇數(shù)}g:NN奇,g(n)=2n+1N

N2n

=

{

x

|

x=2n

nN

}h:

NN2n,

h(n)=2n容易證明,

f,g,h都是雙射2008-10-9《集合論與圖論》第9講5定理5.1Z

NNN

NN

Q(0,1)

R[0,1]

(0,1)定理5.1證明(1)(1)

Z

N證明:取f:ZN,f(n)

=0,

n=02n,

n>02|n|-1,

n<0容易證明,

f是雙射.

Z

N2008-10-9《集合論與圖論》第9講62008-10-9《集合論與圖論》第9講7定理5.1證明(2)(2)

NN

N證明:

例3.6,

f:NNN,f(<i,j>)=2i(2j+1)-1定理5.1證明(3)(3)

N

Q證明:

f:NQ,

f(n)=

[n]的既約分數(shù)2008-10-9《集合論與圖論》第9講8定理5.1證明(4)(4)

(0,1)

R證明一: f:

(0,1)R,

f(x)=tg

(x-1/2)證明二:2008-10-9《集合論與圖論》第9講9定理5.1證明(5)(5)

[0,1]

(0,1)證明:f:[0,1](0,1),1/2,f(x)

=1/(n+2),x,x=0x=1/n,

nN-{0}其他可以證明,

f是雙射,

[0,1](0,1)

#2008-10-9《集合論與圖論》第9講10Hilbert旅館有自然數(shù)那么多間房子2008-10-9《集合論與圖論》第9講11012345678012345678-1012345678012345678[0,1](0,1)1/3

1/22008-10-9《集合論與圖論》第9講121/n

…1/41/12008-10-9《集合論與圖論》第9講13定理5.2P(A)

2A

=A22A={0,1}A=A{0,1}={f|f:A2}2008-10-9《集合論與圖論》第9講14定理5.2證明P(A)

2A

=

A2證明:

取H:

P(A)2A,

H(B)=B:A{0,1},B是B的特征函數(shù),B(x)=1xB.H是單射.設(shè)B1,B2

A且B1B2,則H(B1)=B1B2=H(B2).H是滿射.任給f:A2,令B={xA|f(x)=1}A,則H(B)=B=f.

#2008-10-9《集合論與圖論》第9講15定理5.3對任意集合A,B,C,AAAB

BAAB

BC

AC等勢關(guān)系是等價關(guān)系2008-10-9《集合論與圖論》第9講16定理5.3證明要點自反:AAIA

:AA雙射對稱:AB

BAf:AB雙射

f

-1:BA雙射傳遞:AB

BC

ACf:AB,

g:BC雙射

g○f:AC雙射2008-10-9《集合論與圖論》第9講17已知等勢關(guān)系N

Z

Q

NN(0,1)

[0,1]

RN

R

?定理5.4(康托定理)N

R對任意集合A,A

P(A)2008-10-9《集合論與圖論》第9講18康托定理證明(1)(1)

N

R證明:(反證)假設(shè)NR[0,1],則存在f:N[0,1]雙射,nN,

令f(n)=xn+1,于是ran

f=[0,1]={x1,x2,x3,…,xn,…}將xi表示成如下小數(shù):2008-10-9《集合論與圖論》第9講192008-10-9《集合論與圖論》第9講20康托定理證明(1)x1=0.a1(1)a2(1)a3(1)……x2=0.a1(2)a2(2)a3(2)……x3=0.a1(3)a2(3)a3(3)……┇xn=0.a1(n)a2(n)a3(n)……┇其中

0aj

9,

i,j=1,2,…(i)2008-10-9《集合論與圖論》第9講21康托定理證明(1)為了使這種表示法惟一,當(dāng)?shù)趓位本身不是9,但第r位以后全為9時,將這些9都改為0,在第r位上加1.例如,0.9999…記作1.0000…0.14999…記作0.15000…2008-10-9《集合論與圖論》第9講22康托定理證明(1)下面選一個[0,1]中的小數(shù)x=0.b1b2b3……使得(1)

0bj9,

i=1,2,…n(2)

bna

(n)(3)對x也注意表示的惟一性康托定理證明(1)由x的構(gòu)造可知,x[0,1],x{x1,x2,x3,…,xn,…}

(x與xn在第n位上不同).這與[0,1]={x1,x2,x3,…,xn,…}

!2008-10-9《集合論與圖論》第9講23康托定理證明(2)AP(A)abcaabacbcabcbc(2)

AP(A)2008-10-9《集合論與圖論》第9講24康托定理證明(2)AP(A)?2008-10-9《集合論與圖論》第9講25康托定理證明(2)(2)對任意集合A,AP(A).證明:(反證)假設(shè)存在雙射f:AP(A),令

B

=

{

xA

|

xf(x)

}

P(A)由于f是雙射,存在x0使得f(x0)=B,則x0B

x0f(x0)

x0B,!

#2008-10-9《集合論與圖論》第9講2627對角化(diagonalization)0123452008-10M-9012345L是否是否是是L否是否否是否L否否否否否否L是否是否是否L是是是是是是L否是否否否是LMM《M集合論與圖M論》第9講MMO28對角化(diagonalization)0123452008-10M-9012345L是否是否是是L否是否否是否L否否否否否否L是否是否是否L是是是是是是L否是否否否是LMM《M集合論與圖M論》第9講MMO29對角化(diagonalization)0123452008-10M-9012345L否否是否是是L否否否否是否L否否是否否否L是否是是是否L是是是是否是L否是否否否否LMM《M集合論與圖M論》第9講MMO對角化簡史(1)公元前7世紀(jì)(600

BC):Epimenides悖論所有

人都是說謊者----一個

詩人說.公元前5世紀(jì)(400

BC):Eubulides悖論這句話是

.公元13世紀(jì)(1200

AD):Medieval

Study

ofInsolubia.我是說謊者.2008-10-9《集合論與圖論》第9講302008-10-9《集合論與圖論》第9講31對角化簡史(2)1874年:Cantor定理實數(shù)集是不可數(shù)的.1901年:Russell悖論不以自身作為元素的集合的全體.1931年:G?del不完全性定理這句話沒有證明.1936年:Turing.停機問題是不可判定的.2008-10-9《集合論與圖論》第9講32有窮集有窮集(finite

set)與某個自然數(shù)n等勢的集合

不能與自身真子集建立雙射的集合2008-10-9《集合論與圖論》第9講33無窮集無窮集(infinite

set)不與某個自然數(shù)n等勢的集合

能與自身真子集建立雙射的集合Bernhard

BolzanoBernhard

Bolzano(1781~1848),Czech人,1851,“Paradoxes

of

the

Infinite”首次使用“set”一詞給出無窮集的上述定義2008-10-9《集合論與圖論》第9講342008-10-9《集合論與圖論》第9講35定理5.5不存在與自己的真子集等勢的自然數(shù)2008-10-9《集合論與圖論》第9講36定理5.5證明(S)不存在與自己的真子集等勢的自然數(shù).證明:(數(shù)學(xué)歸納法)令S

={nN

|

f(f(nn)

f單射

f滿射)}.2008-10-9《集合論與圖論》第9講37定理5.5證明(1)S

={nN

|

f(f(nn)f單射

f滿射)}.(1)

0S:f(00)

f是空函數(shù)

f滿射.定理5.5證明(2)說明(a)

ran

f

=

ran

fn

{f(n)}2008-10-9《集合論與圖論》第9講38(b)

ran

f

=

f(n-{m})

{f(m)}

{f(n)}n-1

nmn-1

n002008-10-9《集合論與圖論》第9講39定理5.5證明(2a)

(2)nSn+S:即f:n+n+單射f滿射:設(shè)g=fn:nn+,分兩種情形：(a)

假設(shè)n

在f

下封閉.則g:nn單射,由歸納假設(shè),ran

g=n.由于f是單射,

必有f(n)=n.

于是,ran

f

=

ran

g

{n}

=

n

{n}

=

n+.定理5.5證明(2b)(b)假設(shè)n

在f

下不封閉.設(shè)mn,f(m)=n,令h:n+n+,f(n),

x=mh(x)

=n,

x=nf(x), xm

xn則n在h下封閉,化為(a)情況.ran

f

=

ran

h

=

n+.

S=N.

#2008-10-9《集合論與圖論》第9講402008-10-9《集合論與圖論》第9講41推論1不存在與自己的真子集等勢的有窮集推論1證明不存在與自己的真子集等勢的有窮集.證明:

(反證法)

假設(shè)存在有窮集AB和f:AB雙射,自然數(shù)n和g:An雙射.令h=(gB)○f○g-1:ng(B),h雙射,但是g(B)n(若g(B)=n,則g不是單射),與定理5.5

!

#2008-10-9《集合論與圖論》第9講422008-10-9《集合論與圖論》第9講43推論2與自己的真子集等勢的集合都是無窮集N是無窮集.

#2008-10-9《集合論與圖論》第9講44推論3任何有窮集都與唯一