144144

离散数学电子教材4(总30页)

--本页仅作为文档封面，使用时请直接删除即可--

--内页可以根据需求调整合适字体及大小--

144144

第4章映射（函数）

映射（函数）是一个基本的数学概念，它是一个特殊的二元关系，我们可

以把映射看作输入输出关系，它把一个集合（输入集合）的元素变成另一个集

合（输出集合）的元素。例如，计算机中的程序可以把一定范围内的任一组数

据变化成另一组数据，它就是一个映射。

映射的概念经常出现在开关理论、自动机理论和可计算理论等领域中，在

计算机科学中有着广泛的应用。

映射（函数）的概念

考虑下面几个由图4-1所示的集合X到集合Y的关系。

图4-1

145145

在这６个关系中，后４个关系

3

R，

4

R，

5

R，

6

R与

1

R，

2

R不同，它们都

有下面两个特点：

（1）其定义域为X；

（2）X中任一元素a对应唯一一个Y中的元素

b

。

我们称具有这样两个特征的关系为映射（函数）。

定义设

,XY

是两个任意的集合，而

f

是X到Y的一个关系，若对每一个

xX

，都存在一个唯一的

yY

，使得,xyf，则称关系

f

为X到Y的映射

(Mapping)，记作

fXY：

或fXY

若,xyf，则称x为自变量(IndependentVariable)，称y为映射

f

在x

处的值（或像（Image）），,xyf亦可记作

()yfx

，

f

的值域

ran

fY

，有时也记为

f

R，即

{()(())}

f

RyyYxxXyfx

或记为

(){()}fXfxxX

集合Y称为

f

的共域，

f

R亦称为映射

f

的像集合。对于AX，称

()fA

为A

的像（ImageofA），定义为

(){()}{(())}fAfxxAyxxAyfx

显然,，

(),({}){()}()ffxfxxX

。

映射

f

是X到Y的特殊的二元关系，其特殊性在于：

（1）dom

fX

，即关系

f

的前域是X本身，而不是X的真子集。

（2）若,xyf，则映射f在x处的值y是唯一的，即

,,xyfxzfyz

例设{,,,},{1,2,3,4,5}XabcdY，且有{,1,,3,,4,,4}fabcd，求

domf、

f

R和()fx。

解dom{,,,}fXabcd

146146

ran

{1,3,4}f

()1,()3,()4,()4fafbfcfd

例判别下列关系中哪个构成映射。

（1）2{,}fxxxR

（2）2{,}fxxxR

（3）

121212

{,,,10}fxxxxNxx且

（4）

121212

{,,,10}fxxxxNxx且

（5）

12122

{,,,fxxxxNx为小于

1

x的素数个数

}

（6）

{,,,}fxyxyRxy

（7）

{,,,}fxyxyRyx

（8）

{,,,}fxyxyRxy

解（1）构成映射。

（2）22,,,xxfxxf

，即值y不唯一，故不构成映射。

（3）因为

1

x不能取定义域中所有的值，且

1

x对应很多

2

x，故不构成映射。

（4）因为

1

x不能取定义域中所有的值，故不构成映射。

（5）构成映射。

（6）构成映射。

（7）因为对

xR

，值y不唯一，故不构成映射。

（8）因为对

xR

，值y不唯一，故不构成映射。

例下列集合中，哪些是映射并求映射的定义域和值域。

（1）

1

{1,2,3,2,3,4,3,1,4,4,1,4}S

（2）

2

{1,2,3,2,3,4,3,3,2}S

（3）

3

{1,2,3,1,2,4,2,3,4}S

（4）

4

{1,2,3,2,2,3,3,2,3}S

解（1）是映射。dom

1

{1,2,3,4}S，

1

{1,4,2,3,3,4}

S

R

147147

（2）是映射。dom

2

{1,2,3}S，

2

{2,3,3,2,3,4}

S

R

（3）不是映射。

（4）是映射。dom

4

{1,2,3}S，

4

{2,3}

S

R

请注意区别x的像和

{}x

的像两个不同的概念。x的像

()fxY

，而像

({})fxY

。关于像有下列性质：

定理设

f

为X到Y映射，对任意

,AXBX

，有

（1）

()()()fABfAfB

；

（2）

()()()fABfAfB

；

（3）

()()()fAfBfAB

。

证明（1）对任一

yY

，

()(()(()))yfABxxAByfx

((()())(()))xxAxByfx

((()(()))(()(())))xxAyfxxByfx

(()(()))(()(()))xxAyfxxxByfx

(())(())yfAyfB

()()yfAfB

因此，

()()()fABfAfB

。

（2）、（3）的证明请读者完成。

注意：（2）、（3）中的“”不能用“=”代替。下面我们举例说明。

例设{,,,}Xabcd，{1,2,3,4,5}Y，fXY：如图4-2所示。那么，

({}){2}fa

({}){2}fb

({})({}){2}fafb

148148

({})({})fafb

({}{})()fabf

({}{})({}){2}fabfa

({}{})({})({})fabfafb

({})({})({}{})fafbfab

图4-2例图

由于映射归结为关系，因而映射的表示及运算可归结为集合的表示及运

算，映射的相等的概念、包含概念，也便归结为关系相等的概念及包含概念。

定义设

fAB：

，

gCD：

，如果

AC

，BD，且对于所有

xA

，有

()()fxgx

，则称映射

f

和g相等，记作

fg

。如果

