笔记与习题：《集合论：对无穷概念的探索》（3）

第三章 实数的构造

3.1 自然数

$0=\emptyset$

$1=\{\emptyset\}$

$2=\{\emptyset,\{\emptyset\}\}$

$\dots$

定义：如果一个集合$X$满足：

$$\emptyset \in X \wedge \forall x(x\in X\rightarrow x^{+}\in X)$$

则称$X$为归纳集

$x^{+}$为$x$的后继，从该定义出发，结合自然数的构造方式，可以得出所有自然数属于任何归纳集，也就是说，自然数集是任何归纳集的子集

所以有

定义：全体自然数的集合$\mathbb{N}$定义为：

$$\mathbb{N}=\{n|\forall X(X是归纳集\rightarrow n\in X)\}$$

$\mathbb{N}$的元素称为自然数

定理：$\mathbb{N}$是归纳集，并且是任何归纳集的子集

所以自然数集合是最小的归纳集，表示为

$$0\in M\wedge \forall x(x\in M\rightarrow x^{+}\in M)\rightarrow \mathbb{N}\subseteq M$$

如果$M$是自然数的某个子集，则上式称为归纳原理，即

$$0\in M\wedge \forall x(x\in M\rightarrow x^{+}\in M)\rightarrow \mathbb{N}=M$$

$\mathbb{N}$上的归纳原理的另一形式：

令$\varphi(x)$为一性质，则

$$[\varphi(0)\wedge \forall n\in \mathbb{N}(\varphi(n)\rightarrow \varphi(n+1))]\rightarrow \forall n \in \mathbb{N} \varphi(n)$$

即，0有性质$\varphi$，且$\varphi(n)$蕴含$\varphi(n+1)$（从$n$有性质$\varphi$可推出$n+1$有性质$\varphi$）

以上为自然数的定义部分

---

接下来考虑$\mathbb{N}$上的序

令$x\underline{\in} y$表示$x\in y\vee x=y$

讨论$x\underline{\in} y$的性质

引理：对所有自然数$m,n,k$

①$n\subseteq n+1$且$n\in n+1$

②如果$x\in n$，则$x\in \mathbb{N}$

③$0\underline{\in} n$

④$k\in n+1$当且仅当$k\underline{\in} n$

⑤如果$m\in n$，则$m+1\underline{\in} n$

⑥如果$k\in n+1$当且仅当$k\in n$

⑦$n\notin n$

⑧$m\in n$当且仅当$m\subset n$

定理：$(\mathbb{N},\underline{\in})$是一个线序集

即$\underline{\in}$正好表示了自然数的“自然”大小关系

所有可以有

定义：对$m,n\in\mathbb{N},m\leq n$定义为$m\underline{\in} n;m<n$定义为$m\in n$

自然数的大小关系除了是线序外，还是“良序”

定义：集合$A$上的线序$\leq$如果还满足：$A$的每一非空子集都有最小元。就称为良序。$(A,\leq)$称为良序集

第二归纳原理：令$\varphi(x)$为一个性质。假设对所有的$n\in \mathbb{N}$，如果对所有的$k<n$都有$\varphi(k)$，那么$\varphi$对所有的自然数$n$都成立

定理：$(\mathbb{N},\leq)$是良序集

证明：即证对$\mathbb{N}$的每一个非空子集$X$，$X$都有最小元。

假设$X$没有最小元，考虑集合$\mathbb{N}-X$，假设对所有$k<n,k\in\mathbb{N}-X$，那么$n$一定属于$\mathbb{N}-X$，因为否则$n\in X$，但是比$n$小的都不属于$X$，所以$n$是$X$的最小元，与$X$没有最小元矛盾。因此$\mathbb{N}-X=\mathbb{N}$，$X=\emptyset$，矛盾。所以$X$有最小元。

3.2 自然数上的递归定理与运算

自然数上的运算由“递归定义法”定义

这种定义为何合理？是否能唯一确定运算？

递归定理：对任意集合$A$，任意$a\in A$，以及任意函数$g:A\times \mathbb{N}\rightarrow A$，存在唯一的函数$f:\mathbb{N}\rightarrow A$满足：

（1）$f(0)=a$

（2）对所有的$n\in \mathbb{N},f(n+1)=g(f(n),n)$

证明定理前，给出定义：

定义：序列是自然数$n$或全体自然数的集合$\mathbb{N}$为定义域的函数。如果它的定义域是$n\in \mathbb{N}$，则称为长度为$n$的有穷序列

