《離散數(shù)學(xué)》函數(shù)

第五章函數(shù)《離散數(shù)學(xué)及應(yīng)用》第五章函數(shù)§5.1函數(shù)的定義§5.2函數(shù)的性質(zhì)§5.3函數(shù)的復(fù)合§5.4逆函數(shù)§5.5計算機科學(xué)中的常用函數(shù)*§5.6雙射函數(shù)及集合的勢2函數(shù)A

和B

為非空集合設(shè)

f

為

A

到

B

的二元關(guān)系,若對于任意x

Dom(f)都存在唯一的

y

Ran(f)使得

(x,y)

f成立，則稱

f

為函數(shù)(function)。函數(shù)也稱作映射（mapping）或變換（transformation）3函數(shù){(1,1),(2,3),(4,1),(3,5),(5,3)}是一個函數(shù){(1,1),(1,3),(4,1),(3,5),(5,3)}不是函數(shù)4函數(shù)假設(shè)A

到

B

的二元關(guān)系

f

為函數(shù)如果

aDom(

f)，那么

f(a)=?如果

f(a)=，習(xí)慣上使用元素b來表示集合



并且寫作f(a)=bf可以被描述為有序?qū)Φ募蟵(a,f(a))|aDom(f)}5函數(shù)f={(1,1),(2,3),(4,1),(3,5),(5,3)}是一個函數(shù)f(1)=1,f(2)=3,f(4)=1,f(3)=5,f(5)=3它也可以寫作

{(1,f(1)),(2,f(2)),(4,f(4)),

(3,f(3)),(5,f(5))}6函數(shù)7xy=f(x)ABf

函數(shù)假設(shè)A

到

B

的二元關(guān)系

f

為函數(shù)y=f(x)

中，x

稱為自變量（argument），y

為

f在

x的值（value）或

x在

f作用下的像（image）。8ab=f(a)AB函數(shù)例

A=

B=

9函數(shù)設(shè)

A、B

是非空集合，f是

A

到

B

的一個關(guān)系，如果對每個

x

A，存在唯一的

y

B

，使得

(x,y)

f，則稱

f

為A到B的函數(shù)，記作

f:A→B。對于

A到

B的函數(shù)

f

，

Dom(f)=A，Ran(f)

B。10函數(shù)例

A=

B=

11A到B的函數(shù)？函數(shù)12f:A

Ba

b

a

b=f(a)函數(shù)設(shè)

A

是一個任意非空集合.A

上的恒等函數(shù)表示為1A，其定義為1A(a)=a13第五章函數(shù)§5.1函數(shù)的定義§5.2函數(shù)的性質(zhì)§5.3函數(shù)的復(fù)合§5.4逆函數(shù)§5.5計算機科學(xué)中的常用函數(shù)*§5.6雙射函數(shù)及集合的勢14函數(shù)的性質(zhì)設(shè)函數(shù)

f:A→B，若

Ran(f)

=B，則稱

f

是滿射

（surjection）或映上的（onto）；若任意

y

Ran(f)

都存在唯一的

x

A使得

f(x)=y，則稱

f:A→B是單射(injection)或一一的（one-to-one）；若

f

既是滿射又是單射，則稱

f

是雙射（bijection）或一一對應(yīng)（one-to-onecorrespondence）。15函數(shù)的性質(zhì)f

是滿射意味著：對于任意

y

B，都存在

x

A使得

f(x)=y

f

是單射另有如下兩個等價定義：對于任意

a,b

A

滿足

a≠b

，均有f(a)≠f(b)如果

a,b

A

滿足

f(a)=f(b)，則

a=b16函數(shù)的性質(zhì)17函數(shù)的性質(zhì)18函數(shù)的性質(zhì)19函數(shù)的性質(zhì)例設(shè)

A

是非空集合，A

上的恒等函數(shù)

1A

既是單射又是滿射，從而是雙射函數(shù)

g:

→

，定義為

g(x)=x2

2x+1g

不是單射——

