可数与不可数，$Schroeder-Bernstein$定理

$A:$实数的性质

$A1)$ 假设非空集合$X\subset R$有上界并且实数$M$是$X$的上界。证明，如下两个命题等价：
– $M=\sup X$
– 对任意的$\epsilon >0$，都存在$x\in X$，使得$x>M-\epsilon$

证明：$M=\sup X$，等价于$M$是上界集的最小元，设$\epsilon >0$，则有$M-\epsilon <M$，而第二个条件等价于$M-\epsilon$不是$X$的上界，根据定义两者等价是显然的。

$A2)$ 证明，每个⾮空开区间都包含⽆限多个有理数。

证明：设$I=(a,b)$是一个非空开区间即$a<b$，那么根据有理数在实数中的稠密性一定存在$l,r\in \mathbb{Q},a<l<\frac{a+b}{2}<r<b$，定义序列$x_n=l+\frac{r-l}{2^n}$，这是一个严格递减的序列从而没有相同的两项，并且根据有理数对四则运算的封闭性{xn}⊂Q\{x_n\}\sub\mathbb{Q}{xn​}⊂Q，并且$a<l<x_n<r<b$即{xn}⊂(a,b)\{x_n\}\sub(a,b){xn​}⊂(a,b)，从而$I$中包含了无穷多个有理数，得证。

$A3)$ $(X,d)$是距离空间，$Y\subset X$。我们定义$Y$上的距离函数:
$$d_Y:Y\times Y\to R,(y_1,y_2)\mapsto d_Y(y_1,y_2)=d(y_1,y_2)$$

证明，$d_Y$是$Y$上的距离函数，从而$(Y,d_Y)$是度量空间。我们称$d_Y$是$d$在$Y$上的诱导度量，$(Y,d_Y)$称作是$(X,d)$的子（度量）空间。

证明：验证定义即可。设$x,y,z\in Y$：

$1)$ 正定性：$d_Y(x,y)=d(x,y)\ge 0$，$d_Y(x,y)=0$当且仅当$d(x,y)=0$当且仅当$x=y$。

$2)$ 对称性：$d_Y(x,y)=d(x,y)=d(y,x)=d_Y(y,x)$。

$3)$ 三角不等式：$d_Y(x,y)+d_Y(y,z)=d(x,y)+d(y,z)\ge d(x,z)=d_Y(x,z)$。

$A4)$ ${\mathbb{R}}^n=\mathbb{R}\times \cdot \cdot \cdot \times \mathbb{R}(n个)=\{(x_1,\cdot \cdot \cdot ,x_n)|x_1,\cdot \cdot \cdot ,x_n\in \mathbb{R}\}$。对于$x,y\in {\mathbb{R}}^n$，我们定义：

$$d(x,y)=\sqrt{(x_1-y_1{)}^2+\cdot \cdot \cdot +(x_n-y_n{)}^2},x=(x_1,\cdot \cdot \cdot ,x_n),y=(y_1,\cdot \cdot \cdot ,y_n)$$

证明，$({\mathbb{R}}^n,d)$是度量空间。

证明：逐一验证定义。设$x,y,z\in {\mathbb{R}}^n$，其中$x=(x_1,\cdot \cdot \cdot ,x_n),y=(y_1,\cdot \cdot \cdot ,y_n),z=(z_1,\cdot \cdot \cdot ,z_n)$：

$1)$ 正定性：$d(x,y)=\sqrt{(x_1-y_1{)}^2+\cdot \cdot \cdot +(x_n-y_n{)}^2}\ge 0$，且$d(x,y)=\sqrt{(x_1-y_1{)}^2+\cdot \cdot \cdot +(x_n-y_n{)}^2}=0$当且仅当$(x_1-y_1{)}^2+\cdot \cdot \cdot +(x_n-y_n{)}^2=0$，由于$(x_i-y_i{)}^2\ge 0$取等当且仅当$x_i=y_i$，从而$d(x,y)=0$当且仅当$x_1=y_1,\cdot \cdot \cdot ,x_n=y_n$，即$x=y$。

