《陶哲轩实分析》(中文第一版)——§8.1解答

习题8.1

8.1.1证明：已知存在X的一个真子集 $Y\subsetneq X$ 使得Y与X有同样的基数，由命题3.6.14(c)知X不能为有限集，即X为无限集.

如果X为无限集，我们递归定义一个函数 $f:\mathbb{N}\rightarrow X$ . 首先记集合 $Z_0:=X$ . 我们递归定义集合 $Z_{n+1}:=Z_n\backslash A_n$ (其中集合 $A_n$ 是与集合 $Z_n$ 有关的集合，其定义如下：如果 $Z_n$ 为空集则 $A_n:=\emptyset$ ；否则由引理3.1.6我们可以选取一个元素 $z_n\in Z_n$ ，定义 $A_n:=\{z_n\}$ ——我这样绕弯的定义 $Z_{n+1}$ 而不用定义“ $Z_{n+1}:=Z_n\backslash\{z_n\}(z_n\in Z_n$ )”是因为后一种递归定义在 $Z_0$ 为有限集是不成功的，我们还需要证明后一种定义在 $Z_0$ 为无限集时是定义成功的，我证明不了，证明过程中总有循环论证. 而前一种定义在逻辑上就是定义成功的，进而不需要证明递归定义是成功的). 现在我们来证明当 $Z_0=X$ 时对每个 $n\in\mathbb{N}$ 有 $Z_n$ 都是无限的. 对自然数0，由于 $Z_0=X$ 而X为无限集知 $Z_0$ 为无限集. 归纳假设对自然数n有 $Z_n$ 为无限集，那么有 $A_n=\{z_n\}(z_n\in Z_n)$ . 那么对自然数n+1，我们假设 $Z_{n+1}$ 为有限集，进而由3.6.14(b)知 $Z_{n+1}\cup A_n=Z_{n+1}\cup\{z_n\}=Z_n$ 也为有限集，这与归纳假设相矛盾，故假设不成立，进而 $Z_{n+1}$ 为无限集，这就完成了归纳. 进而我们知道当 $Z_0=X$ 为无限集时，有 $Z_{n+1}=Z_n\backslash\{z_n\}(z_n\in Z_n)$ . 于是我们可以定义 $f(n):=Z_n\backslash Z_{n+1}=z_n$ . 这里还有一个问题，就是每次从集合 $Z_n$ 选取一个元素 $z_n$ 时，我们知道这个选取是随意的，即我们知道非构造性存在一个元素 $z_n$ 属于 $Z_n$ . 或者从递归上说，我们有无数个集合序列满足上述过程(取决于每一步 $z_n$ 的选取)，这个递归结果不是“唯一确定的”，如果我们加上依序选择公理就可使递归结果唯一.