g(0)=g(2)=1g

也不是滿射——

g

在

x=1

取得最小值

0從而

g

不是雙射。2021函數(shù)的性質(zhì)練習(xí)f：

+

→

+

，f(1)=1，f(n)=

n–1(n>1)

單射?滿射?雙射?函數(shù)的性質(zhì)對于有限集合上的函數(shù)，有如下主要結(jié)果：定理

假設(shè)

A

和

B

是兩個有限集合且滿足

|A|=|B|，則函數(shù)

f:A

B

是單射當(dāng)且僅當(dāng)

f

是滿射。22函數(shù)的性質(zhì)定理

假設(shè)

A

和

B

都是有限集合，則：(a)若

|A|<|B|，則必然存在從

A

到

B

的單射函數(shù)、必然不存在從

A

到

B

的滿射函數(shù)；(b)若

|A|>|B|，則必然存在從

A

到

B

的滿射函數(shù)、必然不存在從

A

到

B

的單射函數(shù)；(c)若

|A|=|B|，則必然存在從

A

到

B

的雙射函數(shù)。23函數(shù)的性質(zhì)推論

假設(shè)

A

是有限集合，B

是無限集合，則：(a)必然不存在從

A

到

B

的滿射函數(shù)(b)必然不存在從

B

到

A

的單射函數(shù)24第五章函數(shù)§5.1函數(shù)的定義§5.2函數(shù)的性質(zhì)§5.3函數(shù)的復(fù)合§5.4逆函數(shù)§5.5計算機科學(xué)中的常用函數(shù)*§5.6雙射函數(shù)及集合的勢25函數(shù)的復(fù)合定理1

設(shè)

A,B,C是集合，f

是

A

到

B

的關(guān)系，g

是

B

到

C

的關(guān)系。若

f,g

是函數(shù)，則：g?f

也是函數(shù)，且滿足Dom(g?f)={x|x

Dom(f)

且

f(x)

Dom(g)}對于任意

x

Dom(g?f)有

g?f(x)=g(f(x))26函數(shù)A

和B

為非空集合設(shè)

f

為

A

到

B

的二元關(guān)系,若對于任意x

Dom(f)都存在唯一的

y

Ran(f)使得

(x,y)

f成立，則稱

f

為函數(shù)(function)。27函數(shù)的復(fù)合證明：（反證法）令

x

Dom(g?f)，若存在y1,y2Ran(g?f)

且(x,y1)

g?f,(x,y2)

g?f

。則存在t1

Dom(g)使得

(x,t1)

f

且(t1,y1)

g存在t2

Dom(g)

使得

(x,t2)

f

且(t2,y2)

g由于

f

是一個函數(shù)，因此

t1=t2由于g

是一個函數(shù)，因此

y1=y2于是

g?f

是一個函數(shù)

28函數(shù)的復(fù)合(g?f)(x)=g(f(x))29xy=f(x)ABz=g(y)

=(g?f

)(x)C函數(shù)的復(fù)合30例f：

→

，f(x)=x+1，g：

→

，g(x)=2x+1,h：

→

，h(x)=x2+1,

g?f(x)=g(f(x))=2f(x)+1=2(x+1)+1=2x+3f?g(x)=f(g(x))=g(x)+1=2x+1+1=2x+2h?g?f(x)=h(g(f(x)))=4x2+12x+10=(2x+3)2+1函數(shù)的復(fù)合定理2

假設(shè)

A、B、C

為非空集合，函數(shù)

f:A→B,g:B→C，則(a)如果

g

和

f

都是滿射，則

g?f

也是滿射(b)如果

g

和

f

都是單射，則

g?f

也是單射(c)如果

g

和

f

都是雙射，則

g?f

也是雙射

31函數(shù)的復(fù)合32函數(shù)的復(fù)合但是反過來，定理2的逆定理并不全部成立，而只是部分成立。定理3

假設(shè)

A、B、C

為非空集合，函數(shù)

