計算機數學4 -2逆函數和復合函數

4-2逆函數和復合函數

定理：設x和丫為有限集，若x和用勺元素個數相等即因=0

貝曠:xfy是入射的。焦?jié)M射的

證明見課本。

4-2.逆函數和復合函數

f：xry函數.H:x->y關系，序偶集合H=｛卜,川工ex,昨斗

TR，=｛｛y,切3,加及｝但卜,力6/工〉仇“Wf)

簡單地把r中序偶顛倒｛3㈤|卜/〉e丹不一定還是函數！

cy.定義域不一定是上

yGy對應X未必V函數九/c未必是函數

1.定義:只有當/是雙射函數時/是/的逆函數，記作TL稱/是可逆的.

定理：/：x-丫是一雙射函數,貝曠t也是雙射函數.

4-2逆函數和復合函數

證：a)/t是一函數。b)/f是雙射。

即dom/匚丫。每仔￡匕三！x使f~\y)=xQ

???/是雙射，，魚滿射。Ranf=X即對每一個歹￡丫者Bm一個r￡彳使得/(打二7

f~l^x)\f(x)=y}domf~x=Y

???/是雙射，...娓入射。.?對不同的玉，/有/(*)±/('2)

若對于歹￡培不/何睡得f1(y)=x\?f~x(y)=x2

而玉。工2?，/(%1)。/(工2)，弘W%矛盾。

是函數。

b)/t是滿射的=domf=X

/T是入射。對不同的凹，”￡丫必有尸。尸尸。2)。否則若項=、2貝I」。

/(%)=/(工2)

4-2逆函數和復合函數

???歹尸〉仔盾。是雙射函數。

例：N={1,2,3}5={a,b,c}.f\Af8J={{1,〃)(2,c)(3,0}則f題射的。

尸={@1)&2)伽3施是雙射。

但若8={。，4。/)(3肉},環(huán)是雙射，則gT不存在。

2.復合函數

?/二|上加eX,zwZ?)(丁eY^f(x)=y^g(y)=zj

定義:/:X—KgM—Z./(X)&邛則g

稱g?J%g在/的左邊可復合。

定理:g?/是一個函數。

證：a).g?/的定義域為X。即對歹￡丫使得

(x,y)e/,y=/(x)又y=/(x)G/(X)cFT,/.3!zGZ

使得〈y,z〉wg,g(y)=z.\<x,z>eg?/,故do加(g?/)=X.

4-2逆函數和復合函數

b).假設x對應4/2,4WZ2.<X，4〉，<x,z2>g?f.:.3y{>%￡丫使得

e

<x,乂/,v?,丁2>/，vX，Ni>eg.<y2.z2>eg.

?*-yi=/(?),=/(x)=>yi=y2

而/是函數「.yi=/(x),、2=/(x),=>yi=y2

g是函數「.g(M)=Ni，g(>2)=22=Z1=22矛盾.是函數

特別地，當Y二W時即「.XTY,g：y-Z時，則g?/稱為復合函數，或g對f的左復合。

g?危XfZ的函數g?/(x)=z,g?/(x)=g(/(x)).

例：X=(x19x2,x3},y={y1,y2},Z={z1,z2}.

f:X->Y,f={(xl,yl)(x2心&,%)}.

2遭={(必，4〉32,22?

4-2逆函數和復合函數

{(M,Z])(％2，Z2X%3，Z2)}=g?

可從圖形上得到.

b)若g和f是入射的，則g?/是入射的。

c)若g和f是雙射的，則g?雙射的。

--z.

對VzeZ由g*氤Rey,g(y)=zX/?茜HxeJV,/(x)=y.g?力茜

4-2逆函數和復合函數

4.多個函數復合y,g：y-z,〃:z一附則〃?他?/)是工g,〃的復合函數.

有性質：力復合函數滿足結合律。(與關系合成一樣)

5.(1)常函數定義必:XT匕若力oe匕使對于每個xeX,都有了(x)=%，則稱/是一常函數.

(2)恒等函數定義八={(x,x)|xeX}恒等關系，則稱乙為XfX的恒等函數.(即/(x)=x)

