集 合 论
第四章 函 数
§ 1 函数的概念
§ 2 逆函数和复合函数
§ 3 基数的概念
§ 4* 可数集与不可数集
第四章 函数
函数是二元关系中特殊的一类，也就是说，函数是一种
特定类型的二元关系。本章讨论的是离散函数，它能
把一个有穷集合变换到另一个有穷集合。
例：在计算机上执行程序可以看作是函数的变换：
（自变量）输入 -----计算机 -----输出（函数值）
在这章我们主要讨论：函数定义、特殊函数及其性质、
函数的运算。最后利用函数的概念，特别是双射函数，
介绍一下无限集合的基数问题。
§ 1 函数的概念
１．函数的定义,
,定义, 设 X和 Y是任意两个集合,f是从 X→Y 的一种关
系，若对于每一个 x∈ X,都存在一个唯一的 y∈ Y,能
使 <x,y>∈ f, 则称关系 f为函数（映射）,并记为：
f,X→Y 。
讨论定义：
（ 1） f,X→Y 中，若 fyx ???,，则称 x为自变量，
与 x对应的 y称作 f作用下的象点（值）；
也可用 y=f(x)表示 fyx ???,,y称作函数 f在 x点处的值。
§ 1 函数的概念
（ 2） X中每一个元素均有定义,
∴ 函数 f的定义域 Xdom f ?
（ 3）对应于某一个 Xx?,其值 f(x)是唯一的，即
)(,,zyfzxfyx ?????????
（ 4） f 值域 Yra n f ?
))}(()(|{ xfyXxxyR f ?????
有时也记为 Rf
集合 Y称为 f 的共域
§ 1 函数的概念
例：判定下列关系是否为函数
XD f ?
YRf ?
是函数
XD f ?
不是函数
值不是唯一的
不是函数
§ 1 函数的概念
例：设 X=Y=R（实数）
},|,{)1( 2xyRyxyxf ??????
值是唯一的2,xyRD
f ??
},|,{)2( 2yxRyxyxg ??????
2yx ?
这不是函数，不满足值唯一性
§ 1 函数的概念
,定义,, 给定函数 f:A→B 和 g:C→D,如果 A=C,B=D，
并对所有的 Ax? 或 Cx?
都有 f(x)=g(x)，则称函数 f和 g是相等的，即 f=g。
２．函数的构成
例：设 X={a,b,c},Y={0,1}，则
}1,0,1,0,1,0,{ ?????????????? ccbbaaYX
YX ? 中，有 642 6 ? 个子集，
§ 1 函数的概念
但在 64个子集中只有 8个 )2( 3
符合函数的定义，这 8个函数为：
???
?
???
?????????
0 0 0}0,0,0,{0
a b ccbaf ??
?
?
???
??
0 0 11
a b cf
???
?
???
??
0 1 02
a b cf
???
?
???
??
0 1 13
a b cf
???
?
???
??
1 0 04
a b cf
???
?
???
??
1 1 06
a b cf
???
?
???
??
1 0 15
a b cf
???
?
???
??
1 1 17
a b cf
§ 1 函数的概念
讨论：从此例中可得到三点结论：
（ 1）设 |X|=m,|Y|=n，则函数 f,X→Y 中均是 m个序偶的集合；
（即序偶个数 =定义域的基数）
（ 2） X中每一个元素所对应的象点 f(x)可能是 Y中 n个，
从 X-Y的所有函数个数
mX nY ?|| |||| XY?
§ 1 函数的概念
（ 3） X→Y 有别函数的个数和 YX ? 子集个数的关系为：
nmmX YXnY ?????? 2||||
即二个集合之间能构成的函数个数比能构成的二元关系数少得多
3.几种特殊函数
,定义,, 给定函数 f,X→Y,如果值域 YR
f ?
则称 f为满射函数。
§ 1 函数的概念
例,满射函数一定有：
(1)|X|≥|Y|
YR f ?)2(
,定义,, 给定 f,X→Y,如果有 )()( 2121 xfxfxx ???
2121 )()( xxxfxf ???
或者,则称 f是入射函数。
§ 1 函数的概念
入射函数有：
?
?
?
?
?
||||)2(
)1(
YX
YR f
,定义,, 给定函数 f,X→Y,如果 f既是满射函数，
又是入射函数，则称 f为双射函数。
（或称“一一对应函数”，“一对一满射函数”）
§ 1 函数的概念
双射函数一定有：
（ 1）（值域）
YRf ?
（ 2）（定义域） |X|=|Y|
例：在全班同学的集合中，设,X={序号 },Y={姓名 }
则,f,X→Y 是一双射函数（序号和姓名的关系）
§ 2逆函数和复合函数
设 Ryx ???,，则 Rxy ~,???
现在讨论函数能否像二元关系那样得到逆函数呢？
先举一例
例：定义一函数
由例题可见：
f~)1( 的定义域不是 Y，而是 Y的子集
f~)2( 不满足函数定义：即值是唯一的
f~? 是一种二元关系，而不是函数
§ 2逆函数和复合函数
（ 3）一个函数的反函数存在的话，则此函数一定是双射函
数，而入射，满射函数的逆关系均不满足函数的定义
YXf ?:
（ 4）为了和逆关系相区别，函数 f的用“逆函数”
1?f 来表示
,定理,, 如果 f,X→Y 是双射函数，则有,XYf ??,1
也为双射函数。
,定义,, 设 是一双射函数，称 XYf ??,1
为 f的逆函数。
§ 2逆函数和复合函数
,定义,, 设 f,X→Y 和 g:W→Z 是二个函数，若 WXf ?)(
))}()((|,{ ygzxfyYyyZzXxzxfg ??????????????
则：
称 g在函数 f的左边可复合。
讨论定义：
(1)两个函数的复合是一个函数。
(2)函数 fg? 称为 f和 g的左复合，
这里和习惯上符合函数的书写求得一致。
例,sin(ln x)，先求 ln x，然后求 sin(ln x)
§ 2逆函数和复合函数
,定理,, 设 f:X→Y 和 g:Y→Z 是二个函数，于是复合函数
fg? 是一个从 X到 Z的函数，对于每一个 Xx? 有：
))(())(( xfgxfg ??
证明：有定义可知 fg? 是从 X→Z 的函数，即
)(,xfgzx ????
设,x∈X 由 f,X→Y 得 y=f(x)
设,y∈Y 由 g:Y→Z 得 z=g(y)
)()( ygzxfy ???由 得,))(())(( xfgxfgz ???
§ 2逆函数和复合函数
例：设 X={1,2,3},Y={p,q},Z={a,b}
f,X→Y={<1,p><2,p><3,q>}
g:Y→Z={<p,b><q,b>} 则：
},3,2,1{ ??????? bbbfg ?
fg ? 是 X→Z 的函数
上例的函数复合图为：
§ 2逆函数和复合函数
f,X→Y g:Y→Z )(xfg ?, X→Z
??gf ? ∴ 函数的复合运算不满足交换律。
§ 2逆函数和复合函数
,定理,, 函数的复合运算是可结合的，
即如果 f,g,h均为函数，则有：
fghfgh ???? )()( ?
证明：函数也是一种二元关系，
∵ 二元关系的复合是满足结合律的，
∴ 函数的复合也是满足结合律的。
例,I是整数集合,f,I→I 定义成 f(i)=2i+1，求复合函数
)(3 if 并证明它满足结合律。
§ 2逆函数和复合函数
解：
?)(3 if )1)12(2()12())(( ????? ififfifff ???
781681)1)12(2(2 ????????? iii
)(3 if 1)1)(2(21)(2))(( 22 ?????? ifififf
781681)1)12(2(2 ????????? iii
§ 2逆函数和复合函数
,定理,, 设 f,X→Y, g:Y→Z, fg? 是一合成函数，则：
(1)如果 f和 g都是满射函数，则 fg? 也是满射函数；
(2)如果 f和 g都是入射函数，则 fg? 也是入射函数；
(3)如果 f和 g都是双射函数，则 fg? 也是双射函数。
证明：（ 2）设任一
jiji xxXxx ???,
∵ f为入射函数,∴ )()(
ji xfxf ?
又 ∵ g为入射函数,且 )()(
ji xfxf ?
§ 2逆函数和复合函数
))(())(( ji xfgxfg ?? 即 )()( ji xfgxfg ?? ?
ji xx,? 是任一的，
fg ?? 也是单射函数。
可用同样的方法证明（ 1）和（ 3）
§ 2逆函数和复合函数
例：设
?I
是负整数集合，定义二个双射函数 f和 g，
?? ? IIf,
f(x)= - x ={<-1,1><-2,2>…},
NIg ??,g(x)= x-1={<1,0><2,1>…},
:fg? }1,20,1{)1)(())(( ?????????????? xxfgNI
是一双射函数。
§ 2逆函数和复合函数
,定义,, 给定 f,X→Y,如果对于所有的
Xx? 和某一个 y∈ Y,有 f(x)=y，则称 f为常函数。
例：
§ 2逆函数和复合函数
,定义,, 给定 XXI
x ?:,若对所有的 Xx? 有
xxI x ?)(,即 }|,{ XxxxI x ????
则称
xI
为恒等函数。
例：
§ 2逆函数和复合函数
,定理,, 对于任何函数 f,X→Y,其中
xI
是 X→X 的恒等函数，
yI
是 Y→Y 的恒等函数，则有
ffIIf yx ?? ??
X
X
Y
Y
§ 2逆函数和复合函数
,定理,, 如果函数 f,X→Y 有逆函数 XYf ??,1
则
xIff ?? ?1
且
yIff ??1?
证明：设任一 fyx ???,，则
1,???? fxy
xIXxxxff ?????? ? }|,{1 ?
yIYyyyff ?????? }|,{1?
此定理说明：可用双射函数 f和 1?f 的复合来生成
恒等函数。
§ 2逆函数和复合函数
,定理,, 若 f是一双射函数，则 ff ??? 11 )(
证明：设任一 fyx ???,则
1,???? fxy
ffyx ???? ?? 11 )(,
,定理,, 设 f,X→Y 和 g:Y→Z,且 f和 g均为双射函数，则有
111)( ??? ? gffg ??
§ 2逆函数和复合函数
证明：由给定条件 f,g均为双射函数,则
111 )(,,,??? fgfggf ?? 均为双射函数
设任一 Xx? 则 y=f(x),z=g(y)
fgzx ?? ???,1)(,????? fgxz ?
1,???? fxy? 且 1,???? gyz
11,?????? gfxz ?
∵ x是任意的 ∴ 有 111)( ??? ? gffg ??
§ 3基数的概念
1.基数的概念
对于有限集：集合中不同元素的个数。
对于无限集：？
是否所有无限集的基数都一样？
为了比较两个集合的“大小”，确定有限集和无限集的概念，
我们首先引进自然数集合。
,定义, 给定集合 A,A+=A?{A}，称 A+是 A的后继集合。
利用后继集合的概念来定义自然数集合 {0,1,2,?? }
§ 3基数的概念
设 A=?，则 A的后继集合可写成：
A+=??{?}={?}，（ A+） +={?}?{{?}}={?,{?}}
（（ A+） +） +={?,{?}}?{{?,{?}}}={?,{?},{?,{?}}}
令,?=0
则 ?+=0+=1，（ ?+） +=1+=2
上述求 0的后继集合而得到 N={0,1,2,?? }
Peano公理
(1)0?N (这里规定 0=?)
(2) n?N?n+?N (这里 n+是 n的后继数 )
(3)若 S?N，且 (ⅰ )0?S
(ⅱ )n?S?n+?S，则可得 S=N
§ 3基数的概念
,定义,, 给定二个集合 P和 Q，如果我们对 P中每一个不
同元素与 Q中每一个不同元素可以分别两两成对，则我们
说 P中的元素和 Q中的元素存在着一一对应。
例,P={1,3,5……2n -1,……} ——奇正数，
Q={2,4,6……2n,……} ——偶正数
则 P和 Q之间存在着一一对应，其函数关系为：
f:P→Q, f(n)=n+1,)(
??In
,定义,, 当且仅当集合 A的元素与集合 B的元素之间
存在着一一对应，则称 A与 B是等势的，记作,A~B。
例：在
?I
集合中，奇整数和偶整数集合是等势的。
f,A→B,f(x)=(x+1),f(1)=2,f(3)=4…
§ 3基数的概念
例,N和正偶整数集合 E是等势的。
证明：作一函数 f,N→E,且对任一 Nn?,有 f(n)=2n，则
ENf ?,为一一对应函数,∴ 有 N~E。
例：推广到对于有限集合，此定义也是适用的
设,A={1,2,3,4,5},B={a,b,c,d,e}，
定义一函数 f=
???
?
???
?
a b cd e
1 2 3 4 5 f为一双射函数,∴ A~B(|A|=|B|)
§ 3基数的概念
,定理,, 集合族上的等势关系是一等价关系
证明：设集合族为 S,任一 SCBA ?,,
则
SA?)1( 必有（ A~A）,自反的
SBA ?,)2( 若 A~B，则 B~A，对称的
SCBA ?,,)3( 若 A~B ? B~C，则 A~C，可传递的
例,P为全班同学的集合,P上的同姓关系是一等价关系，
其集合族 S={[张 ][李 ]…}
则同姓关系中的等势关系是一等价关系，即若 [张 ]~[李 ]的
等势关系是一等价关系。
§ 3基数的概念
,定义,, 如果从集合 {0,1,2,…n -1}是到集合 A的双
射函数，那么称 A是有限集合，若集合 A不是有限的，
则它一定是无限的。
此定义也可叙述为：基数为某一自然数的任何集合是有
限集合，反之为无限集合。
,定理,, 自然数集合 N是无限集合。
证明：设 Nn? 作一 f,{0,1,2…n -1}→N 的函数
f(x)=x
§ 3基数的概念
只要证明它不是双射函数，则 N一定为无限集合
定义一个 k，设 k=1+max{f(0),f(1)…f(n)},则 Nk?
}1,2,1{ ?? nx ? 中的元素不能和 k对应
n和 f是任意的,∴ N一定是无限集合
如果两个集合能够建立双射函数，则两集合元素间必
一一对应，该两集合具有相同的基数。
§ 4可数集与不可数集
,定义,, 与自然数集合等势的任何集合称为可数集合（或
称可数无限集合），它们的基数等于等于
0?
例：,.,, },.,,16,9,4,1{ 2nA ?,.,, },.,,27,8,1{ 3nB ?
.,, }3,.,,27,12,3{ 2nC ?,...}1,...
3
1,
2
1,1{
nD ?
则 |A|=|B|=|C|=|D|=
0?
§ 4可数集与不可数集
,定理,,实数的子集 (0,1)是不可数集。
证明：设集合 }10,|{
1 ???? xRxxR
（用反证法） R1是任一实数必可写成无限的十进制小数
........0 21 naaa 其中 ai是 0,1,2….9 中某个数
这里，我们规定，所有的有限小数都写成以 9为循环节
的循环小数（例如 0.2写成 0.19999…,）
现设 R1是可数集，则它的元素可编号如下：
§ 4可数集与不可数集
.,,.,,,.0
.
.
.,,.,,,.0
.,,.,,,.0
321
22322212
11312111
nnnnnn
n
n
aaaaa
aaaaa
aaaaa
?
?
?
而一切适合 0<x<1的实数应该完全在其中，现在我们构
造一个新的实数
........0 332211 nnbbbbb ?
§ 4可数集与不可数集
1
1
2
1
?
?
?
?
??
ii
ii
ii a
ab
所以 bii?aii，且 b也是 (0,1)区间的一个数，即 b∈R 1。但显然 b
与所有实数 a1,a2,a3? 都不相同。
因此 b?R1，这就产生了矛盾。
∴ R1是一个不可数集。
以上定理说明集合 R1与自然数集 N属于不同的基数类。
我们用 表示 R1的基数。
1?
§ 4可数集与不可数集
,定理,, 实数 R是不可数集，并且它的基数就是
12
1
2
10
1
1
)1(2
1
2
1
)(
:
1
??
??
?
?
?
?
?
??
?
?
?
?
?
x
x
x
x
xf
RRf
1?
证明：定义函数
这是一个由 R1到 R的双射，因此 R也是不可数集，且具有连
续基数
1?
集合论小结
通过第三，第四章的学习应该达到下面的基本要求：
（ 1） 能够正确地表示一个集合，会画文氏图。
（ 2） 能判定元素是否属于给定的集合。
（ 3） 能判断两个集合之间是否存在包含、相等或真包
含的关系。
（ 4） 能熟悉地进行集合的并，交，相对补，绝对补，
对称差运算，会计算幂集。
（ 5） 能正确地使用集合表达式、关系矩阵和关系图表
示给定的二元关系。
（ 6） 给定 A上的关系 R（可能是集合表达式，也可能
是关系矩阵或关系图），能判别 R的性质。
集合论小结
（ 7） 给定关系 R和 S，求 R?S；给定 A上的关系 R，求 Rn，
r(R),s(R),t(R)。
（ 8） 给定 A上的等价关系 R，求所有的等价类和商集
A/R，或者求与 R相对应的划分，以及给定 A的划分，
求对应的等价关系。
（ 9） 给定 A上的偏序关系，画出偏序集的哈斯图；给定
偏序集 <A,≤> 的哈斯图，求 A和 ≤的集合表达式。
（ 10） 确定偏序集的极大元、极小元、最大元、最小元、
最大下界和最小上界。
（ 11） 给定集合 A,B和 f，判别 f是否为 A到 B的函数，如
果是，说明是否为入射、满射、双射。
§ 3基数的概念
1.基数的概念
对于有限集：集合中不同元素的个数。
对于无限集：？
是否所有无限集的基数都一样？
为了比较两个集合的“大小”，确定有限集和无限集的概念，
我们首先引进自然数集合。
,定义, 给定集合 A,A+=A?{A}，称 A+是 A的后继集合。
利用后继集合的概念来定义自然数集合 {0,1,2,?? }
§ 3基数的概念
设 A=?，则 A的后继集合可写成：
A+=??{?}={?}，（ A+） +={?}?{{?}}={?,{?}}
（（ A+） +） +={?,{?}}?{{?,{?}}}={?,{?},{?,{?}}}
令,?=0
则 ?+=0+=1，（ ?+） +=1+=2
上述求 0的后继集合而得到 N={0,1,2,?? }
Peano公理
(1)0?N (这里规定 0=?)
(2) n?N?n+?N (这里 n+是 n的后继数 )
(3)若 S?N，且 (ⅰ )0?S
(ⅱ )n?S?n+?S，则可得 S=N
§ 3基数的概念
,定义,, 给定二个集合 P和 Q，如果我们对 P中每一个不
同元素与 Q中每一个不同元素可以分别两两成对，则我们
说 P中的元素和 Q中的元素存在着一一对应。
例,P={1,3,5……2n -1,……} ——奇整数，
Q={2,4,6……2n,……} ——偶整数
则 P和 Q之间存在着一一对应，其函数关系为：
f:P→Q, f(n)=n+1,)(
??In
,定义,, 当且仅当集合 A的元素与集合 B的元素之间
存在着一一对应，则称 A与 B是等势的，记作,A~B。
例：在
?I
集合中，奇整数和偶整数集合是等势的。
f,A→B,f(x)=(x+1),f(1)=2,f(3)=4…
§ 3基数的概念
例,N和正偶整数集合 E是等势的。
证明：作一函数 f,N→E,且对任一 Nn?,有 f(n)=2n，则
ENf ?,为一一对应函数,∴ 有 N~E。
例：推广到对于有限集合，此定义也是适用的
设,A={1,2,3,4,5},B={a,b,c,d,e}，
定义一函数 f=
???
?
???
?
a b cd e
1 2 3 4 5 f为一双射函数,∴ A~B(|A|=|B|)
§ 3基数的概念
,定理,, 集合族上的等势关系是一等价关系
证明：设集合族为 S,任一 SCBA ?,,
则
SA?)1( 必有（ A~A）,自反的
SBA ?,)2( 若 A~B，则 B~A，对称的
SCBA ?,,)3( 若 A~B ? B~C，则 A~C，可传递的
例,P为全班同学的集合,P上的同姓关系是一等价关系，
其集合族 S={[张 ][李 ]…}
则同姓关系中的等势关系是一等价关系。
§ 3基数的概念
,定义,, 如果 f是从集合 {0,1,2,…n -1}是到集合 A
的双射函数，那么称 A是有限集合，若集合 A不是有限
的，则它一定是无限的。
此定义也可叙述为：基数为某一自然数的任何集合是有
限集合，反之为无限集合。
,定理,, 自然数集合 N是无限集合。
证明：设 Nn? f 是任意从 {0,1,2…n -1}→N 的函数
§ 3基数的概念
定义一个 k，设 k=1+max{f(0),f(1)…f(n -1)},则 Nk?
}1,2,1{ ?? nx ? 中的元素不能和 k对应
因为 n和 f是任意的,∴ N一定是无限集合
如果两个集合能够建立双射函数，则两集合元素间必
一一对应，该两集合具有相同的势。
但
§ 4可数集与不可数集
,定义,, 与自然数集合等势的任何集合称为可数集合
（或称可数无限集合），它们的基数等于
0?
例：,.,, },.,,16,9,4,1{ 2nA ?,.,, },.,,27,8,1{ 3nB ?
.,, }3,.,,27,12,3{ 2nC ?,...}1,...
3
1,
2
1,1{
nD ?
则 |A|=|B|=|C|=|D|=
0?
§ 4可数集与不可数集
,定理,,实数的子集 (0,1)是不可数集。
证明：设集合 }10,|{
1 ???? xRxxR
（用反证法） R1是任一实数必可写成无限的十进制小数
........0 21 naaa 其中 ai是 0,1,2….9 中某个数
这里，我们规定，所有的有限小数都写成以 9为循环节
的循环小数（例如 0.2写成 0.19999…,）
现设 R1是可数集，则它的元素可编号如下：
§ 4可数集与不可数集
.,,.,,,.0
.
.
.,,.,,,.0
.,,.,,,.0
321
22322212
11312111
nnnnnn
n
n
aaaaa
aaaaa
aaaaa
?
?
?
而一切适合 0<x<1的实数应该完全在其中，现在我们构
造一个新的实数
........0 332211 nnbbbbb ?
§ 4可数集与不可数集
1
1
2
1
?
?
?
?
??
ii
ii
ii a
ab
所以 bii?aii，且 b也是 (0,1)区间的一个数，即 b∈ R1。但显然 b
与所有实数 a1,a2,a3… 都不相同。
因此 b?R1，这就产生了矛盾。
∴ R1是一个不可数集。
以上定理说明集合 R1与自然数集 N属于不同的基数类。
我们用 表示 R1的基数。
1?
§ 4可数集与不可数集
,定理,, 实数 R是不可数集，并且它的基数就是
12
1
2
10
1
1
)1(2
1
2
1
)(
:
1
??
??
?
?
?
?
?
??
?
?
?
?
?
x
x
x
x
xf
RRf
1?
证明：定义函数
这是一个由 R1到 R的双射，因此 R也是不可数集，且具有连
续基数
1?
集合论小结
通过第三，第四章的学习应该达到下面的基本要求：
（ 1） 能够正确地表示一个集合，会画文氏图。
（ 2） 能判定元素是否属于给定的集合。
（ 3） 能判断两个集合之间是否存在包含、相等或真包
含的关系。
（ 4） 能熟悉地进行集合的并，交，相对补，绝对补，
对称差运算，会计算幂集。
（ 5） 能正确地使用集合表达式、关系矩阵和关系图表
示给定的二元关系。
（ 6） 给定 A上的关系 R（可能是集合表达式，也可能
是关系矩阵或关系图），能判别 R的性质。
集合论小结
（ 7） 给定关系 R和 S，求 R?S；给定 A上的关系 R，求 Rn，
r(R),s(R),t(R)。
（ 8） 给定 A上的等价关系 R，求所有的等价类和商集 A/R，
或者求与 R相对应的划分，以及给定 A的划分，求对应
的等价关系。
（ 9） 给定 A上的偏序关系，画出偏序集的哈斯图；给定
偏序集 <A,≤> 的哈斯图，求 A和 ≤ 的集合表达式。
（ 10） 确定偏序集的极大元、极小元、最大元、最小元、
最大下界和最小上界。
（ 11） 给定集合 A,B和 f，判别 f是否为 A到 B的函数，如
果是，说明是否为入射、满射、双射。
例题选讲
例 1.设 A,B,C,D代表任意集合，判断以下命题是否
恒真，如果不是，请举一反例。
(1)A?B ? C?D?A?C ? B?D
(2)A?B ? C?D?A-D?B-C
(3)A?B ? B=A?(B-A)
(4)A-B=B-A ? A=B
解：
(1)不为真。举反例如下：
令 A＝ {1},B={1,4},C={2},D={2,3}
则 A?B且 C?D，但 A?C ＝ B?D，与结论矛盾。
例题选讲
(2)由于 C?D?～ D?～ C，又由 A ?B可得
A?～ D?B?～ C
即 A－ D ?B－ C成立。
(3)由于 A?(B－ A)=A ?B
故有：
B= A?(B－ A) ?B= A ?B ?A ?B
即 A ?B的充要条件为 B= A ?B或 A=A?B或 A－ B=?
例题选讲
(4)易见，当 A=B时，必有 A-B=B-A
由 A-B=B-A得 (A-B)?B=(B-A)?B
即,(A?~B)?B=(B?~A) ?B
即,B-A=?
∴ B?A
同理可证,A?B
从而得到,A＝ B
例题选讲
例 2.设,A,B是任意的集合
(1) 试证明 ?(A)??(B)=?(A?B)
(2) ?(A)??(B)=?(A?B)成立吗？为什么？
解,
(1)证明 S??(A)??(B)，则 S??(A)且 S??(B)，
因此,S?A且 S?B
∴ S? A?B 即 S??(A?B)
∴ ?(A)??(B)??(A?B)
反之，设 S??(A?B)，则 S?A?B，
例题选讲
因此 S?A且 S?B
∴ S??(A)且 S??(B)
于是 S??(A)??(B)
∴ ?(A?B)??(A)??(B)
由上知 ?(A)??(B)＝ ?(A?B)
(2) ?(A)??(B)??(A?B)成立。其证明如下：
设,S??(A)??(B)，则 S??(A)或 S??(B)
因此 S?A或 S?B
∴ S?A?B 即 S??(A?B)故 ?(A)??(B)??(A?B)
成立
例题选讲
?(A?B) ??(A)??(B)不成立
设,S??(A?B)，则 S?A?B。但此时无法推断 S?A，也
无法推断 S?B，因此既不能得出 S??(A)，也不能得出
S??(B)。
例如：
设 A={a,c},B={c,b}
则 A?B={a,b,c},设 S={a,b}，则 S?A?B
即 S??(A?B)
但 S??(A)且 S??(B)
因此 S??(A)??(B)
例题选讲
例 3,设 S={1,2,3,…10}, ≤是 S上的整除关系，求
<S,≤>的哈斯图，并求其中的最大元，最小元。
最小上界，最大下界。
分析：画哈斯图的关键在于确定结点的层次和元素间的
盖住关系。
画图的基本步骤是：
(1)确定偏序集 <A,≤>中的极小元，并将这些极小元放在
哈斯图的最底层；
(2)若第 n层的元素已确定完毕，从 A中剩余的元素中选
取至少能盖住第 n层中一个元素的元素，将这些元素
放在哈斯图的第 n+1层。
例题选讲
在排列结点的位置时，注意把盖住较多元素的结点放在
中间，将只盖住一个元素的结点放在两边，以减少连
线的交叉；
(3)将相邻两层的结点根据盖住关系进行连线。
例题选讲
在画哈斯图时应该注意下面几个问题：
(1)哈斯图中不应该出现三角形，如果出现三角形，一定
是盖住关系没找对。纠正的方法是重新考察这 3个元
素在偏序集中的顺序，然后将不满足盖住关系的那条
边去掉。
(2)哈斯图中不应该出现水平线段。出现这种错误的原因
在于没有将“较大”元素放在“较小”元素的上方。
纠正时只要根据“大小”顺序将“较大”的元素放到
更高的一层，将水平线改为斜线就可以了。
(3)哈斯图中要尽量减少线的交叉。图形中线的交叉多少
主要取决于同一层结点的排列顺序，
例题选讲
如果出现交叉过多，可以适当调整结点的排列顺序。
最后，如何确定哈斯图中极大元、极小元、最大元、最
小元、最小上界和最大下界。
方法如下：
(1)如果图中有孤立结点，那么这个结点既是极小元，也
是极大元，并且图中既无最小元，也无最大元。
（除只有唯一孤立结点的情况）
(2)除了孤立结点以外，其它的极小元是图中所有向下通
路的终点，其它的极大元是图中所有向上通路的终点。
例题选讲
例 4.设 Z+={x|x?Z?x>0},?1,?2是 Z+的 2个划分，
?1={{x}|x? Z+}，
?2={Z+ }，求划分 ?1,?2所 确定的 Z+上的等价关
系。
分析：等价关系和划分是两个不同的概念。等价关系是
有序对的集合，而划分是子集的集合。但对于给定的
集合 A,A上的等价关系 R和 A的划分 ?是一一对应的。
即,<x,y>?R?x 和 y在 ?的同一划分块里。
本题中,?1的划分块都是单元集，没有含两个以上
元素的划分块；
例题选讲
?2中只有一个划分块 Z+,Z+包含了集合中的全体元素。
∴ R1就是 Z+上的恒等关系；
R2就是 Z+上的全域关系。
例 5.对下面给定的集合 A和 B，构造从 A到 B的双射函数
]1,1[],23,2[ ??? BA ??
分析：
构造从集合 A到 B的双射函数，一般可采用下面的方法：
(1)若 A,B都是有穷集合，可以先用列元素的方法表示 A,B
例题选讲
然后，顺序将 A中的元素与 B中的元素建立对应。
(2)若 A,B是实数区间，可以采用直线方程作为从 A到 B
的双射函数。
例如,A＝ [1,2],B＝ [2,6]是实数区间。先将 A,B区间
分别标记在直角坐标系的 x轴和 y轴上，过 (1,2)和 (2,6)
两点的直线方程将 A中的每个数映到 B中的每一个数。
因此，该直线方程：
24)(,,??? xxfBAf
就是从 A到 B的双射函数。
例题选讲
这种通过直线方程构造双射函数的方法对任意两个同类
型的实数区间 (同为闭区间、开区间或半开半闭区间 )
都是适用的。此外，对于某些特殊的实数区间，可能
选择其它严格单调的初等函数更方便。
对于本题,
xxfBAf s i n)(,,??
(3)A是一个无穷集合,B是自然数集 N
只须将 A中的元素排成一个有序序列，且指定这个序列
的初始元素，这就叫做把 A“良序化”。
例如：构造从整数集 Z到自然数集 N的双射，如下排列：
例题选讲
Z,0,-1,1,-2,2,-3,3,…….
N,0,1,2,3,4,5,6,…….
即：
0
0
12
2)(,:
?
?
?
?
?
???? x
x
x
xxfNZf
显然 f是从 Z到 N的双射。
第四章 函 数
§ 1 函数的概念
§ 2 逆函数和复合函数
§ 3 基数的概念
§ 4* 可数集与不可数集
第四章 函数
函数是二元关系中特殊的一类，也就是说，函数是一种
特定类型的二元关系。本章讨论的是离散函数，它能
把一个有穷集合变换到另一个有穷集合。
例：在计算机上执行程序可以看作是函数的变换：
（自变量）输入 -----计算机 -----输出（函数值）
在这章我们主要讨论：函数定义、特殊函数及其性质、
函数的运算。最后利用函数的概念，特别是双射函数，
介绍一下无限集合的基数问题。
§ 1 函数的概念
１．函数的定义,
,定义, 设 X和 Y是任意两个集合,f是从 X→Y 的一种关
系，若对于每一个 x∈ X,都存在一个唯一的 y∈ Y,能
使 <x,y>∈ f, 则称关系 f为函数（映射）,并记为：
f,X→Y 。
讨论定义：
（ 1） f,X→Y 中，若 fyx ???,，则称 x为自变量，
与 x对应的 y称作 f作用下的象点（值）；
也可用 y=f(x)表示 fyx ???,,y称作函数 f在 x点处的值。
§ 1 函数的概念
（ 2） X中每一个元素均有定义,
∴ 函数 f的定义域 Xdom f ?
（ 3）对应于某一个 Xx?,其值 f(x)是唯一的，即
)(,,zyfzxfyx ?????????
（ 4） f 值域 Yra n f ?
))}(()(|{ xfyXxxyR f ?????
有时也记为 Rf
集合 Y称为 f 的共域
§ 1 函数的概念
例：判定下列关系是否为函数
XD f ?
YRf ?
是函数
XD f ?
不是函数
值不是唯一的
不是函数
§ 1 函数的概念
例：设 X=Y=R（实数）
},|,{)1( 2xyRyxyxf ??????
值是唯一的2,xyRD
f ??
},|,{)2( 2yxRyxyxg ??????
2yx ?
这不是函数，不满足值唯一性
§ 1 函数的概念
,定义,, 给定函数 f:A→B 和 g:C→D,如果 A=C,B=D，
并对所有的 Ax? 或 Cx?
都有 f(x)=g(x)，则称函数 f和 g是相等的，即 f=g。
２．函数的构成
例：设 X={a,b,c},Y={0,1}，则
}1,0,1,0,1,0,{ ?????????????? ccbbaaYX
YX ? 中，有 642 6 ? 个子集，
§ 1 函数的概念
但在 64个子集中只有 8个 )2( 3
符合函数的定义，这 8个函数为：
???
?
???
?????????
0 0 0}0,0,0,{0
a b ccbaf ??
?
?
???
??
0 0 11
a b cf
???
?
???
??
0 1 02
a b cf
???
?
???
??
0 1 13
a b cf
???
?
???
??
1 0 04
a b cf
???
?
???
??
1 1 06
a b cf
???
?
???
??
1 0 15
a b cf
???
?
???
??
1 1 17
a b cf
§ 1 函数的概念
讨论：从此例中可得到三点结论：
（ 1）设 |X|=m,|Y|=n，则函数 f,X→Y 中均是 m个序偶的集合；
（即序偶个数 =定义域的基数）
（ 2） X中每一个元素所对应的象点 f(x)可能是 Y中 n个，
从 X-Y的所有函数个数
mX nY ?|| |||| XY?
§ 1 函数的概念
（ 3） X→Y 有别函数的个数和 YX ? 子集个数的关系为：
nmmX YXnY ?????? 2||||
即二个集合之间能构成的函数个数比能构成的二元关系数少得多
3.几种特殊函数
,定义,, 给定函数 f,X→Y,如果值域 YR
f ?
则称 f为满射函数。
§ 1 函数的概念
例,满射函数一定有：
(1)|X|≥|Y|
YR f ?)2(
,定义,, 给定 f,X→Y,如果有 )()( 2121 xfxfxx ???
2121 )()( xxxfxf ???
或者,则称 f是入射函数。
§ 1 函数的概念
入射函数有：
?
?
?
?
?
||||)2(
)1(
YX
YR f
,定义,, 给定函数 f,X→Y,如果 f既是满射函数，
又是入射函数，则称 f为双射函数。
（或称“一一对应函数”，“一对一满射函数”）
§ 1 函数的概念
双射函数一定有：
（ 1）（值域）
YRf ?
（ 2）（定义域） |X|=|Y|
例：在全班同学的集合中，设,X={序号 },Y={姓名 }
则,f,X→Y 是一双射函数（序号和姓名的关系）
§ 2逆函数和复合函数
设 Ryx ???,，则 Rxy ~,???
现在讨论函数能否像二元关系那样得到逆函数呢？
先举一例
例：定义一函数
由例题可见：
f~)1( 的定义域不是 Y，而是 Y的子集
f~)2( 不满足函数定义：即值是唯一的
f~? 是一种二元关系，而不是函数
§ 2逆函数和复合函数
（ 3）一个函数的反函数存在的话，则此函数一定是双射函
数，而入射，满射函数的逆关系均不满足函数的定义
YXf ?:
（ 4）为了和逆关系相区别，函数 f的用“逆函数”
1?f 来表示
,定理,, 如果 f,X→Y 是双射函数，则有,XYf ??,1
也为双射函数。
,定义,, 设 是一双射函数，称 XYf ??,1
为 f的逆函数。
§ 2逆函数和复合函数
,定义,, 设 f,X→Y 和 g:W→Z 是二个函数，若 WXf ?)(
))}()((|,{ ygzxfyYyyZzXxzxfg ??????????????
则：
称 g在函数 f的左边可复合。
讨论定义：
(1)两个函数的复合是一个函数。
(2)函数 fg? 称为 f和 g的左复合，
这里和习惯上符合函数的书写求得一致。
例,sin(ln x)，先求 ln x，然后求 sin(ln x)
§ 2逆函数和复合函数
,定理,, 设 f:X→Y 和 g:Y→Z 是二个函数，于是复合函数
fg? 是一个从 X到 Z的函数，对于每一个 Xx? 有：
))(())(( xfgxfg ??
证明：有定义可知 fg? 是从 X→Z 的函数，即
)(,xfgzx ????
设,x∈X 由 f,X→Y 得 y=f(x)
设,y∈Y 由 g:Y→Z 得 z=g(y)
)()( ygzxfy ???由 得,))(())(( xfgxfgz ???
§ 2逆函数和复合函数
例：设 X={1,2,3},Y={p,q},Z={a,b}
f,X→Y={<1,p><2,p><3,q>}
g:Y→Z={<p,b><q,b>} 则：
},3,2,1{ ??????? bbbfg ?
fg ? 是 X→Z 的函数
上例的函数复合图为：
§ 2逆函数和复合函数
f,X→Y g:Y→Z )(xfg ?, X→Z
??gf ? ∴ 函数的复合运算不满足交换律。
§ 2逆函数和复合函数
,定理,, 函数的复合运算是可结合的，
即如果 f,g,h均为函数，则有：
fghfgh ???? )()( ?
证明：函数也是一种二元关系，
∵ 二元关系的复合是满足结合律的，
∴ 函数的复合也是满足结合律的。
例,I是整数集合,f,I→I 定义成 f(i)=2i+1，求复合函数
)(3 if 并证明它满足结合律。
§ 2逆函数和复合函数
解：
?)(3 if )1)12(2()12())(( ????? ififfifff ???
781681)1)12(2(2 ????????? iii
)(3 if 1)1)(2(21)(2))(( 22 ?????? ifififf
781681)1)12(2(2 ????????? iii
§ 2逆函数和复合函数
,定理,, 设 f,X→Y, g:Y→Z, fg? 是一合成函数，则：
(1)如果 f和 g都是满射函数，则 fg? 也是满射函数；
(2)如果 f和 g都是入射函数，则 fg? 也是入射函数；
(3)如果 f和 g都是双射函数，则 fg? 也是双射函数。
证明：（ 2）设任一
jiji xxXxx ???,
∵ f为入射函数,∴ )()(
ji xfxf ?
又 ∵ g为入射函数,且 )()(
ji xfxf ?
§ 2逆函数和复合函数
))(())(( ji xfgxfg ?? 即 )()( ji xfgxfg ?? ?
ji xx,? 是任一的，
fg ?? 也是单射函数。
可用同样的方法证明（ 1）和（ 3）
§ 2逆函数和复合函数
例：设
?I
是负整数集合，定义二个双射函数 f和 g，
?? ? IIf,
f(x)= - x ={<-1,1><-2,2>…},
NIg ??,g(x)= x-1={<1,0><2,1>…},
:fg? }1,20,1{)1)(())(( ?????????????? xxfgNI
是一双射函数。
§ 2逆函数和复合函数
,定义,, 给定 f,X→Y,如果对于所有的
Xx? 和某一个 y∈ Y,有 f(x)=y，则称 f为常函数。
例：
§ 2逆函数和复合函数
,定义,, 给定 XXI
x ?:,若对所有的 Xx? 有
xxI x ?)(,即 }|,{ XxxxI x ????
则称
xI
为恒等函数。
例：
§ 2逆函数和复合函数
,定理,, 对于任何函数 f,X→Y,其中
xI
是 X→X 的恒等函数，
yI
是 Y→Y 的恒等函数，则有
ffIIf yx ?? ??
X
X
Y
Y
§ 2逆函数和复合函数
,定理,, 如果函数 f,X→Y 有逆函数 XYf ??,1
则
xIff ?? ?1
且
yIff ??1?
证明：设任一 fyx ???,，则
1,???? fxy
xIXxxxff ?????? ? }|,{1 ?
yIYyyyff ?????? }|,{1?
此定理说明：可用双射函数 f和 1?f 的复合来生成
恒等函数。
§ 2逆函数和复合函数
,定理,, 若 f是一双射函数，则 ff ??? 11 )(
证明：设任一 fyx ???,则
1,???? fxy
ffyx ???? ?? 11 )(,
,定理,, 设 f,X→Y 和 g:Y→Z,且 f和 g均为双射函数，则有
111)( ??? ? gffg ??
§ 2逆函数和复合函数
证明：由给定条件 f,g均为双射函数,则
111 )(,,,??? fgfggf ?? 均为双射函数
设任一 Xx? 则 y=f(x),z=g(y)
fgzx ?? ???,1)(,????? fgxz ?
1,???? fxy? 且 1,???? gyz
11,?????? gfxz ?
∵ x是任意的 ∴ 有 111)( ??? ? gffg ??
§ 3基数的概念
1.基数的概念
对于有限集：集合中不同元素的个数。
对于无限集：？
是否所有无限集的基数都一样？
为了比较两个集合的“大小”，确定有限集和无限集的概念，
我们首先引进自然数集合。
,定义, 给定集合 A,A+=A?{A}，称 A+是 A的后继集合。
利用后继集合的概念来定义自然数集合 {0,1,2,?? }
§ 3基数的概念
设 A=?，则 A的后继集合可写成：
A+=??{?}={?}，（ A+） +={?}?{{?}}={?,{?}}
（（ A+） +） +={?,{?}}?{{?,{?}}}={?,{?},{?,{?}}}
令,?=0
则 ?+=0+=1，（ ?+） +=1+=2
上述求 0的后继集合而得到 N={0,1,2,?? }
Peano公理
(1)0?N (这里规定 0=?)
(2) n?N?n+?N (这里 n+是 n的后继数 )
(3)若 S?N，且 (ⅰ )0?S
(ⅱ )n?S?n+?S，则可得 S=N
§ 3基数的概念
,定义,, 给定二个集合 P和 Q，如果我们对 P中每一个不
同元素与 Q中每一个不同元素可以分别两两成对，则我们
说 P中的元素和 Q中的元素存在着一一对应。
例,P={1,3,5……2n -1,……} ——奇正数，
Q={2,4,6……2n,……} ——偶正数
则 P和 Q之间存在着一一对应，其函数关系为：
f:P→Q, f(n)=n+1,)(
??In
,定义,, 当且仅当集合 A的元素与集合 B的元素之间
存在着一一对应，则称 A与 B是等势的，记作,A~B。
例：在
?I
集合中，奇整数和偶整数集合是等势的。
f,A→B,f(x)=(x+1),f(1)=2,f(3)=4…
§ 3基数的概念
例,N和正偶整数集合 E是等势的。
证明：作一函数 f,N→E,且对任一 Nn?,有 f(n)=2n，则
ENf ?,为一一对应函数,∴ 有 N~E。
例：推广到对于有限集合，此定义也是适用的
设,A={1,2,3,4,5},B={a,b,c,d,e}，
定义一函数 f=
???
?
???
?
a b cd e
1 2 3 4 5 f为一双射函数,∴ A~B(|A|=|B|)
§ 3基数的概念
,定理,, 集合族上的等势关系是一等价关系
证明：设集合族为 S,任一 SCBA ?,,
则
SA?)1( 必有（ A~A）,自反的
SBA ?,)2( 若 A~B，则 B~A，对称的
SCBA ?,,)3( 若 A~B ? B~C，则 A~C，可传递的
例,P为全班同学的集合,P上的同姓关系是一等价关系，
其集合族 S={[张 ][李 ]…}
则同姓关系中的等势关系是一等价关系，即若 [张 ]~[李 ]的
等势关系是一等价关系。
§ 3基数的概念
,定义,, 如果从集合 {0,1,2,…n -1}是到集合 A的双
射函数，那么称 A是有限集合，若集合 A不是有限的，
则它一定是无限的。
此定义也可叙述为：基数为某一自然数的任何集合是有
限集合，反之为无限集合。
,定理,, 自然数集合 N是无限集合。
证明：设 Nn? 作一 f,{0,1,2…n -1}→N 的函数
f(x)=x
§ 3基数的概念
只要证明它不是双射函数，则 N一定为无限集合
定义一个 k，设 k=1+max{f(0),f(1)…f(n)},则 Nk?
}1,2,1{ ?? nx ? 中的元素不能和 k对应
n和 f是任意的,∴ N一定是无限集合
如果两个集合能够建立双射函数，则两集合元素间必
一一对应，该两集合具有相同的基数。
§ 4可数集与不可数集
,定义,, 与自然数集合等势的任何集合称为可数集合（或
称可数无限集合），它们的基数等于等于
0?
例：,.,, },.,,16,9,4,1{ 2nA ?,.,, },.,,27,8,1{ 3nB ?
.,, }3,.,,27,12,3{ 2nC ?,...}1,...
3
1,
2
1,1{
nD ?
则 |A|=|B|=|C|=|D|=
0?
§ 4可数集与不可数集
,定理,,实数的子集 (0,1)是不可数集。
证明：设集合 }10,|{
1 ???? xRxxR
（用反证法） R1是任一实数必可写成无限的十进制小数
........0 21 naaa 其中 ai是 0,1,2….9 中某个数
这里，我们规定，所有的有限小数都写成以 9为循环节
的循环小数（例如 0.2写成 0.19999…,）
现设 R1是可数集，则它的元素可编号如下：
§ 4可数集与不可数集
.,,.,,,.0
.
.
.,,.,,,.0
.,,.,,,.0
321
22322212
11312111
nnnnnn
n
n
aaaaa
aaaaa
aaaaa
?
?
?
而一切适合 0<x<1的实数应该完全在其中，现在我们构
造一个新的实数
........0 332211 nnbbbbb ?
§ 4可数集与不可数集
1
1
2
1
?
?
?
?
??
ii
ii
ii a
ab
所以 bii?aii，且 b也是 (0,1)区间的一个数，即 b∈R 1。但显然 b
与所有实数 a1,a2,a3? 都不相同。
因此 b?R1，这就产生了矛盾。
∴ R1是一个不可数集。
以上定理说明集合 R1与自然数集 N属于不同的基数类。
我们用 表示 R1的基数。
1?
§ 4可数集与不可数集
,定理,, 实数 R是不可数集，并且它的基数就是
12
1
2
10
1
1
)1(2
1
2
1
)(
:
1
??
??
?
?
?
?
?
??
?
?
?
?
?
x
x
x
x
xf
RRf
1?
证明：定义函数
这是一个由 R1到 R的双射，因此 R也是不可数集，且具有连
续基数
1?
集合论小结
通过第三，第四章的学习应该达到下面的基本要求：
（ 1） 能够正确地表示一个集合，会画文氏图。
（ 2） 能判定元素是否属于给定的集合。
（ 3） 能判断两个集合之间是否存在包含、相等或真包
含的关系。
（ 4） 能熟悉地进行集合的并，交，相对补，绝对补，
对称差运算，会计算幂集。
（ 5） 能正确地使用集合表达式、关系矩阵和关系图表
示给定的二元关系。
（ 6） 给定 A上的关系 R（可能是集合表达式，也可能
是关系矩阵或关系图），能判别 R的性质。
集合论小结
（ 7） 给定关系 R和 S，求 R?S；给定 A上的关系 R，求 Rn，
r(R),s(R),t(R)。
（ 8） 给定 A上的等价关系 R，求所有的等价类和商集
A/R，或者求与 R相对应的划分，以及给定 A的划分，
求对应的等价关系。
（ 9） 给定 A上的偏序关系，画出偏序集的哈斯图；给定
偏序集 <A,≤> 的哈斯图，求 A和 ≤的集合表达式。
（ 10） 确定偏序集的极大元、极小元、最大元、最小元、
最大下界和最小上界。
（ 11） 给定集合 A,B和 f，判别 f是否为 A到 B的函数，如
果是，说明是否为入射、满射、双射。
§ 3基数的概念
1.基数的概念
对于有限集：集合中不同元素的个数。
对于无限集：？
是否所有无限集的基数都一样？
为了比较两个集合的“大小”，确定有限集和无限集的概念，
我们首先引进自然数集合。
,定义, 给定集合 A,A+=A?{A}，称 A+是 A的后继集合。
利用后继集合的概念来定义自然数集合 {0,1,2,?? }
§ 3基数的概念
设 A=?，则 A的后继集合可写成：
A+=??{?}={?}，（ A+） +={?}?{{?}}={?,{?}}
（（ A+） +） +={?,{?}}?{{?,{?}}}={?,{?},{?,{?}}}
令,?=0
则 ?+=0+=1，（ ?+） +=1+=2
上述求 0的后继集合而得到 N={0,1,2,?? }
Peano公理
(1)0?N (这里规定 0=?)
(2) n?N?n+?N (这里 n+是 n的后继数 )
(3)若 S?N，且 (ⅰ )0?S
(ⅱ )n?S?n+?S，则可得 S=N
§ 3基数的概念
,定义,, 给定二个集合 P和 Q，如果我们对 P中每一个不
同元素与 Q中每一个不同元素可以分别两两成对，则我们
说 P中的元素和 Q中的元素存在着一一对应。
例,P={1,3,5……2n -1,……} ——奇整数，
Q={2,4,6……2n,……} ——偶整数
则 P和 Q之间存在着一一对应，其函数关系为：
f:P→Q, f(n)=n+1,)(
??In
,定义,, 当且仅当集合 A的元素与集合 B的元素之间
存在着一一对应，则称 A与 B是等势的，记作,A~B。
例：在
?I
集合中，奇整数和偶整数集合是等势的。
f,A→B,f(x)=(x+1),f(1)=2,f(3)=4…
§ 3基数的概念
例,N和正偶整数集合 E是等势的。
证明：作一函数 f,N→E,且对任一 Nn?,有 f(n)=2n，则
ENf ?,为一一对应函数,∴ 有 N~E。
例：推广到对于有限集合，此定义也是适用的
设,A={1,2,3,4,5},B={a,b,c,d,e}，
定义一函数 f=
???
?
???
?
a b cd e
1 2 3 4 5 f为一双射函数,∴ A~B(|A|=|B|)
§ 3基数的概念
,定理,, 集合族上的等势关系是一等价关系
证明：设集合族为 S,任一 SCBA ?,,
则
SA?)1( 必有（ A~A）,自反的
SBA ?,)2( 若 A~B，则 B~A，对称的
SCBA ?,,)3( 若 A~B ? B~C，则 A~C，可传递的
例,P为全班同学的集合,P上的同姓关系是一等价关系，
其集合族 S={[张 ][李 ]…}
则同姓关系中的等势关系是一等价关系。
§ 3基数的概念
,定义,, 如果 f是从集合 {0,1,2,…n -1}是到集合 A
的双射函数，那么称 A是有限集合，若集合 A不是有限
的，则它一定是无限的。
此定义也可叙述为：基数为某一自然数的任何集合是有
限集合，反之为无限集合。
,定理,, 自然数集合 N是无限集合。
证明：设 Nn? f 是任意从 {0,1,2…n -1}→N 的函数
§ 3基数的概念
定义一个 k，设 k=1+max{f(0),f(1)…f(n -1)},则 Nk?
}1,2,1{ ?? nx ? 中的元素不能和 k对应
因为 n和 f是任意的,∴ N一定是无限集合
如果两个集合能够建立双射函数，则两集合元素间必
一一对应，该两集合具有相同的势。
但
§ 4可数集与不可数集
,定义,, 与自然数集合等势的任何集合称为可数集合
（或称可数无限集合），它们的基数等于
0?
例：,.,, },.,,16,9,4,1{ 2nA ?,.,, },.,,27,8,1{ 3nB ?
.,, }3,.,,27,12,3{ 2nC ?,...}1,...
3
1,
2
1,1{
nD ?
则 |A|=|B|=|C|=|D|=
0?
§ 4可数集与不可数集
,定理,,实数的子集 (0,1)是不可数集。
证明：设集合 }10,|{
1 ???? xRxxR
（用反证法） R1是任一实数必可写成无限的十进制小数
........0 21 naaa 其中 ai是 0,1,2….9 中某个数
这里，我们规定，所有的有限小数都写成以 9为循环节
的循环小数（例如 0.2写成 0.19999…,）
现设 R1是可数集，则它的元素可编号如下：
§ 4可数集与不可数集
.,,.,,,.0
.
.
.,,.,,,.0
.,,.,,,.0
321
22322212
11312111
nnnnnn
n
n
aaaaa
aaaaa
aaaaa
?
?
?
而一切适合 0<x<1的实数应该完全在其中，现在我们构
造一个新的实数
........0 332211 nnbbbbb ?
§ 4可数集与不可数集
1
1
2
1
?
?
?
?
??
ii
ii
ii a
ab
所以 bii?aii，且 b也是 (0,1)区间的一个数，即 b∈ R1。但显然 b
与所有实数 a1,a2,a3… 都不相同。
因此 b?R1，这就产生了矛盾。
∴ R1是一个不可数集。
以上定理说明集合 R1与自然数集 N属于不同的基数类。
我们用 表示 R1的基数。
1?
§ 4可数集与不可数集
,定理,, 实数 R是不可数集，并且它的基数就是
12
1
2
10
1
1
)1(2
1
2
1
)(
:
1
??
??
?
?
?
?
?
??
?
?
?
?
?
x
x
x
x
xf
RRf
1?
证明：定义函数
这是一个由 R1到 R的双射，因此 R也是不可数集，且具有连
续基数
1?
集合论小结
通过第三，第四章的学习应该达到下面的基本要求：
（ 1） 能够正确地表示一个集合，会画文氏图。
（ 2） 能判定元素是否属于给定的集合。
（ 3） 能判断两个集合之间是否存在包含、相等或真包
含的关系。
（ 4） 能熟悉地进行集合的并，交，相对补，绝对补，
对称差运算，会计算幂集。
（ 5） 能正确地使用集合表达式、关系矩阵和关系图表
示给定的二元关系。
（ 6） 给定 A上的关系 R（可能是集合表达式，也可能
是关系矩阵或关系图），能判别 R的性质。
集合论小结
（ 7） 给定关系 R和 S，求 R?S；给定 A上的关系 R，求 Rn，
r(R),s(R),t(R)。
（ 8） 给定 A上的等价关系 R，求所有的等价类和商集 A/R，
或者求与 R相对应的划分，以及给定 A的划分，求对应
的等价关系。
（ 9） 给定 A上的偏序关系，画出偏序集的哈斯图；给定
偏序集 <A,≤> 的哈斯图，求 A和 ≤ 的集合表达式。
（ 10） 确定偏序集的极大元、极小元、最大元、最小元、
最大下界和最小上界。
（ 11） 给定集合 A,B和 f，判别 f是否为 A到 B的函数，如
果是，说明是否为入射、满射、双射。
例题选讲
例 1.设 A,B,C,D代表任意集合，判断以下命题是否
恒真，如果不是，请举一反例。
(1)A?B ? C?D?A?C ? B?D
(2)A?B ? C?D?A-D?B-C
(3)A?B ? B=A?(B-A)
(4)A-B=B-A ? A=B
解：
(1)不为真。举反例如下：
令 A＝ {1},B={1,4},C={2},D={2,3}
则 A?B且 C?D，但 A?C ＝ B?D，与结论矛盾。
例题选讲
(2)由于 C?D?～ D?～ C，又由 A ?B可得
A?～ D?B?～ C
即 A－ D ?B－ C成立。
(3)由于 A?(B－ A)=A ?B
故有：
B= A?(B－ A) ?B= A ?B ?A ?B
即 A ?B的充要条件为 B= A ?B或 A=A?B或 A－ B=?
例题选讲
(4)易见，当 A=B时，必有 A-B=B-A
由 A-B=B-A得 (A-B)?B=(B-A)?B
即,(A?~B)?B=(B?~A) ?B
即,B-A=?
∴ B?A
同理可证,A?B
从而得到,A＝ B
例题选讲
例 2.设,A,B是任意的集合
(1) 试证明 ?(A)??(B)=?(A?B)
(2) ?(A)??(B)=?(A?B)成立吗？为什么？
解,
(1)证明 S??(A)??(B)，则 S??(A)且 S??(B)，
因此,S?A且 S?B
∴ S? A?B 即 S??(A?B)
∴ ?(A)??(B)??(A?B)
反之，设 S??(A?B)，则 S?A?B，
例题选讲
因此 S?A且 S?B
∴ S??(A)且 S??(B)
于是 S??(A)??(B)
∴ ?(A?B)??(A)??(B)
由上知 ?(A)??(B)＝ ?(A?B)
(2) ?(A)??(B)??(A?B)成立。其证明如下：
设,S??(A)??(B)，则 S??(A)或 S??(B)
因此 S?A或 S?B
∴ S?A?B 即 S??(A?B)故 ?(A)??(B)??(A?B)
成立
例题选讲
?(A?B) ??(A)??(B)不成立
设,S??(A?B)，则 S?A?B。但此时无法推断 S?A，也
无法推断 S?B，因此既不能得出 S??(A)，也不能得出
S??(B)。
例如：
设 A={a,c},B={c,b}
则 A?B={a,b,c},设 S={a,b}，则 S?A?B
即 S??(A?B)
但 S??(A)且 S??(B)
因此 S??(A)??(B)
例题选讲
例 3,设 S={1,2,3,…10}, ≤是 S上的整除关系，求
<S,≤>的哈斯图，并求其中的最大元，最小元。
最小上界，最大下界。
分析：画哈斯图的关键在于确定结点的层次和元素间的
盖住关系。
画图的基本步骤是：
(1)确定偏序集 <A,≤>中的极小元，并将这些极小元放在
哈斯图的最底层；
(2)若第 n层的元素已确定完毕，从 A中剩余的元素中选
取至少能盖住第 n层中一个元素的元素，将这些元素
放在哈斯图的第 n+1层。
例题选讲
在排列结点的位置时，注意把盖住较多元素的结点放在
中间，将只盖住一个元素的结点放在两边，以减少连
线的交叉；
(3)将相邻两层的结点根据盖住关系进行连线。
例题选讲
在画哈斯图时应该注意下面几个问题：
(1)哈斯图中不应该出现三角形，如果出现三角形，一定
是盖住关系没找对。纠正的方法是重新考察这 3个元
素在偏序集中的顺序，然后将不满足盖住关系的那条
边去掉。
(2)哈斯图中不应该出现水平线段。出现这种错误的原因
在于没有将“较大”元素放在“较小”元素的上方。
纠正时只要根据“大小”顺序将“较大”的元素放到
更高的一层，将水平线改为斜线就可以了。
(3)哈斯图中要尽量减少线的交叉。图形中线的交叉多少
主要取决于同一层结点的排列顺序，
例题选讲
如果出现交叉过多，可以适当调整结点的排列顺序。
最后，如何确定哈斯图中极大元、极小元、最大元、最
小元、最小上界和最大下界。
方法如下：
(1)如果图中有孤立结点，那么这个结点既是极小元，也
是极大元，并且图中既无最小元，也无最大元。
（除只有唯一孤立结点的情况）
(2)除了孤立结点以外，其它的极小元是图中所有向下通
路的终点，其它的极大元是图中所有向上通路的终点。
例题选讲
例 4.设 Z+={x|x?Z?x>0},?1,?2是 Z+的 2个划分，
?1={{x}|x? Z+}，
?2={Z+ }，求划分 ?1,?2所 确定的 Z+上的等价关
系。
分析：等价关系和划分是两个不同的概念。等价关系是
有序对的集合，而划分是子集的集合。但对于给定的
集合 A,A上的等价关系 R和 A的划分 ?是一一对应的。
即,<x,y>?R?x 和 y在 ?的同一划分块里。
本题中,?1的划分块都是单元集，没有含两个以上
元素的划分块；
例题选讲
?2中只有一个划分块 Z+,Z+包含了集合中的全体元素。
∴ R1就是 Z+上的恒等关系；
R2就是 Z+上的全域关系。
例 5.对下面给定的集合 A和 B，构造从 A到 B的双射函数
]1,1[],23,2[ ??? BA ??
分析：
构造从集合 A到 B的双射函数，一般可采用下面的方法：
(1)若 A,B都是有穷集合，可以先用列元素的方法表示 A,B
例题选讲
然后，顺序将 A中的元素与 B中的元素建立对应。
(2)若 A,B是实数区间，可以采用直线方程作为从 A到 B
的双射函数。
例如,A＝ [1,2],B＝ [2,6]是实数区间。先将 A,B区间
分别标记在直角坐标系的 x轴和 y轴上，过 (1,2)和 (2,6)
两点的直线方程将 A中的每个数映到 B中的每一个数。
因此，该直线方程：
24)(,,??? xxfBAf
就是从 A到 B的双射函数。
例题选讲
这种通过直线方程构造双射函数的方法对任意两个同类
型的实数区间 (同为闭区间、开区间或半开半闭区间 )
都是适用的。此外，对于某些特殊的实数区间，可能
选择其它严格单调的初等函数更方便。
对于本题,
xxfBAf s i n)(,,??
(3)A是一个无穷集合,B是自然数集 N
只须将 A中的元素排成一个有序序列，且指定这个序列
的初始元素，这就叫做把 A“良序化”。
例如：构造从整数集 Z到自然数集 N的双射，如下排列：
例题选讲
Z,0,-1,1,-2,2,-3,3,…….
N,0,1,2,3,4,5,6,…….
即：
0
0
12
2)(,:
?
?
?
?
?
???? x
x
x
xxfNZf
显然 f是从 Z到 N的双射。