AC

，

BD，且对于所有

xA

，有

()()fxgx

，则称映射

f

包含于g，记作

fg

。

事实上，当不强调映射是定义在哪个集合上的时候，由于映射是序偶的集

合（特殊的关系），所以f=g的充分必要条件是

fg

且

gf

。

从映射的定义可以知道XY的子集并不能都成为X到Y的映射。

例如，设{,,}Xabc，{0,1}Y，

{,0,,0,,0,,1,,1,,1}XYabcabc，XY有62个可能的子集，但其中

只有32个子集为从X到Y的映射：

0

{,0,,0,,0}fabc，

1

{,0,,0,,1}fabc

149149

2

{,0,,1,,0}fabc，

3

{,0,,1,,1}fabc

4

{,1,,0,,0}fabc，

5

{,1,,0,,1}fabc

6

{,1,,1,,0}fabc，

7

{,1,,1,,1}fabc

同理可知，从Y到X可定义23

个不同的映射：

0

{0,,1,}gaa，

1

{0,,1,}gab，

2

{0,,1,}gac，

3

{0,,1,}gba，

4

{0,,1,}gbb，

5

{0,,1,}gbc

6

{0,,1,}gca，

7

{0,,1,}gcb，

8

{0,,1,}gcc

一般地，设X和Y都为有限集，分别有m和n个不同元素，由于从X到Y

任意一个映射的定义域是X，在这些映射中每一个恰有m个序偶。另外任何元

素

xX

，可以有Y的n个元素中的任何一个作为它的像，故共有mn个不同的

映射。在上例中3,2XY，故从X到Y有32个不同的映射，从Y到X有23

个不同的映射。今后我们用符号XY表示从X到Y的所有映射的集合，甚至当

X和Y是无限集时，也用这个符号，即

{:}XYffXY

则有X

XYY。特别地AA表示集合A上映射的全体。

习题

1．指出下列各关系是否为X到Y的函数：

（1）

XYN

，{,()()(100)}RxyxXyYxy

（2）XYR(实数集)，3{,()()()}SxyxXyYyx

（3）

{1,2,3,4},XYXX

，

1

{1,2,3,2,3,4,3,1,4,4,2,3}R

2

{1,2,3,2,3,4,3,2,3}R

（4）设{,},{1,2,3}XabY，

1

{,1,,2}Rab，

2

{,1,,1}Rab，

3

{,1,,2}Raa，

4

{,3}Ra。

2．设fXY：，gXY：，求证：

150150

（1）

fg

为X到Y的函数当且仅当

fg

。

（2）

fg

为X到Y的函数当且仅当

fg

。

3．设{,{,{}},{},}f为一函数，计算

()f，

({})f，

({,{}})f。

4．设

{,,,},{1,2,3,4}XabcdY

，

fXY：

为：

{,1,,3,,1,,4}fabcd，求

({})fa

，

({,})fab

，

({,,})fabc

，

({,,,})fabcd

。

特殊映射

定义设

fXY：

，

（1）如果ran

fY

，即Y的每一个元素都是X中一个或多个元素的像，

则称这个映射为满射(Surjection)（或到上映射）。

（2）如果对于任意

12

,xxX，若

12

xx，则有

12

()()fxfx，则称这个映

射为入射(Injection)（或单射）。

（3）若

f

既是满射又是入射，则称

f

是双射(Bijection)。双射也称为1

—1对应(OneToOneMapping)。

由定义不难看出，如果

fXY：

是满射，则对于任意

yY

，必存在

xX

，使得

()fxy

成立；如果

fXY：

是入射，则X中没有两个不同元素

有相同的像，即对于任意

12

,xxX，

1212

()()fxfxxx。

图4-3说明了这三类映射之间的关系。注意，既非单射又非满射的函数是

大量存在的。

151151

图4-3

例（1）设

{,,,},{1,2,3}AabcdB

，如果fAB定义为

()1,()1,()3,()2fafbfcfd

则

f

是满射的。

（2）

{,}{1,3,5}fxy：

定义为

()1,()5fxfy

，则这个函数是入射，但不

是满射。

（3）令

[,]ab

表示实数的闭区间，即[,]{}abxaxb，

[0,1][,]fab：

定

义为：

()()fxbaxa

则这个映射是双射。

例在图4-4中，

()a

、

()c

是满射，

()b

、

()c

是入射，

()c

是双射。

图4-4

例设N是自然数集，下列映射哪些是满射、入射、双射。

（1）fNN：，2()2fjj。

（2）fNN：，()(mod3)fjj。

152152

（3）

fNN：

，

1

()(mod2)

0

j

fjj

j









为奇数

为偶数

（4）

{0,1}fN：

，

1

()

0

j

fj

j









为奇数

为偶数

（5）

fNR：

，

10

()logfjj

（6）

fRR：

，22()215(1)16fjjjj。

（7）2fNN：，2

121

(,)nfnnn

解：（1）入射。

（2）一般映射（既非满射，也非入射）。

（3）一般映射（既非满射，也非入射）。

（4）满射。

（5）不是映射，

(0)f

无定义。

（6）一般映射（既非满射，也非入射）。

（7）不是映射，

(0,0)f

无定义。

定理令X和Y为有限集，若X和Y的元素个数相同，即XY，则

fXY：

是入射的，当且仅当它是一个满射。

证明（1）若

f

是入射，则()fXXY。从

f

的定义我们有

