雙射函數(shù)與集合的基數(shù)第一頁(yè)，共四十七頁(yè)，編輯于2023年，星期二本章說(shuō)明本章的主要內(nèi)容集合的等勢(shì)及其性質(zhì)重要的等勢(shì)或不等勢(shì)的結(jié)果集合的優(yōu)勢(shì)及其性質(zhì)自然數(shù)與自然數(shù)集合集合的基數(shù)可數(shù)集

第二頁(yè)，共四十七頁(yè)，編輯于2023年，星期二8.3.1集合的等勢(shì)與優(yōu)勢(shì)8.3.2集合的基數(shù)

本節(jié)小結(jié)

習(xí)題

作業(yè)本章內(nèi)容第三頁(yè)，共四十七頁(yè)，編輯于2023年，星期二定義8.8設(shè)A,B是集合，如果存在著從A到B的雙射函數(shù)，就稱(chēng)A和B是等勢(shì)（samecardinality）的，記作A≈B。 如果A不與B等勢(shì)，則記作AB。8.3.1集合的等勢(shì)與優(yōu)勢(shì)≈通俗的說(shuō)，集合的勢(shì)是量度集合所含元素多少的量。集合的勢(shì)越大，所含的元素越多。第四頁(yè)，共四十七頁(yè)，編輯于2023年，星期二（1）Z≈N。則f是Z到N的雙射函數(shù)。從而證明了Z≈N。等勢(shì)集合的實(shí)例(1)第五頁(yè)，共四十七頁(yè)，編輯于2023年，星期二等勢(shì)集合的實(shí)例(2)（2）

N×N≈N。雙射函數(shù)第六頁(yè)，共四十七頁(yè)，編輯于2023年，星期二等勢(shì)集合的實(shí)例(3)（3）N≈Q。把所有形式為p/q(p,q為整數(shù)且q>0)的數(shù)排成一張表。-2/1[5]-1/1[4]-3/1[18]2/1[10]3/1[11]0/1[0]1/1[1]-2/2-1/2[3]-3/2[17]2/23/2[12]0/21/2[2]-2/3[6]-1/3[7]-3/32/3[9]3/30/31/3[8]-2/4-1/4[15]-3/4[16]2/43/4[13]0/41/4[14]……………………以0/1作為第一個(gè)數(shù)，按照箭頭規(guī)定的順序可以“數(shù)遍”表中所有的數(shù)。計(jì)數(shù)過(guò)程中必須跳過(guò)第二次以及以后各次所遇到的同一個(gè)有理數(shù)。第七頁(yè)，共四十七頁(yè)，編輯于2023年，星期二等勢(shì)集合的實(shí)例(4)（4）(0,1)≈R。其中實(shí)數(shù)區(qū)間(0,1)={x|x∈R∧0<x<1}。令雙射函數(shù)則f是(0,1)到R的雙射函數(shù)。從而證明了(0,1)≈R

。第八頁(yè)，共四十七頁(yè)，編輯于2023年，星期二等勢(shì)集合的實(shí)例(5)（5）[0,1]≈(0,1)。其中(0,1)和[0,1]分別為實(shí)數(shù)開(kāi)區(qū)間和閉區(qū)間。雙射函數(shù)

f:[0,1](0,1)，第九頁(yè)，共四十七頁(yè)，編輯于2023年，星期二等勢(shì)集合的實(shí)例(6)（6）對(duì)任何a,b∈R，a<b，[0,1]≈[a,b]。

雙射函數(shù)f：[0,1]→[a,b]，f(x)＝(ba)x+a。第十頁(yè)，共四十七頁(yè)，編輯于2023年，星期二例8.10

設(shè)A為任意集合，則P(A)≈{0,1}A。構(gòu)造f：P(A)→{0,1}A，

f(A)=A，A∈P(A)。

其中A是集合A的特征函數(shù)。(1)易證

f是單射的。(2)對(duì)于任意的g∈{0,1}A，那么有g(shù)：A→{0,1}。令 B={x|x∈A∧g(x)=1}

則BA，且B=g，即B∈P(A)，使得f(B)=g。

所以

