从现实生活中我们可以看到一些等势的例子,例如自然数3这个概念是人类从观察许多只含三个元素的集合的共同特点而加以抽象概括出来的,这个共同特点就是体现于这些被观察的任意一个集合的元素都可与集合 中元素存在一一对应,且其任意两个集合的元素之间也存在一一对应,我们可称这些集合是等势的。
定义12.2.1
对集合A和B,如果存在从A到B的双射函数,就称A和B等势,记作A≈
B,如果不存在从A到B的双射函数,就称A和B不等势,记作
注意,A≈B时不一定有A
= B,反之是一定成立的。
例1
N ≈ Z。
因为存在双射函数
例2
R ≈ R+,
其中R+是正实数集合。因为存在双射函数
f:
R→R+,
f(x)=ex。
例3
{a,b,c}≈3, 因为存在双射函数 f:{a,b,c}→3,
f(a)=0, f(b)=1,
f(c)=2. 例4
N× N≈
N。 因为在9.1节已定义了双射函数
f:N
× N→ N。
例5
N ≈ Q。
构造双射函数的方法类似于例4。 把Q的元素排成有序图形,
沿一条不重复地穿过整个图形的路径, 把Q的元素排成一列,
即把有理数和自然数一一配对。 所有分母为正的分数有序地排在图12.2.1中,Q的任一元素都在其中,
并且可以多次出现。 用箭头标注穿过图形的路径, 并用自然数标注次序。 但一个有理数的第二次及以后各次出现都要跳过去。 定义双射函数f:N→Q,
f(n)是[n]旁的有理数。
例如, f(4)=-1/1,
以后就要跳过-2/2, -3/3等。 图12.2.1

例6
(0,1)≈R。因为存在双射函数
f:(0,1)→R,
。 例7
[0,1]≈(0,1), 因为存在双射函数 f:(0,1)→(0,1),
上述各例表明, 无限集合可以与它的真子集等势, 有限集合却不能。
定理12.2.1
对任意的集合A, 有P(A)≈A2
证明
因为2={0,1}, 所以A2是所有函数f:A→{0,1}组成的集合。
构造双射函数 H:P(A)→A2,
H(B)=xB(x)。
其中xB(x)是以A为全集时B的特征函数。对任意的B∈P(A),
有B|A,
则存在唯一的特征函数xB(x)。
所以, H是函数。 对任意的g∈A,
则g:A→{0,1},
存在集合B为 B={x|x∈A∧g(x)=1},
则g(x)=xB(x)=H(B),
且这样的B是唯一的。 所以,
H是双射的。 定理12.2.2
对任意的集合A、B和C,
(1) A≈A
(2) 若A≈B,
B≈A,
(3) 若A≈B且B≈C,
则A≈C。
由定理可知N≈N×N≈Z≈Q,
且
R≈R+≈(0,1)≈[0,1]。
定理表明, 等势具有自反性, 对称性和传递性。 在一部分集合的集合上, 等势是等价关系。 但是所有集合的汇集不是集合, 所以不能说等势是"所有集合的集合"上的关系。
定理12.2.3
(康托尔)定理 (1) ┐N≈R,
(2) 对任意的集合A,┐A≈P(A)。
证明
(1)只要证明┐N≈[0,1]即可。
为此只要证明对任何函数f:N→[0,1],
都存在 x∈ [0,1],使x ran(f),
即任何函数f:N→[0,1]都不是双射的。
对任意一个f:N→[0,1],
顺序列出f 值
f(0)=x1=0.a11a21…an1…
f(1)=x2=0.a12a22…an2…
… f(n-1)=xn=0.a1na2n…ann…
… 其中aij
∈{0,1,…,9},对i,j=1,2,3,…。 为了使表示法唯一, 约定像0.4999…这样的数写成0.5000…。这样, 对i=1,2,3,…,
取bi∈{0,1,2,…,8},
使bi≠aij。 则有x=0.b1b2…bn…。
显然, x∈[0,1]。
但是x和任一xn比较,
因bn≠ann,
则x≠xn。
于是,x ran(f)。
所以, f 不可能是满射的,
即不存在双射函数f:N→[0,1]。
(2)对任意的函数g:A→P(A),
构造集合 B={x|x∈A∧x g(x)}。
显然, B A,
B∈P(A)。对任意的x∈A,有x∈B x g(x),则B≠g(x)。所以B ran(g),但B∈P(A),所以g不是满射的。不存在双射函数g:A→P(A)。
由定理12.2.1, P(N)≈N2,
可以证明P(N)≈R。因为N R,但┐N≈R,可以设想R和P(N)是比N大的集合。P(R)是比R大的集合。
P(P(R))是比P(R)大的集合。并可依此类推。
|