f:A→B,g:B→C，則(a)若

g?f是單射，則

f

是單射(b)若

g?f是滿射，則

g

是滿射(c)若

g?f是雙射，則

f是單射，g

是滿射33函數(shù)的復(fù)合34函數(shù)的復(fù)合定理4

假設(shè)

A、B

為集合，函數(shù)

f:A

B，則

f=f?1A

=1B?f

。35第五章函數(shù)§5.1函數(shù)的定義§5.2函數(shù)的性質(zhì)§5.3函數(shù)的復(fù)合§5.4逆函數(shù)§5.5計算機科學(xué)中的常用函數(shù)*§5.6雙射函數(shù)及集合的勢36逆函數(shù)R={(1,1),(3,1),(2,2)}是一個函數(shù)R

1={(1,1),(1,3),(2,2)}不是一個函數(shù)37逆函數(shù)假設(shè)

A、B為集合，如果函數(shù)

f:A

B作為關(guān)系的逆關(guān)系

f

1是

B

到

A

的函數(shù)，則稱之為可逆的（invertible），此時稱

f

1為

f

的反函數(shù)或逆函數(shù)（inversefunction）。38逆函數(shù)定理

假設(shè)

A、B

為集合，設(shè)

f:A→B，若函數(shù)

f

1

存在則；(a)f

1?f=1A(b)

f?f

1

=1B39逆函數(shù)證明

（

f

1?f=1A

）假設(shè)函數(shù)

f

1

存在。對于任意

x

A，由于

f

是

A

到

B

的函數(shù)，因此存在

y

B，使得

(x,y)

f于是

(x,x)

f

1?f

，即得

1A

f

1?f

又由于

f

和

f

1

都是函數(shù)，因此f

1?f

也是函數(shù)對于任意

x

A

，若還存在

y

A

使得

(x,y)

f

1?f，則必然有

y=x，即

f

1?f=1A40逆函數(shù)下面一個定理給出了逆函數(shù)存在的充要條件：定理

假設(shè)

A、B

為非空集合，函數(shù)

f:A

B，則(a)f

可逆當(dāng)且僅當(dāng)

f

是雙射(b)f

的逆函數(shù)若存在則也是雙射41逆函數(shù)證明.（充分性）若

f

是雙射，則

f

1

是

B

到

A

的函數(shù)。f

1是一個關(guān)系，且由

f

是雙射有

Dom(f

1)=Ran(f)=B， Ran(f

1)=Dom(f)=A對于任意的

b

B，若存在

a1,a2

A

使得

(b,a1)

f

1

且

(b,a2)

f

1則由關(guān)系逆的定義有

(a1,b)

f

且

(a2,b)

f

，根據(jù)

f

是單射可得

a1=a2

42逆函數(shù)證明.（必要性）假設(shè)

f

可逆，以下分兩個步驟證明

f

是雙射：①

f

是單射：由

f

1?f=1A

及1A是單射，知f是單射。②

f

是滿射：由

f?f

1=1B

及1B是滿射，知f是滿射。43逆函數(shù)證明.下面證明

f

1也是雙射：①

f

1

是滿射：由

f

1?f=1A

及1A是滿射，知f

1

是滿射。②

f

1

是單射：由

f?f

1=1B

及1B是單射，知f

1

是單射。44逆函數(shù)例h:

→

，h(x)=2x+1是雙射，因此可逆，逆函數(shù)是

h

1(x)=(x

1)/2g:

→

，g(x)=

x2+2x

1不是雙射因此不存在

g

的逆函數(shù)4546逆函數(shù)定理3

若函數(shù)

f:A

B

和g:B

A

滿足g?f=1A

和f?g=1B

，則f是一個

A

到

B

的雙射，g

是一個

B

到

A

的雙射，而且

f

和

g

互為逆函數(shù)。

逆函數(shù)由此逆函數(shù)也可以等價地定義為：假設(shè)

A、B

為集合，對于函數(shù)

f:A

B若存在函數(shù)