f是滿射的。由等勢(shì)定義得P(A)≈{0,1}A。例8.10證明復(fù)習(xí)第十一頁(yè)，共四十七頁(yè)，編輯于2023年，星期二定理8.6設(shè)A，B，C是任意集合，（1）A≈A。（2）若A≈B，則B≈A。（3）若A≈B，B≈C，則A≈C。（1） IA是從A到A的雙射，因此A≈A。（2） 假設(shè)A≈B，存在f:

AB是雙射， 那么f1:

BA是從B到A的雙射，所以B≈A。（3） 假設(shè)A≈B，B≈C，存在f:AB，g:BC是雙射， 則fg:

AC是從A到C的雙射。

所以A≈C。等勢(shì)的性質(zhì)證明第十二頁(yè)，共四十七頁(yè)，編輯于2023年，星期二

N≈Z≈Q≈N×NR≈[0,1]≈(0,1)任何的實(shí)數(shù)區(qū)間（開(kāi)區(qū)間、閉區(qū)間以及半開(kāi)半閉的區(qū)間）都與實(shí)數(shù)集合R等勢(shì)。問(wèn)題：N和R是否等勢(shì)？若干等勢(shì)集合第十三頁(yè)，共四十七頁(yè)，編輯于2023年，星期二（1）如果能證明N[0,1]，就可以斷定NR。

只需證明任何函數(shù)f：N→[0,1]都不是滿射的。

構(gòu)造一個(gè)[0,1]區(qū)間的小數(shù)b，使得b在N中不存在原像。（2）任取函數(shù)f：AP(A)，構(gòu)造B∈P(A)，使得B在A中不存在原像。 或者使用反證法。定理8.7

康托定理（1）NR。（2）對(duì)任意集合A都有AP(A)。康托定理≈≈≈≈分析第十四頁(yè)，共四十七頁(yè)，編輯于2023年，星期二（1）首先規(guī)定[0,1]中數(shù)的表示。

對(duì)任意的x∈[0,1]，令x=0.x1x2…,（0≤xi≤9）

注意：為了保證表示式的唯一性，如果遇到0.24999…，則將x表示為0.25000…。

設(shè)f:N→[0,1]是從N到[0,1]的任何一個(gè)函數(shù)。f的所有函數(shù)值為：

f(0)=0.a1(1)a2(1)…

f(1)=0.a1(2)a2(2)…

…

f(n1)=0.a1(n)a2(n)…

…

令y的表示式為0.b1b2…，并且滿足bi≠ai(i)，i=1,2,…， 則y∈[0,1]，但y與上面列出的任何一個(gè)函數(shù)值都不相等。 即f不是滿射的。

所以，NR?？低卸ɡ怼值谑屙?yè)，共四十七頁(yè)，編輯于2023年，星期二康托定理假設(shè)A≈P(A)，則必有函數(shù)f:A→P(A)是雙射函數(shù)。 如下構(gòu)造集合B：

B＝{x|x∈A∧xf(x)}

可知

B∈P(A)。

于是存在唯一一個(gè)元素b∈A，使得f(b)＝B。

若b∈B，則由B的定義知，bf(b)，即bB，矛盾。

若bB，則bf(b)，于是由B的定義知，b∈B，矛盾。第十六頁(yè)，共四十七頁(yè)，編輯于2023年，星期二（2）設(shè)g：A→P(A)是從A到P(A)的任意函數(shù)，如下構(gòu)造集合B：

B＝{x|x∈A∧xg(x)}

則B∈P(A)。

但是對(duì)任意x∈A，都有

x∈B

xg(x) 所以，對(duì)任意的x∈A都有B≠g(x)，即Brang 即P(A)中存在元素B，在A中找不到原像。所以，g不是滿射的。所以，AP(A)。說(shuō)明康托定理≈根據(jù)這個(gè)定理可以知道NP(N)。綜合前面的結(jié)果，可知N

{0,1}N。實(shí)際上，P(N)，{0,1}N和R都是比N“更大”的集合。

≈≈第十七頁(yè)，共四十七頁(yè)，編輯于2023年，星期二定義8.9（1）設(shè)A,B是集合，如果存在從A到B的單射函數(shù)，就稱(chēng)B優(yōu)勢(shì)于A，記作A≤·B。如果B不是優(yōu)勢(shì)于A，則記作A≤·B。（2）設(shè)A,B是集合，若A≤·B且AB，則稱(chēng)B真優(yōu)勢(shì)于A，記作A＜·B。如果B不是真優(yōu)勢(shì)于A，則記作A≮·B。例如：N≤·