()fXY

，而()fXY，因为Y是有限的，故

()fXY

，因此，

f

是一个满

射。

（2）若

f

是一个满射，则

()fXY

，于是()XYfX。因为

()XfX和X是有限的，所以，

f

是一个入射。

这个定理必须在有限集情况下才能成立，在无限集上不一定有效，如

fII：，这里()2fxx，在这种情况下整数映射到偶数，显然这是一个入

射，但不是满射。

另外，还有两个特殊而又重要的映射—常映射和恒等映射。

定义（1）设fXY：，如果存在cY，使得对所有的xX都有

()fxc，即(){}fXc，则称fXY：是常映射。

153153

（2）任意集合X上的恒等关系

X

I为一映射，常称为恒等映射，因为对任

意

xX

都有()

X

Ixx，即

{,}

X

IxxxX。

对任意

12

xx，有

12

()()

XX

IxIx，故

X

I是入射；且

X

I

RX，

X

I是满射。

所以，

X

I是双射。

习题

1．设,,,ZZRC



分别表示正整数集、整数集、实数集、复数集，试指出下列映

射中哪些是单射、满射、双射，并写出定义域和值域。

(1):fZZ



为()21fxx。

(2)

:fRR

为

()cosfxx

。

(3):1,1fR为

()sinfxx

。

(4):0,1,1

2

f











为

()cosfxx

。

(5):0,1,1f为

()sinfxx

。

(6)

:fCC

为()iQfzez（其中

Q

为一常数）。

2．下列关系中哪些能构成映射。

（1）

121212

,|,,10xxxxNxx，其中

N

为自然数集。

（2）2

121221

,|,,yyyyRyy

，其中R为实数集。

(3)2

121221

,|,,yyyyRyy

，其中R为实数集。

3．下列集合能定义成映射吗？如能，试求出它们的定义域及值域。

（1）1,2,3,2,3,4,3,1,4,4,1,4。

（2）1,2,3,2,3,4,3,3,2。

（3）1,2,3,2,3,4,1,2,4。

（4）1,2,3,3,2,3

154154

4．设映射

:fAB

，这里2{1,0,1}A，

{2,1,0,1,2}B

12

12

12

00

(,)

xx

fxx

xx













其它

（1）

f

定义了何种关系？

(2)

f

的值域是什么？

（3）有多少与

f

具有同样定义域和陪域的不同映射。

（4）设

:fXY

的映射且

X

，问

f

可能是单射吗可能是双射吗

（5）证明存在一个从X到

()PX

的单射，其中X为任意集合。

（6）设X与Y均是有限集且X有m个元素，Y有n个元素，说明下列断言

为真时，m和n必须成立的关系：

1）存在从X到Y的单射。

2）存在从X到Y的满射。

3）存在从X到Y的双射。

复合映射和逆映射

复合映射

因为映射是一种特殊的关系，所以和关系一样也有复合运算。

定义设映射

fXY：

，

WZg：

，若

()fXW

，则

{,()(()())}gfxzxXzZyyYyfxzgy

称g在映射

f

的左边可复合。

对于映射的复合我们有下面的定理：

定理设fXY：，

WZg：

，g在映射f的左边可复合，即

()fXW，则gf是一个XZ映射。

证明(1)对于任意xX，因为f为映射，故必有唯一的序偶,xy，使

()yfx成立，而()()fxfX即()fxW，又因为g是映射，故必有唯一序偶

155155

,yz，使

()zgy

成立，根据复合定义，,xzgf，即X中每个x对应Z中

某个z。

(2)假定

gf

中包含序偶

1

,xz和

2

,xz，这样在Y中必存在

1

y和

2

y，使

得在

f

中有

1

,xy和

2

,xy，在g中有

11

,yz和

22

,yz。因为

f

是一个映射，

故

12

yy；又因为g是一个映射，故

12

zz，即每个

xX

只能有唯一的

,xzgf。

由(1)、(2)可知

gf

是一个映射。

在定义中，当

WY

时，则映射

{,()(()())}gfxzxXzZyyYyfxzgy

称为映射

f

与映射g的复合映射，或称

gf

为g对

f

的左复合。

注意：在定义中，假定ran

f

domg，如果不满足这个条件，则定义

gf

为空。

根据复合映射的定义，显然有

()(())gfxgfx

。

例设

{1,2,3,4},{1,2,3,4,5},{1,2,3}XYZ

。

fXY：

，{1,2,2,1,3,3,4,5}f

gYZ：

，{1,1,2,2,3,3,4,3,5,2}g

求

gf

。

解{1,2,2,1,3,3,4,2}gf

例设

f

，g均为实函数，

()21fxx

，2()1gxx。求

fg

，

gf

，

ff，gg。

解22()2(1)123fgxxx

22()(21)1442gfxxxx

()2(21)143ffxxx

2242()(1)122ggxxxx

156156

所以

2{,23}fgxxxR

2{,442}gfxxxxR

{,43}ffxxxR

42{,22}ggxxxxR

定理设

gf

是一个复合映射。

（1）若

f

和g是满射，则

gf

是满射。

（2）若

f

和g是入射，则

gf

是入射。

（3）若

f

和g是双射，则

gf

是双射。

证明给定集合

,,XYZ

，

fXY：

，

gYZ：

，

（1）zZ，因为g是满射，故

yY

，使得

()gyz

；又因为

f

是满

射，故

xX

，使得