f

1

使得

f

1?f=1A且

f?f

1=1B。則稱

f為可逆的，此時稱

f

1為

f

的反函數(shù)或逆函數(shù)。47第五章函數(shù)§5.1函數(shù)的定義§5.2函數(shù)的性質(zhì)§5.3函數(shù)的復(fù)合§5.4逆函數(shù)§5.5計算機科學(xué)中的常用函數(shù)*§5.6雙射函數(shù)及集合的勢48使用序列表示集合如何在計算機中表示序列？使用數(shù)組、線性表如何在計算機中表示集合和進行集合的運算？49使用序列表示集合設(shè)

U

為全集，對于任意集合

A

U，可定義

A

的特征函數(shù)（characteristicfunction）

A:U→{0,1}為50Ifx

A.

0Ifx

A

1

A(x)=使用序列表示集合例U={0,1,…,9},A={0,1,2,3},B={1,3,5,7,9}A∪B={0,1,2,3,5,7,9}A∩B={1,3}A

B={0,2}A={4,5,6,7,8,9}B={0,2,4,6,8}A

B={0,2,5,7,9}51使用序列表示集合52U={0,1,…,9},A={0,1,2,3},B={1,3,5,7,9}0123456789

A1111000000

A

B0101010101

B

A∩B

A∪B

A-B

A

B使用序列表示集合53U={0,1,…,9},A={0,1,2,3},B={1,3,5,7,9}0123456789

A1111000000

A0000111111

B0101010101

B1010101010

A∩B

A∪B

A-B

A

B使用序列表示集合54U={0,1,…,9},A={0,1,2,3},B={1,3,5,7,9}0123456789

A1111000000

A

B0101010101

B

A∩B0101000000

A∪B

A-B

A

B使用序列表示集合55U={0,1,…,9},A={0,1,2,3},B={1,3,5,7,9}0123456789

A1111000000

A

B0101010101

B

A∩B

A∪B1111010101

A-B

A

B使用序列表示集合56U={0,1,…,9},A={0,1,2,3},B={1,3,5,7,9}0123456789

A1111000000

A

B0101010101

B

A∩B

A∪B

A-B1010000000

A

B使用序列表示集合57U={0,1,…,9},A={0,1,2,3},B={1,3,5,7,9}0123456789

A1111000000

A

B0101010101

B

A∩B

A∪B

A-B

A

B使用序列表示集合58U={0,1,…,9},A={0,1,2,3},B={1,3,5,7,9}0123456789

A1111000000

A

B0101010101

B

A∩B

A∪B

A-B

A

B1010010101使用序列表示集合對于所有

x

U，特征函數(shù)滿足以下等式：(a)

A(x)=

1

A(x)(b)

A∩B(x)=

A(x)

B(x)(c)

A∪B(x)=

A(x)+

B(x)

A(x)

B(x)(d)

A

B(x)=

A(x)+

B(x)

2

A(x)

B(x)(e)

A

B(x)=

A(x)(1

B(x))59使用序列表示集合一般情況下，假設(shè)全集

U的基數(shù)是

n且其元素有一個確定的順序于是每一個全集的子集都一一對應(yīng)著一個

n

維0-1向量，集合運算可以轉(zhuǎn)化為0-1向量之間的運算60地板函數(shù)與天花板函數(shù)定義在

上的地板函數(shù)（floorfunction），也稱作下取整函數(shù)或者高斯函數(shù)，其值是不超過自變量

x

的最大整數(shù)，記作

floor(x)

或

x

定義在

上的天花板函數(shù)（ceilingfunction），也稱作上取整函數(shù)，其值是不小于

x

的最小整數(shù)，記做

ceiling(x)或

x

61

x

x

x

地板函數(shù)與天花板函數(shù)下取整函數(shù)

和

上取整函數(shù)（圖片來自WolframMathWorld）62地板函數(shù)與天花板函數(shù)例

5

=5,

2.4

=2,

2.4

=

3,

=

4

