Skip to content
Cavill's Blog
Go back

如何使用伯恩斯坦定理

1,242 字

在讲解如何使用伯恩斯坦定理之前,首先需要了解什么是伯恩斯坦定理。

伯恩斯坦定理

对任意集合 A,BA,B,

A↪B⟺∃B0⊆B,A∼B0.A\hookrightarrow B \quad\Longleftrightarrow\quad \exists B_0\subseteq B,\quad A\sim B_0.

因此,下列两种表述等价:

若存在单射

f:A→B,g:B→A,f:A\to B, \qquad g:B\to A,

则存在双射

h:A→B.h:A\to B.

等价地,若存在子集

A0⊆A,B0⊆B,A_0\subseteq A, \qquad B_0\subseteq B,

使得

A∼B0,B∼A0,A\sim B_0, \qquad B\sim A_0,

则

A∼B.A\sim B.

换言之,

∣A∣≤∣B∣,∣B∣≤∣A∣⟹∣A∣=∣B∣.|A|\le |B|, \qquad |B|\le |A| \quad\Longrightarrow\quad |A|=|B|.
可以不看的证明

设

f:A→B,g:B→Af:A\to B,\qquad g:B\to A

都是单射。我们要证明:存在一个双射

h:A→B.h:A\to B.

令 A0=A∖g(B)A_0=A\setminus g(B),并递归定义 An+1=g(f(An))A_{n+1}=g(f(A_n))。再记 A∗=⋃n=0∞AnA_*=\bigcup_{n=0}^{\infty}A_n。

直观地说,A0A_0 是那些没有被 gg 映到的元素;从它们出发,沿着

A→fB→gAA\xrightarrow{f}B\xrightarrow{g}A

不断前进,得到集合 A∗A_*。

现在定义映射