$2)$ 对称性：$d(x,y)=\sqrt{(x_1-y_1{)}^2+\cdot \cdot \cdot +(x_n-y_n{)}^2}=\sqrt{(y_1-x_1{)}^2+\cdot \cdot \cdot +(y_n-x_n{)}^2}=d(y,x)$。

$3)$ 三角不等式：$(d(x,y)+d(y,z){)}^2=(\sqrt{(x_1-y_1{)}^2+\cdot \cdot \cdot +(x_n-y_n{)}^2}+\sqrt{(y_1-z_1{)}^2+\cdot \cdot \cdot +(y_n-z_n{)}^2}{)}^2=(x_1-y_1{)}^2+\cdot \cdot \cdot +(x_n-y_n{)}^2+(y_1-z_1{)}^2+\cdot \cdot \cdot +(y_n-z_n{)}^2+2\sqrt{((x_1-y_1{)}^2+\cdot \cdot \cdot +(x_n-y_n{)}^2)((y_1-z_1{)}^2+\cdot \cdot \cdot +(y_n-z_n{)}^2)}\ge (x_1-y_1{)}^2+2(x_1-y_1)(y_1-z_1)+(y_1-z_1{)}^2+\cdot \cdot \cdot +(x_n-y_n{)}^2+2(x_n-y_n)(y_n-z_n)+(y_n-z_n{)}^2=(x_1-z_1{)}^2+\cdot \cdot \cdot +(x_n-z_n{)}^2=(d(x,z){)}^2$，其中不等号是来源于$Cauchy-Schwarz$不等式。

$A5)$（重要）给定距离空间$(X,d),Y\subset X$是子集。如果对任意的$x\in X$ 和任意的$\epsilon >0$，都存在$y\in Y$，使得$d(y,x)<\epsilon$，我们就称$Y$在$X$中是稠密的。证明，有理数在$\mathbb{R}$中（距离函数由两个数的差的绝对值定义）是稠密的。

证明：等价的命题已在过去证明过。

$A6)$ 对于$(x,y)\in {\mathbb{R}}^2$，如果它的坐标$x$和$y$都是有理数，我们就称这个点是有理点。证明，$({\mathbb{R}}^2,d)$中的有理点是稠密的。

证明：注意到这里的距离函数$d$定义为$d((a_1,a_2),(b_1,b_2))=\sqrt{(a_1-b_1{)}^2+(a_2-b_2{)}^2}$。设$(x,y)\in {\mathbb{R}}^2$，设$\epsilon >0$，根据有理数在$\mathbb{R}$中的稠密性，存在$x^{\prime },y^{\prime }\in \mathbb{Q},|x-x^{\prime }|<\frac{\epsilon }{\sqrt{2}},|y-y^{\prime }|<\frac{\epsilon }{\sqrt{2}}$，显然$d((x^{\prime },y^{\prime }),(x,y))<\epsilon$，得证。

$A7)$ 证明，假定域公理$(F)$和序公理$(O)$，确界原理可以推出 $Archimedes$公理$(A)$。

证明：设$a>0,b\in \mathbb{R}$，想要证明存在$k\in \mathbb{Z},ka>b$。不妨设$b>0$，定义K={k∈Z∣ka≤b}K=\{k\in\Z|ka\le b\}K={k∈Z∣ka≤b}，显然对于每个$k\in K,k\le b{a}^{-1}$，因此$K$有上界从而有上确界$\sup K$，令$k_0=\sup K=[b{a}^{-1}]$，这里$[\cdot ]$表示下取整函数。从而$k_0+1\notin K$即$(k_0+1)a>b$，证毕。

$A8)$ （无理数的存在性）令X={x∈R∣x2≤2}X=\{x\in\R|x^2\le 2\}X={x∈R∣x2≤2}，这是一个有界的集合。令$\sqrt{2}=\sup X$。证明，$\sqrt{2}$不是有理数。

证明：已经在过去证明过。

$A9)$ 证明，每个开区间总包含无穷多个无理数。