()fxy

，所以，

()(())()gfxgfxgyz

即zZ，xX，使得

()gfxz

。因此，

gf

RZ，gf

是满射。

（2）对

12

,xxX，

12

xx，因为f是入射，故

12

()()fxfx；又因为g

是入射，故

12

(())(())gfxgfx，于是

1212

()()xxgfxgfx

所以，

gf

是入射。

（3）因为f和g是双射，根据（1）和（2），gf为满射和入射，即

gf是双射。

定理设gf是一个复合映射。

（1）若gf是满射，则g是满射。

（2）若gf是入射，则f是入射。

157157

（3）若

gf

是双射，则g是满射，

f

是入射。

证明设

fXY：

，

gYZ：

，

gfXZ：

。

（1）因为

gf

是满射，则

gf

RZ，zZ，xX，使

()gfxz

，

故

yY

使得

()yfx

，

()zgy

，可见，

g

RZ，所以g是满射。

（2）设

12

,xxX且

12

xx。因为

gf

是入射，故

12

()()gfxgfx，即

12

(())(())gfxgfx，因为g是一个映射，则

12

()()fxfx，即

1212

()()xxfxfx

所以，

f

是入射。

（3）

gf

是双射，则

gf

是满射且是入射。

gf

是满射，由（1）可知

g是满射；

gf

是入射，由（2）可知

f

是入射。

由于映射的复合仍然是一个映射，故可求三个以上映射的复合。

例设R为实数集合，对

xR

，有

()2fxx

，

()2gxx

，

()3hxx

求

gf

，

hg

，

()hgf

与

()hgf

。

解：{,}gfxxxR，

hg{,3(2)}xxxR

(){,3}hgfxxxR

(){,3}hgfxxxR

所以有

()()hgfhgf

一般地，有如下定理。

定理设有函数fXY：，gYZ：和hZW：，则有

()()hgfhgf

158158

证明这可由关系的复合的可结合性得出，这里我们直接由映射相等的定义

证明。

首先

()hgf

和

()hgf

都是X到

W

的函数。另外对任一

xX

，有

()()(()())((()))

(())()()

hgfxhgfxhgfx

hgfxhgfx





由元素x的任意性，有

()()hgfhgf

由此可见，映射的复合运算满足结合律，因此多个映射复合时可去掉括

号，对3个映射的复合即有

()()hgfhgfhgf

。

若有

fXX：

，则

ff

仍为X到X的映射，简记为2f，一般地

n

fff简记为nf。显然

0

1

()()

()(())

X

nn

fxIxx

fxffx















注意：映射的复合运算不满足交换律。

例（1）设

{1,2,3}X

，

fXX：

，{1,2,2,2,3,1}f，

gXX：

，{1,2,2,1,3,3}g，

则

{1,1,2,1,3,2}gf，

{1,2,2,2,3,1}fg。

所以

gffg

。

映射的复合运算还有如下明显的性质：

定理设映射fXY：，则

XY

ffIIf。

证明对,xXyY，有()

X

Ixx，()

Y

Iyy，则

()()(())()

XX

fIxfIxfx

()()(())()

YY

IfxIfxfx

159159

所以，

XY

ffIIf

当XY时，有

XX

ffIIf

逆映射

在关系的定义中曾提到，从X到Y的关系R，其逆关系1R是Y到X的关

系，

1,,yxRxyR

但是，对于映射就不能用简单的交换序偶的元素而得到逆映射，这是因为

若有映射

fXY：

，但

f

的值域

f

R可能只是Y的一个真子集，即

f

RY，此

时，

dom1

f

fRY，这不符合映射对定义域的要求。此外，若fXY的映射

是多对一的，即有

1212

,,,,xyfxyfxx，其逆关系将有

11

1212

,,,,yxfyxfxx，这就违反了映射值唯一性的要求。为此，有如

下定理：

定理设

fXY：

是一个双射，那么1f是

YX

的双射。

证明设{,()}fxyxXyYyfx，1{,,}fyxxyf

，

因为

f

是满射，故对每一

yY

，必存在,xyf，所以，1,yxf，即1f

的前域为Y。又因为

f

是入射，对每一个

yY

恰有一个

xX

，使,xyf，

即仅有一个

xX

，使1,yxf，y对应唯一的x，故1f是映射。

因为ran1fdom

fX

，所以，1f是满射。

又设

12

yy时，有11

12

()()fyfy，令11

1122

(),()fyxfyx，则

12

xx，故

12

()()fxfx，即

12

yy，与假设矛盾。所以11

12

()()fyfy，即

1f是单射。

因此，1f是一个双射。

160160

定义设

fXY：

是一双射，称

YX

的双射1f为

f

的逆映射，记作

1f。

例如，设

{0,1,2},{,,}XYabc

。若

fXY：

为：

{0,,1,,2,}fcab，

则有1:fYX，1{,1,,2,,0}fabc。

若{0,,1,,2,}fcaa，

则

f

的逆关系1{,1,,2,,0}faac

就不是一个函数。

再如，

fRR：

，3()2fxx，则1

3()2fxx。

函数的逆具有下面一些重要性质。

定理如果映射

fXY：

有逆映射1fYX：，则1

X

ffI，

1

Y

ffI。

证明因为

fXY：

是双射，所以1fYX：也是双射。由定理知，

1ffXX：和1ffYY：都是双射。

任取

,xXyY

，若

()fxy