5

=5,

2.4

=3,

2.4

=

2,

=

363地板函數(shù)與天花板函數(shù)上取整函數(shù)和下取整函數(shù)具有如下性質(zhì)：設(shè)

n

為任意整數(shù)，x

為實數(shù)，則(a1)

x

=n當(dāng)且僅當(dāng)

n

≤x<n+1(a2)

x

=n當(dāng)且僅當(dāng)

n

1<x≤n(a3)

x

=n當(dāng)且僅當(dāng)

x

1<n≤x(a4)

x

=n當(dāng)且僅當(dāng)

x

≤n<x+1(b1)

x+n

=

x

+n

(b2)

x+n

=

x

+n64地板函數(shù)與天花板函數(shù)上取整函數(shù)和下取整函數(shù)具有如下性質(zhì)：(c)x

1<

x

≤x≤

x

<x+1(d1)

x

=

x

(d2)

x

=

x

65置換假設(shè)非空有限集合

S

包含

n

個元素，S

上的一個雙射稱為

S

的一個

n元置換或簡稱置換（permutation），表示為其中

xi表示

S

中互異元素。n

稱為置換的階（order）。66

=x1x2…xnf(x1)f(x2)…f(xn)置換置換的表示形式是不唯一的，例如：67

=123321

=132312

=213231

=231213

=312132

=321123置換集合

S={1,2,3}上的置換（雙射函數(shù)）有

3!=6

個，分別為：68

1

=123123

2

=123132

3

=123213

4

=123231

5

=123312

6

=123321置換一般地講，假設(shè)

S

是有

n

個元素的有限集，則(a)S

的任一個置換都有

n!

種不同的表示(b)S

共有

n!

個彼此不同的置換69置換假設(shè)有限集合

S

包含

n

個元素，則稱

S

上的恒等函數(shù)為

S

的恒等置換或不變置換。置換存在逆置換置換可以進行復(fù)合也稱作置換的乘積或積70置換例71

1

=123312

2

=123213(

1)1

=123231

2?

1

=123321(

2)1

=123213

1?

2

=123132置換假設(shè)

是集合

S

的一個置換，則可定義

的冪為：(1)

0=1S，(2)

n=

n

1?

，n

1。注：易見(

1)n=(

n)

1。72置換假設(shè)

是集合

S

的一個置換，使得

k=1S成立的最小正整數(shù)

k

稱作

的周期（period），記作per(

)。73置換例

1=

3=1S因此

的周期為374

=123312

2

=123231置換定理

假設(shè)

是有限集合

S的一個置換，則

的周期必定存在。75置換證明

考察無限序列

1,

2,

3,…由于有限集合

S

的置換只有有限個因此必定存在

1

i<j使得

i

=

j于是

j

i=(

j)?(

i)

1=1S即序列

1,

2,

3,…,

j

i中必定存在最小正整數(shù)

k

使得

k=1S，其即為

的周期。

76輪換假設(shè)有限集合

S

包含

n

個元素，以

(a1,a2,…,ar)

表示

S

的一個如下置換：將

a1

映射為

a2

，將

a2映射為

a3，......，將

ar

1

映射為

ar

，將

ar映射為

a1

，同時將其它元素映射到自身。(a1,a2,…,ar)稱為一個r-輪換或簡稱輪換（cyclepermutation），r

稱作該輪換的長度。2-輪換也稱作對換。通常將

1S

寫作輪換(1)。77輪換例78

1

=123123

2

=123132

3

=123213

4

=123231

5

=123312

6

=123321可寫作(1)可寫作(2,3)可寫作(1,2)可寫作(1,2,3)可寫作(1,3,2)可寫作(1,3)輪換若兩個輪換

1=(a1,a2,…,ar)和

2=(b1,b2,…,bs)滿足{a1,a2,…,ar}∩{b1,b2,…,bs}=

，則稱它們是不相交的輪換。容易證明，不相交輪換對于復(fù)合運算是可換的。定理