证明：设开区间$(l,r)$，取$x_n=l+\frac{r-l}{2^n}\cdot \sqrt{2}$，显然$x_n$不是有理数并且$l<x_n<r$。注意到{xn}\{x_n\}{xn​}单调递减从而互不重复，从而开区间内包含了无穷多个无理数。

---

$B:$可数与不可数

令$\mathbb{N}$表示自然数的集合(包括$0$)。$X$是一个集合，如果存在单射$f:X\to \mathbb{N}$，我们就称$X$是可数的。如果$X$不是可数的，我们就称它是不可数的。

$B1)$ 证明，有限集是可数的。

证明：执行以下步骤：（设$X_1=X$）

第$j$步：当$X_j=\varnothing$时结束，否则从$X_j$中取一个元素$x_j$，定义$f(x_j)=j$然后定义Xj+1=Xj−{xj}X_{j+1}=X_j-\{x_j\}Xj+1​=Xj​−{xj​}

显然上述步骤会于有限步内结束因为$X$是有限集，且$f$显然是一个单射因为每一次赋的函数值不同。

$B2)$ 证明，可数集合的子集是可数的。

证明：设$X$是一个可数集而$Y\subset X$，那么$f{|}_Y:Y\to \mathbb{N},y\mapsto f(y)$是$f$在$Y$上的限制，这显然还是个单射。

$B3)$ 证明，如果$X$是可数集，那么我们总可以将$X$写成X={x1,x2,x3,⋯ }X=\{x_1,x_2,x_3,\cdots\}X={x1​,x2​,x3​,⋯}（即可以把$X$中的元素用自然数来标号）。（我们可以从一开始一个一个地数下去把这些元素都罗列出来，所以叫做可数集）

证明：显然$\mathbb{N}$的子集都可数（考虑恒等映射即可），从而f(X)={n∈N∣存在x∈X,使得f(x)=n}f(X)=\{n\in\N|存在x\in X,使得f(x)=n\}f(X)={n∈N∣存在x∈X,使得f(x)=n}是可数的。自然数集有下界从而其子集也有下界，因而$f(X)$及其任意子集的最小元都存在。执行以下步骤：（设$Y_1=f(X)$）

第$j$步，取$Y_j$的最小元$y_j$，定义$g(y_j)=j$，然后定义Yj+1=Yj−{yj}Y_{j+1}=Y_j-\{y_j\}Yj+1​=Yj​−{yj​}。

那么$f(X)$中的任意元素都被赋了一个相应于函数$g$的函数值（因为第$j$小的元素一定在第$j$步被取出），即构造了g:f(X)→{1,2,3,⋯ }g:f(X)\rightarrow \{1,2,3,\cdots\}g:f(X)→{1,2,3,⋯}，从而$f:X\to f(X)$和$g:f(X)\to g(f(X))$都是双射，从而$g\circ f:X\to g(f(X))$是双射因而存在着逆映射$\tau :g(f(X))\to X$。据此定义$x_j=\tau (j)$即可。

$B5)$ 证明，可数个可数集的并也是可数集，也就是说，如果$X_1,X_2,\cdots ,X_n,\cdots$都是可数集，那么它们的并集${\bigcup }_{n\in \mathbb{N}}{X}_n$也是可数集。

证明：如下列出各集合并按照箭头顺序从小到大标号即可。

$B4)$ 证明，有理数$\mathbb{Q}$是可数集。

证明：定义Xj={nj∣n∈N}X_j=\{\frac{n}{j}|n\in\N\}Xj​={jn​∣n∈N}显然可数，那么${\mathbb{Q}}_{\ge 0}={\bigcup }_{n\in \mathbb{N}}{X}_n$也可数，同理${\mathbb{Q}}_{\le 0}$也可数，从而$\mathbb{Q}$可数。

$B6)$ 证明，$X$是可数的，映射$f:X\to Y$是满射。证明，$Y$是可数的。