，1()fyx，则

111()()(())()ffxffxfyx

11()()(())()ffyffyfxy

所以，

1

X

ffI；

1

Y

ffI。

定理若fXY：是双射，则11()ff。

证明因fXY：是双射，1fYX：也是双射，因此，11()fXY：

是双射。由于

domf=dom11()fX

161161

且

111,(),,xyfyxfxyf

所以，11()ff。

定理若

fXY：

，YZg：均为双射，则111()gffg。

证明（1）因

fXY：

，YZg：均为双射，故1f和1g均存在，且

1fYX：，1gZY：均为双射，所以，11fgZX：为双射。

根据定理，

gfXZ：

是双射，故1()gfZX：是双射，且

dom11()fg=dom1()gfZ

（2）对任意zZ存在唯一

yY

，使得

()gyz

存在唯一

xX

，使得

()fxy

故

11111()()(())()fgzfgzfyx

又

()()(())()gfxgfxgyz

故

1()()gfzx

因此，对任一zZ有：111()()()()gfzfgz

由（1）、（2）可知

111()fggf。

例设

{0,1,2},{,,},{,,}XYabcZ

，若有

fXY：

，

gYZ：

，

其中，{1,,2,,3,},{,,,,,}fcabgabc，求1()gf和11fg。

解{1,,2,,3,}gf，1(){,1,,3,,2}gf

1{,1,,2,,3}fcab，1{,,,,,}gcba

11{,1,,3,,2}fg

可见，

162162

111()gffg

习题

1．证明或反驳下列命题：

(1)设BAX，

:fXY

为任一映射，则

()()()fABfAfB

，其

中

(){|(),}fAyyfxxA

，

(){|(),}fByyfxxB

，

(){|(),}fAByyfxxAB

。

(2)

:fXY

是双射，当且仅当对X中任两个子集A与B，若

AB

，

则

()()fAfB

。

(3)设

:fXY

，

,XY

均为有限集且XY，则下列命题等价：

①

f

是单射；②

f

是满射；③

f

是可逆的。

2．设

:fRR

为3()2fxx，其中R为实数集，试求1f。

3．证明从XY到YX存在单射，并说明此映射是否为满射。

4．设

{1,2,3,4}X

。

(1)试定义映射:fXX使

X

fI且是单射。

(2)求211,,,fffffff。

(3)能否找到另一

X

gI的单射:gXX，有

X

ggI

(4)试定义一个映射:fXX使2ff且

X

fI。

(5)试定义一个映射:fXX使1ff且

X

fI。

5．求下列各映射的逆映射：

(1):,()fRRfxx；

(2)

131

:[0,1][,],()

4424

x

ffx

；

(3):,()2fRRfxx；

(4):,()2xfRRfx.

6．如果N为{0,1,2,}且

163163

:fNN

为

()1fnn

；

:gNN

为

()2gnn

；

:hNN

为

0

()

1

n

hn

n









为偶数

为奇数

试求

ff

，

fg

，

gf

，

gh

，

hg

，

()fgh

。

7．设

:fXX

，

:gXX

为任意两个映射，证明

(1)如果g不是满射，则

gf

也不是满射。

(2)如果

f

不是单射，则

gf

也不是单射。

(3)如果

f

为满射，

fff

，则

X

fI。

置换

定义设

12

{,,,}

n

Xxxx，双射

fXX：

称为集合X的置换

(Permutation)，记作

pXX：

这里，X中元素的个数X称作置换的阶。

定理在n个元素的集合中，不同的n阶置换的总数为n！个。

证明形如：123

123

()()()()

n

n

xxxx

p

pxpxpxpx









中的

123

(),(),(),,()

n

pxpxpxpx可以取

123

,,,,

n

xxxx的任意一个全排列，故总数

为n！个。

定义给定

12

{,,,}

n

Xxxx，恒等映射()

X

IxXX：称为集合X上的恒

等置换(IdenticalPermutation)，记作

123

123

n

X

n

xxxx

I

xxxx









定义设

p

是集合

12

{,,,}

n

Xxxx的置换，如果可以取到

X

的元素

164164

12

,,,(1)

r

xxxrn



，使

122311

(),(),,(),()

rrr

pxxpxxpxxpxx





，且

X

的

其余元素（如果还有的话）不变，则称

p

为一个轮换，记为

12

()

r

xxx



。

若

123

{,,}Xxxx，则

X

的6个置换

123

123

,

xxx

xxx







123

213

,

xxx

xxx







123

132

,

xxx

xxx







123

321

,

xxx

xxx







123

231

,

xxx

xxx







123

312

xxx

xxx







都是轮换，它们分别记为

11223

(),(),(),xxxxx

13123

(),()xxxxx和

132

()xxx。当

1234

{,,,}Xxxxx时，置换1234

2143

xxxx

xxxx







不是轮

换。一般地，

3X

时，

X

的置换都是轮换；

3X

时，

X

的置换未必是轮

换。

定义把置换看作定义在集合

12

{,,,}

n

Xxxx上的双射，置换的复合定义

为相应映射复合构成的置换。

例如，

1

1234

3124

p









，

2

1234

4321

p









则

12

1234

4213

pp









，

21

1234

2431

pp









可见，

1221

pppp。

两个轮换

12

()

r

iii

xxx与

12

()

s

jjj

xxx的复合记为：

12

()

s

jjj

xxx

12

()

r

iii

xxx。

定义给定

