JHY-第五章-函數(shù)省名師優(yōu)質(zhì)課賽課獲獎?wù)n件市賽課一等獎?wù)n件

第五章函數(shù)

主講人：姜慧研

東北大學(xué)軟件學(xué)院多媒體醫(yī)療信息處理研究室

E-mail:

hyjiang@

第1頁第五章函數(shù)

函數(shù)是一個基本數(shù)學(xué)概念，應(yīng)用范圍很廣，在計(jì)算機(jī)科學(xué)理論中，如計(jì)算理論、開關(guān)理論、編譯理論、數(shù)據(jù)庫理論、軟件工程、計(jì)算機(jī)安全保密，操作系統(tǒng)等都用到函數(shù)。函數(shù)---輸入和輸出間關(guān)系。也叫變換、映射。比如：編譯源程序目標(biāo)代碼自動售貨機(jī)硬幣商品

本章主要介紹函數(shù)概念、函數(shù)復(fù)合、逆函數(shù)，以及在集合基數(shù)中應(yīng)用。含有分析、使用函數(shù)能力在很多領(lǐng)域都是十分主要。第2頁25-1函數(shù)基本概念一.概念1.定義：X與Y集合，f是從X到Y(jié)關(guān)系，假如任何x∈X，都存在唯一y∈Y，使得<x,y>∈f,則稱f是從X到Y(jié)函數(shù)，

1。2。。1。2。。1。2。。1。2。。3333R2R1R3R4

假如f:X

X是函數(shù),也稱f是X上函數(shù).下面給出A={1,2,3}上幾個關(guān)系，哪些是A到A函數(shù)？f

(變換、映射)，記作f:XY,或XY.第3頁3

下面是大家熟悉實(shí)數(shù)集合R上幾個關(guān)系，哪些是R到R函數(shù)？

可見這里所說函數(shù)與以前數(shù)學(xué)中函數(shù)有區(qū)分。2.自變元與函數(shù)值(像源與映像)：f:XY,假如<x,y>∈f,稱x是自變元(像源)，稱y是x函數(shù)值(x映像)。<x,y>∈f

y=f(x)

f:xy__1xf={<x,y>|x,y∈R∧y=}g={<x,y>|x,y∈R∧x2+y2=4}h={<x,y>|x,y∈R∧y=x2}r={<x,y>|x,y∈R∧y=lgx}v={<x,y>|x,y∈R∧y=}第4頁43.定義域、值域和陪域(共域)

：f:XY,

1).f定義域(domain)，記作domf，或Df即

Df=domf={x|x∈X∧y(y∈Y∧<x,y>

f)}=X

2).f值域(range)：記作ranf，或Rf

即或f(X)Rf=ranf=f(X)={y|y∈Y∧x(x∈X∧<x,y>

f)}

(假如AX定義集合f(A)以下：

f(A)={y|y∈Y∧x(x∈A∧<x,y>

f)})

AXYff(A)前面例中Rh=ranh=h(R)=R+,R+是非負(fù)實(shí)數(shù)。

3).f陪域(codomain):即是Y稱之為f陪域。二.函數(shù)表示方法同關(guān)系表示方法，也能夠有：枚舉法、有向圖、矩陣、謂詞描述法。這里不再贅述。函數(shù)矩陣特點(diǎn)：每行必有且只有一個1。第5頁5三.從X到Y(jié)函數(shù)集合YX：

YX={f|f:XY}YX：它是由全部從X到Y(jié)函數(shù)組成集合

例X={1,2,3}Y={a,b}全部從X到Y(jié)函數(shù):

f1X

Y。。。。。123abX

Yf2。。。。。123abX

Yf3。。。。。123abX

Yf4。。。。。123abX

Yf5。。。。。123abX

Yf6。。。。。123abX

Yf7。。。。。123abf8X

Y。。。。。123abYX={f1,f2,f3,f4,f5,f6,f7,f8}假如X和Y是有限集合，|X|=m,|Y|=n,因?yàn)閄中每個元素對應(yīng)函數(shù)值都有n種選擇，于是可組成nm個不一樣函數(shù)，所以|YX|=|Y||X|=nm,可見符號YX

有雙重含義.第6頁6四.特殊函數(shù)

1.常值函數(shù)：函數(shù)f:XY，假如

y0∈Y,使得對

x∈X,有f(x)=y0,即ranf={y0},稱f是常值函數(shù)。如上例f1和f8。