证明：这是因为满射可以诱导出一个逆向的单射$g:Y\to X$，即对任意的$y\in Y$，显然{x∈X∣f(x)=y}\{x\in X|f(x)=y\}{x∈X∣f(x)=y}非空，从中任取一个定义为$g(y)$，此时$g$是单射，因为假设$g(a)=g(b)$，就有$f(g(a))=f(g(b))$，而根据定义$f(g(a))=a,f(g(b))=b$，从而$a=b$。而$X$可数，从而存在单射$h:X\to \mathbb{N}$，那么$h\circ g:Y\to \mathbb{N}$也是单射，得证。

$B7)$ 按照以下步骤证明$\mathbb{R}$是不可数的：

$B7-1)$ $J\subset \mathbb{R}$是闭区间并且它的长度$|J|>0$。证明，对任意的$x\in \mathbb{R}$，总存在闭区间$I$，使得$I\subset J,|I|>0,x\notin I$。

证明：不妨设$x\in J=[l,r]$且$x\ne l$，取$I=[l,\frac{x+l}{2}]$即符合要求。

$B7-2)$ 证明，如果{x1,x2,⋯ }\{x_1,x_2,\cdots\}{x1​,x2​,⋯}是$\mathbb{R}$的一个可数子集，那么存在闭区间套$I_1\supset I_2\supset \cdots$，使得对任意的$n,x_n\notin I_n$。

证明：在R−{x1}\R-\{x_1\}R−{x1​}中取一个闭区间定义为$I_1$。对于$I_n$，取$I_{n+1}\subset I_n$，使得$x_{n+1}\notin I_{n+1}$，$B7-1)$保证这样的$I_{n+1}$是存在的。从而得到区间套。

$B7-3)$ 证明，$\mathbb{R}$不可数。

证明：用反证法，假设$\mathbb{R}$可数，那么有R={x1,x2,⋯ }\R=\{x_1,x_2,\cdots\}R={x1​,x2​,⋯}，由$B7-2)$得存在闭区间套$I_1\supset I_2\supset \cdots$，使得对任意的$n,x_n\notin I_n$，从而对任意的$x_n\in \mathbb{R}$，$x_n\notin {\bigcap }_{n>0}{I}_n$因为$x_n\notin I_n$，因而${\bigcap }_{n>0}{I}_n=\varnothing$，与区间套公理矛盾。从而$\mathbb{R}$不可数。

$B8)$ 证明，如果$X$是不可数集，$A$是$X$的可数子集，那么$X-A$是不可数的。

证明：否则$X=(X-A)\cup A$可数。

$B9)$ 证明，任意的长度不为$0$的区间（无论开或闭）都是不可数的。

证明：用反证法，假设区间$(l,r)$是可数的，在这个区间内部可以取出一个区间套$I_1\supset I_2\supset \cdots$使得${\bigcap }_{n>0}{I}_n$不包含任意的$(l,r)$中的元素，然而由于这个区间套取自$(l,r)$即$I_1\subset (l,r)$因此${\bigcap }_{n>0}{I}_n$也不包含$\mathbb{R}-(l,r)$中的元素，从而${\bigcap }_{n>0}{I}_n=\varnothing$，与区间套公理矛盾。因此$(l,r)$不可数。闭区间的情形是类似的。

$B10)$ 证明，复数$\mathbb{C}$是不可数的。

证明：由于可数集的子集可数，可知子集不可数的集合不可数，由于$\mathbb{R}\subset \mathbb{C}$可知$\mathbb{C}$不可数。

$B11)$ 假设$\mathcal{I}$是$\mathbb{R}$上某些开区间组成的集合，它满足如下性质：对任意的$I,J\in \mathcal{I},I\ne J$，那么它们的交集是空集，即$I\cap J=\varnothing$。证明，$\mathcal{I}$是可数集。

证明：由于任意开区间总包含无限个有理数，定义$f:\mathcal{I}\to \mathbb{Q}$，对于$I\in \mathcal{I}$，定义$f(I)$为$I$中某个有理数。那么$f$是一个单射，因为假设$f(I)=f(J)=p\in \mathbb{Q}$，那么$p\in I\cap J$即$I\cap J\ne \varnothing$从而$I=J$（否则两个开区间交集为空）。由于有理数是可数的即存在单射$g:\mathbb{Q}\to \mathbb{N}$，因而$g\circ f:\mathcal{I}\to \mathbb{N}$是单射，因而$\mathcal{I}$可数。