特别的，定义域为0的序列称为空序列；定义域为$\mathbb{N}$的序列称为无穷序列

表示方式：

有穷序列

$$\langle a_i |i<n\rangle,或\langle a_i |i=0,1,2,\dots,n-1\rangle,或\langle a_0,a_1,\dots,a_{n-1}\rangle$$

无穷序列

$$\langle a_i|i\in \mathbb{N}\rangle,或\langle a_i|i=0,1,2,\dots\rangle,或\langle a_i\rangle^{\infty}_{i=0}$$

空序列

$$\langle\rangle$$

由$A$的元素组成的所有有穷序列的集合

$$A^{<\mathbb{N}}=\cup_{n\in \mathbb{N}}A^n$$

有穷序列的值域

$$\{a_i|i<n\},\{a_0,a_1,\dots,a_n\}$$

无穷序列的值域

$$\{a_i|i\in\mathbb{N}\},\{a_i\}^{\infty}_{i=0}$$

递归定理的证明

首先，证明$f$的存在性

任取序列$t:(m+1)\rightarrow A$，如果$t_0=a$而对所有的$k<m,t_{k+1}=g(t_k,k)$，就称其为基于$a$和$g$的$m$-近似，定义

$$\mathcal{F}=\{t\in\mathcal{P}(\mathbb{N\times A})|t是m-近似\}$$

并且令$f=\bigcup\mathcal{F}$

利用以上定义

①证明$f$是函数，即证明$\mathcal{F}$是相容的函数系统

②证明$dom(f)=\mathbb{N}$且$ran(f)\subseteq A$

③证明$f$满足递归定理的（1）和（2）

再证$f$的唯一性

通常使用递归定理定义运算时，定理是带参数的

带参数的递归定理

令$a:P\rightarrow A$和$g:P\times A\times \mathbb{N}\rightarrow A$为函数。存在唯一的函数$f:P\times\mathbb{N}\rightarrow A$满足：

（1）对所有的$p\in P$，$f(p,0)=a(p)$

（2）对任意$n\in \mathbb{N}$和$p\in P$，$f(p,n+1)=g(p,f(p,n),n)$

现在开始定义自然数上的运算

以下的两个定理可看作递归定理的两个特例，分别“携带着”加法运算与乘法运算的信息

定理：存在唯一的函数$+:\mathbb{N}\times\mathbb{N}\rightarrow\mathbb{N}$满足：

（1）对所有的$m\in \mathbb{N},+(m,0)=m$

（2）对所有$m,n\in \mathbb{N},+(m,n+1)=+(m,n)+1$

定理：存在唯一的函数$\cdot:\mathbb{N}\times\mathbb{N}\rightarrow\mathbb{N}$满足：

（1）对所有的$m\in \mathbb{N},\cdot(m,0)=0$

（2）对所有$m,n\in \mathbb{N},\cdot(m,n+1)=\cdot(m,n)+m$

定义：自然数上的加法与乘法是如下定义的$\mathbb{N}\times\mathbb{N}$到$\mathbb{N}$的函数：

加法：$m+0=m$且$m+(n+1)=(m+n)+1$

乘法：$m0=0$且$m(n+1)=mn+m$

由加法与乘法的定义，可推出加法的交换、结合律，乘法的交换交换、结合、分配律

3.3 等势

数一数，这个集合里有多少元素？

定义：

如果存在一个以集合$X$为定义域，以集合$Y$为值域的双射，就称集合$X$和$Y$是等势的（即存在一一对应关系），用符号表示为$|X|=|Y|$

如果存在集合$X$到集合$Y$的单射，就称$X$的势小于等于$Y$的势，记为$|X|\leq|Y|$，意味着存在$Y$的子集$Z$使得$|X|=|Z|$

$|X|<|Y|$表示$|X|\leq|Y|$但并非$|X|=|Y|$

练习：对任意集合$X,Y$，定义$X\sim Y$当且仅当$|X|=|Y|$。证明$\sim$是一个等价关系

罗素曾定义$X$的”基数“为等价类$[X]_{\sim}$，这样的定义有什么问题？

（1）自反性：一个集合显然和自己等势

传递性：

$X$与$Y$等势，即存在一个以集合$X$为定义域，以集合$Y$为值域的双射，即集合$X$中的元素与集合$Y$中的元素存在一一对应关系

$Y$与$Z$等势，即存在一个以集合$Y$为定义域，以集合$Z$为值域的双射，即集合$Y$中的元素与集合$Z$中的元素存在一一对应关系