定理:貝獷=/"x=/「f

f=/?右如何證明：

1有相同的定義域X

2VxeX,彭(x)=丫4.乙(幻=fQx('))=fM=V有本目同的象「./=/?/丫.

上節(jié)課我們學習了函數。/:X-y一個特殊的關系VxeX都有：歹￡Y使<X/〉￡/;

f是雙射.L也是雙射；/：x—匕g：y.z則g?f：XTz的復合函數。

i》：xtx<x,x>"x.恒等函如:xfy.有7?ix=f=iy?/；還有如下定理

1淀理若f:XTFt逆函數,.廣：YT卯財T?/=/,,/?尸=>

4-2逆函數和復合函數

證：。)定義域相同：/：》-＞匕廣1：丫f＞則廣1?7/—工乙：丫一入.

b)1x(%)=%J:Xf/(x)JT:/(x)T%???(/—1/)(%)=fT(/(x))="

???廣?/=/工同理可得產?/=4。

4-2逆函數和復合函數

arI°T均存在了Ty-X,.,./TogT：ZfX

J，(5

g」：Zfy

go/:XfZ，(g。/)—1:ZfX定義域相同共域

bVZEZ,3J；GFf吏gT(z)=y或者g(y)=z

3xEX^-\y)=x=y

(g°/)(%)=g(f(x))=g(y)=z(g。/尸(z)=x

1111

(/°gT)(Z)=f-(y)=X-.f-og-=(goy)-

4-4基數的概念

注意:當廠看不存在時，此式不成立，但可能是復合后有逆函數存在

4-4,基數的概念

1.等勢.A,B兩集合，若存在A->B的雙射函數f,即A和B的元素兩兩成對，則稱A和B

的元素一一對應.

若A和B中元素一一對應，則稱A和B是等勢的(或同濃的)記作A?B

例:N={0,1,2,3,…}M={0,2,4,6,....}

f:N->MVxeN,f(x)=2x,f是一雙射函數，.二所以N~M

R：實數集S=(0,1)f:R->S,f{x}=-arctgx+-f是一雙射函數

712

所以R~S

SuK說明對無限集來說，集合可與其某一真子集等勢.這對有限集是不可

能的，這是它們的本質區(qū)別。

4-4基數的概念

定理.等勢關系是集合族中的一個等價關系.

證：S是集合族.則

a）/￡S則A?A

b）若A?B則//：雙射,，廣4雙射,二?B~A

C）若A~B,B~C則/：4-5雙射，g：BfC雙射「.g。/：%-C

雙射/.A~CJ■是等價關系?有了等勢關系后可將集合族中集合

按是否等勢分類：分為有限，無限集

2.有限集、無限集，集A若三%，使得從｛0,1,2,……n-1｝到A有一個

雙射函數，則稱集合A為有限集合，且閡=〃否則

稱A是無限集.（不存在n,使它們兩集合---對應）.

4-4基數的概念

定理：N是自然數集，則N是無限集。

證：任取一個n,{0,1,2，…n-1}建立任意f：{0,1,2,……n-1}到N的函數

貝獷(0),/(1)…f(n-1)GN^k=1+imx{/(0),/(I),-

則左eN,且Vxe{0,1,2……，〃―1}

.?./不可能是雙射函數。由〃J均是任意,.?.找不到”,任何{0,1,…,nF

到N有雙射，所以N是無限的.

有限集0{〃},{/處N無限集.

012

3.基數

定義度量集合大小的數稱為基數.如集合A,其基數記作K[Z]o〃M也稱4的勢

4-4基數的概念

力有限集，血使｛0,1,…〃-1｝與/等勢，則〃是義的基數刀是4中元素個數

K[/]=/=〃

而無限集就不是這么簡單.但至少有:A和B等勢，則f3雙射，因此A,B基數相等.

K[A]=K[B]

例:[0,1]與(0,1)有相同的基數

MA=[0A]B=(0,1)分析：4比5多了兩個

數0,1,而｛0,1,2,3,……｝,｛2,3,4,……｝等勢.類

似地找兩個集.將A分為兩個子集.取4=｛0

X

4-4基數的概念

｝貝忸［5A-A^B-3

「：A1B，

r（o）=1rd）=1八I1IcI

0—>一A—>一,2—>一是雙射

2nn+2〃+2

而對—4―>B-B，：x―x

擴充到/fB

F:A?B

產(0)=；

1

n+2

xE.A.—A

4-5可數集與不可數集

則F是雙射。所以A?B。

若/為無限集，K[如如何比較？并非所有無限集均與N等勢。

N一無限集。定義K[N]=S0.一阿里夫零4物〃0,任一無N,則

但并非所有無限集均與N等勢。N={0,1,2,3,……}可以數下去。

4-5可數集與不可數集

定義：與N等勢的任意集合均稱為可數的。/函數，則K[/]=S0

例.A二{0,2,4,6,……}A?N2n

B={1,3,5,……}B~N2n-1可數集與有限集，稱為至多可數集。

C二{0,1,4,9,25,……}C~Nri?

N可按次序排列A?N則A也是可數

定理A是可數集=A={%,出，……an……}A中元素可依次編號排列

4-5可數集與不可數集芯

證:n若/可數，則A?N

手：Nf4雙射。/(O)=qJ⑴=%,……/(〃)=%……則4={q,出，

a

……n……}=4={%,仁……an……}

貝心一1一arlJ/:N-4雙射則/I可數。

定理：A是可數集，A中的任意無限子集也是可數集。

4-5可數集與不可數集

證：A={ax,%,....,an),設3三N且B是無限的。

從4開始，將不是B中的元素刪去，得

}=AB可數。

定理：可數個兩兩不相交的可數集合的并集合仍是可數集。

證：設可數個可數集為

OO

=S]US2US3U???=s

k=\

4-5可數集與不可數集

則將s中的元素排列如下:

足碼之和相等,S可數。

N可數，/整數集，/=

1_?N,7_可數，「./?W可數o

注：有限個可數集的并仍是可數集（不必互不相交）或至多可數個可數集的并是

可數集。

4-5可數集與不可數集

定理：N自然數集，則NXN也是可數集。

證：NxN=￡N},可由下列可數個可數集并得:

S[={<0,0><0,1><0,2><0,3

S?={<1,0><1,1><1,2><1,3

S3={<2,0〉<2,1><2,2><2,3

8

NxN=?數個，NxN可數。

（比書上的簡單，均應用了重要的定理*）

4-5可數集與不可數集

定理：有理數集Q是可數集。

所有有理數可寫成既約分數形式

證：Q={土_w互質}

m

而。+={—w互質bQ~={——w互質）

mm

N乂N—{<m^n>\m^neN}可數，

S={vm,〃>w互質，m,〃仁N}=NxN}無限子集

「.S可教。

建立fd.〈m,ri），/:Q+fS雙射，「.Q+可數。

n

從而。一可數=>Q可數。

4-5可數集與不可數集毆

上次課我們介紹了兩集合等勢，A?B而A與B之間存在雙射，A與B

一一對應，A,B有相同的基數，把所有集合構成一集合S,等勢關

系是一等價關系，將之分類，同一類中K[A]=K[B]。A有限時A?{0,

1,.......,n-1},即K[A]=n。

把所有與N等勢的集合均稱為可數集，K[N]=So

可數集的性質:A為可數集=/=也介必，…}

可數集的無限子基可數；至多可數個可數集的并是可數集；

NN可數；Q可數；并可得/=/+1^_1^0}為可數集。

???到現(xiàn)在為止，可數集介紹了N"+,,Q」,。和NxN

4-5可數集與不可數集

今天我們繼續(xù)討論無限集的性質。

定理：任一無限集都含有可數子集。

證：/無限則/W取巧w/,貝無限，

3a2GA-{a1}9則/一{/,電}無限。依次取4，%，%

定理：任一無限集必與其某一真子集等勢。無限集的本質特征

證：/無限，一.三/的可數子集/'={ax,4/2,—A\

取■=/—{%}u/。

r

下證/?Af,fzAM,B=A—A,M—{a2.a3

f，a)—%+i，丸=1,2,

了./是雙身寸，A-Mo

f(x)=JV,XGB

4-5可數集與不可數集]

對有限集不可能有此性質，因此可能將此性質作為無限集的定義。

如：火=(—8,+8),RQU，J1L=(0,1),火?(0,1)=4U1，JL

對于有限集無此性質，必須是無限集。

已知K[N]=S。，K[I]=50,K[Q]=50,對于RK[R]=?

定義：不可數的無限集合稱為不可數集，即不能與N等勢的集合

定理：實數集R是不可數的。

4-5可數集與不可數集

證：已知火?只要證明(0,1)不可數即可■■是不是用數

/.用反證法：假設(0,1)是可數的.(。,1)={41，。2,

d20?CL

則4與％1不同也與口22不同

/.b與a、,a2,a3―'個分量不同)

「.b信{4,。2,%,^^^^>0,1)與(0,1)是可數的矛盾.?.(0,1)是不可數的

從而火不可數.

4-5可數集與不可數集

將R的基數記為S,K[R]=S,也稱連續(xù)系統(tǒng)的勢。因而我們可知全

體無理數集是不可數集。

如何比較兩集合的基數？4-6基數的比較。

A?B,K[A]=K[B],要找出f：雙射函數往往比較困難，介紹

另一種方法。

定義：集合A和B,若存在A-B入射函數f,則稱A的基數不大于B

的基數，記作K[A]WK[B]。

若存在f：』B入射，但不存在g：A-B雙射，則稱A的基數小于

B的基數，記作K[A]vK[B]。

定理(Zermelo定理)A和B是集合，則下面三者恰有一個成立：

a)K[A]<K[B],b)K[B]<K[A],c)K[A]=K[B]o

證明比較困難，即任兩個集合是可以比較大小的。

4-5可數集與不可數集毆

定理（Cantor-Schroder-Bernstein定理）A,B是集合，若

K[A]<K[B],且K[B]0K[A],則K[A]=K[B]。（反對稱性）

為證明兩個集合的基數相等提供了有效的方法。

找入射函數，f：A-B,則K[A]WK[B],找g：B—A,K[B]<K[A],

入射比雙射容易找到降低了要求。

4-5可數集與不可數集

例：[0,1]與(0,1)有相同的基數直接按雙射切分困難

證：一[0,1]

VxG(0,1)/(x)=x程入射

.-.M(o9i)]<M[o9i]]

