集 合 论第四章 函 数
§ 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
则
xIff1
且
yIff1?
证明：设任一 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
则
xIff1
且
yIff1?
证明：设任一 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的双射。