2.恒等函數(shù)：恒等關(guān)系IX是X到X函數(shù)，即IX:XX,稱之為恒等函數(shù)。顯然對于x∈X，有IX(x)=x。五.兩個函數(shù)相等設(shè)有兩個函數(shù)f:ABg:CD,f=g當(dāng)且僅當(dāng)A=C，B=D，且對任何x∈A，有f(x)=g(x)。

即它們定義域相等、陪域相等、對應(yīng)規(guī)律相同。六.函數(shù)類型先看下面例子：

X1

Y。。。。。123ab。csX

Y。。。。。123ab4。。cgX1

Y1。。。。。123abd。。chX

Y。。。。。123ab4。。cfRf=YRs=YRgYRhY1一對一一對一第7頁71.滿射：f:XY是函數(shù)，假如Rf=Y,則稱f是滿射。2.映內(nèi)：f:XY是函數(shù)，假如RfY則稱f是映內(nèi)。3.入射：f:XY是函數(shù)，假如對于任何x1,x2∈X,假如

x1≠x2

有f(x1)≠f(x2),(或者若f(x1)=f(x2),則x1=x2),則稱

f是入射，也稱f是單射，也稱f是一對一。4.雙射：f:XY是函數(shù)，假如f既是滿射，又是入射，則稱f是雙射，也稱f是一一對應(yīng)。y=ax+by=x2y=2x雙射映內(nèi)映內(nèi)入射思索題：假如

f:XX是入射函數(shù)，則必是滿射，所以f也是雙射。此命題成立嗎？第8頁8

答案是：不一定。比如f:NN,f(n)=2n,f是入射，但不是滿射函數(shù)。只有當(dāng)X是有限集合時，上述命題才成立。本節(jié)重點(diǎn)掌握：函數(shù)定義、函數(shù)類型判定和證實(shí)。

1.證實(shí)f:XY是滿射：任取y∈Y，推出存在x∈X，使得y=f(x)。

2.證實(shí)f:XY是入射：方法1：任取x1,x2∈X,設(shè)x1≠x2,推出f(x1)≠f(x2)。方法2：任取x1,x2∈X,設(shè)f(x1)=f(x2),推出x1=x2。作業(yè)第151頁(1),(3),(5),(6)第9頁95-2函數(shù)復(fù)合

因?yàn)楹瘮?shù)就是關(guān)系，所以也能夠進(jìn)行復(fù)合運(yùn)算。下面先回顧關(guān)系復(fù)合。設(shè)是R從X到Y(jié)關(guān)系，S是從Y到Z關(guān)系，則R和S復(fù)合關(guān)系記作R

S。定義為：

R

S={<x,z>|x

X

z

Z

y(y

Y

<x,y>

R

<y,z>

S)}一.定義:f:X

Y,g:Y

Z是函數(shù),則定義

g

f={<x,z>|x

X

z

Z

y(y

Y

<x,y>

f

<y,z>

g)}則稱g

f

為f與g復(fù)合函數(shù)(左復(fù)合).注意:這里把g寫在f左邊了.所以叫左復(fù)合.g

f:XZ,即g

f

是X到Z函數(shù).這么寫是為了照料數(shù)學(xué)習(xí)慣:g

f(x)=g(f(x))二.復(fù)合函數(shù)計(jì)算計(jì)算方法同復(fù)合關(guān)系計(jì)算.

但要注意是左復(fù)合.第10頁10

例f:X

Y,g:Y

ZX={1,2,3}Y={1,2,3,4,}Z={1,2,3,4,5,}f={<1,2>,<2,4>,<3,1>}g={<1,3>,<2,5>,<3,2>,<4,1>}g

f={<1,3>,<2,5>,<3,2>,<4,1>}

{<1,2>,<2,4>,<3,1>}。3。2。1。3。2。1。4XYZ。3。2。1。4。5。3。2。1。3。2。1。4。5XZg

ffg={,，}<1,5><2,1><3,3>用有向圖復(fù)合:第11頁11例令f和g都是實(shí)數(shù)集合R上函數(shù),以下:f={<x,y>|x,y∈R∧y=3x+1}g={<x,y>|x,y∈R∧y=x2+x}分別求g

f

、f

g、f

f

、g

g

g

f(x)=g(f(x))=(3x+1)2+(3x+1)=9x2+9x+2f

g(x)=f(g(x))=3(x2+x)

+1=3x2+3x+1f

f(x)=f(f(x))=3(3x+1)

+1=9x+4g