12

{,,,}

n

Xxxx，对任意的n阶置换

123

123

()()()()

n

n

xxxx

p

pxpxpxpx









记

123

1

123

()()()()

n

n

pxpxpxpx

p

xxxx











165165

容易验证

11

X

ppppI

我们称1p为p的逆置换。

集合

12

{,,,}

n

Xxxx上的所有n阶置换的全体记作

n

S。

置换的复合有以下性质：

（1）

n

S对于复合运算是封闭的；

（2）结合律成立，即,,

ijkn

pppS，有()()

ijkijk

pppppp；

（3）

n

S中有一个元素称为恒等置换，使对任意

n

pS有

pIIpp

；

（4）任意

n

pS，都存在有逆置换1p，使11ppppI。

习题

1．若

{1,2,3}X

，试写出X上的全部置换，并指出各置换的逆。

2．设

{1,2,3,4}X

，

123

,,ppp是X上的置换，

1

1234

2413

p









，

2

1234

3421

p









，

3

1234

2413

p









，

求

12

pp，

21

pp，

13

pp，

32

pp，1

1

p，1

2

p及1

3

p。

3．已知

1

123

312

p









，

2

123

132

p









，

2

123

213

p









，

请验证：

123123

()()pppppp。

4．设

{1,2,3,4}A

，计算

(123)(234)(14)(23)

。

5．设

{1,2,3,4,5,6}A

，

A

上的置换

(1234)f

，

(134)(25)g

。求

（1）1f；

（2）1fgf。

*特征函数

166166

有些映射与集合之间可以建立一些特殊的关系，借助于这些映射，可对集

合进行运算。

定义令E是全集，AE，由

1

()

0A

xA

x

xA















定义的映射{0,1}

A

E：，称为集合A的特征函数(Eigen-function)。

定理给定全集E，且AE，BE，对于所有xE，特征函数有如下

一些性质。

（1）()0

A

xA

（2）()1

A

xAE

（3）()()

AB

xxAB

（4）()()

AB

xxAB

（5）()()()

ABAB

xxx

（6）()()()()

ABABAB

xxxx

（7）()1()

A

A

xx

（8）()()()()

ABAAB

AB

xxxx





证明：（1）、（2）、（7）显然。

（3）若AB，则对xE，当xA时，必有xB，即()1

A

x，

()1

B

x，可见，()()

AB

xx；当xA时，则()0

A

x，故也有

()()

AB

xx。

若()()

AB

xx，即()1

A

x时，()1

B

x，亦即xA时必有xB，所

以，

AB

。

（4）若AB，即

AB

且

BA

。

由（3）得()()

AB

xx且()()

BA

xx，所以，()()

AB

xx。

167167

若()()

AB

xx，则()1

A

x时，()1

B

x，即

xA

时必有

xB

，故

AB；()0

A

x时，()0

B

x，即

xA

时必有

xB

，则

xB

时必有

xA，即BA。

所以，AB。

（5）()1

AB

xxABxAxB()1

A

x且()1

B

x

所以()()()

ABAB

xxx

（6）xABxAxB，有以下三种可能：

1)

xA

且

xB

，则xAB，()1

A

x，()1

B

x，()1

AB

x，所

以，()()()()1

ABABAB

xxxx；

2)

xA

且

xB

，则xAB，()1

A

x，()0

B

x，()0

AB

x，所以，

()()()()1

ABABAB

xxxx；

3)

xA

且

xB

，则xAB，()0

A

x，()1

B

x，()0

AB

x，所以，

()()()()1

ABABAB

xxxx。

xABxAxBxAB，则()0

A

x，()0

B

x，

()0

AB

x，所以，

()()()()0

ABABAB

xxxx。

综上所述，

()()()()

ABABAB

xxxx。

（8）由于ABAB，则

()()()()(1())

ABAAB

B

xxxxx





()()()()()

AABAAB

xxxxx

应用特征函数的一些性质，也可以证明一些集合恒等式。

例试证明：

（1）

AA

168168

（2）

()()()ABCABAC

证明（1）因为()1()1(1())()

AA

A

A

xxxx，所以，

AA。

（2）

()

()()()

ABCABC

xxx

()(()()())

ABCBC

xxxx

()()()()()()

ABACABC

xxxxxx

()

()()()

ABACABC

xxx

()()

()()()

ABACABAC

xxx

()()

()

ABAC

x

所以，

()()()ABCABAC

。

例设

{,,}Eabc

，E的子集是：

,{},{},{},{,},{,},{,}abcabacbc和

{,,}abc

，试给出E的所有子集的特征函数且建立特征函数与二进制之间的对应

关系。

解：E的任何子集A的特征函数的值由表4-1列出。

表4-1E的任何子集A的特征函数的值

()

A

x

x

A

{}a{}b{}c{,}ab{,}ac{,}bc{,,}abc

a

b

c

0

0

0

1

0

0

0

1

0

0

0

1

1

1

0

1

0

1

0

1

1

1

1

1

如果规定元素的次序为

,,abc

，则每个子集A的特征函数与一个三位二进制

数相对应。如

{,}

()101

ac

x。令{000,001,010,011,100,101,110,111}B，那么

表4-1亦可看作从E的幂集到B的一个双射。

习题

169169

1．设()()()SABACBC，其中

,,ABC

是全集E的子集，试用特征函

数

(),(),()

ABC

xxx

来表示()

S

x

。