任一置換可唯一（不計輪換的次序）表示成若干不相交輪換的復(fù)合（積）。79輪換(1,2,3,5,8)801234567823578461輪換(1,2,3,5,8)81467746(4,7,6)哈希函數(shù)設(shè)

A

為有限集合，n

為一確定正整數(shù)，則

A

到

An

的函數(shù)

H:A*→An可稱作一個哈希函數(shù)（hashfunction）。82哈希函數(shù)哈希函數(shù)也稱散列函數(shù)

或雜湊函數(shù)可以將任意長度的輸入數(shù)據(jù)（字符串）打亂、混合、壓縮，映射成一個定長的輸出字符串于是創(chuàng)建一個叫做“摘要”的數(shù)字“指紋”，使得數(shù)據(jù)量變小，并將數(shù)據(jù)格式固定下來83哈希函數(shù)并非所有這樣的函數(shù)都是“好”的、

適合實際應(yīng)用的哈希函數(shù)一個好的哈希函數(shù)一般要滿足以下兩個要求：(a)沖突盡可能少H必定不是單射必定存在不同的自變量產(chǎn)生相同的哈希值這種現(xiàn)象稱為沖突(Collision)或碰撞好的哈希函數(shù)應(yīng)盡可能減少沖突的出現(xiàn)(b)散列值應(yīng)盡可能均勻地分布在整個

值域范圍內(nèi)84哈希函數(shù)設(shè)

A={0,1,2,…,9}，則每一個非負(fù)整數(shù)都可以看作

A*中的一個元素，對于給定的正整數(shù)

m，可定義函數(shù)

f

為：

f(x)=x

modm則

f

是

A*

到

An的哈希函數(shù)（不一定是滿射），其中

n=

log10m

85哈希函數(shù)對于密碼學(xué)中使用的安全哈希函數(shù)，有如下要求：快速性：已知

m，計算

H(m)

是容易的。單向性：已知

c=H(m)，求

m在計算上是不可行的。弱抗碰撞性：對給定的消息

m1

，找到另一個與之不同的消息

m2，使得

H(m1)=H(m2)在計算上是不可行的。強抗碰撞性：找到兩個不同的消息

m1

和

m2，使得

H(m1)=H(m2)

在計算上是不可行的。敏感性：c=H(m)，c

的每一比特都與

m

的每一比特相關(guān)，并有高度敏感性，即每改變

m

的一比特，都將對

c

產(chǎn)生明顯影響。86第五章函數(shù)§5.1函數(shù)的定義§5.2函數(shù)的性質(zhì)§5.3函數(shù)的復(fù)合§5.4逆函數(shù)§5.5計算機科學(xué)中的常用函數(shù)*§5.6雙射函數(shù)及集合的勢87集合的勢1638年，伽利略（GalileoGalilei）在《關(guān)于兩種新科學(xué)的對話》中借三個中世紀(jì)的學(xué)者的對話指出：對于每個自然數(shù)，都有且只有一個平方數(shù)與之對應(yīng)881

12

43

94

16

n

n2

集合的勢于是產(chǎn)生一個問題：自然數(shù)和自然數(shù)的平方哪個多？部分和全體哪個多？當(dāng)時它不僅困惑了伽利略，也使許多數(shù)學(xué)家束手無策。89集合的勢1874-1894年間，康托（Cantor，1845-1918）圓滿地解決了這個問題，其基本思想是“一一對應(yīng)”。假設(shè)

A

和

B

是兩個集合，如果存在

A

到

B

的雙射，則稱集合

A

與集合

B

是等勢的，記作

A

B；或稱

A

和

B

的基數(shù)相等，記作

|A|=|B|。90集合的勢定理

集合族（即集合的集合）上的等勢關(guān)系是一個等價關(guān)系。91集合的勢例A={a,b,c}和

B={劉備,關(guān)羽,張飛}

