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

习题3.6

3.6.1 证明：对集合X，存在函数 $f:X\rightarrow X$ ，其由 $f(x):=x\in X$ 定义. 对任意 $x_1,x_2$ ，如果 $x_1\neq x_2$ ，则 $f(x_1)=x_1\neq x_2=f(x_2)$ ，则f为单射. 对任何 $x\in X$ ，存在 $x\in X$ 使得 $f(x)=x$ ，故f为满射. 综上f为满射，故集合X与集合X具有相同的基数.（自反性）

如果集合X和集合Y具有相同的基数，由定义3.6.1知存在一个从X到Y的双射函数 $f:X\rightarrow Y$ . 由习题3.3.6知f的逆 $f^{-1}:Y\rightarrow X$ 也是双射函数，故集合Y和集合X具有同样的基数.

如果集合X和集合Y具有相同的基数并且集合Y和集合Z具有相同的基数，则存在双射函数 $f:X\rightarrow Y$ 和双射函数 $g:Y\rightarrow Z$ ，由习题3.3.7知 $g\circ f:X\rightarrow Z$ 也是双射函数，故集合X和集合Z具有同样的基数.

3.6.2 证明：若集合X有基数0，则存在双射函数 $f:X\rightarrow\{i\in\mathbb{N} : 1\leqslant i\leqslant 0\}=\emptyset$ ，即双射函数 $f:X\rightarrow\emptyset$ . 我们假设X不是空集，由引理3.1.6知存在 $x\in X$ ，于是我们有 $f(x)\in\emptyset$ ，这是不可能的，所以假设不成立，故X是空集. 即，集合X有基数0 $\Longrightarrow$ X是空集.

若X是空集，由习题3.3.3知 $f:\emptyset\rightarrow\emptyset$ 为双射，而 $\{i\in\mathbb{N} : 1\leqslant i\leqslant 0\}=\emptyset$ ，即存在双射函数 $f:\emptyset\rightarrow\{i\in\mathbb{N} : 1\leqslant i\leqslant 0\}$ ，由定义3.6.5知集合X有基数0.

3.6.3 证明：对一切 $1\leqslant i\leqslant n$ ，显然自然数 $\displaystyle\sum_{1\leqslant i\leqslant n}{f(i)}=\sum_{1\leqslant j\leqslant i-1}{f(j)}+f(i)+\sum_{i+1\leqslant j\leqslant n}{f(j)}\geqslant f(i)$ 成立.

或者我们构造一个新的函数 $g:\{i\in\mathbb{N} : 1\leqslant i\leqslant n\}\rightarrow\{f(i) : i\in\{i\in\mathbb{N} : 1\leqslant i\leqslant n\}\}$ ,其由 $g(i):=f(i)$ 定义，容易证明其是一个满射函数，由习题3.5.2知我们可以把其当作有序n元组，再由注3.5.10知我们可以把其当作有限序列，再由引理5.1.14知有限序列是有界的，即存在自然数M(可以推得到)对一切 $1\leqslant i\leqslant n$ 有 $g(i)=f(i)\leqslant M$ .

3.6.4 证明：(a)由于X是有限集，则其基数 $\#(X)=n$ 为某一自然数，故存在双射函数 $f:\{i\in\mathbb{N} : 1\leqslant i\leqslant n\}\rightarrow X$ . 已知 $x\notin X$ ，对于集合 $X\cup\{x\}$ ，要证 $\#(X\cup\{x\})=\#(X)+1=n+1$ ，只需证存在双射函数 $g:\{i\in\mathbb{N} : 1\leqslant i\leqslant n+1\}\rightarrow X\cup\{x\}$ .

我们定义函数g如下：若 $i\in\{i\in\mathbb{N} : 1\leqslant i\leqslant n\}\subseteq\{i\in\mathbb{N} : 1\leqslant i\leqslant n+1\}$ ，则 $g(i):=f(i)\in X\subsetneq X\cup\{x\}$ ;若 $i=n+1\in\{i\in\mathbb{N} : 1\leqslant i\leqslant n+1\}$ ，则 $g(i):=g(n+1)=x\in X\cup\{x\}$ . 到此，对任意 $i\in\{i\in\mathbb{N} : 1\leqslant i\leqslant n+1\}$ ，我们都定义了 $g(i)$ 并且 $g(i)\in X\cup\{x\}$ ，即g是定义成功的. 现在来考虑g的双射性.

对任意 $i_1,i_2\in\{i\in\mathbb{N} : 1\leqslant i\leqslant n+1\}$ ，若 $i_1\neq i_2$ ，我们分四种情况讨论：若 $i_1,i_2\in\{i\in\mathbb{N} : 1\leqslant i\leqslant n\}$ ，由f的单射性我们有 $f(i_1)\neq f(i_2)$ ，此时 $g(i)=f(i)$ ，故有 $g(i_1)\neq g(i_2)$ ；若 $i_1\in\{i\in\mathbb{N} : 1\leqslant i\leqslant n\}$ 并且 $i_2=n+1$ 时， $g(i_1)=f(i_1)\in X$ ，而 $g(i_2)=g(n+1)=x\notin X$ ，故 $g(i_1)\neq g(i_2)$ ；剩下的两种情形一种与第二种相似另一种在 $i_1\neq i_2$ 的条件下不存在. 综上，对任意 $i_1,i_2\in\{i\in\mathbb{N} : 1\leqslant i\leqslant n+1\}$ ，若 $i_1\neq i_2$ 我们总有 $g(i_1)\neq g(i_2)$ . 所以g是单射的.

再来考虑g的满射性，对任何 $x_0\in X\cup\{x\}$ ，若 $x_0\in X$ ，由f的满射性知存在 $i\in\{i\in\mathbb{N} : 1\leqslant i\leqslant n\}\subsetneq\{i\in\mathbb{N} : 1\leqslant i\leqslant n+1\}$ 使得 $f(i)=x_0$ ，而此时 $g(i)=f(i)$ ，故 $g(i)=x_0$ . 若 $x_0\in\{x\}$ ，即 $x_0=x$ ，则有 $n+1\in\{i\in\mathbb{N} : 1\leqslant i\leqslant n+1\}$ 使得 $g(n+1)=x$ . 综上，对任何 $x_0\in X\cup\{x\}$ ，总存在 $i\in\{i\in\mathbb{N} : 1\leqslant i\leqslant n+1\}$ 使得 $g(i)=x_0$ ，故g为满射. 综上g为双射. 故 $\#(X\cup\{x\})=\#(X)+1=n+1$ .