---

$C:$ $Schroeder-Bernstein$定理

假设$X$和$Y$是两个集合，映射$f:X\to Y$和$g:Y\to X$都是单射。我们令$X^{\prime }=X-g(Y)。$

$C1)$ 如果$X$是有限集，证明，存在$\phi :X\to Y$，使得$\phi$是双射。

证明：设X={x1,⋯ ,xn},Y={y1,⋯ ,ym}X=\{x_1,\cdots,x_n\},Y=\{y_1,\cdots,y_m\}X={x1​,⋯,xn​},Y={y1​,⋯,ym​}。由于存在由$X$到$Y$的单射，有$n\le m$，同理$n\ge m$，从而$n=m$。定义$\phi :X\to Y,x_j\mapsto y_j$符合要求。

$C2)$ 如果$X$是可数集，证明，存在$\phi :X\to Y$，使得$\phi$是双射。

证明：设$X$是有限集，由于存在$Y$到$X$的单射，$Y$也必为有限集（否则取{y1,⋯ ,yn+1}⊂Y\{y_1,\cdots,y_{n+1}\}\sub Y{y1​,⋯,yn+1​}⊂Y，其中$n$是$X$的元素个数，从而{g(y1),⋯ ,g(yn+1)}⊂X\{g(y_1),\cdots,g(y_{n+1})\}\sub X{g(y1​),⋯,g(yn+1​)}⊂X，与$X$有$n$个元素矛盾），而有限集的情形已经证明过了。不妨设$X,Y$都是无限可数集。对于无限可数集X={x1,x2,⋯ }X=\{x_1,x_2,\cdots\}X={x1​,x2​,⋯}，可以定义双射$h:X\to \mathbb{N},x_j\mapsto j-1$。显然$h$是一个双射。同理存在双射$i:Y\to \mathbb{N}$，因此$i^{-1}\circ h:X\to Y$是双射。

从现在开始，对$X$不加任何的限制。我们令$h:X\to X$是复合映射$h=g\circ f$：

我们期望结合$f$与$g$的映射关系来构造这个双射。即找到一个$X$的划分和$Y$的划分，让$f$和$g$分别在对应的划分上成为双射，从而得到$X,Y$之间的一个双射。

$C3)$ 考虑$X$的子集的集合F={A⊂X∣X′∪h(A)⊂A}\mathcal{F}=\{A\sub X|X'\cup h(A)\sub A\}F={A⊂X∣X′∪h(A)⊂A}。证明，$\mathcal{F}$非空。

证明：$X^{\prime },h(X)\subset X$从而$X\in \mathcal{F}$。

$C4)$ 证明，如果$A\in \mathcal{F}$，那么$X^{\prime }\cup h(A)\in \mathcal{F}$。

证明：先证若$A\subset B$，那么$A\cup C\subset B\cup C$。设$x\in A\cup C$即$x\in A$或$x\in C$则$x\in B$或$x\in C$那么$x\in B\cup C$，得证。

由$A\in \mathcal{F}$有$X^{\prime }\cup h(A)\subset A$，$h(X^{\prime }\cup h(A))\subset h(A)$从而$X^{\prime }\cup h(X^{\prime }\cup h(A))\subset X^{\prime }\cup h(A)$，根据定义有$X^{\prime }\cup h(A)\in \mathcal{F}$。

$C5)$ 我们定义

A0=⋂A∈FA={x∈X∣对任意的A∈F,都有x∈A} A_0=\bigcap_{A\in\mathcal{F}}A=\{x\in X|对任意的A\in\mathcal{F},都有x\in A\} A0​=A∈F⋂​A={x∈X∣对任意的A∈F,都有x∈A}

证明，$A_0\in \mathcal{F}$。

