集合论与图论-第9讲基数上

自然数的两个基本性质匹配(matching):多少,大小(基数)----双射{a}

{0}=1{a,b}

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

{0,1,2}=3…计数(counting):首尾,先后(序数)----良序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为偶数}f:NN偶,f(n)=2nN

N奇={n

|

n

N

n为奇数}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]的既约分数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旅馆有自然数那么多间房子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的特征函数,B(x)=1xB.H是单射.设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等势关系是等价关系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已知等势关系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证明:(反证)假设NR[0,1],则存在f:N[0,1]双射,nN,

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

f=[0,1]={x1,x2,x3,…,xn,…}将xi表示成如下小数: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)为了使这种表示法惟一,当第r位本身不是9,但第r位以后全为9时,将这些9都改为0,在第r位上加1.例如,0.9999…记作1.0000…0.14999…记作0.15000…2008-10-9《集合论与图论》第9讲22康托定理证明(1)下面选一个[0,1]中的小数x=0.b1b2b3……使得(1)

0bj9,

i=1,2,…n(2)

bna

(n)(3)对x也注意表示的惟一性康托定理证明(1)由x的构造可知,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).证明:(反证)假设存在双射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世纪(600

BC):Epimenides悖论所有

人都是说谎者----一个

诗人说.公元前5世纪(400

BC):Eubulides悖论这句话是

.公元13世纪(1200

AD):Medieval

Study

ofInsolubia.我是说谎者.2008-10-9《集合论与图论》第9讲302008-10-9《集合论与图论》第9讲31对角化简史(2)1874年:Cantor定理实数集是不可数的.1901年:Russell悖论不以自身作为元素的集合的全体.1931年:Gödel不完全性定理这句话没有证明.1936年:Turing.停机问题是不可判定的.2008-10-9《集合论与图论》第9讲32有穷集有穷集(finite

set)与某个自然数n等势的集合

不能与自身真子集建立双射的集合2008-10-9《集合论与图论》第9讲33无穷集无穷集(infinite

set)不与某个自然数n等势的集合

能与自身真子集建立双射的集合Bernhard

BolzanoBernhard

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

of

the

Infinite”首次使用“set”一词给出无穷集的上述定义2008-10-9《集合论与图论》第9讲342008-10-9《集合论与图论》第9讲35定理5.5不存在与自己的真子集等势的自然数2008-10-9《集合论与图论》第9讲36定理5.5证明(S)不存在与自己的真子集等势的自然数.证明:(数学归纳法)令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是空函数

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满射:设g=fn:nn+,分两种情形：(a)

假设n

在f

下封闭.则g:nn单射,由归纳假设,ran

g=n.由于f是单射,

必有f(n)=n.

于是,ran

f

=

ran

g

{n}

=

n

{n}

=

n+.定理5.5证明(2b)(b)假设n

在f

下不封闭.设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证明不存在与自己的真子集等势的有穷集.证明:

(反证法)

假设存在有穷集AB和f:AB双射,自然数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任何有穷集都与唯一