在高等数学中, 函数的概念在一步一步拓广, 最初微积分中研究的是连续函数, 可微函数, 在实分析中, 这个概念要推广到可测函数, 下面还要把函数概念推广到映射.

在这一节, 可以认为要研究如何”数”集合中元素的个数, 其中概念中比较重要的是映射, 一一映射和集合的势, 同时应了解有限集和无限集的区别.

仍然和1.2节一样, 先了解概念, 再了解它们之间的关系, 然后看几个例子.

定义1.3.1 映射$f: X \rightarrow Y$, 对每一个$x \in X$, $Y$中均存在唯一的$y = f(x)$.

满射($X$到$Y$上的映射): $\forall y \in Y$, 存在$x \in X$, 使得$y = f(x)$.

单射: 当$x_1$, $x_2 \in X$且$x_1 \neq x_2$时, 有$f(x_1) \neq f(x_2)$.

一一映射(双射): 既是单射又是满射. 此时可以定义你映射$f^{-1}$.

复合映射: $f: X \rightarrow Y$, $g: Y \rightarrow W$, 则有$X$到$W$的映射$h$: $h(x) = g[f(x)]$.

集合的对等: 存在一个从$A$到$B$的一一映射, 则称$A$与$B$对等, 记作$A \sim B$.

集合的基数(或者势): 如果$A$与$B$对等, 则说$A$与$B$的基数是相同的.

有两个基数经常会用到: 全体自然数集的基数(用$\aleph_0$表示); 全体实数的基数(用$\aleph$表示). 有一个猜想是证明: $\aleph$和$\aleph_0$之间不存在其它基数.

这一节的概念不多, 而且也不难理解, 但是在应用上却难度极大, 书中许多结论没有证明, 这里给出证明. 其中难度最大的是如何确定集合的势, 或者说如何构造对等关系.

(1)

$$\begin{aligned}
f(\bigcup_{\alpha \in I}{A_{\alpha}}) &= \bigcup_{\alpha \in I}{f(A_{\alpha})}, \\
f(\bigcap_{\alpha \in I}{A_{\alpha}}) &\subset \bigcap_{\alpha \in I}{f(A_{\alpha})}.
\end{aligned}$$.

证明: $\forall y \in f(\bigcup\limits_{\alpha \in I}{A_{\alpha}})$, 则存在$x \in \bigcup\limits_{\alpha \in I}{A_{\alpha}}$, 使得$f(x) = y$. 于是存在某个$\alpha_0$, 使得$x \in A_{\alpha_0}$, $y = f(x)$, 即有$y \in f(A_{\alpha_0})$, 从而$y \in \bigcup\limits_{\alpha \in I}{f(A_{\alpha})}$, $f(\bigcup\limits_{\alpha \in I}{A_{\alpha}}) \subset \bigcup\limits_{\alpha \in I}{f(A_{\alpha})}$.

反之, $\forall y \in \bigcup\limits_{\alpha \in I}{f(A_{\alpha})}$, 则存在$\alpha_0$, 使得$y \in f(A_{\alpha_0})$, 从而存在$x \in A_{\alpha_0}$, 使得$y = f(x)$, 也就是说, $x \in \bigcup\limits_{\alpha \in I}{A_{\alpha}}$, $y = f(x) \in f(\bigcup\limits_{\alpha \in I}{A_{\alpha}})$, 于是$\bigcup\limits_{\alpha \in I}{f(A_{\alpha})} \subset f(\bigcup\limits_{\alpha \in I}{A_{\alpha}})$, 第一个等式获证.

关于第二个式子, $\forall y \in f(\bigcap\limits_{\alpha \in I}{A_{\alpha}})$, 于是存在$x \in \bigcap\limits_{\alpha \in I}{A_{\alpha}}$, 使得$f(x) = y$, 这意味着$\forall \alpha \in I$, $x \in A_{\alpha}$, $y \in f(A_{\alpha})$, 从而有$y \in \bigcap\limits_{\alpha \in I}{f(A_{\alpha})}$, 获证.

必须注意后一个式子中的关系是”$\subset$”, 而不是”$=$” 下面来看看为什么不是$=$, 要使$=$成立, 则应有$\forall y \in \bigcap\limits_{\alpha \in I}{f(A_{\alpha})}$, 由此$\forall \alpha \in I$, $y \in f(A_{\alpha})$, 意味着$\exists x_{\alpha} in A_{\alpha}$, 使得$y = f(x_{\alpha})$, 很遗憾, 在一般的映射中, $x_{\alpha}$不一定都相等, 从而就可能出现$y \notin f(\bigcap\limits_{\alpha \in I}{A_{\alpha}})$, 从这一个讨论中, 马上就可以构造一个例子: $f(0) = 0$, $f(1) = 1$, $f(2) = 0$, 考虑集合

$$\begin{aligned}
A & = \{0, 1\}, \\
B &= \{1, 2\}.
\end{aligned}$$

则显然有$f(A \cap B) = \{f(1)\} = \{1\}$, $f(A) \cap f(B) = \{0, 1\}$, 于是$f(A \cap B) \neq f(A) \cap f(B)$.

(2)记$f^{-1}(B) = \{x \in X: f(x) \in B, B \subset Y\}$, 则有下面的结论:

(i) 若$B \subset A$, 则$f^{-1}(B) \subset f^{-1}(A)$;

(ii) $f^{-1}(\bigcup\limits_{\alpha \in I}{B_{\alpha}}) = \bigcup\limits_{\alpha \in I}{f^{-1}(B_{\alpha})}$;

(iii) $f^{-1}(\bigcap\limits_{\alpha \in I}{B_{\alpha}}) = \bigcap\limits_{\alpha \in I}{f^{-1}(B_{\alpha})}$;

(iv) $f^{-1}(B^c) = (f^{-1}(B))^c$.

证明: 注意比较这里的(ii), (iii)和前面的结论, 这里的两个式子全部都是等号($=$).