h(x)={f(x),x∈A∗,g−1(x),x∉A∗.h(x)= \begin{cases} f(x), & x\in A_*,\\ g^{-1}(x), & x\notin A_*. \end{cases}

这个定义是合理的。因为 A0=A∖g(B)A_0=A\setminus g(B),所以只要 x∉A∗x\notin A_*,就必有 x∈g(B)x\in g(B),从而 g−1(x)g^{-1}(x) 存在。

下面证明 hh 是双射。

首先,hh 是单射。因为 ff 与 g−1g^{-1} 都是单射;此外,若 x∈A∗x\in A_*、y∉A∗y\notin A_*,且 f(x)=g−1(y)f(x)=g^{-1}(y),那么 y=g(f(x))∈A∗y=g(f(x))\in A_*,这与 y∉A∗y\notin A_* 矛盾。因此,两部分的像不会重合。

其次,hh 是满射。任取 b∈Bb\in B。若 b∈f(A∗)b\in f(A_*),则存在 a∈A∗a\in A_*,使得 h(a)=f(a)=bh(a)=f(a)=b。

若 b∉f(A∗)b\notin f(A_*),则 g(b)∉A∗g(b)\notin A_*。否则,若 g(b)∈A∗g(b)\in A_*,它不可能属于 A0A_0,于是必属于某个 An+1A_{n+1}。

由定义可得,对某个 a∈Ana\in A_n,有 g(b)=g(f(a))g(b)=g(f(a))。由于 gg 是单射,b=f(a)∈f(A∗)b=f(a)\in f(A_*),矛盾。因此,h(g(b))=g−1(g(b))=bh(g(b))=g^{-1}(g(b))=b。

所以 hh 既是单射又是满射,即为双射。故

∣A∣=∣B∣.|A|=|B|.

在了解定理之后,我们需要知道如何运用,这是非常关键和重要的,某种程度上我觉得比证明还重要,尽管数学教育本不该这样。事实上,即使我觉得曾经学高等数学的时候认为分析领域不算难(因为我觉得高等代数更折磨我),而且当时感觉自己掌握的还不错,但现在很多定理我完全不会证明,甚至忘记了。不过对于我深恶痛绝的考试制度而言,似乎完全没有影响……

总之,我们现在要通过具体的例子,来理解抽象的定理了。

例题一

证明:

(0,1]∼(0,1).(0,1]\sim(0,1).

证明

如果你注意力惊人,那么完全可以直接构造双射:

h(x)={12n+1,x=12n, n=0,1,2,…,x,其他情形.h(x)= \begin{cases} \dfrac{1}{2^{n+1}}, & x=\dfrac{1}{2^n},\ n=0,1,2,\dots,\\[8pt] x, & \text{其他情形}. \end{cases}

但一般来说,我们很难直接构造双射,因此伯恩斯坦定理会成为一个强大的工具。

我们可以这样来证明:

f:(0,1)⟶(0,1],f(x)=x.f:(0,1)\longrightarrow(0,1],\qquad f(x)=x. f(x)=f(y)⟹x=y,f(x)=f(y)\Longrightarrow x=y,

故 ff 为单射。

g:(0,1]⟶(0,1),g(x)=x2.g:(0,1]\longrightarrow(0,1),\qquad g(x)=\frac{x}{2}. g((0,1])=(0,12]⊂(0,1).g\bigl((0,1]\bigr)=\left(0,\frac12\right]\subset(0,1). g(x)=g(y)⟹x2=y2⟹x=y,g(x)=g(y) \Longrightarrow \frac{x}{2}=\frac{y}{2} \Longrightarrow x=y,

故 gg 为单射。

由伯恩斯坦定理:

(0,1)↪(0,1],(0,1]↪(0,1).(0,1)\hookrightarrow(0,1], \qquad (0,1]\hookrightarrow(0,1). (0,1)∼(0,1].(0,1)\sim(0,1].

例题二

取

N={0,1,2,… }.\mathbb{N}=\{0,1,2,\dots\}.

证明:

Z∼N.\mathbb{Z}\sim\mathbb{N}.

证明:

取

N={0,1,2,… }.\mathbb{N}=\{0,1,2,\dots\}.

定义

f:N⟶Z,f(n)=n.f:\mathbb{N}\longrightarrow\mathbb{Z},\qquad f(n)=n. f(m)=f(n)⟹m=n,f(m)=f(n) \Longrightarrow m=n,

故 ff 为单射。

定义

g:Z⟶N,g(z)={2z,z≥0,−2z−1,z<0.g:\mathbb{Z}\longrightarrow\mathbb{N},\qquad g(z)= \begin{cases} 2z, & z\ge 0,\\ -2z-1, & z<0. \end{cases}

设

g(x)=g(y).g(x)=g(y).

当

x,y≥0,x,y\ge 0,

有

2x=2y⟹x=y.2x=2y \Longrightarrow x=y.

当

x,y<0,x,y<0,

有

−2x−1=−2y−1⟹x=y.-2x-1=-2y-1 \Longrightarrow x=y.

当

x≥0,y<0,x\ge 0,\qquad y<0,

有

g(x)=2x,g(y)=−2y−1.g(x)=2x, \qquad g(y)=-2y-1.

前者为偶数,后者为奇数,故不可能有

g(x)=g(y).g(x)=g(y).

同理,

x<0,y≥0x<0,\qquad y\ge 0

时也不可能有

g(x)=g(y).g(x)=g(y).

故 gg 为单射。

N↪Z,Z↪N.\mathbb{N}\hookrightarrow\mathbb{Z}, \qquad \mathbb{Z}\hookrightarrow\mathbb{N}.

由伯恩斯坦定理,

Z∼N.\mathbb{Z}\sim\mathbb{N}.

例题三

设

A⊆B⊆C,A∼CA\subseteq B\subseteq C, \qquad A\sim C

证明:

A∼BA\sim B

证明

设

A⊇B⊇C,A∼C.A\supseteq B\supseteq C, \qquad A\sim C.

则存在双射

h:A→C.h:A\to C.

由于

C⊆B,C\subseteq B,

包含映射

j:C→B,j(x)=xj:C\to B,\qquad j(x)=x

为单射。因此,

j∘h:A→Bj\circ h:A\to B

为单射。

另一方面,由于

B⊆A,B\subseteq A,

包含映射

i:B→A,i(x)=xi:B\to A,\qquad i(x)=x

为单射。

于是,

A↪B,B↪A.A\hookrightarrow B, \qquad B\hookrightarrow A.

由伯恩斯坦定理,

A∼B.A\sim B.

证明范式

在看过这两道比较经典的习题之后,我们也可以总结出证明两个集合对等的范式。

定义

依循定义,构造双射。

伯恩斯坦定理

  1. 设两个集合分别为 A,BA,B;
  2. 构造单射 f:A→Bf:A\to B;
  3. 构造单射 g:B→Ag:B\to A;
  4. 由伯恩斯坦定理,得到 ∣A∣=∣B∣|A|=|B|。

Edit page
Share this post:

Previous Post
如何在Notion数据库里的属性中自动化添加字数和预计阅读时间
Next Post
Why we need CNN