g(x)=g(g(x))=(x2+x)2+(x2+x)=x4+2x3+2x2+

x

可見復(fù)合運(yùn)算不滿足交換性。三.函數(shù)復(fù)合性質(zhì)1.定理5-2.1滿足可結(jié)合性。f:X

Y,g:Y

Z,h:Z

W是函數(shù),

則(h

g)

f=h

(g

f)。證實(shí)與關(guān)系復(fù)合可結(jié)合證實(shí)類似，這里從略。第12頁122.定理5-2.2f:X

Y,g:Y

Z是兩個函數(shù),則

⑴假如f和g是滿射，則g

f

也是滿射；

⑵假如f和g是入射，則g

f

也是入射；

⑶假如f和g是雙射，則g

f

也是雙射。證實(shí)：⑴設(shè)f和g是滿射，因g

f:XZ,任取z∈Z,因g:Y

Z是滿射，所以存在y∈Y,使得z=g(y),又因f:X

Y是滿射，所以存在x∈X,使得y=f(x),于是有z=g(y)=g(f(x))=g

f(x),所以g

f

是滿射。⑵設(shè)f和g是入射，因g

f:XZ,任取x1,x2∈X,x1≠x2因f:X

Y是入射，f(x1)≠f(x2),而f(x1),f(x2)∈Y，因g:Y

Z是入射，g(f(x1))≠g(f(x2))

即g

f(x1)≠g

f(x2)所以g

f

也是入射。

⑶由⑴⑵可得此結(jié)論。第13頁133.定理5-2.3⑴假如g

f

是滿射，則g是滿射；⑵假如gf

是入射，則f是入射；

⑶假如g

f

是雙射，則f是入射和g是滿射。此定理證實(shí)是作業(yè)題第156頁題(3)。4.定理5-2.4f:X

Y是函數(shù),則

f

IX=f且IY

f=f

。證實(shí)：先證實(shí)定義域、陪域相等。因?yàn)镮X:X

X，f:XY，∴f

IX:XY,IY

f:XY可見fIX、IY

f

與f含有相同定義域和陪域。再證它們對應(yīng)規(guī)律相同：任取x∈X，

f

IX(x)=f(IX(x))=f(x)IY

f(x)=IY(f(x))=f(x)所以fIX

=f且

IY

f=f

。第14頁145-3逆函數(shù)

R是A到B關(guān)系，其逆關(guān)系RC是B到A關(guān)系。

RC={<y,x>|<x,y>R}f:XYfC:YX,是否是個函數(shù)？請看下面例子：

。3。2。1。c。b。af:XY。3。2。1。c。b。afC:YX顯然fC不是函數(shù)?？梢娂偃缫粋€函數(shù)不是雙射，它逆就不是函數(shù)。一.定義：設(shè)f:XY是雙射函數(shù)，fC:YX也是函數(shù),稱之為f逆函數(shù)。并用f-1代替fC

。f-1存在，也稱f可逆。顯然，f-1也是雙射函數(shù)。第15頁15二.性質(zhì)1.定理5-3.1設(shè)f:XY是雙射函數(shù)，則(f-1)-1=f。結(jié)論顯然成立，證實(shí)從略。2.定理5-3.2設(shè)f:XY是雙射函數(shù)，則有

f-1

f=IX

且f

f-1=IY。證實(shí)：先證明定義域、陪域相等。因?yàn)閒:XY是雙射，f-1:YX也是雙射，所以

f-1

f:X

X,IX:X

X可見f-1

f與IX

含有相同定義域和陪域。再證它們對應(yīng)規(guī)律相同：

x∈X，因f:XY，yY,使得y=f(x),又f可逆，故f-1(y)=x，于是

f-1

f(x)=f-1(f(x))=f-1(y)=x=IX(x)

所以有f-1

f=IX

。同理可證

f

f-1

=IY。第16頁16可見f-1

f=IX

。3.定理5-3.3令f:X

Y,g:Y

X是兩個函數(shù),假如g

f=IX

且f

g=IY,則g=f-1

。證實(shí)：⑴證f和g都可逆。因?yàn)間

f=IX，IX是雙射，由關(guān)系復(fù)合性質(zhì)3得，f是入射和g是滿射。同理由

f

g=IY，得g是入射和f是滿射。所以f和g都可逆。

⑵顯然f-1和g含有相同定義域和陪域。X

Y。。。。。123ab。cf。。。123Xf-1。。。123X。。。123XIX下面看一個例子：第17頁17⑶證實(shí)它們對應(yīng)規(guī)律相同。任取yY，f-1(y)=f-1