(i) $\forall x \in f^{-1}(B)$, 则$f(x) \in B \subset A$, 于是$x \in f^{-1}(A)$.

(ii) 由(i), $B_{\alpha} \subset \bigcup\limits_{\alpha \in I}{B_{\alpha}}$, 故$f^{-1}(B_{\alpha}) \subset f^{-1}(\bigcup\limits_{\alpha \in I}{B_{\alpha}})$. 于是$\bigcup\limits_{\alpha \in I}{f^{-1}(B_{\alpha})} \subset f^{-1}(\bigcup\limits_{\alpha \in I}{B_{\alpha}})$, 另一方面, $\forall x \in f^{-1}(\bigcup\limits_{\alpha \in I}{B_{\alpha}})$, 则$f(x) \in \bigcup\limits_{\alpha \in I}{B_{\alpha}}$, 不妨设$f(x) \in B_{\alpha_0}$, 则$x \in f^{-1}(B_{\alpha_0})$, 从而$x \in \bigcup\limits_{\alpha \in I}{f^{-1}(B_{\alpha})}$. 获证.

(iii) 同样由(i), $\bigcap\limits_{\alpha \in I}{B_{\alpha}} \subset B_{\alpha}$, 则$f^{-1}(\bigcap\limits_{\alpha \in I}{B_{\alpha}}) \subset f^{-1}(B_{\alpha})$, 可以得到$f^{-1}(\bigcap\limits_{\alpha \in I}{B_{\alpha}}) \subset \bigcap\limits_{\alpha \in I}{f^{-1}(B_{\alpha})}$. 另一方面, $\forall x \in \bigcap\limits_{\alpha \in I}{f^{-1}(B_{\alpha})}$, 有$x \in f^{-1}(B_{\alpha})$, $\forall \alpha \in I$, 于是, $\forall \alpha$, $f(x) \in B_{\alpha}$, 即$f(x) \in \bigcap\limits_{\alpha \in I}{B_{\alpha}}$, $x \in f^{-1}(\bigcap\limits_{\alpha \in I}{B_{\alpha}})$. 获证.

(iv) $\forall x \in f^{-1}(B^c)$, 则$f(x) \in B^c$ $\Rightarrow$ $x \notin f^{-1}(B)$, 即$x \in [f^{-1}(B)]^c$. 反过来, $\forall x \in [f^{-1}(B)]^c$, 则$x \notin f^{-1}(B)$ $\Rightarrow$ $f(x) \in B^c$, 即$x \in f^{-1}(B^c)$.

对于集合关系来说, 文氏图是极其有用的辅助工具.

(3) 令