(c)我们先证(c)，因为(b)的证明用到了(c). 由于X是有限集，则其基数 $\#(X)=n$ 为某一自然数，故存在双射函数 $f:\{i\in\mathbb{N} : 1\leqslant i\leqslant n\}\rightarrow X$ .

若 $n=0$ ，由习题3.6.2知双射函数 $f:\{i\in\mathbb{N} : 1\leqslant i\leqslant n\}\rightarrow X$ 即为 $\emptyset\rightarrow\emptyset$ ，即此时 $X=\emptyset$ . 若Y为X的子集，我们假设Y不空，则有 $y\in Y$ ，进而 $y\in X=\emptyset$ ，这是不可能的，故Y也是空集. 此时显然有 $\#(\emptyset)\leqslant\#(\emptyset)=0$ ，即 $\#(Y)\leqslant\#(X)$ . 并且若 $Y\neq X$ 则 $\#(Y)<\#(X)$ 成了一个空蕴含，没有任何意思，所以我们再来考虑 $n=1$ 的情形.

若 $n=1$ ，则存在双射函数 $f:\{1\}\rightarrow X$ . 由函数定义知X不空，由引理3.6.1知存在对象 $x_0\in X$ ，现在来证 $X=\{x_0\}$ . 若X不为单元素集，则存在对象 $x_1\in X$ 并且 $x_1\neq x_0$ . 由函数f满射性知：对于 $x_0\in X$ 存在 $i\in\{1\}$ (即 $i=1$ )使得 $f(i)=x_0$ ；同理可得 $f(1)=x_1$ ，这与函数定义相矛盾，故假设不成立，所以X此时为单元素集 $\{x_0\}$ . 若Y为X的子集，假设Y非空，则存在元素 $x\in Y$ ，进而 $x\in X=\{x_0\}$ ，故 $x=x_0$ ，所以此时Y也为单元素集 $Y=\{x_0\}$ . 若Y为空集，那么显然 $Y\subsetneq X$ . 综上，若Y为X的子集，那么有 $Y=\emptyset$ 或 $Y=X$ ，故 $\#(Y)=0$ 或 $\#(Y)=1$ ，进而我们有 $\#(Y)\leqslant\#(X)$ . 如果我们还知道 $Y\neq X$ ，那么 $Y=\emptyset$ ，故有 $\#(Y)=0<\#(X)$ . 这就完成了基础情形的证明.

归纳假设当 $\#(X)=n$ 时结论成立. 现设 $\#(X)=n++$ . 已知 $Y\subseteq X$ . 若 $Y=X$ ，显然有 $\#(Y)\leqslant\#(X)$ ；若 $Y\neq X$ ，则存在元素 $x_0\in X$ 并且 $x_0\notin Y$ ，由引理3.6.9知 $\#(X\backslash\{x_0\})=n$ ，易验证 $Y\subseteq X\backslash\{x_0\}$ ，由归纳假设知 $\#(Y)\leqslant\#(X\backslash\{x_0\})=n<\#(X)=n++$ . 综上，当 $\#(X)=n++$ 时，若Y为X的子集，则有 $\#(Y)\leqslant\#(X)$ . 并且若还知道 $Y\neq X$ 那么有 $\#(Y)<\#(X)$ . 至此我们完成了归纳.

(b)由于X和Y是有限集，则有 $\#(X)=m,\#(Y)=n$ (m,n为自然数). 即存在双射函数 $f:X\rightarrow\{i\in\mathbb{N} : 1\leqslant i\leqslant m\}$ 和双射函数 $g:Y\rightarrow\{i\in\mathbb{N} : 1\leqslant i\leqslant n\}$ . 易证 $Y\backslash X\subseteq Y$ . 由习题3.6.4(c)的结果知 $\#(Y\backslash X)\leqslant\#(Y)=n$ . 不妨记 $p:=\#(Y\backslash X)\leqslant n$ . 现定义函数 $h:X\cup Y\rightarrow\{i\in\mathbb{N} : 1\leqslant i\leqslant m+p\}$ 如下：若 $x\in X$ 则 $h(x):=f(x)\in\{i\in\mathbb{N} : 1\leqslant i\leqslant m\}\subseteq\{i\in\mathbb{N} : 1\leqslant i\leqslant m+p\}$ ；若 $x\in Y\backslash X$ ，记 $Y\backslash X$ 到 $\{i\in\mathbb{N} : 1\leqslant i\leqslant p\}$ 的双射函数为 $I:Y\backslash X\rightarrow\{i\in\mathbb{N} : 1\leqslant i\leqslant p\}$ ，定义 $h(x):=I(x)+m\in\{i\in\mathbb{N} : 1\leqslant i\leqslant p+m\}$ . 可以验证，对任意元素 $x\in X\cup Y$ ， $h(x)$ 是唯一定义的且 $h(x)\in\{i\in\mathbb{N} : 1\leqslant i\leqslant p+m\}$ . 现在来证h的双射性.

对任意 $x_1,x_2\in X\cup Y$ ，已知 $x_1\neq x_2$ . 我们分四种情况进行说明：1.若 $x_1,x_2\in X$ ，则有 $h(x_1)=f(x_1)$ 和 $h(x_2)=f(x_2)$ ，由f的单射性我们知 $f(x_1)\neq f(x_2)$ ，进而 $h(x_1)\neq h(x_2)$ ；2.若 $x_1,x_2\in Y\backslash X$ ，则有 $h(x_1)=I(x_1)+m$ 和 $h(x_2)=I(x_2)+m$ ，由I的单射性我们知 $I(x_1)\neq I(x_2)$ ，进而 $I(x_1)+m\neq I(x_2)+m$ ，即 $h(x_1)\neq h(x_2)$ ；3.若 $x_1\in X$ 且 $x_2\in Y\backslash X$ ，则有 $h(x_1)=f(x_1)\leqslant m$ 和 $h(x_2)=I(x_2)+m>m$ ，进而也有 $h(x_1)\neq h(x_2)$ ；4.若 $x_2\in X$ 且 $x_1\in Y\backslash X$ 同理可证 $h(x_1)\neq h(x_2)$ . 综上，若 $x_1\neq x_2$ 我们总有 $h(x_1)\neq h(x_2)$ . 所以函数h是单射的.