证明：只需证明$X^{\prime }\cup h(A_0)\subset A_0$。任取$A^{\prime }\in \mathcal{F}$，注意到$h(A_0)=h({\bigcap }_{A\in \mathcal{F}}A)\subset h(A^{\prime })$从而$X^{\prime }\cup h(A_0)\subset X^{\prime }\cup h(A^{\prime })\subset A^{\prime }$，从而$X^{\prime }\cup h(A_0)\subset {\bigcap }_{A\in \mathcal{F}}A=A_0$，得证。

$C6)$ 证明，$X^{\prime }\cup h(A_0)=A_0$。

证明：由于$A_0\in \mathcal{F}$可知$X^{\prime }\cup h(A_0)\subset A_0$。由$C4)$知$X^{\prime }\cup h(A_0)\in \mathcal{F}$，因此$A_0={\bigcap }_{A\in \mathcal{F}}A\subset X^{\prime }\cup h(A_0)$，从而$X^{\prime }\cup h(A_0)=A_0$。

$C7)$ 令$B_0=X-A_0$。证明，$f(A_0)\cap g^{-1}(B_0)=\varnothing$并且$f(A_0)\cup g^{-1}(B_0)=Y$。

证明：设$y\in Y$。设$y\in f(A_0)$即存在$x\in A_0$使得$y=f(x)$，考虑那么$g(y)=g(f(x))=h(x)\in h(A_0)\subset X^{\prime }\cup h(A_0)=A_0$因而$g(y)\notin B_0$从而$y\notin g^{-1}(B_0)$，因此$f(A_0)\cap g^{-1}(B_0)=\varnothing$；另一方面，假设$y\notin g^{-1}(B_0)$即$g(y)\in A_0=X^{\prime }\cup h(A_0)$，由于$X^{\prime }=X-g(Y)$从而$g(y)\notin X^{\prime }$从而$g(y)\in h(A_0)$即存在$x\in A_0$使得$g(y)=g(f(x))$，由于$g$是单射有$y=f(x)$即$y\in f(A_0)$，证毕。

注意到此处证明了对所有的$x\in U$：$1)$若$x\in A$则$x\notin B$，这就证明了$A\cap B=\varnothing$；$2)$若$x\notin B$则$x\in A$，这就证明了$x\in B$或$x\in A$必居其一，即$A\cup B=U$。

$C8)$ 我们定义映射$\phi :X\to Y$：对于$x\in X$，我们要求

$$\begin{gathered} 若x\in A_0,则\phi (x)=f(x) \\ 若x\in B_0,则\phi (x)=g^{-1}(x) \end{gathered}$$

证明，这是双射。

证明：先证明$g^{-1}$在$B_0$上是存在的，也即$g:g^{-1}(B_0)\to B_0$是双射。由于$g:Y\to X$是单射从而$g{|}_{g^{-1}(B_0)}:g^{-1}(B_0)\to X$也是单射，那么$g:g^{-1}(B_0)\to B_0$也是单射；另一方面，根据$g^{-1}(B_0)$的定义即g−1(B0)={y∈Y∣g(y)∈B0}g^{-1}(B_0)=\{y\in Y|g(y)\in B_0\}g−1(B0​)={y∈Y∣g(y)∈B0​}，对任意的$b\in B_0$，由于$B_0=X-A_0=X-X^{\prime }\cup h(A_0)$，有$B_0\subset g(Y)$，从而存在$y\in g^{-1}(B_0)$使得$g(y)=b$。从而$g:g^{-1}(B_0)\to B_0$是双射从而在这个局部$g^{-1}$存在。

现在证明$\phi$是双射。这是因为$A_0,B_0$是$X$的一个划分，而$f(A_0),g^{-1}(B_0)$是$Y$的一个划分，而$f:A_0\to f(A_0),g^{-1}:B_0\to f^{-1}(B_0)$都是双射，从而$\phi$是一个双射。形式证明的细节容易补充。

根据上述，我们证明了

定理（$Schroeder-Bernstein$）如果有单射$f:X\to Y$和单射$g:Y\to X$，那么存在着两个集合之间的双射$\phi :X\to Y$。

---

$D：$$Dedekind$分割的细节

（略）