NN≤·

RA≤·

P(A)N＜·RA＜·

P(A)R≮·

N

N≮·

N優(yōu)勢(shì)≈R≤·N第十八頁(yè)，共四十七頁(yè)，編輯于2023年，星期二定理8.8

設(shè)A,B,C是任意的集合，則（1）A≤·

A。（2）若A≤·

B且B≤·

A，則A≈B。（3）若A≤·

B且B≤·

C,則A≤·

C

。證明：（1）IA是A到A的單射，因此A≤·

A。（2）證明略。（3）假設(shè)A≤·

B且B≤·

C，那么存在單射f:A→B，g:B→C，于是fg：A→C也是單射的，因此A≤·

C

。優(yōu)勢(shì)的性質(zhì)說(shuō)明該定理為證明集合之間的等勢(shì)提供了有力的工具。構(gòu)造兩個(gè)單射f：AB和g：BA函數(shù)容易集合等勢(shì)。第十九頁(yè)，共四十七頁(yè)，編輯于2023年，星期二例題例題：證明[0,1]與(0,1)等勢(shì)。證明：構(gòu)造兩個(gè)單射函數(shù)f:(0,1)→[0,1]，f(x)＝xg:[0,1]→(0,1)，g(x)＝x/2+1/4第二十頁(yè)，共四十七頁(yè)，編輯于2023年，星期二證明{0,1}N≈[0,1)(1)設(shè)x[0,1)，0.x1x2…是x的二進(jìn)制表示。為了使表示唯一，規(guī)定表示式中不允許出現(xiàn)連續(xù)無(wú)數(shù)個(gè)1。例如x＝0.1010111，應(yīng)按規(guī)定記為0.1011000。

對(duì)于x，如下定義f：[0,1)→{0,1}N，使得

f(x)=tx，且tx：N→{0,1}，tx(n)=xn+1，n=0,1,2,…

例如

x=0.10110100…，則對(duì)應(yīng)于x的函數(shù)tx是： n 01234567… tx(n) 10110100…易見(jiàn)tx∈{0,1}N，且對(duì)于x,y∈[0,1)，x≠y，必有tx≠ty，

即f(x)≠f(y)。所以，f：[0,1)→{0,1}N是單射的。

第二十一頁(yè)，共四十七頁(yè)，編輯于2023年，星期二(2)定義函數(shù)g：{0,1}N→[0,1)。

g的映射法則恰好與

f相反，即t∈{0,1}N，t：N→{0,1}，g(t)=0.x1x2…,其中xn+1=t(n)。

但不同的是，將0.x1x2…看作數(shù)x的十進(jìn)制表示。 例如t1，t2∈{0,1}N，且g(t1)＝0.0111…，g(t2)＝0.1000…， 若將g(t1)和g(t2)都看成二進(jìn)制表示，則g(t1)＝g(t2)； 但若看成十進(jìn)制表示，則g(t1)≠g(t2)。

所以，g：{0,1}N→[0,1)是單射的。

根據(jù)定理9.3，有{0,1}N≈[0,1)。證明{0,1}N≈[0,1)第二十二頁(yè)，共四十七頁(yè)，編輯于2023年，星期二總結(jié)N≈Z≈Q≈N×NR≈[a,b]≈(c,d)≈{0,1}N≈P(N) 其中[a,b]，(c,d)代表任意的實(shí)數(shù)閉區(qū)間和開(kāi)區(qū)間。{0,1}A≈P(A)N＜·RA＜·

P(A)第二十三頁(yè)，共四十七頁(yè)，編輯于2023年，星期二8.3.2集合的基數(shù)

上一節(jié)我們只是抽象地討論了集合的等勢(shì)與優(yōu)勢(shì)。本節(jié)將進(jìn)一步研究度量集合的勢(shì)的方法。最簡(jiǎn)單的集合是有窮集。盡管前面已經(jīng)多次用到“有窮集”這一概念，當(dāng)時(shí)只是直觀地理解成含有有限多個(gè)元素的集合，但一直沒(méi)有精確地給出有窮集的定義。為解決這個(gè)問(wèn)題我們需要先定義自然數(shù)和自然數(shù)集合。第二十四頁(yè)，共四十七頁(yè)，編輯于2023年，星期二定義8.10設(shè)a為集合，稱(chēng)a∪{a}為a的后繼，記作a+，即