对任意 $i\in\{i\in\mathbb{N} : 1\leqslant i\leqslant p+m\}$ ，若 $i\in\{i\in\mathbb{N} : 1\leqslant i\leqslant m\}\subseteq\{i\in\mathbb{N} : 1\leqslant i\leqslant p+m\}$ ，由f满射性知存在 $x\in X\subseteq X\cup Y$ ，使得 $f(x)=i$ ，由于 $x\in X$ 故 $h(x)=f(x)=i$ ，即若 $i\in\{i\in\mathbb{N} : 1\leqslant i\leqslant m\}$ 那么存在 $x\in X$ 使得 $h(x)=i$ ；若 $i\in\{i\in\mathbb{N} : m+1\leqslant i\leqslant m+p\}$ ，我们令 $i':=i-m\in\{i\in\mathbb{N} : 1\leqslant i\leqslant p\}$ ，由I的满射性知存在 $x\in Y\backslash X$ 使得 $I(x)=i'$ ，由于 $x\in Y\backslash X$ 故 $h(x)=I(x)+m=i'+m=i$ ，即若 $i\in\{i\in\mathbb{N} : m+1\leqslant i\leqslant m+p\}$ 那么存在 $x\in Y\backslash X$ 使得 $h(x)=I(x)+m=i'+m=i$ . 综上，函数h是满射的. 综上，函数h是双射的. 故 $\#(X\cup Y)=m+p\leqslant m+n=\#(X)+\#(Y)$ . 如果还知道 $X\cap Y=\emptyset$ ，则 $Y\backslash X=Y$ ，故 $\#(Y\backslash X)=n$ ，故 $\#(X\cup Y)=m+n=\#(X)+\#(Y)$ .

(d)由定义3.4.1知 $f(X)=\{f(x) : x\in X\}$ . 若 $x_0\in X$ 则有 $f(x_0)\in f(X)$ ，现在定义函数 $g:X\rightarrow\{f(x) : x\in X\}$ 如下： $g(x):=f(x)\in f(X)$ . 易知对任意 $x\in X$ 我们都定义了 $g(x)$ 并且有 $g(x)\in\{f(x) : x\in X\}$ . 如果f是1对1的，即对任意 $x_1,x_2\in X$ ，若 $x_1\neq x_2$ 则 $f(x_1)\neq f(x_2)$ ，即 $g(x_1)\neq g(x_2)$ ，故g也为单射. 对任意 $y\in\{f(x) : x\in X\}$ ，由替换公理知对某 $x\in X$ 有 $y=f(x)$ ，即有 $y=g(x)$ ，故此时g为满射. 综上，g为双射，由定义3.6.1和习题3.6.1以及定义3.6.5和定义3.6.10知 $\{f(x) : x\in X\}$ 也是有限集，并且 $\#(f(X))=\#(X)$ .

由于X是有限集，则 $\#(X)=n$ 为某一自然数. 若 $n=0$ ，由习题3.6.2知 $X=\emptyset$ ，进而 $f:X\rightarrow Y$ 是空函数，由习题3.3.3知其也为单射的，由替换公理知 $f(X)=\{f(x) : x\in X\}=\emptyset$ ，故此时有 $\#(f(X))=\#(\emptyset)\leqslant\#(\emptyset)\#(X)$ . 若 $n=1$ ，由习题3.6.4(c)知 $X=\{x_0\}$ ，进而 $f(X)=\{f(x) : x\in X\}=\{f(x_0)\}$ . 故此时 $\#(f(X))=1=\#(X)$ ，故也有 $\#(f(X))\leqslant\#(X)$ . 现归纳假设当 $\#(X)=n$ 时命题成立，那么对 $\#(X)=n++$ 时，当f不是1对1的，则存在 $x_1,x_2\in X$ ，有 $x_1\neq x_2$ 但 $f(x_1)=f(x_2)$ . 易验证 $f(X)=f(X\backslash \{x_1\})$ ，由引理3.6.8知 $\#(X\backslash\{x_1\})=\#(X)-1=n$ ，由归纳假设知 $\#(f(X\backslash\{x_1\}))\leqslant\#(X\backslash\{x_1\})=n$ . 再由于 $f(X)=f(X\backslash\{x_1\})$ 知 $\#(f(X))=\#(f(X\backslash\{x_1\}))\leqslant n<n+1=\#(X)$ . 这就完成了归纳.

(e)已知X和Y是有限集，则有 $\#(X)=m,\#(Y)=n$ (其中m,n为自然数). 若 $n=0$ 或者 $m=0$ ，显然有 $\#(X)\times\#(Y)=0$ ，由习题3.6.2和习题3.5.8知 $X\times Y=\emptyset$ ，进而 $\#(X\times Y)=0$ ，故 $\#(X\times Y)=\#(X)\times\#(Y)$ .

再来考虑m,n是均不为0的自然数. 由于X和Y是有限集，所以存在双射函数 $f:X\rightarrow\{i\in\mathbb{N} : 1\leqslant i\leqslant m\}$ 和双射函数 $g:Y\rightarrow\{i\in\mathbb{N} : 1\leqslant i\leqslant n\}$ . 我们现在定义一个新函数 $h:X\times Y\rightarrow\{i\in\mathbb{N} : 1\leqslant i\leqslant m\times n\}$ 如下： $h(x,y):=f(x)+(g(y)-1)\times m$ . 由于 $f(x)\in\{i\in\mathbb{N} : 1\leqslant i\leqslant m\}$ 并且 $g(y)\in\{i\in\mathbb{N} : 1\leqslant i\leqslant n\}$ 知 $1\leqslant f(x)\leqslant m$ 并且 $1\leqslant g(y)\leqslant n$ . 故有 $0\leqslant g(y)-1\leqslant n-1$ ，进一步有 $0\leqslant (g(y)-1)\times m\leqslant (n-1)\times m$ ，故 $1\leqslant f(x)+(g(y)-1)\times m\leqslant m\times n$ ，故 $h(x,y)\in\{i\in\mathbb{N} : 1\leqslant i\leqslant m\times n\}$ ，综上，函数h是定义成功的. 接下来我们证明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$ ”. 由f和g的单射性有“ $f(x_1)\neq f(x_2)$ 或者 $(g(y_1)-1)\times m\neq (g(y_2)-1)\times m$ ”. 我们分三种情况讨论：1. $f(x_1)=f(x_2)$ 并且 $(g(y_1)-1)\times m\neq (g(y_2)-1)\times m$ ，此时显然有 $h(x_1,y_1)\neq h(x_2,y_2)$ . 2. $f(x_1)\neq f(x_2)$ 并且 $(g(y_1)-1)\times m=(g(y_2)-1)\times m$ ，此时显然有 $h(x_1,y_1)\neq h(x_2,y_2)$ . 3. $f(x_1)\neq f(x_2)$ 并且 $(g(y_1)-1)\times m\neq(g(y_2)-1)\times m$ ，我们假设有 $h(x_1,y_1)=h(x_2,y_2)$ ，即有 $f(x_1)+(g(y_1)-1)\times m=f(x_2)+(g(y_2)-1)\times m$ ，即有 $f(x_2)-f(x_1)=m\times (g(y_1)-g(y_2))$ ，故 $f(x_2)-f(x_1)$ 应为m的整数倍. 而 $f(x_1),f(x_2)\in\{i\in\mathbb{N} : 1\leqslant i\leqslant m\}$ ，故 $1-m\leqslant f(x_2)-f(x_1)\leqslant m-1$ ，故 $f(x_2)-f(x_1)$ 不可能为m的整数倍，所以假设不成立，即 $h(x_1,y_1)\neq h(x_2,y_2)$ . 综合这三种情况，我们知若 $(x_1,y_1)\neq(x_2,y_2)$ 则 $h(x_1,y_1)\neq h(x_2,y_2)$ . 故h单射性得证.