现在我们来证明f的单射性. 我们用P(n)表示关于自然数n的如下命题：对一切自然数 $n_1,n_2\leqslant n$ ，如果 $n_1\neq n_2$ 那么 $f(n_1)\neq f(n_2)$ . 对自然数1，对一切自然数 $n_1,n_2\leqslant 1$ ，如果 $n_1\neq n_2$ 那么有“ $n_1=0 \text{ and } n_2=1$ ”或“ $n_1=1 \text{ and } n_2=0$ ”，但无论何种情况，由于 $f(0)=Z_0\backslash Z_{1}$ 知有 $f(n_1)\neq f(n_2)$ ，这就完成了归纳基始. 归纳假设P(k)(对某 $k\geqslant 1$ )成立. 那么对自然数k+1，如果“ $n_1=k+1 \text{ and } n_2\leqslant k$ ”，首先由f的定义知 $f(n_1)\neq f(k)$ . 而对一切自然数m有 $f(m)\in Z_m$ 并且 $Z_{m+1}\subsetneq Z_m$ ，假设对某自然数 $k'<k$ 有 $f(n_1)=f(k')\in Z_{k'}$ ，进而有 $f(k')\in Z_{k+1}$ ，由于 $k>k'$ ，所以有 $f(k')\in Z_{k+1}\subseteq Z_{k'+1}=Z_{k'}\backslash\{f(k')\}$ ，这是一个矛盾，故假设不成立，即对一切自然数 $k'<k$ 有 $f(n_1)\neq f(k')$ ，所以此时 $f(n_1)\neq f(n_2)$ ；如果“ $n_2=k+1 \text{ and } n_1\leqslant k$ ”同理知 $f(n_1)\neq f(n_2)$ ；再结合归纳假设知对一切自然数 $n_1,n_2\leqslant k+1$ 有 $f(n_1)\neq f(n_2)$ ，这就完成了归纳. 所以对任意自然数n都有P(n)成立. 所以对任意自然数 $n_1,n_2$ ，如果 $n_1\neq n_2$ ，由 $P(max\{n_1,n_2\})$ 知 $n_1\neq n_2$ ，进而f为单射.

由于f为单射，进而我们把f的值域限制到 $f(\mathbb{N})$ 时其变成双射(这一部分其实是证明了任意无限集都有一个可数子集)，所以 $f(\mathbb{N})$ 为可数集. 记 $W:=f(\mathbb{N})\backslash\{f(0)\}$ ，再定义函数 $h:\mathbb{N}\rightarrow W,h(n):=f(n+1)$ ，容易验证h为双射. 我们记 $Y:=W\cup(X\backslash f(\mathbb{N}))$ ，由于 $f(0)\in X$ 而 $f(0)\notin Y$ ，所以 $Y\subsetneq X$ ，即Y为X的真子集. 我们定义函数 $g:Y\rightarrow X$ 如下：如果 $y\in W$ 则 $g(y):=f\circ h^{-1}(y)$ ；如果 $y\in X\backslash f(\mathbb{N})$ 则 $g(y):=y$ . 由于 $W\cap(X\backslash f(\mathbb{N}))=\emptyset$ ，所以函数g是定义成功了的.

现在来验证g的双射性. 对任何 $x\in X$ ，如果 $x\in X\backslash f(\mathbb{N})$ ，显然有 $x\in X\backslash f(\mathbb{N})\subseteq Y$ 使得 $g(x)=x$ ；如果 $x\in f(\mathbb{N})$ ，进而对某 $n_x\in\mathbb{N}$ 有 $x=f(n_x)$ ，所以存在 $h\circ f^{-1}(x)\in W\subseteq Y$ 使得 $g(h\circ f^{-1}(x))=f\circ h^{-1}(h\circ f^{-1}(x))=x$ . 综上，对任何 $x\in X$ 都存在 $y\in Y$ 使得 $g(y)=x$ ，所以函数g为满射. 对任何元素 $y_1,y_2\in Y$ ，如果 $y_1\neq y_2$ ，我们分四种情况讨论：a. $y_1,y_2\in W$ ，则有 $g(y_1)=f\circ h^{-1}(y_1)$ 和 $g(y_2)=f\circ h^{-1}(y_2)$ ，由f和h的双射性我们知道此时 $g(y_1)\neq g(y_2)$ ；b. $y_1,y_2\in X\backslash f(\mathbb{N})$ ，则有 $g(y_1)=y_1$ 和 $g(y_2)=y_2$ ，所以 $g(y_1)\neq g(y_2)$ ；c. $y_1\in W,y_2\in X\backslash f(\mathbb{N})$ ，则有 $g(y_1)=f\circ h^{-1}(y_1)\in f(\mathbb{N})$ 和 $g(y_2)=y_2\in X\backslash f(\mathbb{N})$ ，此时 $g(y_1)\neq g(y_2)$ ；d. $y_2\in W,y_1\in X\backslash f(\mathbb{N})$ ，同理如c知此时 $g(y_1)\neq g(y_2)$ . 综上g为单射. 这就证明了g为双射.

至此我们终于可以说找到了一个X的真子集Y使得X和Y具有同样的基数.

8.1.2证明：a.对任何自然数集的非空子集X，由于对任何元素 $x\in X$ 有 $x\geqslant 0$ ，即集合X有下界，由定理5.5.9知X有最大下界实数M，即对任意元素 $x\in X$ 有 $x\geqslant M$ . 我们假设 $M\notin X$ ，则对任意 $x\in X$ 有 $x>M$ . 而 $M\geqslant[M]$ ，进而 $x>[M]$ ，故 $x\geqslant [M]+1>M$ ，即[M]+1也为X的下界，这与M为X的最大下界相矛盾，故假设不成立，即 $M\in X$ . 综上，对任何自然数集的非空子集X存在 $M\in X$ 使得对一切 $x\in X$ 有 $x\geqslant M$ ，即X有最小元.

b.对任何自然数集合X，如果 $0\in X$ ，由于对任何 $x\in X$ 有 $x\geqslant 0$ ，故0为集合X的最小元. 归纳假设对任何自然数 $k\leqslant n(n\in\mathbb{N})$ ：对任何自然数集合X，如果 $k\in X$ ，则X有最小元. 那么对自然数n+1，对任何自然数集合X，如果n+1为X的最小元，那么命题得证；如果n+1不是X的最小元. 即存在一个元素 $x\in X$ 使得 $x<n+1$ ，即 $x\leqslant n$ ，由归纳假设知X也有最小元，这就完成了归纳. 综上，任何自然数集合X的非空子集总有最小元.

c.假设存在一个自然数集的非空子集X没有最小元，即对任何元素 $x\in X$ 都存在 $x'\in X$ 使得 $x'<x$ . 我们定义一个函数 $f:\mathbb{N}\rightarrow X$ . 首先由于X非空，我们可以选取一个元素 $x_0\in X$ ，我们定义 $f(0):=x_0$ . 归纳假设已对自然数n定义好 $f(n)\in X$ ，那么我们定义 $f(n+1):=x_{n+1}<f(n)$ . 这样我们就得到了一个严格减函数f，即一个自然数的严格减序列 $(f(n))_{n=0}^{\infty}$ ，这明显与自然数的无限下降原理相矛盾.

8.1.3证明：1.对任意自然数n，容易验证集合 $X=\{x\in X : \text{for all }m<n,x\neq a_m\}\cup\{x\in X : x=a_m\text{ for some }m<n\}$ . 假设 $\{x\in X : \text{for all }m<n,x\neq a_m\}$ 为有限集，容易验证 $\{x\in X : x=a_m\text{ for some }m<0\}=\emptyset$ ，并且 $\{x\in X : x=a_m\text{ for some }m<n\}\cup\{a_n\}\\=\{x\in X : x=a_m\text{ for some }m<n+1\}$ ，由命题3.6.14(b)和归纳法知对任意自然数n集合 $\{x\in X : x=a_m\text{ for some }m<n\}$ 均为有限集，再由命题3.6.14(b)知 $\{x\in X : \text{for all }m<n,x\neq a_m\}\cup\{x\in X : x=a_m\text{ for some }m<n\}$ 为有限集，即X为有限集，这明显是矛盾的，故假设不成立，即对任意自然数n有 $\{x\in X : \text{for all }m<n,x\neq a_m\}$ 为无限集.

2.由1知递归定义 $a_n:=min\{x\in X : \text{for all }m<n,x\neq a_m\}$ 是定义成功的，从而有对一切自然数n有 $a_n\neq a_{n+1}$ ，而两者都属于集合X，故有 $a_n<a_{n+1}$ 或 $a_n>a_{n+1}$ . 我们不妨假设 $a_n>a_{n+1}$ ，由于 $a_{n+1}\in\{x\in X : \text{for all }m<n+1,x\neq a_m\}$ 并且 $a_{n}\in\{x\in X : \text{for all }m<n,x\neq a_m\}$ ，再由 $a_n\neq a_{n+1}$ 知 $a_n\in\{x\in X : \text{for all }m<n+1,x\neq a_m\}$ . 于是我们看到 $min\{x\in X : \text{for all }m<n+1,x\neq a_m\}$ 不可能为 $a_{n+1}$ ，这与“递归定义 $a_n:=min\{x\in X : \text{for all }m<n,x\neq a_m\}$ 是定义成功的”的相矛盾，故假设 $a_n>a_{n+1}$ 不成立，于是 $a_n<a_{n+1}$ . 进而 $(a_n)_{n=0}^{\infty}$ 为递增序列.

3.由习题6.1.1知对于一切 $n\neq m$ 有 $a_n\neq a_m$ .

4.由“递归定义 $a_n:=min\{x\in X : \text{for all }m<n,x\neq a_m\}$ ”知 $a_n\in X$ .

5.已知 $x\in X$ 并且对每个自然数n有 $a_n\neq x$ ，进而有 $x\in X$ 并且对每个自然数n，对每个自然数 $m<n$ 有 $x\neq a_m$ . 故 $x\in\{x\in X : \text{for all }m<n,x\neq a_m\}$ .

6. $a_0\in X\subseteq\mathbb{N}$ ，则有 $a_0\geqslant 0$ . 归纳假设 $a_n\geqslant n$ ，那么有 $a_{n+1}>a_n\geqslant n$ ，即有 $a_{n+1}>n$ . 而 $a_{n+1}\in\mathbb{N}$ ，进而 $a_{n+1}\geqslant n+1$ ，这就完成了归纳.

7.由1知 $min\{x\in X : \text{for all }t<m,x\neq a_t\}$ 是定义成功的，再由 $g:\mathbb{N}\rightarrow X$ 为增的双射知 $g(m)\in\{x\in X : \text{for all }t<m,x\neq a_t\}$ . 我们假设 $g(m)\neq min\{x\in X : \text{for all }t<m,x\neq a_t\}$ ，进而有 $g(m)>min\{x\in X : \text{for all }t<m,x\neq a_t\}$ ，综合“对于一切 $n<m,g(n)=a_n$ ”知对一切自然数 $n<m$ 有 $g(n)\notin\{x\in X : \text{for all }t<m,x\neq a_t\}$ ，进而对一切自然数n有 $g(n)\neq min\{x\in X : \text{for all }t<m,x\neq a_t\}\subseteq X$ ，这与g为从 $\mathbb{N}$ 到X的双射相矛盾，故有 $g(m)=min\{x\in X : \text{for all }t<m,x\neq a_t\}$ .

8.1.4证明：已知 $f:\mathbb{N}\rightarrow Y$ ，定义函数 $g:A\rightarrow f(A),g(x):=f(x)$ . 对任何 $x_1,x_2\in A$ ，若 $x_1\neq x_2$ ，则有 $x_1<x_2$ 或 $x_1>x_2$ ，但无论哪种情况由集合A的定义知有 $f(x_1)\neq f(x_2)$ ，即 $g(x_1)\neq g(x_2)$ ，故g为单射. 对任何 $y\in f(A)$ ，有对某 $x\in A$ 有 $y=f(x)=g(x)$ ，故g为满射，综上g为双射. 由于 $A\subseteq\mathbb{N}$ 显然有 $f(A)\subseteq f(\mathbb{N})$ . 我们假设 $f(\mathbb{N})\subseteq f(A)$ 不成立，即存在元素 $x\in f(\mathbb{N})$ 并且 $x\notin f(A)$ ，即对某 $n\in\mathbb{N}$ 有 $x=f(n)$ 并且不存在 $n'\in A$ 使 $x=f(n')$ ，进而有 $n\notin A$ ，由A定义知这意味着存在 $0\leqslant n_1<n$ 使 $f(n_1)=f(n)=x\notin f(A)$ . 而 $f(n_1)\in f(\mathbb{N})$ ，于是我们找到 $n_1<n$ 使得 $f(n_1)\in f(\mathbb{N})$ 并且 $f(n_1)\notin f(A)$ ，重复上面的操作我们就找到一个严格递减的自然数序列 $n,n_1,n_2,...$ 使得他们都属于 $f(\mathbb{N})$ 但不属于 $f(A)$ ，这明显与自然数的无限减小原理相矛盾，故假设不成立，即 $f(\mathbb{N})\subseteq f(A)$ . 所以我们有 $f(A)=f(\mathbb{N})$ . 而 $A\subseteq\mathbb{N}$ ，当A为有限集时 $f(A)=f(\mathbb{N})$ 显然是至多可数的；当A为无限集时，由命题8.1.5知在 $\mathbb{N}$ 与A之间存在双射函数，再由 $g:A\rightarrow f(A)$ 为双射知 $\mathbb{N}$ 与f(A)之间存在双射函数，即 $\mathbb{N}$ 与 $f(\mathbb{N})$ 之间存在双射函数，所以此时 $f(\mathbb{N})$ 为可数的. 综上， $f(\mathbb{N})$ 总是至多可数的.

8.1.5证明：已知X为可数集，则存在双射函数 $g:\mathbb{N}\rightarrow X$ ，则 $f\circ g$ 为从 $\mathbb{N}$ 到Y的函数，由命题8.1.8知 $f\circ g(\mathbb{N})$ 为至多可数的. 对任意元素 $x\in f\circ g(\mathbb{N})$ ，有对某 $n\in\mathbb{N}$ 有 $x=f\circ g(n)=f(g(n))$ . 进而对某 $g(n)\in X$ 有 $x=f(g(n))$ ，故 $x\in f(X)$ ，故 $f\circ g(\mathbb{N})\subseteq f(X)$ . 对任意元素 $y\in f(X)$ ，有对某 $x\in X$ 有 $y=f(x)$ ，即对某 $g^{-1}(x)\in\mathbb{N}$ 有 $y=f(g(g^{-1}(x)))=f(x)$ ，即 $y=f\circ g(g^{-1}(x))$ ，故 $y\in f\circ g(\mathbb{N})$ ，进而 $f(X)\subseteq f\circ g(\mathbb{N})$ . 综上， $f\circ g(\mathbb{N})=f(X)$ . 所以f(X)是至多可数的.

8.1.6证明：若存在从A到 $\mathbb{N}$ 的单射 $f:A\rightarrow\mathbb{N}$ ，我们容易验证 $f:A\rightarrow f(A)$ 为双射. 而 $f(A)\subseteq\mathbb{N}$ ，由推论8.1.6知f(A)是至多可数的，所以A是至多可数的.

若A是至多可数的，即A为有限集或可数集. 当A为有限集时显然存在从A到 $\mathbb{N}$ 的单射. 如果A为可数集，则存在从A到 $\mathbb{N}$ 的双射函数，亦即存在从A到 $\mathbb{N}$ 的单射.

8.1.7证明：对任意元素 $z\in h(\mathbb{N})$ ，有对某自然数 $n\in\mathbb{N}$ 有 $z=h(n)$ . 若n为偶数，则有 $z=h(n)=h(2k_1)=f(k_1)\in X\subseteq X\cup Y$ ；若n为奇数，则有 $z=h(n)=h(2k_2+1)=g(k_2)\in Y\subseteq X\cup Y(k_1,k_2\in\mathbb{N})$ . 故有 $h(\mathbb{N})\subseteq X\cup Y$ . 对任意元素 $z\in X\cup Y$ ，如果 $z\in X$ ，则有 $2f^{-1}(z)\in\mathbb{N}$ 使得 $h(2f^{-1}(z))=f(f^{-1}(z))=z$ ，故 $z\in h(\mathbb{N})$ ；如果 $z\in Y$ ，则有 $2g^{-1}(z)+1\in\mathbb{N}$ 使得 $h(2g^{-1}(z)+1)=g(g^{-1}(z))=z$ ，故 $z\in h(\mathbb{N})$ ，综上总有 $z\in h(\mathbb{N})$ ，所以 $X\cup Y\subseteq h(\mathbb{N})$ . 综上有 $h(\mathbb{N})=X\cup Y$ . 由命题8.1.8知 $h(\mathbb{N})=X\cup Y$ 是至多可数的. 若 $X\cup Y$ 为有限的，由命题3.6.14(c)知X为有限集，这与X为可数集相矛盾，故假设不成立，即 $X\cup Y$ 为可数集.

8.1.8证明：已知X和Y都是可数集合，即存在双射函数 $f:X\rightarrow\mathbb{N}$ 和双射函数 $g:Y\rightarrow\mathbb{N}$ . 我们定义函数 $h:X\times Y\rightarrow\mathbb{N}\times\mathbb{N},h(x,y):=(f(x),g(y))$ . 现在来证明h的双射性. 对任意 $(x_1,y_1),(x_2,y_2)\in X\times Y$ ，如果 $(x_1,y_1)\neq (x_2,y_2)$ ，则有 $x_1\neq x_2$ 或者 $y_1\neq y_2$ . 若 $x_1\neq x_2$ ，进而有 $f(x_1)\neq f_(x_2)$ ，进而 $h(x_1,y_1)\neq h(x_2,y_2)$ ；同理若 $y_1\neq y_2$ 则 $h(x_1,y_1)\neq h(x_2,y_2)$ ，所以h为单射. 对任意 $(a,b)\in\mathbb{N}\times\mathbb{N}$ ，有 $(f^{-1}(a),g^{-1}(b))\in X\times Y$ 使得 $h(f^{-1}(a),g^{-1}(b))=(a,b)$ ，故h为满射. 综上，h为双射. 由推论8.1.13知 $\mathbb{N}\times\mathbb{N}$ 为可数集，故 $X\times Y$ 也为可数集.

8.1.9证明：小命题：如果I为至多可数集而I’为可数集，则 $I\cup I'$ 为可数集. 证明：设Y为可数集. 如果X为可数集，由命题8.1.10知 $X\cup Y$ 为可数集. 如果X为有限集，我们知道有双射函数 $f_1:\{i\in\mathbb{N} : 1\leqslant i\leqslant \#(X)\}\rightarrow X$ 和双射函数 $f_2:\mathbb{N}\rightarrow Y$ ，进而我们定义函数 $f:\mathbb{N}\rightarrow X\cup Y$ 如下：对每个 $n\in\mathbb{N}$ ，如果 $n<\#(X)$ 则 $f(n):=f_1(n+1)$ ；如果 $n\geqslant \#(X)$ 则 $f(n):=f_2(n-\#(X))$ . 现在我们来说明f的满射性. 对任意元素 $z\in X\cup Y$ ，如果 $z\in X$ ，则存在 $n\in\{i\in\mathbb{N} : 1\leqslant i\leqslant \#(X)\}$ 使 $f_1(n)=z$ ，进而存在 $n-1\in\{i\in\mathbb{N} : 0\leqslant i\leqslant \#(X)-1\}\subseteq\mathbb{N}$ 使得 $f(n-1)=f_1(n)=z$ ；如果 $z\in Y$ ，则存在 $n\in\mathbb{N}$ 使 $f_2(n)=z$ ，进而存在 $n+\#(X)\in\mathbb{N}$ 使得 $f(n+\#(X))=f_2(n)=z$ . 综上f为满射. 故有 $f(\mathbb{N})=X\cup Y$ ，再由命题8.1.8知 $f(\mathbb{N})$ 是至多可数的，即 $X\cup Y$ 是至多可数的. 再由于为Y可数集，所以 $X\cup Y$ 是可数的.

现在来证明习题. 已知I为至多可数集并且对每个 $\alpha\in I$ 有 $A_\alpha$ 是一个至多可数的集合. 由上面的小命题我们知对每个 $\alpha\in I$ 有 $A_\alpha\cup\mathbb{N}$ 是一个可数的集合. 此时有 $\bigcup_{\alpha\in I}{A_\alpha}\subseteq\bigcup_{\alpha\in I}{(A_\alpha\cup\mathbb{N})}$ . 若I为有限集，当 $\#(I)=0$ ，即I为空集，我们知道 $\bigcup_{\alpha\in I}{A_\alpha}$ 为空集，进而是至多可数的；当 $\#(I)=1$ ，即I为单元素集，进而 $\bigcup_{\alpha\in I}{A_\alpha}=A_\beta(\beta\in I)$ ，所以此时 $\bigcup_{\alpha\in I}{A_\alpha}$ 是至多可数的；当 $\#(I)=2$ ，由命题8.1.10知 $\bigcup_{\alpha\in I}{(A_\alpha\cup\mathbb{N})}$ 是可数的. 归纳假设对某自然数 $n\geqslant 2$ ，如果 $\#(I)=n$ 有 $\bigcup_{\alpha\in I}{(A_\alpha\cup\mathbb{N})}$ 是可数的. 那么对自然数 $n+1$ ，如果 $\#(I)=n+1$ ，进而I非空，所以可以选取一个元素 $i\in I$ 使得 $\#(I\backslash\{i\})=n$ ，由归纳假设和命题8.1.10知 $\bigcup_{\alpha\in I\backslash\{i\}}{(A_\alpha\cup\mathbb{N})}\cup\bigcup_{\alpha\in \{i\}}{(A_\alpha\cup\mathbb{N})}=\bigcup_{\alpha\in I}{(A_\alpha\cup\mathbb{N})}$ 是可数的，这就完成了归纳. 综上，当I为有限集时有 $\bigcup_{\alpha\in I}{(A_\alpha\cup\mathbb{N})}$ 是可数的，由推论8.1.7知 $\bigcup_{\alpha\in I}{A_\alpha}$ 是至多可数的. 当I为可数集时，我们只需要证明可数集的可数并是可数的即可，我们可以采用习题8.1.10中图解的思路，但这有点难度，下面我们采用另一种思路.

设I是可数集，并且对于每个 $\alpha\in I$ 有 $A_\alpha$ 是可数集. 那么存在双射函数 $f:\mathbb{N}\rightarrow I$ 并且对每个 $\alpha\in I$ 有双射函数 $g_\alpha:\mathbb{N}\rightarrow A_\alpha$ (函数 $g_\alpha$ 的选择用到选择公理). 我们可以定义函数 $h:\mathbb{N}\times\mathbb{N}\rightarrow\bigcup_{\alpha\in I}{A_\alpha},h(m,n):=g_{f(m)}(n)$ . 对任意元素 $x\in\bigcup_{\alpha\in I}{A_\alpha}$ ，有对某 $\alpha_0\in I$ 有 $x\in A_{\alpha_0}$ ，进而对自然数 $f^{-1}(\alpha_0),g_{\alpha_0}^{-1}(x)$ 有 $x=g_{f(f^{-1}(\alpha_0))}(g_{\alpha_0}^{-1}(x))$ ，即 $x=h(f^{-1}(\alpha_0),g_{\alpha_0}^{-1}(x))$ ，故h为满射函数. 则有 $h(\mathbb{N}\times\mathbb{N})=\bigcup_{\alpha\in I}{A_\alpha}$ . 由命题8.1.8和推论8.1.13知 $h(\mathbb{N}\times\mathbb{N})$ 为至多可数的，即 $\bigcup_{\alpha\in I}{A_\alpha}$ 为至多可数的. 而由于对任意 $\beta\in I$ 有 $A_\beta$ 为可数集并且 $A_\beta\subseteq\bigcup_{\alpha\in I}{A_\alpha}$ ，所以 $\bigcup_{\alpha\in I}{A_\alpha}$ 为可数的. 这就证明了可数集的可数并仍为可数集.

8.1.10证明：我们先构建从 $\mathbb{N}$ 到 $\mathbb{N}\times\mathbb{N}$ 的双射，从图像上很容易理解这一双射，但递归地写出此双射是比较困难的.

《陶哲轩实分析》(中文第一版)——§8.1解答——图像1 — 证明可数集的可数并仍为可数集——图源《实数的构造理论》

由引理8.1.12启发，我们选择一个更容易写出来的双射. 从引理8.1.12证明中我们已经构建了从 $\{(m,n)\in\mathbb{N}\times\mathbb{N} : 0\leqslant n\leqslant m\}$ 到 $\mathbb{N}$ 的双射 $f_1$ ，同理我们容易构造从 $\{(m,n)\in\mathbb{N}\times\mathbb{N} : 0\leqslant m<n\}$ 到 $\mathbb{N}$ 的双射 $f_2$ . 而我们有 $\{(m,n)\in\mathbb{N}\times\mathbb{N} : 0\leqslant n\leqslant m\}\cup\{(m,n)\in\mathbb{N}\times\mathbb{N} : 0\leqslant m<n\}=\mathbb{N}\times\mathbb{N}$ 并且有 $\{(m,n)\in\mathbb{N}\times\mathbb{N} : 0\leqslant n\leqslant m\}\cap\{(m,n)\in\mathbb{N}\times\mathbb{N} : 0\leqslant m<n\}=\emptyset$ . 进而我们定义 $f:\mathbb{N}\rightarrow\mathbb{N}\times\mathbb{N}$ 如下：如同习题8.1.7，对任意自然数n，有 $f(2n):=f_1^{-1}(n)$ 并且 $f(2n+1):=f_2^{-1}(n)$ . 现在我们来证明f的双射性. 对任意 $n_1,n_2\in\mathbb{N}$ ，如果 $n_1\neq n_2$ ，我们分三种情况说明：a. $n_1,n_2$ 具有不同奇偶性，不妨假设 $n_1$ 为偶而 $n_2$ 为奇. 则有 $f(n_1)\in\{(m,n)\in\mathbb{N}\times\mathbb{N} : 0\leqslant n\leqslant m\}$ 并且有 $f(n_2)\in\{(m,n)\in\mathbb{N}\times\mathbb{N} : 0\leqslant m<n\}$ ，而已知 $\{(m,n)\in\mathbb{N}\times\mathbb{N} : 0\leqslant n\leqslant m\}\cap\{(m,n)\in\mathbb{N}\times\mathbb{N} : 0\leqslant m<n\}=\emptyset$ ，所以 $f(n_1)\neq f(n_2)$ ；b. $n_1,n_2$ 均为偶，由 $f_1^{-1}$ 的双射性知 $f(n_1)\neq f(n_2)$ ；c. $n_1,n_2$ 均为奇，由 $f_2^{-1}$ 的双射性知 $f(n_1)\neq f(n_2)$ . 故f为单射. 对任意元素 $(a,b)\in\mathbb{N}\times\mathbb{N}$ ，如果 $a\geqslant b$ ，则 $(a,b)\in\{(m,n)\in\mathbb{N}\times\mathbb{N} : 0\leqslant n\leqslant m\}$ ，由 $f_1^{-1}$ 的双射性知存在 $n\in\mathbb{N}$ 使得 $f_1^{-1}(n)=(a,b)$ ，即存在 $2n\in\mathbb{N}$ 使得 $f(2n)=f_1^{-1}(n)=(a,b)$ ；如果 $a<b$ ，则 $(a,b)\in\{(m,n)\in\mathbb{N}\times\mathbb{N} : 0\leqslant m<n\}$ ，由 $f_2^{-1}$ 的双射性知存在 $n\in\mathbb{N}$ 使得 $f_2^{-1}(n)=(a,b)$ ，即存在 $2n+1\in\mathbb{N}$ 使得 $f(2n+1)=f_2^{-1}(n)=(a,b)$ . 故f为满射. 综上，f为双射.

我们很容易构造双射 $g_1:\mathbb{N}\rightarrow(\mathbb{Z}\backslash\{0\})$ ，进而在 $g_1$ 的基础上很容易构造双射 $g_2:\mathbb{N}\rightarrow\mathbb{Z}$ ，最后我们构造函数 $g:\mathbb{N}\times\mathbb{N}\rightarrow\mathbb{Z}\times(\mathbb{Z}\backslash\{0\}),g(m,n):=(g_1(m),g_2(n))$ ，很容易验证g为双射.

综上 $g\circ f:\mathbb{N}\rightarrow\mathbb{Z}\times(\mathbb{Z}\backslash\{0\})$ 为双射，而由推论8.1.15证明知 $h:\mathbb{Z}\times(\mathbb{Z}\backslash\{0\})\rightarrow\mathbb{Q},h(a,b):=\frac{a}{b}$ 为满射，进而 $h\circ(g\circ f)$ 为满射. 最后仿照习题8.1.4将 $h\circ(g\circ f)$ 的定义域限制到 $A:=\{n\in\mathbb{N} : \text{for all }0\leqslant m<n,f(m)\neq f(n)\}$ ，再由命题8.1.5知存在 $\mathbb{N}$ 到 $\mathbb{Q}$ 的双射.

文内补充

1.集合 $\mathbb{N}\backslash\{0\}$ 是无限集.

若其为有限集，由命题3.6.14(a)知集合 $(\mathbb{N}\backslash\{0\})\cup\{0\}=\mathbb{N}$ 也是有限的，这明显与定理3.6.12相矛盾.

2. $f:\mathbb{N}\rightarrow\mathbb{N}\backslash\{0\},f(n):=n+1$ 为双射.

对任意自然数 $n_1,n_2\in\mathbb{N}$ ，若 $n_1\neq n_2$ ，则有 $n_1+1\neq n_2+1$ ，即 $f(n_1)\neq f(n_2)$ ，所以f为单射.

对任意元素 $n\in\mathbb{N}\backslash\{0\}$ ，有 $n\in\mathbb{N}$ 并且 $n\neq 0$ ，进而有 $n\in\mathbb{N}$ 并且 $n>0$ ，所以 $n-1\geqslant 0$ ，即存在 $n-1\in\mathbb{N}$ 使得 $f(n-1)=n$ ，所以f是满射.

3. $f:\mathbb{N}\rightarrow\{2n : n\in\mathbb{N}\},f(n):=2n$ 为双射.

同2论证.

4.自然数集的非空子集的最小元与定义5.5.10给出的集合下确界是同一个元素.

详见习题8.1.2的a.

5.如果 $f:X\rightarrow Y$ 为双射，设 $X'\subseteq X$ ，那么 $f:X'\rightarrow f(X')$ 也为双射.

由 $f:X\rightarrow Y$ 的单射性我们知道 $f:X'\subseteq X\rightarrow f(X')$ 也为单射.

由f(X’)和前象的定义知 $f:X'\rightarrow f(X')$ 的满射性.

6.递归定义 $a_0:=0;a_{n+1}:=a_n+n+1$ 是严格增的.

证明：由 $(a_n)_{n=0}^{\infty}$ 的定义知对一切 $n\in\mathbb{N}$ 有 $a_{n+1}>a_n$ .

对自然数1，有 $a_{n+1}>a_n$ . 归纳假设对某自然数 $k\geqslant 1$ 有 $a_{n+k}>a_n$ . 那么对自然数k+1，有 $a_{n+(k+1)}>a_{n+k}>a_n$ ，这就完成了归纳. 故对一切 $k\geqslant 1$ 有 $a_{n+k}>a_n$ . 由 $n>m$ 知 $n=m+k(k\in\mathbb{N},k\geqslant 1)$ ，故 $a_n=a_{m+k}>a_m$ .

7. $A:=\{(n,m)\in\mathbb{N}\times\mathbb{N} : 0\leqslant m\leqslant n\},B:=\{(n,m)\in\mathbb{N}\times\mathbb{N} : 0\leqslant n\leqslant m\},f:A\rightarrow B,f(n,m):=(m,n)$ . 所以f为双射，并且集合A和集合B的并为自然数集合的笛卡尔乘积.

显然.

《陶哲轩实分析》(中文第一版)——§8.1解答

习题8.1

文内补充

发布者：iknetfomi

留下评论取消回复

习题8.1

文内补充

共享此文章：

相关

发布者：iknetfomi

留下评论 取消回复

留下评论取消回复