$$\chi_A(x) = \left\{
\begin{aligned}
1, \quad & x \in A \\
0, \quad & x \notin A
\end{aligned}
\right.$$

则有下列结论:

(i) $\chi_{A \cup B}(x) = \chi_{A}(x) + \chi_{B}(x) – \chi_{A \cap B}(x)$;

(ii) $\chi_{A \cap B}(x) = \chi_A(x) \cdot \chi_B(x)$;

(iii) $\chi_{A \backslash B}(x) = \chi_A(x)[1 – \chi_B(x)]$;

(iv) $\chi_{A \triangle B}(x) = |\chi_A(x) = \chi_B(x)|$.

证明: 直接根据定义即可证明这些结论.

(i) 若$x \in A \cap B$, 则有$x \in A$或$x \in B$, 如果$x \in A$, 则$\chi_A(x) = 1$, 如果同时有$x \in B$, $\chi_B(x) = 1$, 且$x \in A \cap B$, $\chi_{A \cap B}(x) = 1$, 于是$\chi_A(x) + \chi_B(x) – \chi_{A \cap B}(x) = 1$, 如果$x \notin B$, 则$\chi_B(x) = 0$, $\chi_{A \cap B}(x) = 0$, 同样成立等式. 而$A$和$B$是对称的, 因此$x \in A \cup B$时等式成立.

当$x \notin A \cup B$时, $\chi_A(x) = \chi_B(x) = \chi_{A \cap B}(x) = 0$, 同样成立.

(ii) 若$x \in A \cap B$, 则$x \in A$且$x \in B$, 有$\chi_A(x) \cdot \chi_B(x) = 1 \cdot 1 = 1$.

若$x \notin A \cap B$, 则$\chi_A(x)$与$\chi_B(x)$中至少有一个等于$0$, 从而$\chi_A(x) \cdot \chi_B(x) = 0$.

(iii) 若$x \in A \backslash B$, 则$x \in A$, $x \notin B$, 于是$\chi_A(x) = 1$, $\chi_B(x) = 0$, $\chi_A(x)[1 – \chi_B(x)] = 1$.

若$x \notin A \backslash B$, 则有两种情形: (1) $x \notin A$, 显然有$\chi_A(x) = 0$, $\chi_A(x)[1 – \chi_B(x)] = 0$. (2) $x \in A$, 且$x \in B$, 则$\chi_A(x)[1 – \chi_B(x)] = 1\cdot[1-1] = 0$.

(iv)若$x \in A \triangle B$, 则或者$x \in A$, 或者$x \in B$, 而且只能是其中之一, 由对称性, 不妨设$x \in A$, $x \notin B$, 则$\chi_A(x) = 1$, $\chi_B(x) = 0$, $|\chi_A(x) – \chi_B(x)| = 1$.

若$x \notin A \triangle B$, 则有两种可能: (1)$x \in A$且$x \in B$; (2) $x \notin A$且$x \notin B$, 此时均有$\chi_A(x) = \chi_B(x)$.

(4) 集合$A$与$B$之间的对等关系是一个等价关系, 即有: (i) $A \sim B$, (ii)若$A \sim B$, 则$B \sim A$, (iii)若$A \sim B$, $B \sim C$, 则$A \sim C$.

证明: 注意到对等关系与一一对应之间的关系, 这实际上就是讨论一一对应.

(i) $A \sim A$, 这可以通过恒等映射来完成: $f:A \rightarrow A$, $f(x) = x$, $\forall x \in A$.

(ii) $A \sim B$, 存在一个一一映射$f: A \rightarrow B$, 其逆映射$f^{-1}:B \rightarrow A$也是一个一一映射, 从而$B \sim A$.

(iii) 由$A \sim B$, $B \sim C$可知, 存在一一映射$f$, $g$, 使得$f: A \rightarrow B$, $g:B \rightarrow C$, 考虑映射$h = g \circ f: A \rightarrow C$, 下面证明$h$是一个一一映射, 也就是证明$h$既是满射又是单射.

(a) 满射: $\forall z \in C$, $\exists y \in B$使$g(y) = z$, 对于$y \in B$, 存在$x \in A$, 使得$f(x) = y$, 于是$h(x) = z$.

(b) 单射: $\forall x_1, x_2 \in A$, $x_1 \neq x_2$, 则$f(x_1) \neq f(x_2)$, 于是$g(f(x_1)) \neq g(f(x_2))$, 即$h(x_1) \neq h(x_2)$.

(5) 要讨论集合的基数, 或者说集合之间的对应关系, 有极为重要的Cantor-Bernstein定理. 不过在证明这个定理之前, 先证明Banach的一个引理, 它涉及到集合在映射下的分解问题.

若有$f: X \rightarrow Y$, $g: Y \rightarrow X$, 则存在分解$X = A \cup A^{\sim}$, $Y = B \cup B^{\sim}$, 其中$f(A) = B$, $g(B^{\sim}) = A^{\sim}$, $A \cap A^{\sim} = \emptyset$以及$B \cap B^{\sim} = \emptyset$.

在证明之前先了解一下这个结论(下面部分内容是个人的一些推测过程, 原来是希望从中找出证明思路, 估计会比较混乱).

设$x_0 \in A$, $y_0 \in B$, $y_0 = f(x_0)$, 设$x_1 = g(y_0)$, $y_1 = f(x_1)$, $\cdots$, $x_n = g(y_{n-1})$, $y_n = f(x_n)$, $\cdots$

$x_n \in A$, $y_n \in B$, 如果$x_n \notin A$, 则$x_n \in A^{\sim}$, 而$g(B^{\sim}) = A^{\sim}$, 即存在$y’ \in B^{\sim}$, 使得$x_n = g(y’)$, 又$x_n = g(y_{n-1})$, 如果$y_{n-1} \in B$, 则$\exists x’$使得$f(x’) = y_{n-1}$.

设$x \in A$, $y \in B$, $y = f(x)$, 设$x’ = g(y)$. 如果$x’ \in A^{\sim}$, 则有$y’$使$x’ = g(y’)$, 于是$y \neq y’$, 即$g^{-1}(x’)$至少有两个元素, 由$x’ \in A^{\sim}$是否有$f(x’) \in B^{\sim}$呢? 如果$x’ \in A$, 则$x = x’$或$x \neq x’$.

$X = A \cup g(B^{\sim})$, $Y = f(A) \cup B^{\sim}$.

应该考虑$A$中元素有什么特性. $x \in A$, $f(x) \in B$, $g(f(x)) = x’$, 且$x \neq x’$的情形下进行讨论. 实际上, 对于$y = f(x)$, $x = g(y)$这类点可以任意归类. 所以只考虑$x \neq x’$的时候. 下面应考虑$x’$如何归类.

如果把$x’$归入$A^{\sim}$, 则存在$y’ \in B^{\sim}$, 使$x’ = g(y’)$, 必有$y \neq y’$.

如果把$x’$归入$A$, 则考虑$f(x’)$, 重复讨论.

这个时候对$y’ = f(x”)$, $x”$必然不属于$A$, 即$x” \in A^{\sim}$.

注: 当时笔记中对$X = \{1, 2, 3\}$和$Y = \{1, 2, 3\}$, 做了一些摸索, 比较乱, 这里省略.

设$x \in A$, 令$y = f(x) \in B$, 设$x_1 = g(y)$, 我们把这样的$x_1$拉入$A$, 则可以继续$y_1 = f(x_1)$, $\cdots$, $x_n = g(y_{n-1})$, $y_n = f(x_n)$, 如此, 只要在这个序列中的$x_i$我们都属于$A$, 接下来看看$X$中剩下来的都是哪些元素? 如果这一部分成为$A$, $B = f(A)$, 对于$B^{\sim}$来说, 是无法满足$g(B^{\sim}) = A^{\sim}$. 或者说是不一定, 其中完全有可能有$x$, 使$x \notin g(B^{\sim})$, 对于这样的$x$, 我们继续扩展$A$, 扩展$A$的同时, 也在扩展$B$, 从而缩小$B^{\sim}$, 必须表明这个过程是可以穷尽的, 无穷递归.

注意$x \notin g(B^{\sim})$, 说明$x \in g(B)$, 或者说$x \in g(f(A))$.

我们这样来考虑集合$E$, $E \cap g(Y \backslash f(E)) = \emptyset$.

(1)首先这样的集合是存在的. 上面构造的$x_i$组成的集合就是.

(2)根据前面的讨论, 是要一直从$x$吸引元素, 那么最好的办法是考虑所有具有这种性质的元素的集合的并集. 令$A = \bigcup{A}$.

下面证明$A$是满足$E \cap g(Y \backslash f(E)) = \emptyset$中的最大的集合. 显然只需要证明$A \cap (x \backslash g(f(A))) = \emptyset$即可. $\forall x \in A$, 则$f(x) \in f(A)\Rightarrow g(f(x))$, 存在某个$E_0$, 使得$x_0 \in E_0$, 即$x \notin X \backslash g(f(E_0))$, 从而$x \in g(f(E_0))$, 注意到$E \subset A$, 从而$f(E) \subset f(A)$, 于是$g(f(E)) \subset g(f(A))$, 于是$x \in g(f(A))$, $x \notin X \backslash g(f(A))$, 从而$A \cap [X \backslash g(f(A))] = \emptyset$.

(3)令$B = f(A)$, $B^{\sim} = Y – B$, $A^{\sim} = X – A$, 下面需要证明$g(B^{\sim}) = A^{\sim}$.

$\forall x \in A^{\sim}$, 则$x \notin A$, $f(x)$是否属于$B^{\sim}$呢? $A \cap [X \backslash g(f(A))] = \emptyset$, $A \cap [X \backslash g(B)] = \emptyset$.

$\forall y \in B^{\sim}$, 则$g(y) \notin g(B)$, 于是$y \in X \backslash g(B)$, 又$A \cap (X \backslash g(B)) = \emptyset$, 从而$g(y) \notin A$, $g(y) \in A^{\sim}$ 于是$g(B^{\sim}) \subset A^{\sim}$.

$x \in A^{\sim}$, $x \notin A$, 是否必有$x \in X \backslash g(B)$, $x \notin g(B)$, $x \in g(B^{\sim})$, 从而$A^{\sim} \subset g(B^{\sim})$, 于是$A^{\sim} = g(B^{\sim})$.

$x \notin g(B^{\sim})$, 即$x \notin g(Y \backslash f(A))$.

设$E$满足$E \cap g(Y \backslash f(X)) = \emptyset$, 令$A = \bigcup\{E: E \cap g(Y \backslash f(E)) = \emptyset\}$, 笔记中$g(Y \backslash f(E))$的$E$是$X$, 我觉得应该是$E$.

$A \cap g(Y \backslash f(A)) = \emptyset\}$.

