雙射函數(shù)與集合的基數(shù)

雙射函數(shù)與集合的基數(shù)第1頁，課件共47頁，創(chuàng)作于2023年2月本章說明本章的主要內(nèi)容集合的等勢及其性質(zhì)重要的等勢或不等勢的結(jié)果集合的優(yōu)勢及其性質(zhì)自然數(shù)與自然數(shù)集合集合的基數(shù)可數(shù)集

第2頁，課件共47頁，創(chuàng)作于2023年2月8.3.1集合的等勢與優(yōu)勢8.3.2集合的基數(shù)

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

習(xí)題

作業(yè)本章內(nèi)容第3頁，課件共47頁，創(chuàng)作于2023年2月定義8.8設(shè)A,B是集合，如果存在著從A到B的雙射函數(shù)，就稱A和B是等勢（samecardinality）的，記作A≈B。 如果A不與B等勢，則記作AB。8.3.1集合的等勢與優(yōu)勢≈通俗的說，集合的勢是量度集合所含元素多少的量。集合的勢越大，所含的元素越多。第4頁，課件共47頁，創(chuàng)作于2023年2月（1）Z≈N。則f是Z到N的雙射函數(shù)。從而證明了Z≈N。等勢集合的實例(1)第5頁，課件共47頁，創(chuàng)作于2023年2月等勢集合的實例(2)（2）

N×N≈N。雙射函數(shù)第6頁，課件共47頁，創(chuàng)作于2023年2月等勢集合的實例(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作為第一個數(shù)，按照箭頭規(guī)定的順序可以“數(shù)遍”表中所有的數(shù)。計數(shù)過程中必須跳過第二次以及以后各次所遇到的同一個有理數(shù)。第7頁，課件共47頁，創(chuàng)作于2023年2月等勢集合的實例(4)（4）(0,1)≈R。其中實數(shù)區(qū)間(0,1)={x|x∈R∧0<x<1}。令雙射函數(shù)則f是(0,1)到R的雙射函數(shù)。從而證明了(0,1)≈R

。第8頁，課件共47頁，創(chuàng)作于2023年2月等勢集合的實例(5)（5）[0,1]≈(0,1)。其中(0,1)和[0,1]分別為實數(shù)開區(qū)間和閉區(qū)間。雙射函數(shù)

f:[0,1](0,1)，第9頁，課件共47頁，創(chuàng)作于2023年2月等勢集合的實例(6)（6）對任何a,b∈R，a<b，[0,1]≈[a,b]。

雙射函數(shù)f：[0,1]→[a,b]，f(x)＝(ba)x+a。第10頁，課件共47頁，創(chuàng)作于2023年2月例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)對于任意的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是滿射的。由等勢定義得P(A)≈{0,1}A。例8.10證明復(fù)習(xí)第11頁，課件共47頁，創(chuàng)作于2023年2月定理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。等勢的性質(zhì)證明第12頁，課件共47頁，創(chuàng)作于2023年2月

N≈Z≈Q≈N×NR≈[0,1]≈(0,1)任何的實數(shù)區(qū)間（開區(qū)間、閉區(qū)間以及半開半閉的區(qū)間）都與實數(shù)集合R等勢。問題：N和R是否等勢？若干等勢集合第13頁，課件共47頁，創(chuàng)作于2023年2月（1）如果能證明N[0,1]，就可以斷定NR。

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

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

康托定理（1）NR。（2）對任意集合A都有AP(A)?？低卸ɡ怼帧帧帧址治龅?4頁，課件共47頁，創(chuàng)作于2023年2月（1）首先規(guī)定[0,1]中數(shù)的表示。

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

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