再来证明其满射性. 对任何 $i\in\{i\in\mathbb{N} : 1\leqslant i\leqslant m\times n\}$ ，由命题2.3.9知 $i=k\times m+r$ (其中k,r均为自然数且 $0\leqslant r<m$ ). 若 $r=0$ ，则 $i=k\times m$ . 又因为 $1\leqslant i\leqslant m\times n$ ，即 $1\leqslant k\times m\leqslant m\times n$ ，进而 $1\leqslant k\leqslant n$ ，再考虑函数f和g的值域我们能取 $f(x)=m$ 和 $g(y)=k$ . 此时 $i=k\times m=g(y)\times m=(g(y)-1)\times m+m=(g(y)-1)\times m+f(x)=h(x,y)$ . 即若 $i=km$ ，那么存在 $(x,y)\in X\times Y$ 使得 $i=h(x,y)$ . 若 $r\neq 0$ ，即 $0<r<m$ ，进而 $1\leqslant r\leqslant m-1$ ，我们取 $f(x)=r$ . 由 $1\leqslant i\leqslant m\times n$ 知 $2-m\leqslant k\times m=i-r\leqslant m\times n-1$ ，故 $\frac{2}{m}-1\leqslant k\leqslant n-\frac{1}{m}$ ，由于k为自然数，故由 $\frac{2}{m}-1\leqslant k\leqslant n-\frac{1}{m}$ 我们知 $-1<k<n$ ，即 $0\leqslant k\leqslant n-1$ ，我们令 $g(y)=k+1$ ，此时 $i=k\times m+r=k\times m+f(x)=f(x)+(g(y)-1)\times m=h(x,y)$ . 综上，对任何 $i\in\{i\in\mathbb{N} : 1\leqslant i\leqslant m\times n\}$ 我们将其化为 $f(x)+(g(y)-1)\times m$ 的形式，即存在 $(x,y)\in X\times Y$ 使得 $h(x,y)=i$ . 所以h的满射性得证. 所以函数h为双射，故 $\#(X\times Y)=m\times n=\#(X)\times \#(Y)$ .

(f)已知X和Y是有限集，即 $\#(X)=m$ 和 $\#(Y)=n$ (m,n均为自然数). 由幂集公理知存在集合 $Y^{X}=\{f : \text{the domian of f is X and the range of f is Y}\}$ . 当 $\#(X)=0$ 时，由习题3.6.2知 $X=\emptyset$ ，考虑函数 $f:X\rightarrow Y$ ，其即为 $f:\emptyset\rightarrow Y$ ，是一个空函数，容易证明其是唯一的，故 $Y^{X}=\{f:\emptyset\rightarrow Y\}$ 是单元素集，易证 $\#(Y^{X})=1$ ，而此时 $(\#(Y))^{\#(X)}=(\#(Y))^{0}=1$ . 综上，当 $\#(X)=0$ 时，有 $\#(Y^{X})=(\#(Y))^{\#(X)}$ .

现归纳假设当 $\#(X)=m$ 时，有 $\#(Y^{X})=(\#(Y))^{\#(X)}$ . 现来证当 $\#(X)=m++$ 时命题亦成立. 由于 $\#(X)=m++\neq 0$ ，故X不为空集，进而Y也不为空集. 由引理3.1.6知存在元素 $x_0\in X$ 和存在元素 $y_0\in Y$ . 对任何对象 $f\in Y^X$ ，由函数定义知 $f(x_0)\in Y$ ，即 $f(x_0)$ 为Y中的一个元素. 由分类公理知存在集合 $\{f\in Y^X : f(x_0)=y_0\}$ ，我们记其为 $A_{y_0}$ . 由替换公理和并公理知存在集合 $\bigcup\{\{f\in Y^X : f(x_0)=y\} : y\in Y\}$ ，我们记其为 $\displaystyle\bigcup_{y\in Y}{A_y}$ . 对任意元素 $f\in Y^X$ ，由函数定义知 $f(x_0)\in Y$ ，我们记 $y_1:=f(x_0)$ . 故对 $y_1\in Y$ ，有 $f\in\{f\in Y^X : f(x_0)=y_1\}$ ，进而 $\displaystyle f\in\bigcup_{y\in Y}{A_y}$ . 对任意元素 $f\in\displaystyle\bigcup_{y\in Y}{A_y}$ ，则有对某 $y_f\in Y$ 有 $f\in A_{y_f}$ ，即对某 $y_f\in Y$ 有 $f\in\{f\in Y^X : f(x_0)=y_f\}$ ，故 $f\in Y^X$ . 综上，我们有 $\displaystyle\bigcup_{y\in Y}{A_y}=Y^X$ . 现考虑集合 $A_y=\{f\in Y^X : f(x_0)=y\}$ 和集合 $Y^{X\backslash\{x_0\}}=\{g : \text{g is a function with domain } X\backslash\{x_0\}\text{ and range Y}\}$ ，我们定义函数 $H:A_y\rightarrow Y^{X\backslash\{x_0\}}$ 如下： $H(f):=g$ ，其中f和g满足性质：对任何 $x\in X\backslash\{x_0\}$ 有 $f(x)=g(x)$ . 我们考虑这个函数是否定义成功，即对每一个 $f\in A_y$ ，恰有一个 $g\in Y^{X\backslash\{x_0\}}$ 满足上述性质. 假若仍有 $g'\in Y^{X\backslash\{x_0\}}$ 满足上述性质，那么对任何 $x\in X\backslash\{x_0\}$ 有 $f(x)=g'(x)=g(x)$ ，进而 $g'=g$ ，故函数定义是成功的. 现在来证明函数H的双射性. 对任何 $f_1,f_2\in A_y$ ，若 $f_1\neq f_2$ ，即存在 $x'\in X$ 使得 $f_1(x')\neq f_2(x')$ . 由于 $f_1,f_2\in A_y$ ，故有 $f_1(x_0)=f_2(x_0)=y$ ，所以我们知道 $x'\neq x_0$ ，进而存在 $x'\in X\backslash\{x_0\}$ 使得 $f_1(x')\neq f_2(x')$ . 我们假设 $H(f_1)=H(f_2)$ ，那么有任何 $x\in X\backslash\{x_0\}$ 有 $f_1(x)=g_1(x)=g_2(x)=f_2(x)$ ，这显然与 $f_1\neq f_2$ 相矛盾，故H为单射. 对任何 $g\in Y^{X\backslash\{x_0\}}$ ，可以定义函数 $f:X\rightarrow Y$ ，其中对任何对象 $x\in X\backslash\{x_0\}$ 有 $f(x)=g(x)$ 并且 $f(x_0)=y$ . 显然有 $f\in A_y$ 并且 $H(f)=g$ ，故H为满射. 综上，H为双射.