$\forall x \in A$, 则$\exists E_0$, 使得$x \in E_0$, $x \notin g(Y \backslash f(E_0))$, 从而$x \in g(f(E_0))$, 而$E_0 \subset A$ $\Rightarrow$ $g(f(E_0)) \subset g(f(A))$ $\Rightarrow$ $x \in g(f(A))$, $A \cap g(Y \backslash f(A)) = \emptyset$.

可惜终究没有自己想出来, 引用书中的证明:

称$E$为隔离集, 如果$E$满足$E \cap g(Y \backslash f(E)) = \emptyset$. 并记隔离集之全体为$\Gamma$, 令$A = \bigcup\limits_{E \in \Gamma}{E}$, 应有$A \in \Gamma$, 证明如下:

$\forall E \in \Gamma$, $E \subset A$, 有$E \cap g(Y \backslash f(E)) = \emptyset$, 而$f(E) \subset f(A)$, $Y \backslash f(E) \supset Y \backslash f(A)$ $\Rightarrow$ $g(Y \backslash f(E)) \supset g(Y \backslash f(A))$ $\Rightarrow$ $E \cap g(Y \backslash f(A)) = \emptyset$. $\forall E \in \Gamma$, 于是存在$(\bigcup E) \cap g(Y \backslash f(A)) = \emptyset$, 即$A \cap g(Y \backslash f(A)) = \emptyset$. 说明$A$是$\Gamma$中的极大值.

令$f(A) = B$, $Y \backslash B = B^{\sim}$, 及$g(B^{\sim}) = A^{\sim}$, 则需要证明$A \cup A^{\sim} = X$.

首先$A \cap A^{\sim} = \emptyset$, 可以从$A \cap g(Y \backslash f(A)) = \emptyset$得出, 因为$A^{\sim} = g(Y \backslash f(A))$.

如果$A \cup A^{\sim} \neq X$, 那么存在$x_0$, $x_0 \in X$, 但$x_0 \notin A \cup A^{\sim}$, 设$A_0 = A \cup \{x_0\}$, 则$A \subset A_0$, 下面证明$A_0 \in \Gamma$, $B = f(A) \subset f(A_0)$ $\Rightarrow$ $B^{\sim} \supset Y \backslash f(A_0)$ $\Rightarrow$ $A^{\sim} \supset g(Y \backslash f(A_0))$, 而$A \cap A^{\sim} = \emptyset$, 于是$A \cap g(Y \backslash f(A_0)) = \emptyset$, 如果$x_0 \notin g(Y \backslash f(A_0))$, 那么$A_0 \cap g(Y \backslash f(A_0)) = \emptyset$. $x_0$显然不属于$g(Y \backslash f(A_0)) \subset A^{\sim}$. 否则$x_0 \in A^{\sim}$, 与$x_0 \notin A \cup A^{\sim}$矛盾. 可这时又有另一个矛盾, $A_0 \in \Gamma$, 与$A_0 \supset A$矛盾, 因为$A$是极大的.

这里的证明使用了良序原理: 如果$S$是非空的良序集合, 则$S$中存在一个极大元.

对于集合来说, 交集和并集都可以用来定义良序关系. 对于这道题目, $A$就是$\Gamma$中的极大元, 然后说明如果$A \cup A^{\sim} \neq X$, 那么还有一个比$A$更大的$A$, 引出矛盾.

这里关键是$E$的构造, 从事后诸葛来看, 从原题本身有一些迹象表明$E$的构造.

$f(A) = B$, $g(B^{\sim}) = A^{\sim}$, $A \cap A^{\sim} = \emptyset$, $B \cap B^{\sim} = \emptyset$.

如果先构造$A$, 则应有$A \cap A^{\sim} = \emptyset$ $\Rightarrow$ $A \cap g(B^{\sim}) = \emptyset$ $\Rightarrow$ $A \cap g(Y \backslash B) = \emptyset$ $\Rightarrow$ $A \cap g(Y \backslash f(A)) = \emptyset$. 这时只与$A$有关了.

这个思路可能还可以应用于其它地方.

从这个引理出发, 可以证明Cantor-Bernstein定理: 若集合$A$与$Y$的某个真子集对等, $Y$与$X$的某个真子集对等, 则$X = Y$.

