习题
1. (a) 写出所有单射
证明它们都不是一一对应。（这里给出了基数为3的集合\(A\)其基数不为4的一个直接的证明。）
(b) 有多少个单射
（你会发现我们为什么不试图直接证明在这两个集合之间不存在一一对应。）
2. 证明：若\(B\)不是有限集，并且\(B\subset A\)，则\(A\)也不是有限集。
3. 设\(X\)为二元素集\(\{0,1\}\)。求出\(X^{\omega}\)与其一个真子集之间的一一对应。
4. 设\(A\)是一个非空的有限全序集。
(a) 证明\(A\)有一个最大元。[提示：对\(A\)的基数进行归纳。]
(b) 证明\(A\)具有正整数的一个截的序型。
5. \(A\times B\)为有限集是否蕴含着\(A\)与\(B\)都是有限集？
6. (a) 设\(A=\{1,\cdots,n\}\)。证明：在\(\mathcal{P}(A)\)与笛卡尔积\(x^n\)之间存在一个一一对应，其中\(X=\{0,1\}\)为二元素集。
(b) 证明：若\(A\)是一个有限集，则\(\mathcal{P}(A)\)也是有限集。
7. 若\(A\)和\(B\)都是有限的，证明所有函数\(f:A\rightarrow B\)的集合是一个有限集。
解答
1. 解 (a) 所有单射如下
| $x$ | 1 | 2 | 3 | $x$ | 1 | 2 | 3 | $x$ | 1 | 2 | 3 | $x$ | 1 | 2 | 3 |
| $y$ | 1 | 2 | 3 | $y$ | 1 | 2 | 4 | $y$ | 1 | 3 | 4 | $y$ | 2 | 3 | 4 |
| $y$ | 1 | 3 | 2 | $y$ | 1 | 4 | 2 | $y$ | 1 | 4 | 3 | $y$ | 2 | 4 | 3 |
| $y$ | 2 | 1 | 3 | $y$ | 2 | 1 | 4 | $y$ | 3 | 1 | 4 | $y$ | 3 | 2 | 4 |
| $y$ | 2 | 3 | 1 | $y$ | 2 | 4 | 1 | $y$ | 3 | 4 | 1 | $y$ | 3 | 4 | 2 |
| $y$ | 3 | 1 | 2 | $y$ | 4 | 1 | 2 | $y$ | 4 | 1 | 3 | $y$ | 4 | 2 | 3 |
| $y$ | 3 | 2 | 1 | $y$ | 4 | 2 | 1 | $y$ | 4 | 3 | 1 | $y$ | 4 | 3 | 2 |
一共有24个。不难看出，对于1-4列，4不存在原像；对于5-8列，3不存在原像；对于9-12列，2不存在原像；对于13-16列，1不存在原像。故它们都不是一一对应。
(b) 有\(\mathrm{A}_{10}^8=1814400\)个。对这些单射逐一验证是极其耗费时间和精力的。
2. 证明 若\(A\)是一个有限集，则存在单射\(f:A\rightarrow \{1,\cdots,n\}\)，那么\(f|_B\)就是从\(B\)到截\(\{1,\cdots, n\}\)的一个单射，与\(B\)的非有限性矛盾。
$\square$
3. 解 定义\(f:X^{\omega}\rightarrow A,f((x_1,x_2,\cdots))=(0,x_1,x_2,\cdots)\)，其中\(A=\{\bm{x}|x_1=0\text{和}\bm{x}\in X^{\omega}\}\subsetneq X^{\omega}\)。现证明\(f\)是单射。对于任意\((x_i)_{i\in\mathbb{Z}_+},(x'_i)_{i\in\mathbb{Z}_+}\in X^{\omega}\)，有以下蕴含关系成立：
故\(f\)为单射。
4. 证明 (a) 设\(A\)的基数为\(n\)，现对\(n\)进行归纳证明。令\(X=\{x|x\in\mathbb{Z}_+,\text{且当}\)A\(\text{的基数为}x\text{时},\)A\(\text{有最大元}\}\)。当\(n=1\)时，\(A\)仅有一个元素，该元素即为\(A\)的最大元，故\(1\in X\)。若\(n\in X\)，当\(A\)的基数为\(n+1\)时，任取\(a_0\in A\)，对于\(A-\{a_0\}\)，其基数为\(n\)，应用归纳假设可知存在\(A-\{a_0\}\)的最大元\(a_1\)。若\(a_1>a_0\)，则\(a_1\)也为\(A\)的最大元，否则\(a_0\)为\(A\)的最大元。故\(n+1\in X\)。由归纳原理可知，\(X=\mathbb{Z}_+\)。由此可知，对于任意有限非空全序集\(A\)，其都有最大元。
(b) 设\(A\)的基数为\(n\)，现对\(n\)进行归纳证明。令\(X=\{x|x\in\mathbb{Z}_+,\text{且当}\)A\(\text{的基数为}x\text{时},\)A\(\text{的序型和正整数的一个截相同}\}\)。注意到若\(A\)的基数为1，\(A=\{a\}\)，容易验证\(f:\{1\}\rightarrow A,f(1)=a\)即为保序映射，故\(1\in X\)。若\(n\in X\)，当\(A\)的基数为\(n+1\)时，令\(A\)的最大元为\(a_0\)，则\(A-\{a_0\}\)的基数为\(n\)，由归纳假设可知，存在保序映射\(g:\{1,\cdots n\}\rightarrow A-\{a_0\}\)。定义\(g':\{1,\cdots,n+1\}\rightarrow A\)
那么\(g'\)显然是一个一一对应。若\(m_1,m_2\in \{1,\cdots,n\}\)，则\(m_1<m_2\Longrightarrow g(m_1)<g(m_2)\Longrightarrow g'(m_1)<g'(m_2)\)成立。若\(m_1<m_2=n+1\)，那么由\(g'(m_1)=g(m_1)\in A-\{a_0\}\)可知\(g'(m_1)<g'(m_2) = a_0\)。综上可知，\(g'\)是保序映射，故\(n+1\in X\)。由归纳原理可知\(X=\mathbb{Z}_+\)，故原论断成立。
$\square$
5. 解 考虑\(A=\varnothing,B=\mathbb{Z}\)，那么\(A\times B=\varnothing\)是有限集，但\(B\)不是有限集，故\(A\times B\)是有限集不蕴含\(A\)与\(B\)都是有限集。
6. 证明 (a) 定义\(f:\mathcal{P}(A)\rightarrow X^n,f(B)=(x_1,\cdots,x_n),B\subset A\)，其中\(x_i\ (i=1,\cdots,n)\)为
先证明\(f\)是一个单射。对任意\(B_1,B_2\in \mathcal{P}(A)\)，设\(f(B_1)=(x_1,\cdots,x_n),f(B_2)=(x'_1,\cdots,x'_n)\)有以下蕴含关系成立
故\(f\)为单射。对于任意\((x_1,\cdots,x_n)\in X^{n}\)，令\(B=\{i|i\in A\text{和}x_i=1\}\subset A\)。容易验证\(f(B) = (x_1,\cdots,x_n)\)，故\(f\)为满射。综上可知，\(f\)是一个从\(\mathcal{P}(A)\)到\(X^n\)的一一对应。
(b) 注意到\(X\)是基数为2的有限集，而\(X^n\)为\(X\)的有限积，故\(X^n\)也是有限集，对某个\(m\in\mathbb{Z}_+\)存在一一对应\(g:X^n\rightarrow \{1,\cdots,m\}\)。又由(a)可知存在一一对应\(f:\mathcal{P}(A)\rightarrow X^n\)，故有一一对应\(g\circ f:\mathcal{P}(A)\rightarrow \{1,\cdots,m\}\)，\(\mathcal{P}(A)\)是有限集。
$\square$
7. 证明 令\(C=\{x|x=f:A\rightarrow B\text{的指派法则}\}\)，容易看出\(C\)与集合\(D=\{f|f:A\rightarrow B\}\)之间存在一一对应。注意到\(C\subset \mathcal{P}(A\times B)\)，而由\(A,B\)的有限性可知\(A\times B\)是有限集，结合习题 6 (b)可知\(\mathcal{P}(A\times B)\)是有限集。若\(C\)不是有限集，由习题 2可知\(\mathcal{P}(A\times B)\)不是有限集，矛盾。故\(C\)是有限集，结合一一对应的存在性易知\(D\)也是有限集合。
$\square$