IY(y)

=f-1

(f

g)

(y)

=(f-1

f)

g

(y)

=(

IX

g)

(y)=g(y)

所以f-1=g順便說明：f-1=g兩個條件必須同時滿足，缺一不可。比如

X

Y。。。。12ab。cf。。12Xg。。12X。。12XIX此例只滿足g

f=IX,

但f與g都非雙射，不可逆。4.定理5-3.4,令f:X

Y,g:Y

X是兩個雙射函數(shù),則

(g

f)-1=f-1

g-1此定理與關(guān)系復(fù)合求逆(R

S)C=SC

RC

類似，證實(shí)略。作業(yè)第156頁

(1),(3)c)，(5)(5)有誤，改成：….,則f是滿射而g是入射不一定成立。第18頁185-4集合特征函數(shù)與含糊子集一.集合特征函數(shù)以前學(xué)過集合A冪集P(A),下面是將A各個子集與函數(shù)(稱之為集合特征函數(shù))建立一一對應(yīng)關(guān)系.集合特征函數(shù)在含糊數(shù)學(xué)中有直接應(yīng)用。1.定義:令E是全集,A是E子集,定義函數(shù)

ψA:E{0,1}對任何x∈E,有{1x∈AψA(x)=

0xA稱ψA:E{0,1}是子集A特征函數(shù).下面以E={a,b,c}為例,看看E各個子集特征函數(shù)。第19頁19

個abcE{0,1}01ψΦabcE{0,1}01ψ{c}abcE{0,1}01ψabcE{0,1}01ψ{b,c}abcE{0,1}01ψ{a}abcE{0,1}01ψ{a,c}abcE{0,1}01ψ{a,b,c}abcE{0,1}01ψ{a,b}AψA(x)xΦ{c}{b,c}{a}{a,c}{a,b}{a,b,c}a00001111b00110011c01010101第20頁20用集合特征函數(shù)能夠進(jìn)行集合運(yùn)算和表示集合間關(guān)系.2.性質(zhì)令A(yù),B是全集E子集,1)A=Φx(ψA(x)=0)

abcE{0,1}01ψΦabcE{0,1}01ψ{a,b,c}xAxBxAxBψA(x)ψB(x))

ψA(x)≤ψB(x))

FFT00TFTT01TTFF10FTTT11T2)A=Ex(ψA(x)=1)3)ABx(ψA(x)≤ψB(x))

證實(shí):任取x∈E,從下表看出ABx(ψA(x)≤ψB(x))

第21頁214)A=Bx(ψA(x)=ψB(x))5)ABx(ψA(x)≤ψB(x))x(ψB(x)=1

ψA(x)=0)

6)ψA∩B(x)=ψA(x)ψB(x)證實(shí):任取x∈E

FFF00×0=0FTF00×1=0TFF01×0=0TTT11×1=1xAxBxA∩BψA∩B(x)

ψA(x)ψB(x)

TF101-1=0FT011-0=1x∈Ax∈~AψA(x)

Ψ~A(x)1-ψA(x)7)Ψ~A(x)=1-ψA(x)證實(shí):任取x∈E第22頁228).ψA∪B(x)=ψA(x)+ψB(x)-ψA∩B(x)證實(shí):任取x∈EFF0F00+0-0=0FT0T10+1-0=1TF0T11+0-0=1TT1T11+1-1=1xAxBψA∩B(x)xA∪BψA∪B(x)

ψA(x)+ψB(x))-ψA∩B(x)

所以ψA∪B(x)=ψA(x)+ψB(x)-ψA∩B(x)9)ψA-B(x)=ψA(x)-ψA∩B(x)證實(shí):任取x∈EψA-B(x)=ψA∩~B(x)=ψA(x)ψ~B(x)=ψA(x)(1-ψB(x))=ψA(x)-ψA(x)ψB(x)=ψA(x)-ψA∩B(x)第23頁23應(yīng)用上述公式能夠證實(shí)一些集合公式.比如證實(shí)吸收律:A∪(A∩B)=A證實(shí):任取x∈A,ψA∪(A∩B)(x)=ψA(x)+ψA∩B(x)-ψA∩(A∩B)(x)=ψA(x)+ψA∩B(x)-ψA∩B(x)=ψA(x)二.含糊子集