设$f$是$X$与$Y$的某个真子集的一一映射, $g$是$Y$与$X$的某个真子集的一一映射. 根据引理, $\exists A, A^{\sim}, B, B^{\sim}$, 使得$f(A) = B$, $g(B^{\sim}) = A^{\sim}$, $A \cup A^{\sim} = X$, $A \cap A^{\sim} = \emptyset$, $B \cup B^{\sim} = Y$, $B \cap B^{\sim} = \emptyset$, 注意到$g$是$Y$到$X$的子集的一一映射, 从而也是$B^{\sim}$到$A^{\sim}$的一一映射, 存在$g^{-1}$.

$$F(x) = \left\{
\begin{aligned}
f(x) &\quad x \in A \\
g^{-1}(x) &\quad x \in A^{\sim}
\end{aligned}
\right.$$

这个证明还提供了构造一一映射的方法.

特别的, $C \subset A \subset B$, $B \sim C$ $\Rightarrow$ $A \sim C$.

(6) 凡是和自然数集对等的集合称为可列集, 其基数为$\aleph_0$. 有结论: 任一无限集$X$必包含一个可列子集.

证明极为简单, 从$X$中取出$x_1$, $\cdots$, $x_{n-1}$, 在$X – \{x_1, \cdots, x_{n-1}\}$中取出$x_n$即可. 这说明无限集的最小基数为$\aleph_0$.

若$A_n(n=1, 2, \cdots)$为可列集, 则并集$A = \bigcup\limits_{n=1}^{\infty}{A_n}$也是可列集. ($\aleph_0 \times \aleph_0 = \aleph_0$)

这里给出一个计数方法:

$$\left.\begin{aligned}
A_1 &= \{a_{11}, a_{12}, \cdots, a_{1j}, \cdots \} \\
A_2 &= \{a_{21}, a_{22}, \cdots, a_{2j}, \cdots \} \\
A_3 &= \{a_{31}, a_{32}, \cdots, a_{3j}, \cdots \} \\
&\cdots
\end{aligned}\right\}
A = \{a_{11}, a_{21}, a_{12}, a_{31}, a_{22}, a_{13}, \cdots, a_{ij}, \cdots\}$$

当$i + j > 2$时, $a_{ij}$排在第$n$位, $n = j + \sum\limits_{k=1}^{i+j-2}{k}$.

由此可知有理数集是可列的, 而它在实数集上是稠密的.

设$A$是无限集且其基数为$\alpha$, 若$B$是可数集(有限的或可列的), 则$A \cup B$的基数仍是$\alpha$.

设$A \cap B = \emptyset$, 在$A$中存在$A_1$与$B$对等, $A_1 \subset A$, $A_1 = \{a_1, a_2, \cdots \}$, $B = \{b_1, b_2, \cdots \}$, 设$A = A_1 \cup A_2$, 下面对$B$为可列集进行讨论, 为$A$与$A \cup B$建立一一映射(有相同的基数).

$$a_1 = b_1, a_2 = a_1, a_3 = b_2, a_4 = a_2, \cdots$$

即$a_{2i} = a_i$, $a_{2i-1} = b_i$, 当$a \in A_2$时, 使用恒等映射. 这就构造了一个一一映射.

对于$B$为有限集情形, 注意$\overline{A \cup B} \ge \overline{A}$, 而$\overline{A \cup B}$又小于或等于$B$为可列集情形, 即为$\alpha$, 因此$A \cup B = \alpha$. 或者也可以直接构造映射如下: 当$B$为有限集时, 令$B = \{b_1, b_2, \cdots, b_n\}$.

仍然从$A$中取出一个可列集$A_1 = \{a_1, a_2, \cdots \}$, 这样来构造一一映射:

$$a_1 = b_1, \cdots, a_n = b_n, a_{n+1} = a_1, \cdots,$$

其余元素采取恒等映射.

下面刻画无限与有限的本质区别: 集合$A$为无限集的充分且必要条件为: $A$与其真子集对等.

有了上面的结论, 这个结论的证明比较简单, 由于有限集不可能与其真子集对等. 故充分性成立. 对于必要性, 只要从$A$中取出一个有限集$B$, 则$A \sim A \backslash B$.

(7) 自然数集的基数为$\aleph_0$, 那么实数集的基数呢? 实数集是不可数的. 由于$\tan(x): (-\frac{\pi}{2}, \frac{\pi}{2}) \rightarrow R^1$, 而$(0, 1) \leftrightarrow (-\frac{\pi}{2}, \frac{\pi}{2})$, 这几个对等关系, 我们只需要考虑$(0, 1)$或者$[0, 1]$. 而对于$[0, 1]$上的实数, 可以采用二进制表示法: $x = \sum\limits_{n=1}^{+\infty}{\frac{a_n}{2^n}}$, 再把$a_n = 0$的项舍去, 则$x = \sum\limits_{i=1}^{+\infty}{\frac{1}{2^{n_i}}}$, 这里$n_i$是严格上升的自然数序列. 令$k_1 = n$, $k_i = n_i – n_{i-1}$, $i=1, 2, \cdots$, 则$k_i$是自然数序列, 它是不可列的.

反证: 如果自然数序列可列, 则设为

$$\begin{aligned}
k_{1}^{(1)}, k_2^{(1)}, \cdots, k_i^{(1)}, \cdots \\
k_{1}^{(2)}, k_2^{(2)}, \cdots, k_i^{(2)}, \cdots \\
\cdots \\
k_{1}^{(i)}, k_2^{(i)}, \cdots, k_i^{(i)}, \cdots \\
\cdots
\end{aligned}$$

构造序列

$$k_1^{(1)} + 1, k_2^{(2)} + 1, \cdots, k_i^{(i)} + 1, \cdots$$

它不在这个排列之中, 矛盾, 说明它是不可数的.

这同时给出了结论, 用$l^{(n)}$表示自然数序列, 则全体自然数序列构成的集合不可列. 这个证明中关键有: 首先是在自然数序列和$(0, 1)$之间建立一一对应; 其次是构造这个新的序列. 另一种方法直接构造. 设$(0, 1)$中数排列如下:

