当前位置: 首页 > news >正文

习题-无限集与选择公理

习题

 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}_+}\)是加标单射的一个族,其中

\[f_n:\{1,\cdots,n\}\rightarrow A. \]

证明\(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}\)的一个子集,它由所有不是它自身的元素的集合组成,即

\[\mathcal{B}=\{A|A\in\mathcal{A}\text{并且}A\notin 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\)

\[\begin{align*}&\bm{x}=f(n)\\&x_i = f(n)\ \mathrm{mod}\ 2^n \end{align*} \]

由正整数二进制表示的唯一性易知\(f\)为单射。

 2.  (a) 定义选择函数\(f:\mathcal{A}\rightarrow \mathbb{Z}_+\)

\[ f(A) = A\text{的最小元} \]

 (b) 由\(\mathbb{Z}\)的可数性可知,存在一一映射\(g:\mathbb{Z}\rightarrow\mathbb{Z}_+\)。定义选择函数\(f:\mathcal{B}\rightarrow\mathbb{Z}\)

\[ f(B) = g^{-1}(g(B)\text{的最小元}) \]

 (c) 由\(\mathbb{Q}\)的可数性可知,存在一一映射\(g:\mathbb{Q}\rightarrow\mathbb{Z}_+\)。定义选择函数\(f:\mathcal{C}\rightarrow\mathbb{Q}\)

\[ f(C) = g^{-1}(g(Q)\text{的最小元}) \]

 (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\)

\[\begin{align*}&f(1) = f_1(1)\\&f(n) = c(f_n(\{1,\cdots,n\})\backslash f(\{1,\cdots,n-1\})),\quad n\geqslant 2 \end{align*} \]

\(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(k,m)=c(B_{g(k)})(m) \]

定义函数

\[ h:\mathbb{Z}_+\times\mathbb{Z}_+\rightarrow\bigcup_{n\in J}A_n. \]

容易验证\(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\)

\[ h(b) = c(C_b) \]

 按定义,对任意\(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\)

\[g(b) = \begin{cases}f^{-1}(b)&b\in f(A)\\a_0&b\in B\backslash f(A) \end{cases} \]

\(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(\bm{x}) = \sum_{i=1}^{\infty} \frac{x_i}{3^i} \]

易验证\(f\)是单射,结合Schroeder-Bernstein 定理可知,\((0,1)\)\(X^{\omega}\)基数相同。又结合第7节的习题 3可知,\((0,1)\)\(\mathcal{P}(\mathbb{Z}_+)\)基数相同,故\(\mathcal{P}(\mathbb{Z}_+)\)\(\mathbb{R}\)基数相同。

$\square$

http://www.hskmm.com/?act=detail&tid=37555

相关文章:

  • Error: [WinError 10013] 以一种访问权限不允许的方式做了一个访问套接字的尝试及其解决方法
  • 项目管理软件是不是伪需求?
  • 题解:CF2115F1 Gellyfish and Lycoris Radiata (Easy Version)
  • 低代码如何重塑IT部门价值?
  • LIS 略解
  • 低代码如何引爆全员创新?揭秘技术民主化背后的蒲公英效应
  • LLM学习笔记DAY10
  • 2025工业冰水机/冷水机厂家推荐东莞市凯诺机械,高效制冷稳定运行
  • 2025小型低温/工业/风冷/一体式螺杆冷冻机厂家推荐:东莞凯诺机械专业制冷解决方案
  • 2025水冷螺杆/风冷螺杆冷水机厂家推荐东莞市凯诺机械,高效制冷稳定可靠
  • LLM学习笔记DAY9
  • OJ模拟面试3(异步判题架构)
  • Edge浏览器网页设置深色模式(仅搜索结果界面)
  • 2025 年 AI 编程工具 TOP5 排名:谁在重新定义研发效率?
  • noipd8t2 - Slayer
  • 【Go】go学习笔记
  • todolist
  • 利用排列组合法实现TOPN路径计算
  • 达梦数据库获取判断字段中的json数据中的值
  • 2025 废气处理/废气治理/环保/污水/分子筛/除臭设备推荐榜:上海深城以专利技术破局,3 家企业凭场景适配登榜,助力异味治理升级
  • Web3 行业 Solidity 高级后端开发工程师岗位要求
  • API 搜索的下一代形态-Apipost智能搜索:只需用业务语言描述需求,就能精准定位目标接口!
  • 2025包装机/全自动包装机/非标定制生产线厂家推荐昆仑智能装备,专业高效!
  • 2025拖鞋机/酒店拖鞋生产线厂家推荐昆仑智能,高效稳定自动化解决方案
  • 2025年口罩机厂家权威推荐榜单:全自动口罩机器,全自动KN95口罩机,高效智能生产线专业选购指南
  • 2025提升机/自动提升机厂家推荐垚林机械,高效稳定省心之选
  • 二分图
  • 2025不锈钢方形/消防/生活/保温水箱厂家推荐莞南节能,专业耐用品质保障
  • 2025-10-23 DeepSeek R1本地部署(ollama)
  • python 异步调用语法