所以集合$X$中的元素与集合$Z$中的元素也存在一一对应关系，即$X$与$Z$等势，传递性成立

对称性：$X$与$Y$等势的话$Y$与$X$等势，对称性显然成立

所以$\sim$是一个等价关系

（2）如果定义$X$的”基数$|A|$“为等价类$[X]_{\sim}$的话，也就是说$|A|=\{B|B\sim A\}$，或者说，“与给定集合等价的所有集合的集合”。但是这样的话，能说$\{B|B\sim A\}$是一个集合吗？不能，它的上面没有“限制”，它不是集合而是一个真类，那么我们又该如何在集合论的背景下讨论它呢？这是这种定义法的问题。

康托-伯恩斯坦定理：如果$|X|\leq|Y|$并且$|Y|\leq|X|$，则$|X|=|Y|$

证明的大致过程：首先将原命题转换为：对任意集合$A,A^{‘},B$

$$如果A^{'}\subseteq B\subseteq A并且|A^{'}|=|A|,则|B|=|A|$$

即证：在$A^{‘}\subseteq B\subseteq A$且存在$A$到$A^{‘}$的双射的情况下，可以推出存在$A$到$B$的双射

令$h$为由$A$到$A^{‘}$的双射

令$A_0=A,B_0=B$

对于每一$n$，定义

$A_{n+1}=h[A_n],B_{n+1}=h[B_n]$

这样，递归定义了两个集合的序列

因为$A_{1}\subseteq B_0\subseteq A_0$，归纳可得$A_{n+1}\subseteq B_n\subseteq A_n$

令$C_n=A_n-B_n$，且$C=\bigcup^{\infty}_{n=0} C_n$

则$C\subseteq A$，令$D=A-C$

由于$h[C_n]=h[A_n-B_n]=h[A_n]-h[B_n]=A_{n+1}-B_{n+1}=C_{n+1}$

因此$h[C]=\bigcup_{n=1}^{\infty} C_n=C-C_0=C-(A-B)$

定义$A$到$B$的双射$j$