$$\begin{aligned}
&0.a_{11}a_{12}\cdots a_{1n}\cdots \\
&0.a_{21}a_{22}\cdots a_{2n}\cdots \\
&\cdots \\
&0.a_{n1}a_{n2}\cdots a_{nn}\cdots \\
&\cdots
\end{aligned}$$

令$l = 0.b_1b_2 \cdots b_n \cdots$, 这里

$$b_i =
\begin{cases}
1, &a_{ii} \neq 1 \\
2, &a_{ii} = 1
\end{cases}
$$

$R^1$的基数为连续基数, 记为$c$, 有些书记为$\aleph$. 对此有如下结论:

设有集合列$\{A_k\}$, 若每个$A_k$的基数都是连续基数, 则其并集$\bigcup\limits_{1}^{\infty}{A_k}$的基数是连续基数.

证明使用了: $A_k \sim [k, k+1)$, 则$\bigcup\limits_{1}^{\infty}{A_k} \sim [1, \infty) \sim R^1$

$R^1$的基数比自然数集的基数大, 那么是否存在最大的基数呢? 下面的结论表明: 不存在最大基数.

若$A$是非空集合, 则$A$与其幂集$\Gamma(A)$不对等.

这个证明的方法也是反证法, 证明比较巧妙, 实际上涉及到了罗素悖论.

设$A$与$\Gamma(A)$之间存在一一对应$f$, 那么对于集合$F = \{x | x \notin f(x) \}$就会引出矛盾:

根据一一对应, 存在$y \in A$, 使得$f(y) = F$, 对于$y$会有矛盾.

(1) 若$y \in F$, 则$y \notin f(y)$, 即$y \notin F$.

(2) 若$y \notin F$, 则$y \in f(y)$, 即$y \in F$.

(8) 基数之间的运算.

对于基数$\alpha_1$和$\alpha_2$, 定义$\alpha_1 + \alpha_2$, $\alpha_1 \cdots \alpha_2$, $\alpha_1^{\alpha_2}$为如下集合的基数: 设$\bar{A} = \alpha_1$, $\bar{B} = \alpha_2$, $A \cap B = \emptyset$, 则$\alpha_1 + \alpha_2$为$A \cup B$的基数, $\alpha_1\cdot\alpha_2$为$A \times B$的基数, $\alpha_1^{\alpha_2}$为$B$到$A$的一切映射所构成的集合的基数. 对于本节的例子, 许多例子具有一定的难度, 而且极有价值.

例子1.3.1 $N \times N \sim N$之间的一一映射$f$: $f(i, j) = 2^{i-1}(2j-1)$;

$(-1, 1) \sim R^1$之间的一一映射$f$: $f(x) = \frac{x}{1 – x^2}$, 还有其他的, 例如$f(x) = \tan{\frac{\pi}{2}x}$.

例子1.3.2 $R^1$中互不相交的开区间族是可数集, 这个结论基于这样一个事实: 有理数集是可列的, 并且有理数又是稠密的. $R^1$上单调函数的不连续点为可数集, 这个结论可以从上一个结论推出. 问题在于构造这个互不相交的开区间集.

设$x_0$为$f(x)$的不连续点, 那么$x_0$有哪些性质呢? 这需要了解不连续点的各种类型: (1) 左右极限都存在, 或者不相等, 或者虽然相等, 但是不等于$x_0$在此处的值. (2)左右极限之一或者两者都不存在. 对于本题来说, 当$f(x)$是单调函数时, 根据有界集合必然存在上下确界, 那么$f(x)$的左右极限都是存在的, 而且必然有$\lim\limits_{x \rightarrow x_0-}{f(x)} < \lim\limits_{x \rightarrow x_0+}{f(x)}$, 这样就有一个开区间$(\lim\limits_{x \rightarrow x_0-}{f(x)}, \lim\limits_{x \rightarrow x_0+}{f(x)})$. 有了开区间, 还应证明对于不同的$x_1$, $x_2$, 对应的开区间不会相交, 即$(f(x_1-0), f(x_1+0)) \cap (f(x_2-0), f(x_2+0)) = \emptyset$, 这是明显的. 不妨设$x_1 < x_2$, 取出中点$\frac{x_1 + x_2}{2}$, 则应有$f(x_1 + 0) < f(\frac{x_1 + x_2}{2}) < f(x_2-0)$.

例子1.3.3 若$f(x)$是$R^1$上的实值函数, 则集合$\{x \in R^1: f$在$x$点不连续, 但右极限存在(有限)$\}$是可列集.

这道题目应该和上一题有类似的地方, 这些问题中的概念都涉及到了微积分的基本概念.

自己没有想出来, 下面的证明来自书本.

令$S = \{x \in R^1: f(x+0)$存在(有限)$\}$.

首先构造集合

$$E_n = \{x \in R^1: \exists \delta > 0, \forall x’, x” \in (x – \delta, x + \delta), |f(x’) – f(x”)| < \frac{1}{n} \}$$

那么$\cap{E_n}$是$f(x)$的连续点集, 从而考虑$S \backslash E_n$即可.

其次, 考虑$f(x+0)$的定义, $\forall n$, $\exists \delta > 0$, $|f(x’) – f(x+0)| < \frac{1}{2n}$, $x’ \in (x, x + \delta)$, 也就是说$x’$, $x” \in (x, x+ \delta)$时, 有$|f(x’) – f(x”)| < \frac{1}{n}$.

故$(x, x + \delta) \subset E_n$, 这就有一个对应关系: $S \backslash E_n$中每个点$x$是某个开区间$I_x = (x, x + \delta)$的左端点, 且$I_x$与$S \backslash E_n$不相交. 当$x_1, x_2 \in S \backslash E_n$, 且$x_1 \neq x_2$时, 有$I_{x_1} \cap I_{x_2} = \emptyset$, 因为若$I_{x_1} \cap I_{x_2} \neq \emptyset$, 则不妨设$x_1 < x_2$, 此时必有$x_2 \in I_{x_1}$, 不可能. 又区间族$\{I_x : x \in S \backslash E_n\}$是可数的. 故$S \backslash E_n$是可数的.

