在讲解如何使用伯恩斯坦定理之前,首先需要了解什么是伯恩斯坦定理。
对任意集合 A,B,
A↪B⟺∃B0⊆B,A∼B0.因此,下列两种表述等价:
若存在单射
f:A→B,g:B→A,则存在双射
h:A→B.等价地,若存在子集
A0⊆A,B0⊆B,使得
A∼B0,B∼A0,则
A∼B.换言之,
∣A∣≤∣B∣,∣B∣≤∣A∣⟹∣A∣=∣B∣.
可以不看的证明
设
f:A→B,g:B→A
都是单射。我们要证明:存在一个双射
h:A→B.
令 A0=A∖g(B),并递归定义 An+1=g(f(An))。再记 A∗=⋃n=0∞An。
直观地说,A0 是那些没有被 g 映到的元素;从它们出发,沿着
AfBgA
不断前进,得到集合 A∗。
现在定义映射
h(x)={f(x),g−1(x),x∈A∗,x∈/A∗.
这个定义是合理的。因为 A0=A∖g(B),所以只要 x∈/A∗,就必有 x∈g(B),从而 g−1(x) 存在。
下面证明 h 是双射。
首先,h 是单射。因为 f 与 g−1 都是单射;此外,若 x∈A∗、y∈/A∗,且 f(x)=g−1(y),那么 y=g(f(x))∈A∗,这与 y∈/A∗ 矛盾。因此,两部分的像不会重合。
其次,h 是满射。任取 b∈B。若 b∈f(A∗),则存在 a∈A∗,使得 h(a)=f(a)=b。
若 b∈/f(A∗),则 g(b)∈/A∗。否则,若 g(b)∈A∗,它不可能属于 A0,于是必属于某个 An+1。
由定义可得,对某个 a∈An,有 g(b)=g(f(a))。由于 g 是单射,b=f(a)∈f(A∗),矛盾。因此,h(g(b))=g−1(g(b))=b。
所以 h 既是单射又是满射,即为双射。故
∣A∣=∣B∣.
在了解定理之后,我们需要知道如何运用,这是非常关键和重要的,某种程度上我觉得比证明还重要,尽管数学教育本不该这样。事实上,即使我觉得曾经学高等数学的时候认为分析领域不算难(因为我觉得高等代数更折磨我),而且当时感觉自己掌握的还不错,但现在很多定理我完全不会证明,甚至忘记了。不过对于我深恶痛绝的考试制度而言,似乎完全没有影响……
总之,我们现在要通过具体的例子,来理解抽象的定理了。
例题一
证明:
(0,1]∼(0,1).
证明
如果你注意力惊人,那么完全可以直接构造双射:
h(x)=⎩⎨⎧2n+11,x,x=2n1, n=0,1,2,…,其他情形.
但一般来说,我们很难直接构造双射,因此伯恩斯坦定理会成为一个强大的工具。
我们可以这样来证明:
f:(0,1)⟶(0,1],f(x)=x.
f(x)=f(y)⟹x=y,
故 f 为单射。
g:(0,1]⟶(0,1),g(x)=2x.
g((0,1])=(0,21]⊂(0,1).
g(x)=g(y)⟹2x=2y⟹x=y,
故 g 为单射。
由伯恩斯坦定理:
(0,1)↪(0,1],(0,1]↪(0,1).
(0,1)∼(0,1].
例题二
取
N={0,1,2,…}.
证明:
Z∼N.
证明:
取
N={0,1,2,…}.
定义
f:N⟶Z,f(n)=n.
f(m)=f(n)⟹m=n,
故 f 为单射。
定义
g:Z⟶N,g(z)={2z,−2z−1,z≥0,z<0.
设
g(x)=g(y).
当
x,y≥0,
有
2x=2y⟹x=y.
当
x,y<0,
有
−2x−1=−2y−1⟹x=y.
当
x≥0,y<0,
有
g(x)=2x,g(y)=−2y−1.
前者为偶数,后者为奇数,故不可能有
g(x)=g(y).
同理,
x<0,y≥0
时也不可能有
g(x)=g(y).
故 g 为单射。
N↪Z,Z↪N.
由伯恩斯坦定理,
Z∼N.
例题三
设
A⊆B⊆C,A∼C
证明:
A∼B
证明
设
A⊇B⊇C,A∼C.
则存在双射
h:A→C.
由于
C⊆B,
包含映射
j:C→B,j(x)=x
为单射。因此,
j∘h:A→B
为单射。
另一方面,由于
B⊆A,
包含映射
i:B→A,i(x)=x
为单射。
于是,
A↪B,B↪A.
由伯恩斯坦定理,
A∼B.
证明范式
在看过这两道比较经典的习题之后,我们也可以总结出证明两个集合对等的范式。
定义
依循定义,构造双射。
伯恩斯坦定理
- 设两个集合分别为 A,B;
- 构造单射 f:A→B;
- 构造单射 g:B→A;
- 由伯恩斯坦定理,得到 ∣A∣=∣B∣。