前邊討論集合是表示一個確定概念.即對任何元素a,要么a∈A,要么aA,是確定.而在實(shí)際生活中,許多概念是含糊,比如,青年人、老年人、涼、熱等都是含糊概念.比如普通認(rèn)為70歲以上是老年人,30歲以下不是老年人,那么,50歲是否老年人就沒有明確回答.對這些概念用以前集合論方法研究就不適用了.所以產(chǎn)生了含糊集合論.第24頁24

含糊集合論是美國學(xué)者L.A.Zaden(查德

)在1965年創(chuàng)建.含糊集合是含糊數(shù)學(xué)基礎(chǔ),含糊數(shù)學(xué)不是讓數(shù)學(xué)變成含糊東西,而是讓數(shù)學(xué)進(jìn)入含糊現(xiàn)象領(lǐng)域.含糊數(shù)學(xué)是借用數(shù)學(xué)工具,經(jīng)過模仿人類思維,描述和處理含糊概念.現(xiàn)在已經(jīng)有了含糊語言,含糊自動機(jī),含糊算法,含糊推理,含糊控制等,總之含糊數(shù)學(xué)已經(jīng)得到廣泛地應(yīng)用.下面介紹含糊集合基本概念.

1.定義:E是個論域,E上一個含糊子集是指:存在一個函數(shù),注意:第25頁25定義說明:

abcde例子.令E={,,,,}表示E中“圓形”含糊子集。表示E中“方形”含糊子集。它們隸屬函數(shù)以下:第26頁26

a1a0.4b0.8b0.3c0.4c1d0.2d0.2e0.1e0.1E[0,1]E[0,1]abcdeE={,,,,}2.

含糊子集表示方法

1).序偶集合表示2).用Zaden記號表示第27頁273).用有序n元組表示

502514).用函數(shù)表示式或曲線表示比如,以年紀(jì)為論域,E={0,1,2,3,…200},Zaden給出了“年老---”“年青---”兩個含糊子集隸屬函數(shù)表示為:第28頁283.含糊集合運(yùn)算

第29頁295-6集合基數(shù)本節(jié)主要借助于函數(shù)討論集合所謂“大小”問題。這里用到自然數(shù)集合這個主要概念。一.自然數(shù)怎樣給自然數(shù)定義，每個自然數(shù)n,就是個集合。

1.集合A后繼集合A+A是個集合，A后繼集合A+

為：

A+=A∪{A}比如:A:A+:Φ=00+=Φ∪{Φ}={Φ}=1={0}{Φ}=11+={Φ}∪{{Φ}}={Φ,{Φ}}=2={0,1}{Φ,{Φ}}=22+={Φ,{Φ}}∪{{Φ,{Φ}}}={Φ,{Φ},{Φ,{Φ}}}=3={0,1,2}

…...…...第30頁302.自然數(shù)集合N定義(Peano,皮亞諾公理)1).0∈N,這里0=Φ2).n∈N,則n+∈N,這里n+=n∪{n}

3).不存在

n∈N,使得n+=04).若n+=m+,則n=m

5).假如S

N，且⑴0∈S⑵n∈S,則n+∈S

則S=N。N極小性從此定義得n={0,1,2,3,…,n-1},所以有：0∈1∈2∈3∈…...

0

123……自然數(shù)這個定義，解釋了許多數(shù)學(xué)問題，是一個很準(zhǔn)確抽象。因?yàn)?,1,2,3,..本身就是個抽象概念。0是最小自然數(shù)后繼數(shù)唯一性第31頁31二.集合等勢比較兩個集合“大小”有兩種方法：

數(shù)集合中元素個數(shù)。這只適合用于有限集合?？磧蓚€集合元素間是否有一一對應(yīng)關(guān)系(雙射)。

這種方法既適合用于有限集合，也適用無限集合。1.定義：A、B是集合，假如存在雙射f:AB，則稱A與B等勢。記作A~B。例以下面集合間是等勢。

N={0,1,2,3,4,…...}A={0,2,4,6,8,…...}f:NA，f(x)=2xB={1,3,5,7,9,…...}g:NB，g(x)=2x+1C={1,10,100,1000,10000,…..}={100,10,102,103,104,,…...}h:NC，h(x)=10x第32頁322.集合間等勢關(guān)系“~”是個等價(jià)關(guān)系令S是個集合族(即“全部集合組成集合”)，在S上等勢關(guān)系~，滿足：⑴自反性：因?yàn)槿魏渭螦有雙射IA:AA,∴A~A⑵對稱性：任何集合A,B，若A~B，有雙射f:AB,