当时我自己考虑到的只有下面这点, $f(x+0)$的定义: $\exists \delta > 0$, 当$x’ \in (x, x + \delta)$时, $|f(x’) – f(x)| < \epsilon$, 这样有一个小区间$(x, x + \delta)$, 可是进一步却不知道如何应用了.

例子1.3.4 设$\bar{A} = \alpha$, 则$\overline{\Gamma(A)} = 2^{\alpha}$.

首先注意定义, $2^{\alpha}$是$A$到$\{0, 1\}$的所有映射的集合的基, 这个集合记为$\{0, 1\}^{A}$, 实际上就是$A$中集合的特征函数, 对于每一个$E \subset A$, 就对应了一个特征函数$\chi_E$, 反之亦然.

$R^1$的基数$\aleph = 2^{\aleph_0}$.

注意$2^{\aleph_0}$是$\{0, 1\}^{\aleph_0}$的基数. 也就是需要在$\{0, 1\}^{\aleph_0}$与$(0, 1]$之间建立对应关系. 这与$[0, 1]$中数的二进制表示有关, 设$\psi$是$N$到$\{0, 1\}$的一个映射, $\psi(n) = 0$或者$1$, $n=1,2, \cdots$, 则$\psi(n) \rightarrow 0.\psi(1)\psi(2)\cdots\psi(n)\cdots$, 刚好是$(0, 1]$间某个数的二进制表示. 反过来也成立. 当然这个映射可能不是单射, 那么可以考虑数的三进制表示.

例子1.3.5 设$f(x)$为$(a, b)$上实值函数, 则集合$\{x \in (a, b):$右导数$f_+'(x)$以及左导数$f_-‘(x)$存在而不相等$\}$为可数集.

首先需要把集合分解为两个集合$A = \{ x| f_+'(x) > f_-‘(x)\}$和$B = \{x|f_+'(x) < f_-‘(x)\}$.

下面需要了解左导数和右导数的含义: $f(x)$在$x_0$点处的导数为

$$f'(x_0) = \lim_{x \rightarrow x_0}\frac{f(x) – f(x_0)}{x – x_0} = \lim_{\Delta{x} \rightarrow 0}\frac{f(x_0 + \Delta{x}) – f(x_0)}{\Delta{x}}.$$

左导数就是这个极限的左极限: $f_-‘(x_0) = \lim\limits_{\substack{\Delta{x} \rightarrow 0 \\ \Delta{x} < 0}}\frac{f(x_0 + \Delta{x}) – f(x_0)}{\Delta{x}}$, 右导数$f_+'(x_0) = \lim\limits_{\substack{\Delta{x} \rightarrow 0 \\ \Delta{x} > 0}}\frac{f(x_0 + \Delta{x}) – f(x_0)}{\Delta{x}}$.

$\forall \epsilon > 0$, $\exists \delta_1$ 当$\Delta{x} \in (-\delta_1, 0)$时, $|\frac{f(x_0 + \Delta{x}) – f(x_0)}{\Delta{x}} – f_-‘| < \epsilon$.

$\exists \delta_2$ 当$\Delta{x} \in (0, \delta_2)$时, $|\frac{f(x_0 + \Delta{x}) – f(x_0)}{\Delta{x}} – f_+’| < \epsilon$.

(i) 对于左导数和右导数存在的点$x$, $f(x)$在$x$点必然是连续的.

(ii) 能否找出一个开区间$I_x$包住$x$, 使$I_x$中没有任何点满足这个条件.

假设对任意的开区间$I_x$, 存在一点$y$异于$x$满足条件

$$f_+'(y) = \lim_{\substack{\Delta{y} \rightarrow 0 \\ \Delta{y} > 0}}{\frac{f(y + \Delta{y}) – f(y)}{\Delta{y}}}, \quad f_-‘(y) = \lim_{\substack{\Delta{y} \rightarrow 0 \\ \Delta{y} < 0}}{\frac{f(y + \Delta{y}) – f(y)}{\Delta{y}}}$$

A)

\[\begin{gather*}
|\frac{f(y + \Delta{y}) – f(y)}{\Delta{y}} – f_+’| < \epsilon, \\
-\epsilon < \frac{f(y + \Delta{y}) – f(y)}{\Delta{y}} – f_+’ < \epsilon, \\
-\epsilon(\Delta{y}) < f(y + \Delta{y}) – f(y) – f_+’\Delta{y} < \epsilon(\Delta{y}), \Delta{y} > 0. \\
(f_+’-\epsilon)\Delta{y} < f(y + \Delta{y}) – f(y)< (f_+’ + \epsilon)\Delta{y}.
\end{gather*}\]

B)

\[\begin{gather*}
|\frac{f(y + \Delta{y}) – f(y)}{\Delta{y}} – f_-‘| < \epsilon,\\
-\epsilon < \frac{f(y + \Delta{y}) – f(y)}{\Delta{y}} – f_-‘ < \epsilon,\\
\epsilon(\Delta{y}) < f(y + \Delta{y}) – f(y) – f_-‘\Delta{y} < -\epsilon(\Delta{y}),\\
(f_-‘+\epsilon)\Delta{y} < f(y + \Delta{y}) – f(y)< (f_-‘ – \epsilon)\Delta{y}.
\end{gather*}\]

对于上述讨论, $f_+’ < r_x < f_-‘$, 则应有(注意$\epsilon$的任意性):

$$f(y + \Delta{y}) < r\Delta{y}$$

$\Delta{y}$属于某个区间.

注意这个$r$是关键, 虽然$r$可以是$(f_+’, f_-‘)$之间的任一值.

下面考虑$y$, $x$满足条件的, 则有$\Delta{y} = y – x$, $y > x$, 则