$$j(x)=\begin{equation} \left\{ \begin{array}{lr} h(x) & 如果x\in C\\ x, & 如果x\in D\\ \end{array} \right. \end{equation}$$

显然该函数是一一对应的，只需证明它是到$B$上的满射，就可证明它是$A$到$B$的双射

$ran(j)=g[C]\cup j[D]=h[C]\cup D=j[C]\cup(A-C)=A-(C-h[C])=A-(A-B)=A\cap B=B$

定义：对任何集合$X$

（1）如果存在$n\in \mathbb{N}$，使得$|X|=n$，就称$X$为有穷的

（2）如果对任意$n\in \mathbb{N}$，都有$|X|\ne n$，就称$X$为无穷的

（3）如果$|X|=|\mathbb{N}|$，就称$X$是可数的或可数无穷的

（4）有穷的或可数的集合称为至多可数的

（5）不是可数的无穷集合称为不可数的

有穷集合的性质

鸽笼原理：如果$n$是自然数，则不存在$n$到它的真子集$X\subset n$上的双射。所以对任意有穷集合$X$，不存在$X$到$X$的真子集的双射

但对于无穷集合，这种映射存在，甚至这可以看作是无穷集合的定义

可数集合的性质

定理：每一无穷集合有一个可数子集

定理：两个可数集合的并是可数集合

推论：有穷个可数集合的并是可数的

定理：如果$A$和$B$是可数的，则$A\times B$是可数的

推论：

（1）如果$A_1,\dots,A_n,\dots$都是可数的，则$\bigcup_{n\in \mathbb{N}} A_n$是可数的

（2）如果$A_1,\dots,A_n$都是可数的，则$A_1\times \dots\times A_n$是可数的。特别地，对任意$m>0$，$\mathbb{N}^{m}$是可数的

（3）如果$A$是可数的，则$A^{<\mathbb{N}}=\bigcup_{n\in\mathbb{N}} A^{n}$是可数的

（4）如果$A$是可数的，则$A$的所有有穷子集组成的集合

$$X=\{x\subseteq A|存在n,|x|=n\}$$

是可数的

一些没有使用自然数的对有穷的定义方式：

以下命题等价

（1）集合$X$是有穷的

（2）存在$X$上的线序$\leq$满足$X$的每一非空子集在$\leq$下有最大元和最小元

（3）$X$的每一非空子集族都有$\subseteq$关系下的极大元

（4）$X$是戴德金有穷的。即：不存在由$X$到其真子集的一一映射。（定义：$X$是戴德金无穷的当且仅当它不是戴德金有穷的）

3.4 整数与有理数

自然数对减法不是封闭的，扩大自然数到整数

定义：令$\sim$是如下定义的集合$\mathbb{N}\times \mathbb{N}$上的等价关系

$$(m_1,n_1)\sim(m_2,n_2)当且仅当m_1+_{\mathbb{N}}n_2=m_2+_{\mathbb{N}}n_1$$

整数集合$\mathbb{Z}$定义为商集$\mathbb{N}\times \mathbb{N}/\sim$

练习：证明以上定义中的$\sim$是$\mathbb{N}\times \mathbb{N}$上的等价关系

自反性：显然对所有$m,n\in \mathbb{N}$，$(m,n)\sim(m,n)当且仅当m+_{\mathbb{N}}n=m+_{\mathbb{N}}n$

传递性：对所有$m_1,m_2,m_3,n_1,n_2,n_3\in \mathbb{N}$，若$(m_1,n_1)\sim(m_2,n_2)$，$(m_2,n_2)\sim(m_3,n_3)$，即$m_1+_{\mathbb{N}}n_2=m_2+_{\mathbb{N}}n_1$，$m_2+_{\mathbb{N}}n_3=m_3+_{\mathbb{N}}n_2$

综合两式可得：$m_1+_{\mathbb{N}}n_3=m_3+_{\mathbb{N}}n_1$

即$(m_1,n_1)\sim(m_3,n_3)$

对称性：对所有$m_1,m_2,n_1,n_2\in \mathbb{N}$

若$(m_1,n_1)\sim(m_2,n_2)$，即$m_1+_{\mathbb{N}}n_2=m_2+_{\mathbb{N}}n_1$，显然有$m_2+_{\mathbb{N}}n_1=m_1+_{\mathbb{N}}n_2$

定义$\mathbb{Z}$上的序和运算

序：$[(m_1,n_1)]\leq_{\mathbb{Z}}[(m_2,n_2)]\leftrightarrow m_1+_{\mathbb{Z}}n_2\leq_{\mathbb{N}}m_2+_{\mathbb{N}}n_1$

加法：$[(m_1,n_1)]+_{\mathbb{Z}}[(m_2,n_2)]=[(m_1+_{\mathbb{N}}m_2,n_1+_{\mathbb{N}}n_2)]$

乘法：$[(m_1,n_1)]\cdot_{\mathbb{Z}}[(m_1,n_2)]=[(m_1\cdot_{\mathbb{N}}m_2+_{\mathbb{N}}n_1\cdot_\mathbb{N}n_2,\\m_1\cdot_{\mathbb{N}}n_2+_{\mathbb{N}}n_1\cdot_\mathbb{N}m_2)]$

命题：对任意整数$a$，存在唯一的整数$a^{‘}$，使得$a+_{\mathbb{Z}}a^{‘}=0_{\mathbb{Z}}$

这个唯一的$a^{‘}$记为$-a$，用$a-b$表示$a+(-b)$

定义绝对值的概念

对任意整数$a$，$a$的绝对值$|a|$定义为

$$|a|=\begin{equation} \left\{ \begin{array}{lr} a & 若a\geq_{\mathbb{Z}}0_{\mathbb{Z}},\\ -a, & 若a<_{\mathbb{Z}}0_{\mathbb{Z}}。\\ \end{array} \right. \end{equation}$$

$\mathbb{N}$可以嵌入$\mathbb{Z}$中，即：

定理：存在函数$f:\mathbb{N}\rightarrow \mathbb{Z}$，满足：

（1）$f$是单射，$f(0)=0_{\mathbb{Z}}$

（2）对任意$m,n\in\mathbb{N},m\leq_{\mathbb{N}}n$当且仅当$f(m)\leq_{\mathbb{Z}}f(n)$

（3）对任意$m,n\in\mathbb{N},f(m+_{\mathbb{N}} n)=f(m)+_{\mathbb{Z}}f(n)$并且$f(m\cdot_{\mathbb{N}}n)=f(m)\cdot_{\mathbb{Z}}f(n)$

---

整数对除法不是封闭的，扩大整数到有理数

定义：令$\mathbb{Z}^{+}=\{a\in \mathbb{Z}|a>_{\mathbb{Z}}0_{\mathbb{Z}}\}$。如果$\sim$是集合$\mathbb{Z}\times\mathbb{Z}^{+}$上的如下定义的等价关系

$$(a_1,b_1)\times(a_2,b_2)当且仅当a_1\cdot_{\mathbb{Z}}b_2=a_2\cdot_{\mathbb{Z}}b_1$$

则有理数集合$\mathbb{Q}$就定义为商集$\mathbb{Z}\times\mathbb{Z}^{+}/\sim$

定义$\mathbb{Q}$上的序和运算

序：$[(a_1,b_1)]\leq_{\mathbb{Q}}[(a_2,b_2)]\leftrightarrow a_1\cdot_{\mathbb{Z}}b_2\leq_{\mathbb{Z}}a_2\cdot_{\mathbb{Z}}b_1$

加法：$[(a_1,b_1)]+_{\mathbb{Q}}[(a_2,b_2)]=[(a_1\cdot_{\mathbb{Z}}b_2+_{\mathbb{Z}}a_2\cdot_{\mathbb{Z}}b_1,b_1\cdot_{\mathbb{Z}}b_2)]$

乘法：$[(a_1,b_1)]\cdot_{\mathbb{Q}}[(a_2,b_2)]=[(a_1\cdot_{\mathbb{Z}}a_2,b_1\cdot_{\mathbb{Z}}b_2)]$

命题：

（1）对任意有理数$p$，存在唯一的有理数$p_1$，使得$p+_{\mathbb{Q}}p_1=0_{\mathbb{Q}}$

（2）对任意有理数$p$，存在唯一的有理数$p_2$，使得$p\cdot_{\mathbb{Q}}p_2=1_{\mathbb{Q}}$

这个唯一的$p_1$记为$-p$，而$p_2$记为$1/p$

$\mathbb{Z}$可以嵌入$\mathbb{Q}$中，即：

定理：存在函数$f:\mathbb{Z}\rightarrow \mathbb{Q}$，满足：

（1）$f$是单射，$f(0)=0_{\mathbb{Q}}$

（2）对任意$a,b\in\mathbb{Z},a\leq_{\mathbb{Z}}b$当且仅当$f(m)\leq_{\mathbb{Q}}f(n)$

（3）对任意$a,b\in\mathbb{Z},f(a+_{\mathbb{Z}} b)=f(a)+_{\mathbb{Q}}f(b)$并且$f(a\cdot_{\mathbb{Z}}b)=f(a)\cdot_{\mathbb{Q}}f(b)$

---

和整数集合$\mathbb{Z}$和有理数集合$\mathbb{Q}$有关的定理

定理：可数集合上的等价关系有至多可数个等价类

定理：整数集合$\mathbb{Z}$和有理数集合$\mathbb{Q}$是可数无穷的

---

有理数集合$\mathbb{Q}$的一个性质

定义：线序集$(X,<)$是稠密的，如果它至少有两个元素，并且对任意$a,b\in X$，如果$a<b$，则存在$x\in X$满足$a<x<b$

由以上定理与定义可知，有理数集合$\mathbb{Q}$稠密且可数

同时，它也没有最大最小元

有：

定理：令$(P,<_P)$为可数的无端点稠密线序，则$(P,<_P)$与$(Q,<)$同构

这个定理表明，有理数集合可以代表所有满足这三个条件（稠密，可数，无端点）的集合

使用往复法证明：

令$\langle p_n|n\in \mathbb{N}\rangle$和$\langle q_n|n\in \mathbb{N}\rangle$分别为一一序列，并且$P=\{p_n|n\in \mathbb{N}\},Q=\{q_n|n\in \mathbb{N}\}$

定义：

对于线序集$(P,<_P)$和$(Q,<_Q)$，$A\subseteq P$和$A^{‘}\subseteq Q$分别为它们的有穷子集。如果$h$是$A$到$A^{‘}$的双射，同时对任意$x,y\in A,x<y$当且仅当$h(x)<h(y)$，则$h$称为$(P,<_P)$的$(Q,<_Q)$的局部同构

以下证明对于无端点稠密线序，任何局部同构都可进一步扩充

引理：假设$(P,<_P)$和$(Q,<_Q)$是无端点稠密线性序。如果$h$是$P$到$Q$的局部同构，$p\in P$而$q\in Q$，则存在局部同构$h_{p,q}\supseteq h$，满足$p\in dom(h_{p,q})$且$q\in ran(h_{p,q})$

对引理的证明：令$h=\{(p_{i_1},q_{i_1}),\dots,(p_{i_k},q_{i_k})\},p_{i_1}<_P p_{i_2}<_P\dots<_Pp_{i_k}$，所以也有$q_{i_1}<q_{i_2}<\dots<q_{i_k}$。如果$p\notin dom(h)$，则$p<_P p_{i_1}$或$p_{i_e}<_P p<_P p_{i_{e+1}}$或$p_{i_k}<_P p$。不论哪种情况，都取最小的$n$使得$q_n$与$q_{i_1},\dots,q_{i_k}$的关系与$p$与$p_{i_1},\dots,p_{i_k}$的关系类似。也就是说：

$$如果p<_P p_{i_1},则q_n<q_{i_1}\\如果p_{i_e}<_P p<_P p_{i_{e+1}},则q_{i_e}<q_n<q_{i_{e+1}}\\如果p_{i_k}<_P p,则q_{i_k}<q_n$$

因为$(Q,<)$是稠密且无端点的，所以$q_n$一定可以找到。显然$h^{‘}=h\cup\{(p,q_n)\}$是局部同构，如果$q\in ran(h^{‘})$，则命题已经证明；否则，用同样的方法可以找到$p_m\in P$使得$h^{‘}\cup\{(p_m,q)\}$是局部同构

现在证明定理

递归定义部分同构的序列：

$$h_0=\emptyset\\h_{n+1}=(h_n)_{p_n,q_n}$$

令$h=\bigcup_{n\in\mathbb{N}}h_n$，则$h:P\rightarrow \mathbb{Q}$是同构

3.5 实数

有理数的缺陷：

定义：线序集$(X,\leq)$如果满足：对任意$X$的非空子集$Y$，如果$Y$有上界，则$Y$在$X$中有上确界，则称$X$有最小上界性质

定理：有理数集合$\mathbb{Q}$没有最小上界性质

与整数与有理数不同，实数不能表示为有理数的有序对，因为实数是不可数的，有理数的有序对是可数的

定义：如果集合$A\subseteq \mathbb{Q}$满足：

（1）$A\ne\emptyset$且$A\ne \mathbb{Q}$

（2）$A$是向下封闭的：如果$p\in A$并且$q<p$，则$q\in A$

（3）$A$没有最大元：如果$p\in A$，则存在$q\in A$，$p<q$

就称$A$是戴德金分割。全体戴德金分割的集合称为$\mathbb{R}$，$\mathbb{R}$的元素又称为实数

定义实数上的序和运算，以及有关的一些定理

定义：实数集合$\mathbb{R}$上的序定义为：$x_1\leq_{\mathbb{R}}x_2$当且仅当$x_1\subseteq x_2$

定理：实数集合$(\mathbb{R},\leq_{\mathbb{R}})$有最小上界性质

定义：实数集合上的加法定义为：$x+_{\mathbb{R}}y=\{p\in x,q\in y\}$

命题：对任意实数$x$，存在唯一实数$x^{‘}$，使得$x+x^{‘}=0_{\mathbb{R}}$，这唯一的$x^{‘}$记为$-x$

定义：实数集合上的乘法定义为：如果$x>0,y>0$，则

$$x\cdot_{\mathbb{R}}y=\{r|r\leq p\cdot_{\mathbb{Q}}q其中p\in x,q\in y并且p,q>_{\mathbb{Q}}0\}$$

如果$x=0$或$y=0$，则$x\cdot_{\mathbb{R}}y=0$

其它情况使用如下方式转换为$x,y$都大于0的情况

$$x\cdot y=\begin{equation} \left\{ \begin{array}{lr} (-x)\cdot(-y) & 若x<0,y<0,\\ -((-x)\cdot y), & 若x<0,y>0,\\ -(x\cdot(-y)), & 若x>0,y<0,\\ \end{array} \right. \end{equation}$$

$\mathbb{Q}$可以嵌入$\mathbb{R}$中 ，即：

定理：存在函数$f:\mathbb{Q}\rightarrow\mathbb{R}$，满足：

（1）$f$是单射，$f(0_{\mathbb{Q}})=0_{\mathbb{R}}$

（2）对任意$p,q\in\mathbb{Q},p\leq_{\mathbb{Q}}q$当且仅当$f(p)\leq_{\mathbb{R}}f(q)$

（3）对任意$p,q\in\mathbb{Q},f(p+_{\mathbb{Q}} q)=f(p)+_{\mathbb{R}}f(q)$并且$f(p\cdot_{\mathbb{Q}}q)=f(p)\cdot_{\mathbb{R}}f(q)$

具有最小上界性质的稠密线序集被称为完备线序集

实数是完备线序集，它包含可数稠密子集（有理数集）

$\mathbb{Q}$在$\mathbb{R}$中稠密——任何两个实数之间都有一个有理数

定理：任何包含可数稠密子集的无端点完备线序集都与$(R,<_{\mathbb{R}})$同构

3.6 不可数集合

区间套定理：设序列$\{I_n|n\in \omega\}$是$\mathbb{R}$中的一个闭区间套，即

（1）每一$I_n$都是$\mathbb{R}$中的闭区间

（2）对任意$n$，$I_{n+1}\subset I_n$

那么$\bigcap_{n\in\omega}I_n\ne \emptyset$

定理（康托）：$\{0,1\}$上的全体无穷序列组成的集合$\{0,1\}^{\mathbb{N}}$是不可数的

证明使用对角线法

通俗来说，就是对所有0与1组成的无穷序列，给它们依次编号

定义一个新的无穷序列，它的第一个数与编号为一的序列的第一个数不同，它的第二个数与编号为二的序列的第二个数不同……

这样定义出来的序列与这些序列里的任意一个都不同，也就是说$\{0,1\}$上的全体无穷序列组成的集合$\{0,1\}^{\mathbb{N}}$是不可数的

定理：所有实数的集合$\mathbb{R}$是不可数的

证明：首先，定义一个实数子集的序列$C_0,C_1,\dots$使其满足以下条件：

（1）$C_0=[0,1]$

（2）$C_{n+1}$是将$C_n$中每个区间的中间三分之一开部分去掉，即$C_n$中的每个$[a,b]$被替换为两个闭区间

$$L[a,b]=[a,a+\frac{1}{3}(b-a)]\\R[a,b]=[a+\frac{2}{3}(b-a),b]$$

所以有$C_0\supset C_1\supset C_2\supset\dots$

考虑上一定理中，定义的所有01序列组成的集合$D$，对每一$\delta\in D$，递归定义一个闭区间的序列

$$F_{0}^{\delta}=C_0=[0,1]\\ F_{n+1}^{\delta}=\begin{equation} \left\{ \begin{array}{lr} LF_{n}^{\delta} & 若\delta(n)=0,\\ RF_{n}^{\delta} & 若\delta(n)=1\\ \end{array} \right. \end{equation}$$

由归纳，对每一$n$，$F_{n}^{\delta}$是$C_n$的一个长度为$3^{-n}$的闭区间

而且$F_0^{\delta}\supset F_1^{\delta}\supset\dots$

由区间套定理可知，这一序列的交不空，又因为当$n$趋向无穷时，$F_n^{\delta}$的长度趋近0，所以这个交至多包含一个实数，令：

$$f(\delta)=\bigcap^{\infty}_{n=0}F_{n}^{\delta}中的唯一元素$$

函数$f$将不可数集合$D$映入实数的子集：

$$C=\bigcap^{\infty}_{n=0}\mathcal{C}_n$$

后者是所谓的康托集

这样，只要再证明$f$是一一映射就可以证明实数不可数了

习题

1、证明：$x\subseteq S(x)$并且不存在$z$，使得$x\subset z\subset S(x)$。因此，不存在$m,n\in\mathbb{N},m<n<m+1$

即证，$x$包含于$x$的后继，并且不存在$z$，使得$z$“夹”在$x$与$x$的后继之间，而且通过这个命题，可以得出两个自然数间不存在自然数的结论

$S(x)=x\cup\{x\}=\{x,\{x\}\}$，所以显然$x\subseteq S(x)$成立

假设存在$z$，使得$x\subset z\subset S(x)$，也就是说存在$z$，使得$x\subset z\subset \{x,\{x\}\}$

这显然不成立，前一个命题得证

现在从前一个命题推出后一个命题

由自然数的定义可知

$m+1=m\cup\{m\}$

$(m<n<m+1)\leftrightarrow (m\in n\in m+1)\leftrightarrow(m\in n\in (m\cup\{m\}))$

又由自然数的一个引理：对所有自然数$m,n$，$m\in n$当且仅当$m\subset n$

可以进一步转换为：$(m\in n\in (m\cup\{m\})\leftrightarrow(m\subset n\subset (m\cup\{m\})$

与前一命题相同

所以通过前一命题可以推出后一命题

2、证明对任意自然数$n$，$n=\{m\in \mathbb{N}|m<n\}$

因为$n=\{m\in \mathbb{N}|m<n\}\leftrightarrow\ n=\{m\in \mathbb{N}|m\in n\}$

即证：$n$是所有属于它的自然数$m$组成的集合

对于空集的情况：$n=\{\emptyset \in\mathbb{N}|\emptyset\in n\}=\{\emptyset\}$（1）

由自然数的引理：对所有自然数$k,o$，$k\subset k+1$且$k\in k+1$;$k\in o+1$当且仅当$k\in o$

又因为已知$n$为自然数

所以$n=\{(n-1)\in \mathbb{N}|(n-1)\in n\}$成立（2）

由（1）（2），归纳可得，对任意自然数$n$，$n=\{m\in \mathbb{N}|m<n\}$成立

3、如果$X$是有穷的，并且$Y\subseteq X$，则$Y$是有穷的。而且，$|Y|\leq|X|$

即证：有穷集合的子集仍是有穷集合，并且它的势小于原集合

对于前半句

令$[n]=\{0，…，n-1\}=X$，将证明分为以下两部分：

1.如果$Y\subseteq[n]$，那么要么$Y=[n]$，要么在$Y$和$m$之间存在一个双射。

2.如果$m<n$，则没有从$[n]$到$[m]$的双射。也就是鸽笼原理，这里省去证明过程

只证明第一部分：

通过递归定义$f(0)=minY$；而$f(k+1)=min(Y\backslash \{f(0),…,f(k)\})$

通过这种定义方式，要么定义出的$f$是$Y$和$[n]$之间的双射（$Y=[n]$），要么归纳过程在那之前中止，并且$f$是$[m]$（对于$m<n$）和$Y$之间的双射（在$Y$和$[m]$（对于$m<n$）之间存在一个双射）。

第一部分证明完毕

前半句证明完毕，即有穷集合的子集仍是有穷集合

对于后半句

由势的定义，$|X|=n,|Y|=m$，又因为$m<n$，所以$|Y|\leq|X|$

4、如果$x,y$是实数，则$x+y=\{p+q|p\in x,q\in y\}$是戴德金分割，因此实数加法的定义是合适的

因为$x,y$是实数，所以$x,y$都是戴德金分割，即：

$x,y\subseteq \mathbb{Q}$且$x,y\ne\emptyset$且$x,y\ne \mathbb{Q}$，并有：

$x$和$y$是向下封闭的：如果$p\in x$或$y$，并且$q<p$，则$q\in x$或$y$

$x$和$y$没有最大元：如果$p\in x$或$y$，则存在$q\in x$或$y$，$p<q$

对于$x+y=\{p+q|p\in x,q\in y\}$，如果$x,y\subseteq \mathbb{Q}$且$x,y\ne\emptyset$且$x,y\ne \mathbb{Q}$，那么显然$x+y\in\mathbb{Q}$且$x+y\ne\emptyset$且$x+y\ne \mathbb{Q}$，

证明$x+y$是向下封闭的：令$a$为$x$的上界，$b$为$y$的上界，所以$a+b$是$x+y=\{p+q|p\in x,q\in y\}$的上界，所以$x+y$是向下封闭的

证明$x+y$没有最大元：如果$m\in \{p+q|p\in x,q\in y\}$，那么$m=a+b$，其中$a\in x$，$b\in y$。那么$x$中存在$u$，$u<a$，$y$中存在$v$，$v<b$，所以$\{p+q|p\in x,q\in y\}$中存在$n=u+v$使$n<m$，所以$x+y$没有最大元

5、证明闭区间套定理

令$[a_i,b_i],i\in I$是一个嵌套区间族，

即对于$i,j\in I$，有$[a_i,b_i]\in [a_j,b_j]$或者$[a_i,b_i]\in[a_j,b_j]$

令$X=\bigcap_{i\in I}[a_i,b_i]$

当$I=\emptyset$时，$X=R \ne \emptyset$

当$I\ne\emptyset$时，选择$\iota \in I$，使$b_{\iota}$是非空集$S:=\{a_i∣i\in I\}$的一个上界

根据最小上界性质，令$s$为$S$的最小上界，那么根据定义，对于所有$i\in I$有$s\geq a_i$

如果$i\in I$，那么$b_i$也是$S$的一个上界，因此$s\leq b_i$

因此，$s\in X$

所以$X$不是空集