a+=a∪{a}。

例

考慮空集的一系列后繼。+

=∪{}={}

++

={}+={}∪{{}}={,{}}={,+}

+++

={,{}}+={,{}}∪{{,{}}}={,{},{,{}}}={,+,++}后繼說(shuō)明前邊的集合都是后邊集合的元素。前邊的集合都是后邊集合的子集。第二十五頁(yè)，共四十七頁(yè)，編輯于2023年，星期二利用后繼的性質(zhì)，可以考慮以構(gòu)造性的方法用集合來(lái)給出自然數(shù)的定義，即 0= 1=0+＝+＝{}＝{0} 2=1+＝{}+＝{}∪{{}}＝{,{}}＝{0,1} 3＝2+＝{,{}}+＝{,{},{,{}}}＝{0,1,2}

… n＝{0,1,…,n1} …說(shuō)明自然數(shù)的定義

這種定義沒(méi)有概括出自然數(shù)的共同特征。第二十六頁(yè)，共四十七頁(yè)，編輯于2023年，星期二定義8.11設(shè)A為集合，如果滿足下面的兩個(gè)條件：（1）∈A（2）a(a∈A→a+∈A)稱(chēng)A是歸納集。例如：下面的集合 {,+,++,+++,…} {,+,++,+++,…,a,a+,a++,a+++,…}

都是歸納集。歸納集

第二十七頁(yè)，共四十七頁(yè)，編輯于2023年，星期二定義8.12自然數(shù)（1）一個(gè)自然數(shù)n是屬于每一個(gè)歸納集的集合。（2）自然數(shù)集N是所有歸納集的交集。說(shuō)明：根據(jù)定義8.12得到的自然數(shù)集

N恰好由,+,++,

+++,…等集合構(gòu)成。而這些集合正是構(gòu)造性方法所定義的全體自然數(shù)。

例如：自然數(shù)都是集合，集合的運(yùn)算對(duì)自然數(shù)都適用。2∪5＝{0,1}∪{0,1,2,3,4}＝{0,1,2,3,4}＝53∩4＝{0,1,2}∩{0,1,2,3}＝{0,1,2}＝34-2＝{0,1,2,3}-{0,1}={2,3}

2×3＝{0,1}×{0,1,2}＝{<0,0>,<0,1>,<0,2>,<1,0>,<1,1>,<1,2>}

自然數(shù)n和自然數(shù)集合N的定義

第二十八頁(yè)，共四十七頁(yè)，編輯于2023年，星期二 P(1)＝P({0})＝{,{0}}＝{0,1} 23＝{0,1}{0,1,2}＝{f|f：{0,1,2}→{0,1}}＝{f0,f1,…,f7}其中f0＝{<0,0>,<1,0>,<2,0>}f1＝{<0,0>,<1,0>,<2,1>}f2＝{<0,0>,<1,1>,<2,0>}f3＝{<0,0>,<1,1>,<2,1>}f4＝{<0,1>,<1,0>,<2,0>}f5＝{<0,1>,<1,0>,<2,1>}f6＝{<0,1>,<1,1>,<2,0>}f7＝{<0,1>,<1,1>,<2,1>}舉例

第二十九頁(yè)，共四十七頁(yè)，編輯于2023年，星期二（1） 對(duì)任何自然數(shù)n，有n≈n。（2） 對(duì)任何自然數(shù)n,m，若m

n，則m≈n。（3） 對(duì)任何自然數(shù)n,m，若m∈n，則m

n。（4） 對(duì)任何自然數(shù)n和m，以下三個(gè)式子：

m∈n，m≈n，n∈m

必成立其一且僅成立其一。（5） 自然數(shù)的相等與大小順序

對(duì)任何自然數(shù)m和n，有 m=n

m≈n

m<

n

m∈n

自然數(shù)的性質(zhì)第三十頁(yè)，共四十七頁(yè)，編輯于2023年，星期二定義8.13