到这我们知道了 $\#(A_y)=\#(Y^{X\backslash\{x_0\}})$ ，而由归纳假设知 $\#(Y^{X\backslash\{x_0\}})=(\#(Y))^{\#(X\backslash\{x_0\})}=n^m$ ，故 $\#(A_y)=n^m$ .

我们现在来证对 $y_1,y_2\in Y$ ，若 $y_1\neq y_2$ 则 $A_{y_1}\cap A_{y_2}=\emptyset$ . 反证法，假设 $A_{y_1}\cap A_{y_2}\neq\emptyset$ ，由引理3.1.6知存在 $f\in\{f\in Y^X : f(x_0)=y_1\}$ 并且 $f\in\{f\in Y^X : f(x_0)=y_2\}$ ，进而我们得到 $f(x_0)=y_1=y_2$ ，这明显与 $y_1\neq y_2$ 相矛盾，故 $A_{y_1}\cap A_{y_2}=\emptyset$ . 至此，我们可以说对任意 $y_1,y_2\in Y$ 我们都有 $A_{y_1},A_{y_2}$ 是不交的.

我们再来证明一个小引理. 若I为(非空)有限集，并且对每个元素 $\alpha\in I$ 对应着一个有限集 $A_\alpha$ ，那么我们有 $\displaystyle\bigcup_{\alpha\in I}{A_\alpha}$ 也是有限集，并且 $\displaystyle\#(\bigcup_{\alpha\in I}{A_\alpha})\leqslant\sum_{\alpha\in I}{\#(A_\alpha)}$ ；若还知道 $A_\alpha$ 两两之间都不相交，则不等式加强为 $\displaystyle\#(\bigcup_{\alpha\in I}{A_\alpha})=\sum_{\alpha\in I}{\#(A_\alpha)}$ .

证明：当 $I=\emptyset$ 时，不存在集族 $A_\alpha$ ， $\displaystyle\bigcup_{\alpha\in I}{A_\alpha}$ 是空集，并且不等式 $\displaystyle\#(\bigcup_{\alpha\in I}{A_\alpha})\leqslant\sum_{\alpha\in I}{\#(A_\alpha)}$ 右边是没有任何意义的，因为不存在集族 $A_\alpha$ ，所以不在我们的考虑范围之内.

若 $\#(I)=1$ ，我们很容易证明其是单元素集. 因为 $\#(I)=1$ ，所以存在双射 $f:\{1\}\rightarrow I$ . 由于f是双射，所以其是满射，进而对任意 $i_1,i_2\in I$ 都存在 $x_1,x_2\in\{1\}$ 使得 $f(x_1)=i_1,f(x_2)=i_2$ ，进而任意 $i_1,i_2\in I$ 都存在 $x_1=x_2=1$ 使得 $f(x_1)=i_1=f(x_2)=i_2$ ，故I是单元素集. 所以I中只有一个标签，对应着一个集族，我们不妨记此标签(即I中唯一元素)为i，此集族为 $A_i$ . 此时 $\displaystyle\bigcup_{\alpha\in I}{A_\alpha}=\bigcup{\{A_\alpha : \alpha\in I\}}=\bigcup{\{A_\alpha : \alpha\in\{i\}\}}=\bigcup{\{A_i : i\}}=A_i$ . 故有 $\displaystyle\#(\bigcup_{\alpha\in I}{A_\alpha})=\#(A_i)=\#(\sum_{\alpha\in I}{A_\alpha})$ ，这就完成了归纳基始. 归纳假设当 $\#(I)=n$ 时命题成立. 那么对 $\#(I)=n++$ ，由于 $n++\neq 0$ ，所以I非空，进一步存在元素 $i_0\in I$ . 易证 $\displaystyle\bigcup_{\alpha\in I}{A_\alpha}=\bigcup_{\alpha\in I\backslash\{i_0\}}{A_\alpha}\cup A_{i_0}$ ，由归纳假设知 $\displaystyle\#(\bigcup_{\alpha\in I\backslash\{i_0\}}{A_\alpha})\leqslant\sum_{\alpha\in I\backslash\{i_0\}}{\#(A_\alpha)}$ ，由习题3.6.4(b)知 $\displaystyle\#(\bigcup_{\alpha\in I\backslash\{i_0\}}{A_\alpha}\cup A_{i_0})\leqslant\#(\bigcup_{\alpha\in I\backslash\{i_0\}}{A_\alpha})+\#(A_{i_0})\leqslant\sum_{\alpha\in I\backslash\{i_0\}}{\#(A_\alpha)}+\#(A_{i_0})$ ，即 $\displaystyle\#(\bigcup_{\alpha\in I\backslash\{i_0\}}{A_\alpha}\cup A_{i_0})\leqslant\sum_{\alpha\in I}{\#(A_\alpha)}$ ，即 $\displaystyle\#(\bigcup_{\alpha\in I}{A_\alpha})\leqslant\sum_{\alpha\in I}{\#(A_\alpha)}$ .