一(0,1)

JV=；1

V[0,1]g(x)JC-1-------

4

13

[0,1]一]]?三人易寸

44

.?gl]?(0,1)

從而左1)]=左([O,口)

4-5可數集與不可數集盟

例：/=NB=(0,1)K[A]=So,K[B]=S,求證：K[Ax6]=S

證：a)K[AxB]<S

?j=(o,+oo)

f:AxBfR+

/(V〃，X>)=〃+X,〃￡N,XG(0,1)

/是入射函數K[AxB]<K[R+]=S

s,g：(0,1)->/x/

g(x)=v0,x>eAxB

/.g是入射,S=40,1]<k[AXB]故K[/xB]=S

由上述定理，可知46兩集合，若有/:/->/入射，g:5f/入射，

則一定存在/T/的雙射函數

4-5可數集與不可數集

有限集合N可數集/實數集火

K[A]=nK[N]=S@K[R]=S

這三者之間有何關系？

定理：N是有限集，則K[N]vS°vS

證：a)N是有限集,三小/?{0,1,........,n-l}

f：{0,1,........，"-l}fN入射

/.^[{0,1,……,n-l}]<=S。，即K[N]4S°

要證K[N]wS0,K[N]=So,而N與N之間不存在雙射函數.二.K[A]wK[N]

則K[N]<So

b)S0=K[N],S=K[尺]=K([0,1])

g：Nf[。,1],g(“)=入射.S<S

n+1o

又[0,1]?尺[0,1]不可數的」.[0,口子N

/.K[(0,1)]wK[W]S=S0

所以，SovS

定理告訴我們，任一有限集的基數<S°,可數集基數<不可數集基數

那么無限集中，基數有無min/max?

4-5可數集與不可數集

定理：力是無限集，則K