2．利用特征函数的性质证明下列等式。

(1)

()()ABCABC

(2)

()AABA

(3)

()AABAB

(4)

()()()ABCABAC

*基数

无限集合

定义如果有一个从集合

{0,1,,1}n

到A的双射函数，那么称集合A是有限

的，并称n为A的计数(Counting)（A中元素的个数），规定空集的计数为

0

；如果集合A不是有限的，则它是无限的。

使用定义证明集合A是无限集，就要证明对任意nI



，在

{0,1,,1}n

与

A之间都不会建立双射。这种排除无数可能再确立结论的推论方法，其困难是

固有的。一个切实有效的克服困难的选择是：

定义称集合A是无限集，当且仅当存在A到自身的单射

f

，使得

()fAA

。如果A不是无限集，则称它是有限集。

定理自然数集合N是无限的。

证明存在单射

fNN：

，

()2fnn

，并且，

()fNN

。所以，

N

是无

限集。

定理子集是无限集合的集合是无限集。

证明若集合A的子集A



是无限集合，则存在A



上的单射

f

，使得

()fAA



。扩充f到A上记为g，g满足：若xA



，则()()gxfx；若

xAA



，则()gxx。显然，g是A上的单射，且

()()()gAfAAAA



。所以，A是无限集。

子集是无限集合的集合是无限集，其逆否命题是：有限集合的子集都是有

限集合。

定理设,AB是任意两个集合且A是无限集，则：

170170

（1）若从A到B存在单射

f

，则B也是无限集；

（2）A的幂集

()PA

是无限集；

（3）AB是无限集；

（4）若

B

，则AB是无限集；

证明仅证（1），其余都是（1）的推论。

A是无限集，存在单射

:gAA

，使得

()gAA

。

f

是从A到B的单射，

()fAB

，

f

是从A到

()fA

的双射，存在逆映射1

()fA

f。

定义映射

:hBB

，

h

满足：若

()xBfA

，则

()hxx

；

()xfA

，则

1

()

()()

fA

hxfgfx。由于1

()

(),,

fA

fxgf都是单射，所以

h

是B上的单射，

且

()(())(())(())(())hBhfABfAfgABfA

()(())fABfAB

所以，B是无限集。

基数的概念

两个集合，如果它们都是有限集，其中元素哪个多哪个少是很容易知道

的，只要比较有限集的计数即可。但是，如果两个集合都是无限集，怎样比较

它们的元素哪个多哪个少呢？例如，自然数集

{0,1,2,3,}N

，正偶数集

{2,4,6,}E，整数集

{,3,2,1,0,1,2,3,}I

，实数集{}(,)Rxx。

设A与B是两个集合，若A中元素和B中元素可以一一对应，即存在A到

B的一个双射，这意味着A的元素个数和B的元素个数一样多。但这句话很不

确切，因为在无限集的情形下，谈不上其中元素个数是多少。在集合论中，若

集合A中元素和B中元素可以一一对应，我们不说它们的元素个数相等，而说

它们有相同的势。

定义对于集合A与B，如果存在着从A到B的双射，则称A与B为等势的

(Equivalent)，或称A与B对等(Equipollent)，记作AB。

例验证自然数集N与非负偶数集合M是等势的。

证明N与M的元素之间可做双射，即

fNM：，()2fnn

171171

所以，

N

与

M

等势。

例设R为实数集合，S是R的子集，即SR，且

{11}(1,1)SxxRx

证明：

SR

证明令

fSR：

，

2

()

1

x

fx

x





(1,1)x

显然

f

的值域是R，

f

是双射函数，所以

SR

。

定理集合族上等势关系是一个等价关系。

证明设集合族为

S

（1）对任意

AS

，恒等映射

A

I是A到A的双射，所以AA；

（2）对任意

,ABS

，如果AB，则存在A到B的双射

f

，从而1f为B

到A的双射，故BA；

（3）对任意

,,ABCS

，如果AB且

BC

，则存在A到B的双射

f

和B

到

C

的双射g，由定理知

gf

是A到

C

的双射，故

AC

。

综合（1）、（2）和（3）知集合族上的等势关系是一个等价关系。

显然，两个有限集对等，当且仅当它们的计数相等。即根据计数是否相等

就能判断两个有限集是否对等。很自然，我们希望将有限集的计数这个概念推

广到无限集。

定义我们将相互对等的集合归为同一类，不对等的集合不属于同一类，对

每类集合予以一个记号，称这个记号是这一类集合中每个集合的基数(Cardinal

Number)（势，浓度，权）。集合A的基数记为

[]KA

。并规定计数就是有限集

合的基数。

定义设A、B是两个集合。

（1）如果AB，就称A与B的基数相同，记作

[][]KAKB

；

（2）如果存在从A到B的入射，就称A的基数小于等于B的基数，记作

[][]KAKB；

（3）如果[][]KAKB且[][]KAKB，就称A的基数小于B的基数，记

作

[][]KAKB。

例证明区间[0,1]与(0,1)基数相同。

172172

证明设集合

11

{0,1,,,,}

2

A

n



，

[0,1]A

。定义

[0,1](0,1)f：

使得

1

(0)

2

11

()1

2

()[01]

f

fn

nn

fxxxA



























，

则

f

是双射，故区间

[0,1]

与

(0,1)

基数相同。

可数集与不可数集

定义我们称自然数集

{0,1,2,3,}N

的基数为

0