等勢如果兩個有限集合的元素個數(shù)相同，它們一定等勢如果兩個有限集合的元素個數(shù)不同，它們一定不等勢因此對于有限集合，可以按其元素個數(shù)劃分為不同的等價類92集合的勢定理

有限集合不能與其任意真子集等勢自然數(shù)集合和自然數(shù)的平方集合等勢雙射函數(shù)為

f(x)=x2可以證明任意無限集必與其某個真子集等勢這給出了無限集的本質(zhì)經(jīng)常用來作為無限集合的定義93集合的勢哪個線段上的點多?94實軸上所有閉區(qū)間都等勢類似地可以證明實軸上所有開區(qū)間都等勢集合的勢線段和直線，哪個上面的點多?95集合的勢線段和直線，哪個上面的點多?雙射：tan函數(shù)96實軸上所有開區(qū)間都與實數(shù)集合等勢集合的勢自然數(shù)集

={0,1,2,…}和整數(shù)集

是等勢的。雙射函數(shù)為97集合的勢98…-5-4-3-2-1012345…012345678910……集合的勢自然數(shù)集

和

是等勢的。99(0,0)(0,1)(0,2)(1,0)(1,1)(1,2)(2,0)(2,1)(0,3)(3,0)……………集合的勢開區(qū)間(0,1)與閉區(qū)間[0,1]是等勢的其他的數(shù)對應(yīng)到自己100集合的勢開區(qū)間

(0,1)

與

(0,1)

(0,1)

等勢將每一個實數(shù)

x

(0,1)

表示成無限小數(shù)形式

x=x1x2…xi…0.5可表示成0.4999……，0.781可表示為0.780999……。建立

(0,1)與

(0,1)

(0,1)之間的雙射：1010.x1x2x3x4x5x6……0.x1x3x5……0.x2x4x6……

集合的勢實數(shù)集

與復(fù)數(shù)集

是等勢的

與

等勢

與

等勢102集合的勢自然數(shù)集

和閉區(qū)間[0,1]不等勢證明：（反證法）假設(shè)存在一個雙射函數(shù)

f:

→[0,1]，則[0,1]中的元素必與

中的元素一一對應(yīng)那么[0,1]中的元素必可排列成如下的形式：Ran(f)=[0,1]={x0,x1,x2,x3,…}103集合的勢設(shè)每個

xi的小數(shù)形式是：0.ai0ai1ai2…aij…，aij

{0,1,…,9}則有由

f

是雙射，任一[0,1]中的實數(shù)均應(yīng)出現(xiàn)在上表中的某一行下面按照對角線構(gòu)造一個新的小數(shù)

y

=0.

b0b1b2…bj…，使得

bi

aii

且

bi

9

避免出現(xiàn)0.79999999....等類似情況那么顯然有

y[0,1]，而又不在上表中因為

y與上表中任一項都至少存在一位不同

因此

f不可能是滿射，更不可能是雙射

104f(0)=x0=0.a00a01a02…a0j…，f(1)=x1=0.a10a11a12…a1j…，f(2)=x2=0.a20a21a22…a2j…，……f(i)=xi=0.ai0ai1ai2…aij…，……集合的勢定理(康托定理，1890)自然數(shù)集

和實數(shù)集

不等勢。105集合的勢假設(shè)

A

和

B

是兩個集合，(a)如果存在

A

到

B

的單射，

則稱集合

A劣勢于集合

B

，記作

A

B；或稱

A

的基數(shù)小于等于

B

的基數(shù)，記作

|A|

|B|。(b)如果存在

A

到

B

的單射，但不存在

A

到

B

的雙射，則稱集合

A

嚴(yán)格劣勢于集合

B

，記作

A<B；或稱

A

的基數(shù)小于

B

的基數(shù)，記作

|A|<|B|。106集合的勢與自然數(shù)集合或其子集等勢的集合稱為可數(shù)（countable）集合或可列集合，自然數(shù)集合的基數(shù)記為

0(讀作阿列夫零)；否則稱作不可數(shù)（uncountable）集合或不可列集合。換言