有窮集、無(wú)窮集（1）一個(gè)集合是有窮的當(dāng)且僅當(dāng)它與某個(gè)自然數(shù)等勢(shì)；（2）如果一個(gè)集合不是有窮的，就稱(chēng)作無(wú)窮集。例如：{a,b,c}是有窮集，因?yàn)?＝{0,1,2}，且{a,b,c}≈{0,1,2}＝3N和R都是無(wú)窮集，

因?yàn)闆](méi)有自然數(shù)與N和R等勢(shì)。任何有窮集只與唯一的自然數(shù)等勢(shì)。說(shuō)明有窮集和無(wú)窮集第三十一頁(yè)，共四十七頁(yè)，編輯于2023年，星期二定義8.14（1）對(duì)于有窮集合A，稱(chēng)與A等勢(shì)的那個(gè)唯一的自然數(shù)為A的基數(shù)，記作cardA，即cardA＝

n

A≈n

（對(duì)于有窮集A，cardA也可以記作|A|）（2）自然數(shù)集合N的基數(shù)記作0，即cardN=0（3）實(shí)數(shù)集R的基數(shù)記作（讀作阿列夫），即cardR=

基數(shù)(cardinality)第三十二頁(yè)，共四十七頁(yè)，編輯于2023年，星期二定義8.15設(shè)A,B為集合，則（1）cardA＝cardB

A≈B（2）cardA≤cardB

A≤·

B（3）cardA<cardBcardA≤cardB∧cardA≠cardB例如：cardZ＝cardQ＝cardN×N＝0cardP(N)＝card2N＝card[a,b]＝card(c,d)＝0<說(shuō)明：集合的基數(shù)就是集合的勢(shì)，基數(shù)越大，勢(shì)就越大?；鶖?shù)的相等和大小

第三十三頁(yè)，共四十七頁(yè)，編輯于2023年，星期二關(guān)于基數(shù)的說(shuō)明

由于對(duì)任何集合A都滿足A≤P(A)，所以有 cardA<

cardP(A)，這說(shuō)明不存在最大的基數(shù)。將已知的基數(shù)按從小到大的順序排列就得到： 0,1,2,…,n,…,0,,…0,1,2…,n,…是全體自然數(shù)，是有窮基數(shù)。0,,…是無(wú)窮基數(shù)。0是最小的無(wú)窮基數(shù)，后面還有更大的基數(shù)，如 cardP(R)等。第三十四頁(yè)，共四十七頁(yè)，編輯于2023年，星期二可數(shù)集定義8.16

設(shè)A為集合，若cardA≤0，則稱(chēng)A為可數(shù)集(enumerable)或可列集。例如：

{a,b,c}、5、整數(shù)集Z、有理數(shù)集Q、N×N等都是可數(shù)集。實(shí)數(shù)集R不是可數(shù)集，與R等勢(shì)的集合也不是可數(shù)集。

對(duì)于任何的可數(shù)集，都可以找到一個(gè)“數(shù)遍”集合中全體元素的順序。回顧前邊的可數(shù)集，特別是無(wú)窮可數(shù)集，都是用這種方法來(lái)證明的。說(shuō)明第三十五頁(yè)，共四十七頁(yè)，編輯于2023年，星期二（1）可數(shù)集的任何子集都是可數(shù)集。

一個(gè)集合的無(wú)限子集若不可數(shù)，則該集合也不可數(shù)。（2）兩個(gè)可數(shù)集的并是可數(shù)集。（3）兩個(gè)可數(shù)集的笛卡兒積是可數(shù)集。（4）可數(shù)個(gè)可數(shù)集的笛卡兒積仍是可數(shù)集。（5）無(wú)窮集A的冪集P(A)不是可數(shù)集。

可數(shù)集的性質(zhì)

第三十六頁(yè)，共四十七頁(yè)，編輯于2023年，星期二例8.11求下列集合的基數(shù)。（1）T＝{x|x是單詞“BASEBALL”中的字母}（2）B＝{x|x∈R∧x2=9∧2x=8}（3）C＝P(A),A={1,3,7,11}（1）由T＝{B,A,S,E,L}知，cardT＝5。（2）由B＝可知，cardB＝0。（3）由|A|＝4可知，cardC＝cardP(A)＝|P(A)|＝24＝16。解答例8.11第三十七頁(yè)，共四十七頁(yè)，編輯于2023年，星期二方法一由cardA＝0，cardB＝n，可知A,B都是可數(shù)集。令A(yù)={a0,a1,

a2,…}，B={b0,

b1,

b2,…,

bn1}。對(duì)任意的<ai,