又有雙射f-1

:BA，所以B~A。⑶傳遞性：任何集合A,B,C，若A~B，且B~C，則有雙射f:AB,和雙射g:BC,由函數(shù)復(fù)合得雙射：

g

f:AC，所以A~C。所以~是等價(jià)關(guān)系。按照等勢關(guān)系“~”對集合族S進(jìn)行劃分，得到商集S/~，進(jìn)而得到基數(shù)類概念。第33頁33三.基數(shù)類和基數(shù)S/~={[0],[1],[2],[3],…,[N],[R],...}

任何集合A，必屬于且僅屬于一個等價(jià)類。如{a,b,0,1}[4],因?yàn)閧a,b,0,1}與4(即集合{0,1,2,3})等勢。偶數(shù)集合E={0,2,4,6,8,...}[N],因?yàn)镋~N.2.基數(shù)給定集合A，A所屬于基數(shù)類，稱之為A基數(shù)，記作K[A]。

如A={1,2},A[2],K[A]=[2],簡記成

K[A]=2

如B={a,b,c},B[3],K[B]=[3],簡記成

K[B]=3無元素1個元素2個元素3個元素可數(shù)集不可數(shù)集...1.基數(shù)類S是集合族，“~”是S上等勢關(guān)系，相對~等價(jià)類稱之為基數(shù)類。S={0,Φ,1,{1},{a},…,2,{1,2},{a,b},…,3,{1,2,3},…,N,I,…R,..}第34頁34采取這種簡單記法，使得對于有限集合A，K[A]=|A|。四.有限集合與無限集合定義:凡是和某個自然數(shù)n等勢集合，都稱之為有限集合；不然是無限集合。如A={a,b,c,d,e},A與5({0,1,2,3,4})等勢，故A是有限集。五.可數(shù)集合及其基數(shù)

1.自然數(shù)集合N基數(shù)因?yàn)镹不可能與某個自然數(shù)n等勢。所以N基數(shù)不能是有限數(shù)，就用一個“無限大”數(shù)

0(讀:阿列夫零)表示,即K[N]=0

。

2.可數(shù)集:與自然數(shù)集合N等勢集合，稱之為可數(shù)集。

A={0,2,4,6,8,…...}f:NAf(n)=2nB={1,3,5,7,9,…...}g:NBg(n)=2n+1C={100,10,102,103,104,,…...}h:NCh(n)=10n都是可數(shù)集合。第35頁353.可數(shù)集判定

定理5-6.1集合A是可數(shù)集，充分且必要條件是可將A元素寫成序列形式，即

A={a0,a1,a2,a3,...}證實(shí)過程很簡單，這里從略。因?yàn)檫@么A就能夠與N之間建立一一對應(yīng)。比如整數(shù)集合I~N、有理數(shù)集合Q~N。因?yàn)镮能夠?qū)懗桑篒={0,-1,1,-2,2,-3,3,-4,4,...}即可將I中元素從0開始按照箭頭指定次序排列：0123-1-2-3所以I是可數(shù)集。第36頁36因?yàn)槊總€有理數(shù)都能夠?qū)懗梢粋€分?jǐn)?shù)形式以下：能夠從0/1開始按照箭頭指定次序排列Q中元素(假如這個有理數(shù)在前面出現(xiàn)，就跳過去)，

0/11/12/13/1-1/1-2/1-3/1-1/2-2/2-3/20/21/22/23/20/31/32/33/3-1/3-2/3-3/3-1/4-2/4-3/40/41/42/43/4.............................................01223-1-1-2-2-34.至多可數(shù)集：有限集合和可數(shù)集統(tǒng)稱至多可數(shù)集。同理可證N×N~N另外I×I~N以及N×N~N

如右圖所表示。所以Q是可數(shù)集。1第37頁37六.不可數(shù)集合及其基數(shù)

1.實(shí)數(shù)軸上(0,1)區(qū)間中實(shí)數(shù)是不可數(shù)。證實(shí)：假設(shè)(0,1)是可數(shù)，則能夠?qū)⑺貙懗梢韵滦蛄行问剑簕x1,x2,x3,...},其中

xi=0.ai1ai2ai3……i=1,2,3,…..即0＜xi＜1aik∈{0,1,2,3,4,5,6,7,8,9}k=1,2,3,4,…令x1=0.a11a12a13a14…...x2=0.a21a22a23a24…...x3=0.a31a32a33a34…...………...xn=0.an1an2an3an4….....……..結(jié)構(gòu)一個數(shù)b=0.b1b2b3b4…bn……，其中