当 $A_\alpha$ 两两之间都不相交时，由归纳假设我们知 $\displaystyle\#(\bigcup_{\alpha\in I\backslash\{i_0\}}{A_\alpha})=\sum_{\alpha\in I\backslash\{i_0\}}{\#(A_\alpha)}$ ，由习题3.6.4(b)知 $\displaystyle\#(\bigcup_{\alpha\in I\backslash\{i_0\}}{A_\alpha}\cup A_{i_0})=\#(\bigcup_{\alpha\in I\backslash\{i_0\}}{A_\alpha})+\#(A_{i_0})=\sum_{\alpha\in I\backslash\{i_0\}}{\#(A_\alpha)}+\#(A_{i_0})=\sum_{\alpha\in I}{\#(A_\alpha)}$ . 这就完成了归纳.

故我们有 $\displaystyle\#(\bigcup_{y\in Y}{A_y})=\sum_{y\in Y}{\#(A_y)}=\sum_{y\in Y}{n^m}=n\times n^m=n^{m++}$ ，即 $\#(Y^X)=n^{m++}$ ，这就完成了归纳.

3.6.5 证明： $A\times B=\{(a,b) : a\in A,b\in B\};B\times A=\{(b,a) : b\in B,a\in A\}$ . 现在定义函数 $f:A\times B\rightarrow B\times A$ 如下： $f(a,b):=(b,a)$ ，容易验证此函数对 $A\times B$ 中每个元素指定了唯一输出. 下面来证明其双射性.

对任意 $(b,a)\in B\times A$ ，存在 $(a,b)\in A\times B$ 使得 $f(a,b)=(b,a)$ ，故f是满射的.

对任意 $(a_1,b_1),(a_2,b_2)\in A\times B$ ，若 $(a_1,b_1)\neq(a_2,b_2)$ ，即“ $a_1\neq a_2$ 或 $b_1\neq b_2$ ”，故有 $(b_1,a_1)\neq(b_2,a_2)$ ，即 $f(a_1,b_1)\neq f(a_2,b_2)$ . 故f为单射，综上f为双射.

由注3.6.15启发，我们可以定义基数乘法： $\#(A)\times\#(B):=\#(A\times B)$ .

由于 $\#(A)\times\#(B)=\#(A\times B)$ 并且 $\#(B)\times\#(A)=\#(B\times A)$ ，我们已证 $\#(A\times B)=\#(B\times A)$ ，故 $\#(A)\times\#(B)=\#(B)\times\#(A)$ . 即乘法是交换的.

3.6.6 证明：由幂集公理知 $(A^B)^C=\{f : \text{f is a function with domain C and range }A^B\}$ ， $A^{B\times C}=\{g : \text{g is a function with domain } B\times C \text{ and range A}\}$ . 现定义函数 $H:(A^B)^C\rightarrow A^{B\times C}$ 如下： $H(f):=g$ ，其中f,g满足性质：对任意 $b\in B$ ，对任意 $c\in C$ 有 $[f(c)](b)=g(b,c)$ . 现考虑函数是否被正确构造. 假若 $H(f)$ 有两输出 $g,g'$ 满足性质要求，即有对任意 $b\in B$ ，对任意 $c\in C$ 有 $[f(c)](b)=g(b,c)$ 并且 $[f(c)](b)=g'(b,c)$ ，进而对任何 $(b,c)\in B\times C$ 有 $g(b,c)=g'(b,c)$ . 故函数对每个输入给出的输出是唯一的，所以函数是定义成功的. 现在来考虑其双射性.

对任意 $f_1,f_2\in (A^B)^C$ ，若 $f_1\neq f_2$ ，则存在 $c_0\in C$ 使得 $f_1(c_0)\neq f_2(c_0)$ . 进而存在 $b_0\in B$ 使得 $[f_1(c_0)](b_0)\neq [f_2(c_0)](b_0)$ . 假若 $H(f_1)=H(f_2)$ ，即有 $H(f_1)=g_1=g_2=H(f_2)$ ，即有对任意 $b\in B$ 对任意 $c\in C$ 有 $[f_1(c)](b)=g_1(b,c)=g_2(b,c)=[f_2(c)](b)$ ，这显然是矛盾的，故 $H(f_1)\neq H(f_2)$ . 故H单射性得证.

对任意对象 $g\in A^{B\times C}$ ，对某个 $c_0\in C$ 我们定义函数 $h_0:B\rightarrow A,h_0(b):=g(b,c_0)$ ;再对每个 $c\in C$ 我们定义函数 $f:C\rightarrow A^B,f(c):=h_c$ . 此时对任意 $c\in C$ 对任意 $b\in B$ 有 $[f(c)](b)=h_c(b)=g(b,c)$ . 故 $H(f)=g$ . 故H是满射的. 综上，H是双射，故有 $\#((A^B)^C)=\#(A^{B\times C})$ .