bj>，<ak,

bl>∈A×B，有

<ai,

bj>＝<ak,

bl>

i＝

k∧j＝

l定義函數(shù)

f：A×B→N

f(<ai,

bj>)＝in+j,i＝0,1,…,j＝0,1,…,n1由于

f是A×B到N的雙射函數(shù)，所以cardA×B＝cardN＝。例8.12解答例8.12

設(shè)A,B為集合，且cardA＝0，cardB＝n，n是自然數(shù)，n≠0。求cardA×B。第三十八頁(yè)，共四十七頁(yè)，編輯于2023年，星期二例8.12方法二因?yàn)閏ardA＝0，cardB＝n，所以A,B都是可數(shù)集。根據(jù)性質(zhì)（3）可知，A×B也是可數(shù)集，所以，

cardA×B≤0

當(dāng)B≠時(shí)，cardA≤cardA×B，這就推出

0≤cardA×B綜合所述，cardA×B＝

0第三十九頁(yè)，共四十七頁(yè)，編輯于2023年，星期二本章主要內(nèi)容集合等勢(shì)的定義等勢(shì)的性質(zhì)集合優(yōu)勢(shì)的定義優(yōu)勢(shì)的性質(zhì)重要的集合等勢(shì)以及優(yōu)勢(shì)的結(jié)果自然數(shù)及其自然數(shù)集合的定義可數(shù)集與不可數(shù)集集合的基數(shù)

第四十頁(yè)，共四十七頁(yè)，編輯于2023年，星期二本章學(xué)習(xí)要求能夠證明兩個(gè)集合等勢(shì)。能夠證明一個(gè)集合優(yōu)勢(shì)于另一個(gè)集合。知道什么是可數(shù)集與不可數(shù)集。會(huì)求一個(gè)簡(jiǎn)單集合的基數(shù)。

第四十一頁(yè)，共四十七頁(yè)，編輯于2023年，星期二等勢(shì)的證明方法證明集合A與B等勢(shì)的方法直接構(gòu)造從A到B的雙射函數(shù)f 需要證明f的滿射性和f的單射性。構(gòu)造兩個(gè)單射函數(shù)f：AB和g：BA。給出函數(shù)f和g，證明f和g的單射性。利用等勢(shì)的傳遞性直接計(jì)算A與B的基數(shù)，得到cardA＝cardB。證明集合A與自然數(shù)集合N等勢(shì)的方法找到一個(gè)“數(shù)遍”A中元素的順序。第四十二頁(yè)，共四十七頁(yè)，編輯于2023年，星期二例題選講1．已知A＝{n7|n∈N}，B＝{n109|n∈N}，求下列各題：（1）cardA （2）cardB（3）card(A∪B) （4）card(A∩B)（1）構(gòu)造雙射函數(shù)f：NA，f(n)=n7，因此cardA＝0。（2）構(gòu)造雙射函數(shù)g：NA，g(n)=n109，因此cardB＝0。（3）可數(shù)集的并仍舊是可數(shù)集(或者由于A∪BN)，因此card(A∪B)≤0，但是

0＝cardA≤card(A∪B)，

從而得到card(A∪B)＝0。（4）因?yàn)?與109互素，card(A∩B)＝{n7109|nN}，與（1）類(lèi)似得到card(A∩B)＝0。解答第四十三頁(yè)，共四十七頁(yè)，編輯于2023年，星期二例題選講2.已知cardA＝0，且cardB<cardA，求card(AB)。由ABA，得到

card(AB)≤cardA，即card(AB)≤0。由cardB<cardA可知，B為有窮集，即存在自然數(shù)n，使得cardB=n。假設(shè)card(AB)<

0，那么存在自然數(shù)m，使

card(AB)＝m。從而得到，cardA＝card((AB)∪B)≤n+m與cardA＝0矛盾。因此，card(AB)＝0。解答第四十四頁(yè)，共四十七頁(yè)，編輯于2023年，星期二復(fù)習(xí)—特征函數(shù)設(shè)A為集合，對(duì)于任意的AA，A的特征函數(shù)A

:A→{0,1}定義為1，a∈A