b1≠a11b2≠

a22b3≠a33…bn≠

ann...

于是

b≠x1,b≠x2,b≠x3...

b≠xn…∴b(0,1)產(chǎn)生矛盾，所以(0,1)是不可數(shù)。第38頁382.連續(xù)統(tǒng)基數(shù)

⑴(0,1)區(qū)間基數(shù)是一個比N基數(shù)

0更大無限大數(shù),用(阿列夫)表示。即>0

。

⑵

整個實(shí)數(shù)集合R~(0,1)證實(shí)：結(jié)構(gòu)函數(shù)f:(0,1)Rf(x)=tg(πx-π/2)

顯然f是雙射，所以R~(0,1).

⑶實(shí)數(shù)軸上任何一段連續(xù)區(qū)間(a,b)基數(shù)都是，所以稱之為連續(xù)統(tǒng)基數(shù)。3.計(jì)算公式⑴K[A1]=K[A2]=...=K[An]=,則

K[A1∪A2∪...∪An]=

⑵K[A]=K[B]=,則K[A×B

]=

01第39頁39⑶K[A]=

K[B]=

0,(或K[B]=n),(B是多可數(shù)集)則K[A－B

]=

七.基數(shù)比較

前邊討論基數(shù)相等是否問題,下面討論諸如和0哪個大問題,即所謂無限集合“次序”問題.

在比較兩個集合基數(shù)相等時,要看這兩個集合之間是否存在雙射,不過找雙射往往是個麻煩事,為了處理這個問題,提出下面定理.定理5-6.2

假如集合A到B存在入射函數(shù),則K[A]≤K[B].定理5-6.3(Zermelo定理)A和B是任何集合,則以下三條之一必有一個成立:a.)K[A]<K[B].b.)K[B]<K[A]c.)K[A]=K[B].第40頁40

定理5-6.4(Contor-Schroder-Bernstein定理)A和B是任何集合,假如K[A]≤K[B]且K[B]≤K[A]則K[A]=K[B].

這三個定理證實(shí)都超出我們范圍.

用這些定理對集合基數(shù)進(jìn)行比較.比如.證實(shí)[0,1]與(0,1)等勢.證實(shí):結(jié)構(gòu)兩個入射函數(shù):f:(0,1)[0,1]f(x)=x

因?yàn)閒和g都是入射,所以有K[(0,1)]≤K[[0,1]]且

K[[0,1]]≤K[(0,1)]

所以K[[0,1]]=K[(0,1)]g:[0,1](0,1)g(x)=第41頁41定理5-6.5

設(shè)A是有限集合,則K[A]<0<.證實(shí):令K[A]=n于是A~{0,1,2,…,n-1}=B顯然K[A]=K[B]結(jié)構(gòu)一個函數(shù)f:BN,f(x)=x顯然f是入射.所以K[B]≤K[N],另外N與B之間不可能存在雙射,所以K[B]≠K[N]所以K[B]<K[N],K[A]<0;所以

0≤,另外N與[0,1]之間不可能存在雙射,所以K[N]≠K[[0,1]]所以K[N]<K[[0,1]],即

0<所以最終得K[A]<0<.定理5-6.6

設(shè)A是無限集合,則0≤K[A]證實(shí):因A是無限集合,所以A必包含一個可數(shù)無限子集B,結(jié)構(gòu)函數(shù)f:BAf(x)=x顯然f是入射,故K[B]≤K[A],而K[B]=0,所以

0≤K[A]。

可見可數(shù)集合是“最小”無限集合.再結(jié)構(gòu)函數(shù)g:N[0,1]g(n)=,顯然g也是入射,第42頁42連續(xù)統(tǒng)假設(shè):

是大于0最小基數(shù),不存在集合A使得

0<K[A]<到當(dāng)前為止,該假設(shè)既沒有被證實(shí),也沒有被否定.不過有些人已證實(shí),依據(jù)現(xiàn)有公理系統(tǒng),既不能證實(shí)它是正確,也不能證實(shí)它是錯誤.本節(jié)主要了解自然數(shù)定義，集合等勢概念，基數(shù)概念，可數(shù)集合與不可數(shù)集合概念及它們基數(shù)。第43頁43本章小結(jié)：重點(diǎn)掌握內(nèi)容：函數(shù)概念、類型判斷和證實(shí)函數(shù)復(fù)合、求逆了解集合特征函數(shù)、*