再由命题3.6.14知 $(\#(A)^{\#(B)})^{\#(C)}=\#(A^B)^{\#(C)}=\#((A^B)^C)=\#(A^{B\times C})=\#(A)^{\#(B\times C)}=\#(A)^{\#(B)\times\#(C)}$ .

综上，对任何自然数a,b,c有 $(a^b)^c=a^{bc}$ 成立.

设A,B,C是集合并且 $B\cap C=\emptyset$ . 现在来证集合 $A^B\times A^C$ 与集合 $A^{B\cup C}$ 之间存在一个双射函数.

证明：定义函数 $H:A^B\times A^C\rightarrow A^{B\cup C},H(f,g):=h$ ，其中f,g,h满足以下性质：对任意输入 $(f,g)\in A^B\times A^C$ ，函数H给出的输出是一个函数 $h:B\cup C\rightarrow A$ ，此h函数满足对 $x\in B$ 有 $h(x):=f(x)$ 并且对 $x\in C$ 有 $h(x):=g(x)$ . 由于 $B\cap C=\emptyset$ ，所以对任意 $x\in B\cup C$ 都唯一定义了h(x)，即输出h是定义成功的. 并且容易验证对任意 $(f,g)\in A^B\times A^C$ 都有唯一的输出h满足上述性质，故H的定义也是成功的. 现在验证H的双射性.

对任意 $(f_1,g_1),(f_2,g_2)\in A^B\times A^C$ ，若 $(f_1,g_1)\neq (f_2,g_2)$ ，即 $f_1\neq f_2$ 或 $g_1\neq g_2$ ，即“存在 $b_0\in B$ 使得 $f_1(b_0)\neq f_2(b_0)$ ”或“存在 $c_0\in C$ 使得 $g_1(b_0)\neq g_2(b_0)$ ”. 我们假设 $H(f_1,g_1)=H(f_2,g_2)$ ，即 $h_1=h_2$ ，即对任意 $x\in B\cup C$ ，若 $x\in B$ 则 $f_1(x)=h_1(x)=h_2(x)=f_2(x)$ ；若 $x\in C$ 则 $g_1(x)=h_1(x)=h_2(x)=g_2(x)$ . 这明显与 $(f_1,g_1)\neq (f_2,g_2)$ 蕴涵的结论矛盾，故假设不成立，所以H是单射的.

对任意 $h\in A^{B\cup C}$ ，我们定义函数 $f:B\rightarrow A,f(x):=h(x)$ ，并且定义函数 $g:C\rightarrow A,g(x):=h(x)$ . 显然有 $f\in A^B,g\in A^C$ ，故存在 $(f,g)\in A^B\times A^C$ 使得 $H(f,g)=h$ . 综上，H为满射，进而为双射，所以 $\#(A^B\times A^C)=\#(A^{B\cup C})$ .

由命题3.6.14知有 $\#(A)^{\#(B)}\times \#(A)^{\#(C)}=\#(A^B)\times\#(A^C)=\#(A^B\times A^C)=\#(A^{B\cup C})=\#(A)^{\#(B\cup C)}=\#(A)^{\#(B)+\#(C)}$ . 由于 $\#(A),\#(B),\#(C)$ 为任意自然数，则 $a^b\times a^c=a^{b+c}$ .

3.6.7 证明：已知A,B均为有限集. 若 $\#(A)\leqslant\#(B)$ ，首先我们知道存在双射函数 $f:A\rightarrow\{i\in\mathbb{N} : 1\leqslant i\leqslant m\}$ 和双射函数 $g:\{i\in\mathbb{N} : 1\leqslant i\leqslant n\}\rightarrow B$ . 由 $\#(A)\leqslant\#(B)$ 知 $m\leqslant n$ . 由习题3.3.2知存在单射函数 $h:A\rightarrow B,h=g\circ f$ ，故A的基数小于或等于B的基数. 综上，若 $\#(A)\leqslant\#(B)$ 那么A的基数小于或等于B的基数.

若A的基数小于或等于B的基数，则存在一个单射函数 $h:A\rightarrow B$ ，由函数前象知 $h(A)=\{h(x) : x\in A\}$ ，易验证 $h(A)\subseteq B$ ，由命题3.6.14(c)知 $\#(h(A))\leqslant\#(B)$ ，再由h是单射和命题3.6.14(d)知 $\#(f(A))=\#(A)$ ，综上，有 $\#(A)\leqslant\#(B)$ . 故若A的基数小于或等于B的基数那么有 $\#(A)\leqslant\#(B)$ .

综上，A的基数小于或等于B的基数当且仅当 $\#(A)\leqslant\#(B)$ .

3.6.8 证明：由函数前象定义知有集合 $f(A)=\{f(x) : x\in A\}$ ，易验证 $f(A)\subseteq B$ .

若 $A=\emptyset$ ，显然f为单射，并且只当 $B=\emptyset$ 时 $g:B\rightarrow A$ 是满射. 所以我们不应考虑此情况.

若 $A\neq\emptyset$ ，易知 $B\neq\emptyset$ 并且 $f(A)\neq\emptyset$ ，我们定义函数g如下：若 $b_0\in f(A)\subseteq B$ ，由替换公理知对某 $x_0\in A$ 有 $b_0=f(x_0)$ ，假若仍有某 $x_1\in A$ 使得 $b_0=f(x_1)=f(x_0)$ ，由f单射性知 $x_1=x_0$ . 综上，若 $b_0\in f(A)\subseteq B$ ，那么有唯一的 $x_0\in A$ 使得 $b_0=f(x_0)$ ，故我们定义 $g(b_0):=x_0$ . 若 $b_1\in B\backslash f(A)$ ，可令 $g(b_1):=x$ ，其中x为A的任意元素.

对任意 $a\in A$ ，由替换公理知 $f(a)\in f(A)\subseteq B$ ，由g定义知 $g(f(a))=a$ ，故g为满射.

3.6.9 证明：当 $\#(A\cap B)=0$ ，即 $A\cap B=\emptyset$ 时，习题3.6.4已证明 $\#(A)+\#(B)=\#(A\cup B)$ ，由于 $\#(A\cap B)=0$ ，即有 $\#(A)+\#(B)=\#(A\cup B)+\#(A\cap B)$ . 现归纳假设当 $\#(A\cap B)=n$ 时有 $\#(A)+\#(B)=\#(A\cup B)+\#(A\cap B)$ ，要证对 $\#(A\cap B)=n++$ 时命题亦成立. 由于 $\#(A\cap B)=n++\neq 0$ ，可知 $A\cap B$ 非空，进而存在一个对象 $x_0\in A\cap B$ ，由引理3.6.9知 $\#((A\cap B)\backslash\{x_0\})=n$ . 易验证 $A\cap(B\backslash\{x_0\})=(A\cap B)\backslash\{x_0\}$ ，由归纳假设知 $\#(A)+\#(B\backslash\{x_0\})=\#(A\cup(B\backslash\{x_0\}))+\#(A\cap(B\backslash\{x_0\}))$ ，易验证 $A\cup B=A\cup(B\backslash\{x_0\})$ ，故 $\#(A\cup(B\backslash\{x_0\}))+\#(A\cap(B\backslash\{x_0\}))=\#(A\cup B)+\#((A\cap B)\backslash\{x_0\})$ ，即 $\#(A)+(\#(B)-1)=\#(A\cup B)+(\#(A\cap B)-1)$ ，故 $\#(A)+\#(B)=\#(A\cup B)+\#(A\cap B)$ ，这就完成了归纳.

3.6.10 证明：由习题3.6.4(f)知 $\displaystyle\#(\bigcup_{i\in\{1,...,n\}}{A_i})\leqslant\sum_{i\in\{1,...,n\}}{\#(A_i)}$ . 假设结论不成立，则对一切 $i\in\{1,...,n\}$ 有 $\#(A_i)<2$ ，即 $\#(A_i)\leqslant 1$ ，故 $\displaystyle\sum_{i\in\{1,...,n\}}{\#(A_i)}\leqslant n$ ，与条件矛盾，故假设不真，结论得证.

文内补充

1.设X为自然数集而Y为偶数集，那么映射 $f:X\rightarrow Y,f(n)=2n$ 为从X到Y的双射.

证明：对任意 $n_1,n_2\in\mathbb{N}$ ，若 $n_1\neq n_2$ ，那么有 $2n_1\neq 2n_2$ ，即 $f(n_1)\neq f(n_2)$ . 故f为单射.

对任意 $n\in\{2k : k\in\mathbb{N}\}$ ，由替换公理知对某 $k\in\mathbb{N}$ 有 $n=2k=f(k)$ ，故f为满射.

2.集合 $\{i\in\mathbb{N} : i<n\}$ 和集合 $\{i\in\mathbb{N} : 1\leqslant i\leqslant n\}$ 具有同样的基数. 双射是什么？

双射为 $f:\{i\in\mathbb{N} : i<n\}\rightarrow\{i\in\mathbb{N} : 1\leqslant i\leqslant n\},f(n)=n+1$ .

3.不存在空集到非空集的双射.

前面我们已经论证了空函数一定是单射，这对空函数是空真的成立的，没有提供出任何其他信息. 所以我们只需考虑其是否可能是满射. 对于值域为非空集的空函数，若其为满射，则有对所有值域中的元素我们都可以在定义域中找到一个元素映射到它. 由于值域非空，我们可以选取一个元素，然后必须在空集中找到一个元素映射到它，而空集不含任何元素，这是不可能的，故空函数在值域为非空集时不可能是满射，进而不可能是双射.

4.引理3.6.9中 $g:X\backslash\{x\}\rightarrow\{i\in\mathbb{N} : 1\leqslant i\leqslant n-1\}$ 是双射的证明.

证明：已知 $f:X\rightarrow\{i\in\mathbb{N} : 1\leqslant i\leqslant n\}$ 为双射，我们定义一个新函数 $g:X\backslash\{x\}\rightarrow\{i\in\mathbb{N} : 1\leqslant i\leqslant n-1\}$ (x为X中的某一元素)，其中 $g(x)$ 定义为：对任何 $y\in X\backslash\{x\}$ ，若 $f(y)<f(x)$ 则 $g(y):=f(y)$ ；若 $f(y)>f(x)$ 则 $g(y):=f(y)-1$ . 注意到对 $y\in X\backslash\{x\}$ 有 $y\neq x$ ，再由f的双射性我们知 $f(y)\neq f(x)$ ，故 $X\backslash\{x\}$ 中的每个元素都定义了其函数值. 我们再来考虑值域的定义是否无误. 已知 $f(x)\in\{i\in\mathbb{N} : 1\leqslant i\leqslant n\}$ ，则 $1\leqslant f(x)\leqslant n$ . 进而对 $y\in X\backslash\{x\}\subsetneq X$ 亦有 $1\leqslant f(y)\leqslant n$ . 若 $f(y)<f(x)$ ，则有 $1\leqslant f(y)<f(x)\leqslant n$ ，进而有 $1\leqslant f(y)\leqslant n-1$ ，故 $g(y)=f(y)\in\{i\in\mathbb{N} : 1\leqslant i\leqslant n-1\}$ ；若 $f(y)>f(x)$ ，则有 $1\leqslant f(x)<f(y)\leqslant n$ ，进而有 $1<f(y)\leqslant n$ ，进而 $0<f(y)-1\leqslant n-1$ ，故 $g(y)=f(y)-1\in\{i\in\mathbb{N} : 1\leqslant i\leqslant n-1\}$ . 至此我们可以肯定地说函数g是定义成功的了. 接下来我们就证明g的双射性.

对任意 $a,b\in X\backslash\{x\}\subsetneq X$ ，若 $a\neq b$ ，由f的单射性我们知 $f(a)\neq f(b)$ . 我们分四种情况讨论g的单射性. 1.若 $f(a)<f(x)$ 且 $f(b)<f(x)$ ，则有 $g(a)=f(a)\neq f(b)=g(b)$ ；2.若 $f(a)>f(x)$ 且 $f(b)>f(x)$ ，则有 $g(a)=f(a)-1\neq f(b)-1=g(b)$ ；3.若 $f(a)<f(x)$ 且 $f(b)>f(x)$ ，则有 $g(a)=f(a)<f(x)<f(b)$ ，进而 $g(a)=f(a)<f(x)\leqslant f(b)-1=g(b)$ ；4.若 $f(a)>f(x)$ 且 $f(b)<f(x)$ 同理如情况3我们也有 $g(a)\neq g(b)$ . 综上g的单射性得证.

对任意 $i_0\in\{i\in\mathbb{N} : 1\leqslant i\leqslant n-1\}$ ，若 $i_0<f(x)$ ，由f双射性知存在 $x_0\in X$ 使得 $f(x_0)=i_0$ . 我们假设 $x_0=x$ ，则有 $f(x_0)=f(x)$ ，故 $i_0=f(x)$ ，这是矛盾的. 故若 $i_0<f(x)$ ，则存在 $x_0\in X\backslash\{x\}$ 使得 $f(x_0)=i_0$ . 又由于 $f(x_0)=i_0<f(x)$ ，故此时 $g(x_0)=f(x_0)=i_0$ . 综上，若 $i_0<f(x)$ ，则存在 $x_0\in X\backslash\{X\}$ 使得 $g(x_0)=f(x_0)=i_0$ . 若 $i_0\geqslant f(x)$ ，我们令 $i_1:=i_0+1>f(x)$ ，由于 $i_0\in\{i\in\mathbb{N} : 1\leqslant i\leqslant n-1\}$ ，故 $i_1\in\{i\in\mathbb{N} : 1\leqslant i\leqslant n\}$ . 再由f双射性知存在 $x_1\in X$ 使得 $f(x_1)=i_1$ . 同理我们假设有 $x_1=x$ ，进而 $f(x_1)=f(x)$ ，这与 $f(x_1)=i_1=i_0+1>f(x)$ 是相矛盾的，故假设不成立. 综上，若 $i_0\geqslant f(x)$ ，那么存在 $x_1\in X\backslash\{x\}$ 使得 $f(x_1)=i_1$ ，此时由于 $f(x_1)=i_1=i_0+1>f(x)$ ，故 $g(x_1)=f(x_1)-1=i_0$ . 即若 $i_0\geqslant f(x)$ ，那么存在 $x_1\in X\backslash\{x\}$ 使得 $g(x_1)=i_0$ .