，称为可列基数

(CountableCardinalNumber)。凡与自然数集

N

对等的任意集合称为可列集

（或可数集）(CountableSet)。

例如，2{1,4,9,16,,,}An，

111

{1,,,,,}

23

B

n



均为可数集。

定义如果集合A是有限的或无限可数的，则统称为至多可数的。如果集合

A是无限的且是不可数的，则称A是不可数的(Non-countable)。

定理A为可数集的充分必要条件是可以排列成

12

{,,,}

n

Aaaa

的形式。

证明若A可排成上述形式，那么将A的元素

n

a与脚标n对应，就得到A与

N之间的双射，故A是可数集。

反之，若A为可数集，那么在A与

N

之间存在一个双射

f

，由

f

得到n的

对应元素

n

a,即A可写为

12

{,,,}

n

aaa的形式。

定理任一无限集，必含有可数子集。

证明设A为无限集合，从A中取出一个元素

1

a，因为A是无限的，它不因

取出

1

a而耗尽，所以，从

1

{}Aa中可取元素

2

a，则

12

{,}Aaa也是非空集，所

以又可取一元素

3

a，如此继续下去，就得到A的可数子集。

定理集合A是无限集，当且仅当A与A的一个真子集对等。

证明留给读者。

这一定理告诉我们任何一个无限集必定可以和它的某个真子集对等，这对

于有限集来说是绝对不可能做到的。因此，能否和自己的某个真子集对等，这

是无限集和有限集的本质区别。

定理下列各结论成立：

173173

（1）可数集的任何无限子集是可数的；

（2）有限或可数个可数集的并是可数集；

（3）有限个可数集的直积是可数集。

证明（1）设A为可数集合，BA为一无限子集，如将A的元素排成

12

,,,

n

aaa，从

1

a开始，向后检查，不断地删去不在B中的元素，则得到新

的一列

12

,,,

iiin

aaa，它与自然数集对等，所以B是可数的。

（2）只需证明可数多个可数集的并是可数集。

设可数个可数集分别表示为：

111121

{,,,}

n

Aaaa

221222

{,,,}

n

Aaaa

331323

{,,,}

n

Aaaa

令

123

AAAA，即

1

k

k

AA





，对A的元素排列如下：

按上面箭头指向的顺序排列得到

314

{,,,,,,,}aaaaaaa，

从中删去重复的元素。这样，

1

k

k

A





中的元素可以排成一个无穷序列，故A是可

数集。

（3）证明留给读者。

174174

定理有理数的全体组成的集合是可数集。

证明设Q和Q分别表示全体正有理数和全体负有理数组成的集合，则

{0}QQQ

由于每一个正有理数都可以表示为

p

q

的形式，其中,pq都是正整数，对于

每一个正整数q，令

123

{0,,,,}

q

A

qqq



则有

1

{0}

q

q

QA









显然，

q

A是可数集。由定理，可数个可数集的并是可数集，所以{0}Q是可

数集。易知{0}Q{0}Q，由于{0}QN

，由对等的传递性，则

{0}QN

。再应用有限个可数集的并是可数集，则

Q

是可数集。

并非所有无限集合都是可数的，例如，实数集合就是不可数的。

定理全体实数构成的集合R是不可数的。

证明作映射

(0,1)fR：

1

0

2(1)

()

1

10

2(1)

x

x

fx

x

x

























显然，

f

是双射，所以

(0,1)R

。

我们只需证明

(0,1)

不可数。用反证法。

假设(0,1)S是可数的，则

S

必可表示为：

123

{,,,}Ssss，其中

i

S是(0,1)

上的任一实数，它可写成无穷小数的形式。

设

123

0.

i

syyy，其中{0,1,2,,9}

i

y（如0.2和0.123可记为0.1999和

0.12299），

设

11112131

0.

n

saaaa

22122232

0.

n

saaaa

175175

33132333

0.

n

saaaa

…

其次，我们构造一个实数

123

使

11

21

jj

j

jj

a

b

a













1,2,j

显然，

(0,1)s

，且s与

12

,,,

n

SSS各数至少有一位数是不同的，因为对

于任何一个

i

s，若

i

s中1

ii

a，则s中1

i

b；若1

ii

a，则2

i

b。因此，s和

i

s

的小数第i位数字是不同的，即

i

ss（

1,2,3,i

）。这就证明了

sS

，产生

矛盾，因此，

S

是不可数的，即

S

是不可数集。

我们把集合

(0,1)

的基数记为“

1



”，因为

(0,1)R

，故

[]KR

1



。

“

1



”称作连续基数。

习题

1．下列集合A的基数是什么？

（1）

{0}A

。（2）

{,,}Aabc

。

（3）{,,Apqpq都是整数

}

。（4）{,,Apqpq都是有理数

}

。

（5）A是由所有半径为1，圆心在x轴上的圆周所组成的集合。

（6）A是由所有圆心在原点的圆周所组成的集合。

（7）A是由所有圆心在原点，以正有理数为半径的圆周所组成的集合。

2．证明下列集合是可数的。

（1）{32,}kknnN。（2）2{,}kknnN

。

（3）（1）与（2）中两集合的并。（4）

1212

{1,xxxx都是有理数

}。

3．构造从[0,1]到下列集合的一个双射，以证明它们有基数

1



。

（1）(,)ab。（2）{0}xxRx

（3）(0,1)（4）22{,,1}xyxyRxy