$$f(y + \Delta{y}) – f(y) < r\Delta{y} \quad f(x + \Delta{y}) – f(x) < r\Delta{y},$$

$$f(x) – f(y) < r(x – y) \quad f(y) – f(x) < r(y – x)$$

矛盾.

下面阐述这个构造过程: 证明集合$A$是可列集.

(i) 首先从$f_+'(x)$与$f_-‘(x)$的定义, 可知对于每一个$x$, 存在一个小区间$I_x$包围$x$, 使$\forall y \in I_x$有

$$f(y) – f(x) < r(y – x),$$

注意$r$与$x$有关.

(ii) 如果只是有这样的$I_x$存在, 还不足以确定可数性, 这里关键是其中还有一个$r_x$, 也就是在这个小区间中不可能有另外一个点$y$, 从而这样的$I_x$是不相交的.

书中的构造是这样的:

从$f_+’$和$f_-‘$推出存在$s_x < y < t_x$, 使得$f(y) – f(x) < r_x(y – x)$, 令$x$与三维空间中的有理点$(r_x, s_x, t_x)$建立对应关系, 实际上, $(s_x, t_x)$可以认为是我的$I_x$, 注意我只选择有理点.

例子1.3.6 定义在$(a, b)$上的凸函数在至多除一可数集外的点上都可微.

这个例子涉及到了凸函数的定义.

$(a, b)$上的凸函数是指对$(a, b)$中的任意两点$x_1$, $x_2$, $x_1 < x_2$, 均有$f(x) \le \frac{(x_2 – x)f(x_1) + (x – x_1)f(x_2)}{x_2 – x_1}$, $x_1 < x < x_2$.

$(x, y)$在过点$(x_1, f(x_1))$和点$(x_2, f(x_2))$的直线上:

\begin{gather*}
\frac{y – f(x_1)}{x – x_1} = \frac{f(x_2) – f(x_1)}{x_2 – x_1} \\
y = \frac{(x – x_1)(f(x_2) – f(x_1))}{x_2 – x_1} + f(x_1) \\
y = \frac{(x – x_1)f(x_2) + (x_2 – x)f(x_1)}{x_2 – x_1}
\end{gather*}

把上述式子变换一下:

\[\begin{gather*}
(x_2 – x_1)f(x) \le (x_2 – x)f(x_1) + (x – x_1)f(x_2) \\
(x_2 – x + x – x_1)f(x) \le (x_2 – x)f(x_1) + (x – x_1)f(x_2) \\
(x_2 – x)(f(x) – f(x_1)) \le (x – x_1)(f(x_2) – f(x)) \\
\frac{f(x) – f(x_1)}{x – x_1} \le \frac{f(x_2) – f(x)}{x_2 – x}
\end{gather*}\]

注意这是对任一的$x_1 < x < x_2$成立的, 固定$x_2$, 令$x_1 \rightarrow x$, 那么此时可有$f(x)$的左导数是存在的, 且为有限值, 另一方面, 固定$x_1$, 令$x_2 \rightarrow x$, 则$f(x)$的右导数存在, 那么$f(x)$只有在左右导数不相等的点不可微, 从而由前一个例子可知原题结论成立.

上面左右导数的存在利用了单调有界原则. 对于任一点$x$, $x < x’ < x_2$, 则$\frac{f(x’) – f(x)}{x’ – x} < \frac{f(x_2) – f(x)}{x_2 – x}$.

A) 这说明$g(x’) = \frac{f(x’) – f(x)}{x’ – x}$是一个递增函数且有界, 从而存在极限.

B) $f_+'(x) = \lim\limits_{x’ \rightarrow x}{g(x’)}$存在.

类似的可知右导数存在.

例子1.3.7 区间$[a, b]$上的连续函数全体$C[a, b]$的基数是$2^{\aleph_0}$.

(1) $[a, b]$上的常数函数与$[a, b]$对等, 说明$C[a,b]$的势大于等于$2^{\aleph_0}$.

(2) 对于每个$\varphi \in C[a, b]$: 平面有理点集$Q \times Q$.

$$f(\varphi) = \{ (s, t) : s \in [a, b], t \le \varphi(s) \} \subset Q \times Q.$$

下面证明当$\varphi_1 \neq \varphi_2$时, $f(\varphi_1) \neq f(\varphi_2)$. 注意, 若$f(\varphi_1) = f(\varphi_2)$, 则

$$\forall t, t \le \varphi_1(s), t \le \varphi_2(s)$$

其中$t \in f(\varphi_1) = f(\varphi_2)$, 此时必须有$\varphi_1 = \varphi_2$, 否则若$\varphi_1(s) < \varphi_2(s)$, 则存在有理数$t’$, $\varphi_1(s) < t’ < \varphi_2(s)$, 矛盾.

这个映射说明$C[a, b]$与$\Gamma(Q \times Q)$的一个子集可以建立一一对应, 而$\Gamma(Q \times Q)$的基数为$2^{\aleph_0}$. 故$C[a, b]$的基数小于等于$2^{\aleph_0}$. 获证.

这里实际上是用到了有理数的稠密性和函数的连续性. 或者说两个连续函数如果在有理点相等, 它们是相等的.

注解: 从这几个例子看来, 关于基数和可列性问题, 主要有这样的思路:

(1) 考虑一个一个列出集合中元素, 或者证明无法列出(通常在列出的元素之外构造一个不在其中的元素).

(2) 使用Cantor-Bernstein定理, 建立两个单射, $A$到$B$的子集, $B$到$A$的子集.

(3) 对于可列集, 考虑和有理数集建立一一对应, 也可以考虑不相交的开区间集.

(4) 应用其他定理, 例如可列个可列集的并集还是可列的.

(5) 对于$2^{\aleph_0}$, 考虑集合之间的映射.

$$f(x) =\begin{cases}
-x^2, & \text{if} \\
\alpha + x, & \text{if} \\
x^2, &\text{other}
\end{cases}$$