习题
1. 不用选择公理定义一个单射\(f:\mathbb{Z}_+\rightarrow X^{\omega}\),其中\(X\)为二元素集\(\{0,1\}\)。
2. 如果有可能的话,试对下列各个集族不用选择公理而求出来一个选择函数。
(a) \(\mathbb{Z}_+\)的所有非空子集的族\(\mathcal{A}\)。
(b) \(\mathbb{Z}\)的所有非空子集的族\(\mathcal{B}\)。
(c) 有理数集\(\mathbb{Q}\)的所有非空子集的族\(\mathcal{C}\)。
(d) \(X^{\omega}\)的所有非空子集的族\(\mathcal{D}\),其中\(X=\{0,1\}\)。
3. 设\(A\)是一个集合,\(\{f_n\}_{n\in\mathbb{Z}_+}\)是加标单射的一个族,其中
证明\(A\)是一个无限集。你能不用选择公理定义一个单射\(f:\mathbb{Z}_+\rightarrow A\)吗?
4. 在第7节中,有一个定理的证明包含有无穷多次任意选择,它是哪一个呢?重新写出一个证明,以便弄清楚选择公理的用法。(前面有一些习题也用到过选择公理。)
5. (a) 应用选择公理证明:若\(f:A\rightarrow B\)为满射,则\(f\)有一个右逆\(h:B\rightarrow A\)。
(b) 证明:若\(f:A\rightarrow B\)为单射,\(A\)非空,则\(f\)有一个左逆。这需要用选择公理吗?
6. 朴素集合论中大多数著名的悖论,都以这种或那种方式与“所有集合的集合”这个概念有关。前面曾经给出过的用来构成集合的各种法则,没有一个允许我们考虑这样的集合。我们有足够的理由指出,这个概念本身是自相矛盾的。假定用\(\mathcal{A}\)表示“所有集合的集合”。
(a) 证明\(\mathcal{P}(\mathcal{A})\subset \mathcal{A}\),并且由此引出矛盾。
(b) (Rusell悖论)。设\(\mathcal{B}\)是\(\mathcal{A}\)的一个子集,它由所有不是它自身的元素的集合组成,即
(当然,可能没有集合\(A\)会使得\(A\in A\)。这时,\(\mathcal{B}=\mathcal{A}\)。)\(\mathcal{B}\)是不是它自身的一个元素呢?
7. 设\(A\)和\(B\)是两个非空集合。如果从\(B\)到\(A\)中有一个单射,而从\(A\)到\(B\)中没有单射,我们说\(A\)有比\(B\)较大的基数(greater cardinality)。
(a) 根据定理 9.1得出,每一个不可数集的基数都大于\(\mathbb{Z}_+\)的基数。
(b) 证明:若\(A\)的基数大于\(B\)的基数,\(B\)的基数大于\(C\)的基数,则\(A\)的基数大于\(C\)的基数。
(c) 求出无限集的一个序列\(A_1,A_2,\cdots,\)使得对于每一个\(n\in\mathbb{Z}_+\),集合\(A_{n+1}\)的基数大于\(A_n\)的基数。
(d) 求出一个集合,使得对于任意\(n\),它的基数大于\(A_n\)的基数。
8. 证明\(\mathcal{P}(\mathbb{Z}_+)\)与\(\mathbb{R}\)的基数相同。[提示:你可以利用这样一个事实,即每一个实数有唯一的一个十进制展开,只要在这个展开式中不允许出现无穷多个9构成的串。]
集合论中一个著名的猜想,称为连续统假设,它断言不存在基数大于\(\mathbb{Z}_+\)小于\(\mathbb{R}\)的集合。广义连续统假设则断言,对于无限集\(A\),不存在基数大于\(A\)小于\(\mathcal{P}(A)\)的集合。令人吃惊的是,这两个论断与集合论的常用公理是独立的。
解答
1. 解 定义\(f\)为
由正整数二进制表示的唯一性易知\(f\)为单射。
2. 解 (a) 定义选择函数\(f:\mathcal{A}\rightarrow \mathbb{Z}_+\):
(b) 由\(\mathbb{Z}\)的可数性可知,存在一一映射\(g:\mathbb{Z}\rightarrow\mathbb{Z}_+\)。定义选择函数\(f:\mathcal{B}\rightarrow\mathbb{Z}\):
(c) 由\(\mathbb{Q}\)的可数性可知,存在一一映射\(g:\mathbb{Q}\rightarrow\mathbb{Z}_+\)。定义选择函数\(f:\mathcal{C}\rightarrow\mathbb{Q}\):
(d) 不可被构造。事实上,我们可以定义\((0,1)\)到\(X^{\omega}\)的映射\(g\),其将实数的二进制小数\(0.x_1x_2\cdots\)映射为\((x_1,x_2,\cdots)\),且不允许末尾有无穷连续多个1。那么,\(g\)是一个单射。若可以构造\(\mathcal{D}\)的选择函数\(f\),则\(h:\mathcal{E}\rightarrow (0,1),h(A) = g^{-1}(f(g(A)))\)即为\((0,1)\)非空子集族\(\mathcal{E}\)的选择函数,进而可以构造\((0,1)\)上的良序,而这已经被证明是不可被构造的(Feferman 1965,Some applications of the notions of forcing and generic sets, Fund. Math. 56, 325-345.)。
3. 证明 若\(A\)是有限集,则存在\(m\),使得\(\{1,\cdots,m\}\)与\(A\)之间存在一一映射\(h:\{1,\cdots,m\}\rightarrow A\)。令\(n=m+1\),则存在\(\{1,\cdots,m+1\}\)到\(A\)的单射\(g:\{1,\cdots,m+1\}\rightarrow A\)。故\(h^{-1} \circ g\)是一个从\(\{1,\cdots,m+1\}\)到\(\{1,\cdots,m\}\)的单射,矛盾,\(A\)必为无限集。
设\(c\)为\(A\)非空子集族的一个选择函数,现归纳定义\(f:\mathbb{Z}_+\rightarrow A\):
\(f\)的单射性显然,只需证明\(f\)是良定义的,而这只需证明\(f_n(\{1,\cdots,n\})\backslash f(\{1,\cdots,n-1\})\ne \varnothing\)。若\(f_n(\{1,\cdots,n\})\backslash f(\{1,\cdots,n-1\})=\varnothing\),则\(f_n(\{1,\cdots,n\})\subset f(\{1,\cdots,n-1\})\),则\(h_n:\{1,\cdots,n\}\rightarrow\{1,\cdots,n-1\},h_n(i) = f^{-1}(f_n(i))\)为单射,这与\(\{1,\cdots,n\}\)的有限性矛盾。
$\square$
4. 解 定理 7.5涉及到了无穷多次任意选择。重写的证明如下:
设\(\{A_n\}_{n\in J}\)为可数集的一个加标族,其指标集\(J\)为\(\{1,\cdots,N\}\)或\(\mathbb{Z}_+\)。为方便起见,还假定每一个\(A_n\)非空——这种假定并不影响结论的一般性。
因为每一个\(A_n\)是可数的,故对每一个\(n\)都存在一个非空集合\(B_n\),其元素为\(\mathbb{Z}_+\)到\(A\)的满射,记\(\mathcal{B}=\{B_n\}_{n\in J}\),则存在对应的选择函数\(c\)。类似地,可以选取一个满射\(g:\mathbb{Z}_+\rightarrow J\)。用
定义函数
容易验证\(h\)是一个满射。因为\(\mathbb{Z}_+\times\mathbb{Z}_+\)与\(\mathbb{Z}_+\)之间有一个一一对应,根据定理 7.1即得出并的可数性。
5. 证明 (a) 对任意\(b\in B\),定义\(C_b = f^{-1}(b)\),由\(f\)的满射性可知\(C_b\)非空,则族\(\mathcal{C}=\{C_b\}_{b\in B}\)存在选择函数\(c\)。定义\(h:B\rightarrow A\):
按定义,对任意\(b\in B\),有\(f(h(b)) = f(c(C_b)) = f(c(f^{-1}(b))) = b\),故\(h\)为\(f\)的右逆。
(b) 不需要用到选择公理。由\(A\ne \varnothing\)可知,存在\(a_0\in A\)。定义\(g:B\rightarrow A\):
由\(f\)的单射性易知\(g\)是良定义的。对于任意\(a\in A\),\(g(f(a)) = f^{-1}(f(a)) = a\)。
$\square$
6. 证明 (a) \(\mathcal{P}(\mathcal{A})\)的元素均为集合,而\(\mathcal{A}\)是所有集合的集合,故\(\mathcal{P}(\mathcal{A})\subset\mathcal{A}\)。内射\(i:\mathcal{P}(\mathcal{A})\rightarrow \mathcal{A}\)即为\(\mathcal{P}(\mathcal{A})\)到\(\mathcal{A}\)的单射,这与定理 7.8矛盾。
(b) 若\(\mathcal{B}\in\mathcal{B}\),则与\(\mathcal{B}\)定义中的\(A\notin A\)矛盾。但若\(\mathcal{B}\notin\mathcal{B}\),则符合\(A\notin A\),应有\(\mathcal{B}\in\mathcal{B}\),矛盾。
$\square$
7. 解 (a) 由定理 9.1可知,对每一个不可数集,存在\(\mathbb{Z}_+\)到其的单射。可以证明不存在不可数集到\(\mathbb{Z}_+\)的单射。否则由Schroeder-Bernstein 定理可知,存在不可数集与\(\mathbb{Z}_+\)之间的一一映射,矛盾。综上可知,不可数集的基数大于\(\mathbb{Z}_+\)。
(b) 由题意可知,存在单射\(f:B\rightarrow A\),\(g:C\rightarrow B\),则\(f\circ g\)是\(C\)到\(A\)的单射。若存在单射\(h:A\rightarrow C\),则\(h\circ f\)是\(B\)到\(C\)的单射,与\(B\)的基数大于\(C\)矛盾。故\(A\)的基数大于\(C\)的基数。
(c) 令\(A_1 = \mathbb{Z}_+,A_{n+1} = \mathcal{P}(A_{n})(n\geqslant 1)\)。结合定理 7.8可知对于每一个\(n\in\mathbb{Z}_+\),\(A_{n+1}\)的基数大于\(A_n\)。
(d) 令\(A=\bigcup_{n=1}^{\infty} A_n\)。我们证明对于任意\(A_n\),\(A\)的基数都大于\(A\)。显然内射\(i\)就是\(A_n\)到\(A\)的单射,但\(A\)到\(A_n\)的单射不存在。否则设该单射为\(f:A\rightarrow A_n\),则\(f|_{A_n+1}\)即是\(A_{n+1}\)到\(A_n\)的单射,这与\(A_{n+1}\)的基数大于\(A_n\)矛盾。综上可知\(A\)的基数大于任意\(A_n\)。
8. 证明 注意到\(f:(0,1)\rightarrow\mathbb{R},f(x) = \frac{2x-1}{1-(2x-1)^2}\)是一一映射,我们只需讨论\(\mathcal{P}(\mathbb{Z}_+)\)与\((0,1)\)的基数是否相同。而对于\((0,1)\)内的任意二进制小数\(x=0.x_1x_2\cdots\),规定其末尾不存在无穷连续多个1,指定其对应\((x_1,x_2,\cdots)\),据此可以定义\((0,1)\)到\(X^{\omega}\)的单射,其中\(X=\{0,1\}\)。定义函数\(f:X^{\omega}\rightarrow (0,1)\):
易验证\(f\)是单射,结合Schroeder-Bernstein 定理可知,\((0,1)\)与\(X^{\omega}\)基数相同。又结合第7节的习题 3可知,\((0,1)\)与\(\mathcal{P}(\mathbb{Z}_+)\)基数相同,故\(\mathcal{P}(\mathbb{Z}_+)\)与\(\mathbb{R}\)基数相同。
$\square$