Hashing函數(shù)了解集合基數(shù)概念、可數(shù)集概念第44頁44習(xí)題課P151(1).

判斷下面函數(shù)類型：a)f:II，f(j)=j(mod3)ranf={0,1,2}f(1)=f(4).映內(nèi)

b)f:NN，f(j)=ranf={0,1}f(1)=f(3).映內(nèi)c)f:N{0,1},f(j)=ranf={0,1}f(1)=f(3).滿射d)f:IN，f(i)=|2i|+1ranfNf(1)=f(-1).映內(nèi)e)f:RR，f(r)=2r-15ranf=R滿射

x,y∈Rx≠yf(x)≠f(y)入射，雙射

{1j是奇數(shù)0j是偶數(shù){1j是奇數(shù)0j是偶數(shù)第45頁45(2).令f:A

B,CA,證實(shí)f(A)－f(C)f(A－C)

假如CA定義集合f(C)以下：

f(C)={y|y∈B∧x(x∈C∧<x,y>

f)}CABff(C)yx第46頁46解.任取y∈f(A)－f(C)，則y∈f(A)－f(C)y∈f(A)yf(C)(y∈B∧x(x∈A∧<x,y>

f))(y∈B∧x(x∈C∧<x,y>

f))

(y∈B∧x(x∈A∧<x,y>

f))

(yBx(xC<x,y>

f))

F

(y∈B∧x(x∈A∧<x,y>

f)x(xC<x,y>

f))(y∈B∧x(x∈A∧<x,y>

f)x(xC<x,y>

f))

(y∈B∧(a∈A∧<a,y>

f)(aC<a,y>

f))(ES、US)

(y∈B∧(a∈A∧<a,y>

f)aC)Fy∈B∧(a∈AaC)∧<a,y>

f))

y∈B∧(a∈A-C∧<a,y>

f))

y∈B∧x(x∈A-C∧<x,y>

f)y∈f(A-C)

所以f(A)－f(C)f(A－C)第47頁47(3).設(shè)f和g是函數(shù)，fg,且domgdomf,證實(shí)f=g.證實(shí)：a)

先證實(shí)domg＝domf,(已知domgdomf,)(證domfdomg)任取x∈domf,因?yàn)閒是函數(shù),y∈ranf使得<x,y>∈f由fg,所以<x,y>∈g,所以x∈domg,故domfdomg。又已知domgdomf∴domg=domf.b)再證gf，任取<x,y>∈g，x∈domg,∵domg=domf∴x∈domf,y’∈ranf,使得<x,y’>∈f,由fg,又得<x,y’>∈g,因?yàn)間是函數(shù)y=y’,所以<x,y>∈f∴gf。又已知fg,所以最終得f=g.(5)(6).X和Y是有限集合，|X|=m|Y|=n從X到Y(jié)存在入射必要條件是什么？有多少個入射函數(shù)？從X到Y(jié)存在雙射必要條件是什么？有多少個雙射函數(shù)？解：從X到Y(jié)存在入射必要條件是：m≤n可有n(n-1)(n-2)…(n-m+1)個入射函數(shù)。第48頁48從X到Y(jié)存在雙射必要條件是:m＝n.可有n!個雙射函數(shù)。(8).

設(shè)f:AB是函數(shù)，定義函數(shù)G:BP(A),對于b∈B,G(b)={x|x∈A,f(x)=b}試證實(shí)，假如f是滿射，則G是入射。其逆成立嗎？先看一看函數(shù)G例子：證實(shí)：任取b1,b2∈B,b1≠b2,(要證出G(b1)≠G(b2))假設(shè)G(b1)＝G(b2)，因?yàn)閒:AB是滿射函數(shù)，所以存在a1,a2∈A,使得f(a1)=b1,f(a2)=b2，于是由G定義得a1∈G(b1),a2∈G(b2),而G(b1)＝G(b2)，∴a1∈G(b2),a2∈G(b1),于是由G定義得f(a1)=b2f(a2)=b1，而b1≠b2,與f是函數(shù)矛盾。所以G(b1)≠G(b2)，所以G是入射。

A

B。。。。。123abf。。Φ。。{1}{2}P(A)G。。{3}{1,2}。。{1,3}{2,3}{1,2,3}第49頁49其逆定理不一定真，請看下面反例。G是入射，但f不是滿射。P156(1).

設(shè)X={1,2,3,4},確定這么函數(shù)f:XX使得f≠IX,而且是入射，求