設(shè)f:N→[0,1]是從N到[0,1]的任何一個函數(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與上面列出的任何一個函數(shù)值都不相等。 即f不是滿射的。

所以，NR?？低卸ɡ怼值?5頁，課件共47頁，創(chuàng)作于2023年2月康托定理假設(shè)A≈P(A)，則必有函數(shù)f:A→P(A)是雙射函數(shù)。 如下構(gòu)造集合B：

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

可知

B∈P(A)。

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

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

若bB，則bf(b)，于是由B的定義知，b∈B，矛盾。第16頁，課件共47頁，創(chuàng)作于2023年2月（2）設(shè)g：A→P(A)是從A到P(A)的任意函數(shù)，如下構(gòu)造集合B：

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

則B∈P(A)。

但是對任意x∈A，都有

x∈B

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

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

≈≈第17頁，課件共47頁，創(chuàng)作于2023年2月定義8.9（1）設(shè)A,B是集合，如果存在從A到B的單射函數(shù)，就稱B優(yōu)勢于A，記作A≤·B。如果B不是優(yōu)勢于A，則記作A≤·B。（2）設(shè)A,B是集合，若A≤·B且AB，則稱B真優(yōu)勢于A，記作A＜·B。如果B不是真優(yōu)勢于A，則記作A≮·B。例如：N≤·

NN≤·

RA≤·

P(A)N＜·RA＜·

P(A)R≮·

N

N≮·

N優(yōu)勢≈R≤·N第18頁，課件共47頁，創(chuàng)作于2023年2月定理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)勢的性質(zhì)說明該定理為證明集合之間的等勢提供了有力的工具。構(gòu)造兩個單射f：AB和g：BA函數(shù)容易集合等勢。第19頁，課件共47頁，創(chuàng)作于2023年2月例題例題：證明[0,1]與(0,1)等勢。證明：構(gòu)造兩個單射函數(shù)f:(0,1)→[0,1]，f(x)＝xg:[0,1]→(0,1)，g(x)＝x/2+1/4第20頁，課件共47頁，創(chuàng)作于2023年2月證明{0,1}N≈[0,1)(1)設(shè)x[0,1)，0.x1x2…是x的二進制表示。為了使表示唯一，規(guī)定表示式中不允許出現(xiàn)連續(xù)無數(shù)個1。例如x＝0.1010111，應(yīng)按規(guī)定記為0.1011000。

對于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…，則對應(yīng)于x的函數(shù)tx是： n 01234567… tx(n) 10110100…易見tx∈{0,1}N，且對于x,y∈[0,1)，x≠y，必有tx≠ty，

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

第21頁，課件共47頁，創(chuàng)作于2023年2月(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的十進制表示。 例如t1，t2∈{0,1}N，且g(t1)＝0.0111…，g(t2)＝0.1000…， 若將g(t1)和g(t2)都看成二進制表示，則g(t1)＝g(t2)； 但若看成十進制表示，則g(t1)≠g(t2)。

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

根據(jù)定理9.3，有{0,1}N≈[0,1)。證明{0,1}N≈[0,1)第22頁，課件共47頁，創(chuàng)作于2023年2月總結(jié)N≈Z≈Q≈N×NR≈[a,b]≈(c,d)≈{0,1}N≈P(N) 其中[a,b]，(c,d)代表任意的實數(shù)閉區(qū)間和開區(qū)間。{0,1}A≈P(A)N＜·RA＜·

P(A)第23頁，課件共47頁，創(chuàng)作于2023年2月8.3.2集合的基數(shù)

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

a+=a∪{a}。

例

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

=∪{}={}

++

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

+++

={,{}}+={,{}}∪{{,{}}}={,{},{,{}}}={,+,++}后繼

說明前邊的集合都是后邊集合的元素。前邊的集合都是后邊集合的子集。第25頁，課件共47頁，創(chuàng)作于2023年2月利用后繼的性質(zhì)，可以考慮以構(gòu)造性的方法用集合來給出自然數(shù)的定義，即 0= 1=0+＝+＝{}＝{0} 2=1+＝{}+＝{}∪{{}}＝{,{}}＝{0,1} 3＝2+＝{,{}}+＝{,{},{,{}}}＝{0,1,2}

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

這種定義沒有概括出自然數(shù)的共同特征。第26頁，課件共47頁，創(chuàng)作于2023年2月定義8.11設(shè)A為集合，如果滿足下面的兩個條件：（1）∈A（2）a(a∈A→a+∈A)稱A是歸納集。例如：下面的集合 {,+,++,+++,…} {,+,++,+++,…,a,a+,a++,a+++,…}

都是歸納集。歸納集第27頁，課件共47頁，創(chuàng)作于2023年2月定義8.12自然數(shù)（1）一個自然數(shù)n是屬于每一個歸納集的集合。（2）自然數(shù)集N是所有歸納集的交集。說明：根據(jù)定義8.12得到的自然數(shù)集

N恰好由,+,++,

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

例如：自然數(shù)都是集合，集合的運算對自然數(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的定義

第28頁，課件共47頁，創(chuàng)作于2023年2月 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>}舉例

第29頁，課件共47頁，創(chuàng)作于2023年2月（1） 對任何自然數(shù)n，有n≈n。（2） 對任何自然數(shù)n,m，若m

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

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

m∈n，m≈n，n∈m

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

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

m≈n

m<

n

m∈n

自然數(shù)的性質(zhì)

第30頁，課件共47頁，創(chuàng)作于2023年2月定義8.13

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

因為沒有自然數(shù)與N和R等勢。任何有窮集只與唯一的自然數(shù)等勢。說明有窮集和無窮集

第31頁，課件共47頁，創(chuàng)作于2023年2月定義8.14（1）對于有窮集合A，稱與A等勢的那個唯一的自然數(shù)為A的基數(shù)，記作cardA，即cardA＝

n

A≈n

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

基數(shù)(cardinality)

第32頁，課件共47頁，創(chuàng)作于2023年2月定義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<說明：集合的基數(shù)就是集合的勢，基數(shù)越大，勢就越大?；鶖?shù)的相等和大小

第33頁，課件共47頁，創(chuàng)作于2023年2月關(guān)于基數(shù)的說明

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

cardP(A)，這說明不存在最大的基數(shù)。將已知的基數(shù)按從小到大的順序排列就得到： 0,1,2,…,n,…,0,,…0,1,2…,n,…是全體自然數(shù)，是有窮基數(shù)。0,,…是無窮基數(shù)。0是最小的無窮基數(shù)，后面還有更大的基數(shù)，如 cardP(R)等。第34頁，課件共47頁，創(chuàng)作于2023年2月可數(shù)集定義8.16

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

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

對于任何的可數(shù)集，都可以找到一個“數(shù)遍”集合中全體元素的順序。回顧前邊的可數(shù)集，特別是無窮可數(shù)集，都是用這種方法來證明的。說明第35頁，課件共47頁，創(chuàng)作于2023年2月（1）可數(shù)集的任何子集都是可數(shù)集。

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

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

第36頁，課件共47頁，創(chuàng)作于2023年2月例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第37頁，課件共47頁，創(chuàng)作于2023年2月方法一由cardA＝0，cardB＝n，可知A,B都是可數(shù)集。令A(yù)={a0,a1,

a2,…}，B={b0,

b1,

b2,…,

bn1}。對任意的<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。第38頁，課件共47頁，創(chuàng)作于2023年2月例8.12方法二因為cardA＝0，cardB＝n，所以A,B都是可數(shù)集。根據(jù)性質(zhì)（3）可知，A×B也是可數(shù)集，所以，

cardA×B≤0

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

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

0第39頁，課件共47頁，創(chuàng)作于2023年2月本章主要內(nèi)容集合等勢的定義等勢的性質(zhì)集合優(yōu)勢的定義優(yōu)勢的性質(zhì)重要的集合等勢以及優(yōu)勢的結(jié)果自然數(shù)及其自然數(shù)集合的定義可數(shù)集與不可數(shù)集集合的基數(shù)

第40頁，課件共47頁，創(chuàng)作于2023年2月本章學(xué)習(xí)要求能夠證明兩個集合等勢。能夠證明一個集合優(yōu)勢于另一個集合。知道什么是可數(shù)集與不可數(shù)集。會求一個簡單集合的基數(shù)。

第41頁，課件共47頁，創(chuàng)作于2023年2月等勢的證明方法證明集合A與B等勢的方法直接構(gòu)造從A到B的雙射函數(shù)f 需要證明f的滿射性和f的單射性。構(gòu)造兩個單射函數(shù)f：AB和g：BA。給出函數(shù)f和g，證明f和g的單射性。利用等勢的傳遞性直接計算A與B的基數(shù)，得到cardA＝cardB。證明集合A與自然數(shù)集合N等勢的方法找到一個“數(shù)遍”A中元素的順序。第42頁，課件共47頁，創(chuàng)作于2023年2月例題選講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）因為7與109互素，card(A∩B)＝{n7109|nN}，與（1）類似得到card(A∩B)＝0。解答第43頁，課件共47頁，創(chuàng)作于2023年2月例題選講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。解答第44頁，課件共47頁，創(chuàng)作于2023年2月復(fù)習(xí)—特征函數(shù)設(shè)A為集合，對于任意的AA，A的特征函數(shù)A

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