§2 映射·集的对等·可列集

7. 试作下列各题中集之间的一一对应:

   (1). \([0, 1)\) 与 \((0, 1)\);

   (2). \([a, b]\) 与 \((-\infty, +\infty)\);

   (3). 开区间 \((0, 1)\) 与 无理数集;

   (4). 开上半平面与开单位圆;

   (5). \(\mathbb{N}^2\) 与 \(\mathbb{N}\).

解

(1). 由于 \((0, 1)\) 中有理数是可列的, 记为 \(\{ r_1, r_2, \dots, r_n, \dots \}\), 记 \(r_0 = 0\), 那么可以通过如下的映射给出一一对应:

\[\begin{split}f: [0, 1) \to (0, 1), \quad x \mapsto \begin{cases} r_{n}, & x = r_{n-1}, n \in \mathbb{N}, \\ x, & x \in (0, 1) \setminus \mathbb{Q}. \end{cases}\end{split}\]

(2). 闭区间 \([a, b]\) 与 \([0, 1]\) 可以通过映射 \(f: x \mapsto \dfrac{x - a}{b - a}\) 得到一一对应. 另一方面, \((-\infty, +\infty)\) 与 \((0, 1)\) 可以通过映射 \(g: x \mapsto \dfrac{1 + \tanh x}{2}\) 得到一一对应. 再利用类似 (1) 中的方法, 可以构造 \([0, 1]\) 与 \((0, 1)\) 的一一对应 \(\varphi\), 那么复合映射 \(g^{-1} \circ \varphi \circ f\) 就给出了 \([a, b]\) 与 \((-\infty, +\infty)\) 的一一对应.

(3). 由于 \(g(x) = \dfrac{1 + \tanh x}{2}\) 给出了 \(\mathbb{R}\) 到 \((0, 1)\) 的一一对应, 所以我们只要给出 \(\mathbb{R}\) 与无理数集 \(\mathbb{R} \setminus \mathbb{Q}\) 的一一对应即可. 记集 \(A = \mathbb{Q} + \sqrt{2} = \{ r + \sqrt{2} : \ r \in \mathbb{Q} \} = \{ a_1, a_2, \dots, a_n, \dots \}\), 那么集 \(A\) 是可列集且 \(A \cap \mathbb{Q} = \emptyset\). 记 \(\mathbb{Q} = \{ r_1, r_2, \dots, r_n, \dots \}\), 那么可以通过如下的映射给出一一对应:

\[\begin{split}f: \mathbb{R} \rightarrow \mathbb{R} \setminus \mathbb{Q}, \quad x \mapsto \begin{cases} x, & x \in \mathbb{R} \setminus (\mathbb{Q} \cup A), \\ a_{2n-1}, & x = r_n, n \in \mathbb{N}, \\ a_{2n}, & x = a_n, n \in \mathbb{N}. \end{cases}\end{split}\]

(4). 记 \(\mathbb{H} = \{ (x, y) \in \mathbb{R}^2 : \ y > 0 \}\) 为开上半平面, \(\mathbb{D} = \{ (x, y) \in \mathbb{R}^2 : \ x^2 + y^2 < 1 \}\) 为开单位圆. 我们将 \(\mathbb{D}\) 分为三个部分

\[\begin{split}\begin{align*} \mathbb{D}_1 & = \{ (x, y) \in \mathbb{D} : \ y < 0 \}, \\ \mathbb{D}_2 & = \{ (x, y) \in \mathbb{D} : \ y > 0 \}, \\ \mathbb{D}_3 & = \{ (x, y) \in \mathbb{D} : \ y = 0 \}. \end{align*}\end{split}\]

类似地, 我们将 \(\mathbb{H}\) 分为三个部分

\[\begin{split}\begin{align*} \mathbb{H}_1 & = \mathbb{D}_2 = \{ (x, y) \in \mathbb{H} : \ x^2 + y^2 < 1 \}, \\ \mathbb{H}_2 & = \{ (x, y) \in \mathbb{H} : \ x^2 + y^2 > 1 \}, \\ \mathbb{H}_3 & = \{ (x, y) \in \mathbb{H} : \ x^2 + y^2 = 1 \}. \end{align*}\end{split}\]

我们给出对应部分之间的一一映射:

\[\begin{split}\begin{align*} \mathbb{D}_1 & \to \mathbb{H}_1: \quad (x, y) \mapsto (x, -y), \\ \mathbb{D}_2 & \to \mathbb{H}_2: \quad (r, \theta) \mapsto (1/r, \theta) \quad \text{(注意, 这里是极坐标)}, \\ \mathbb{D}_3 & \to \mathbb{H}_3: \quad (x, 0) \mapsto (x, \sqrt{1 - x^2}). \end{align*}\end{split}\]

另解: 将 \(\mathbb{R}^2\) 与 \(\mathbb{C}\) 对等, 那么 \(\mathbb{D} = \{ z \in \mathbb{C} : \ \lvert z \rvert < 1 \}\) 到 \(\mathbb{H} = \{ z \in \mathbb{C} : \ \mathfrak{Im} (z) > 0 \}\) 的一一对应可以通过 Möbius 变换给出:

\[f: \mathbb{D} \rightarrow \mathbb{H}, ~ z \mapsto i \dfrac{1 + z}{1 - z}.\]

(5). \(f: \mathbb{N}^2 \rightarrow \mathbb{N}: \quad (m, n) \mapsto 2^{m-1} (2n - 1)\), 或者

\[f: \mathbb{N}^2 \rightarrow \mathbb{N}: \quad (m, n) \mapsto \dfrac{(m + n - 2)(m + n - 1)}{2} + m.\]

8. 设 \(A = \{0, 1\}\), 试证一切排列

   \[(a_1, a_2, \cdots, a_n, \cdots): \quad a_n \in A, n \in \mathbb{N}\]

   所成之集的势为 \(\aleph\).

证明

令集合 \(B = \{ (a_1, a_2, \cdots, a_n, \cdots): \ a_n \in A, n \in \mathbb{N} \}\), 以及集合 \(B_0 = \{ (a_1, a_2, \cdots, a_n, \cdots) \in B: \ \exists ~ n \in \mathbb{N}, s.t. \forall ~ k \geqslant n, a_k = 1 \}\), 并考虑映射

\[f: B \setminus B_0 \to [0, 1), \quad (a_1, a_2, \cdots, a_n, \cdots) \mapsto \sum_{n=1}^{\infty} a_n 2^{-n}.\]

以上映射给出了集合 \(B \setminus B_0\) 与区间 \([0, 1)\) 之间的一一对应, 而 \(B_0\) 是可列集, 所以集合 \(B = (B \setminus B_0) \cup B_0\) 也与区间 \([0, 1)\) 对等 [1] , 从而它的势为 \(\aleph\).

9. 问下列各集能否与自然数集或区间 \([0, 1]\) 构成一一对应:

   (1). 以有理数为端点的区间集；

   (2). 闭正方形 \([0, 1; 0, 1]\).

   如果可能, 试作出对应方法.

解

(1). 以有理数为端点的 (开）区间集为 \(A = \left\{ (a, b) : \ a < b, a, b \in \mathbb{Q} \right\}\). 首先, \(A\) 是 \(\mathbb{Q}^2\) 的子集； 另一方面, 可以通过单射 \(\mathbb{Q} \to A: \ a \mapsto (a, a + 1)\) 将 \(\mathbb{Q}\) 视为 \(A\) 的子集, 从而集合 \(A\) 是可列的. 令 \(\mathbb{Q} = \{ r_1, r_2, \dots, r_n, \dots \}\), 那么 \(A\) 到自然数集 \(\mathbb{N}\) 的一一对应可以通过如下方式构造:

首先, 将集合 \(A\) 改写为 \(A = \left\{ (a, d) : \ a \in \mathbb{Q}, d \in \mathbb{Q}^+ \right\}\), 其中 \(d\) 为区间长度. 那么 \(A \cong \mathbb{Q} \times \mathbb{Q}^+\). 我们可以定义 \(\mathbb{Q}^* = \mathbb{Q} \setminus \{ 0 \}\) 上的高度函数 \(H: \mathbb{Q}^* \to \mathbb{N}\) 如下:

\[H(\dfrac{p}{q}) = \max \{ \lvert p \rvert, \lvert q \rvert \}, \quad \text{其中} \dfrac{p}{q} \text{ 是既约分数}, q > 0.\]

那么 \(\mathbb{Q}\) 以及 \(\mathbb{Q}^+\) 中高度等于定值 \(h\) 的元素全体是有限集, 于是可以通过如下的排序方式分别给出 \(\mathbb{Q}\) 以及 \(\mathbb{Q}^+\) 到 \(\mathbb{N}\) 的一一对应:

\[\begin{split}\begin{align*} r_1 & \quad \{ 0 \}, \mathcal{H}_{11}, \mathcal{H}_{12}, \dots, \mathcal{H}_{1k}, \dots \\ r_2 & \quad \{ 0 \}, \mathcal{H}_{21}, \mathcal{H}_{22}, \dots, \mathcal{H}_{2k}, \dots \end{align*}\end{split}\]

对于 \(k \in \mathbb{N}\), \(\mathcal{H}_{1k}\) 表示 \(\mathbb{Q}\) 中高度为 \(k\) 的元素全体；\(\mathcal{H}_{2k}\) 表示 \(\mathbb{Q}^+\) 中高度为 \(k\) 的元素全体. 在每一个 \(\mathcal{H}_{1k}\) 以及 \(\mathcal{H}_{2k}\) 中, 将元素按其作为有理数的大小排序. 这样, 我们就给出了 \(\mathbb{Q} \times \mathbb{Q}^+\) 到 \(\mathbb{N} \times \mathbb{N}\) 的一一对应 \((r_1, r_2): \mathbb{Q} \times \mathbb{Q}^+ \to \mathbb{N} \times \mathbb{N}\).

类似地, 可以通过如下的排序方式给出一一对应 \(\mathbb{N} \times \mathbb{N} \to \mathbb{N}\):

\[s: \mathcal{G}_1, \mathcal{G}_2, \dots, \mathcal{G}_k, \dots\]

其中, \(\mathcal{G}_k = \{ (n_1, n_2) \in \mathbb{N} \times \mathbb{N} : \ n_1 + n_2 = k \}\), 其内部按 \(n_1\) 的大小进行排序. 于是, 我们就给出了一一对应

\[A \cong \mathbb{Q} \times \mathbb{Q}^+ \xrightarrow{(r_1, r_2)} \mathbb{N} \times \mathbb{N} \xrightarrow{s} \mathbb{N}.\]

备注

可以通过显式表达式给出一一对应 \(\mathbb{N} \times \mathbb{N} \to \mathbb{N}\):

\[s: \mathbb{N} \times \mathbb{N} \to \mathbb{N}, \quad (n_1, n_2) \mapsto \dfrac{(n_1 + n_2 - 2)(n_1 + n_2 - 1)}{2} + n_1.\]

见 习题1.7.

(2). 这题是课本 §2 的例1, 做法如下:

将 \([0, 1]\) 中的数写成二进制小数的形式 \(x = 0.x_1x_2 \cdots\), 相应的一一对应关系为

\[[0, 1] \times [0, 1] \to [0, 1] : \quad (x, y) \mapsto z = 0.x_1y_1x_2y_2 \cdots\]

由于约定了二进制小数不用 \(0.\cdots 0111\cdots\) 的形式表示, 需要检查的就只有通过上述映射得到的 \(z\) 不具有这种形式, 用反证法很容易证明这种情况不会发生.

10. 证明整系数多项式全体是可列的.

证明

对于整系数多项式全体 \(\mathbb{Z}[X]\) 有分解

\[\mathbb{Z}[X] = \bigcup_{n=0}^{\infty} \mathbb{Z}_n[X], \quad \mathbb{Z}_n[X] = \{ f \in \mathbb{Z}[X]: \ \deg f = n \} \cong \mathbb{Z}^{n} \times \mathbb{Z}^{\ast},\]

其中 \(\mathbb{Z}^{\ast} = \mathbb{Z} \setminus \{ 0 \}\) (最高次项系数不为 \(0\)). 由于 \(\mathbb{Z}^{n} \times \mathbb{Z}^{\ast}\) 是可列集, 所以 \(\mathbb{Z}_n[X]\) 是可列集, 从而 \(\mathbb{Z}[X]\) 是可列集.

11. 设用 \(C[0, 1]\) 表示 \([0, 1]\) 上的一切连续函数所成的集, 试证它的势为 \(\aleph\).

证明

\([0, 1]\) 上常值函数全体与 \(\mathbb{R}\) 对等, 而且是 \(C[0, 1]\) 的真子集. 另一方面, \([0, 1]\) 上的任一连续函数 \(f\) 完全由它在所有有理点上的取值决定, 于是 \(C[0, 1]\) 与 \(\mathbb{R}^{\mathbb{N}}\) 的真子集对等. 这里是真子集是因为需要排除不能对应于连续函数的实数列, 例如设 \(a_1, a_2, \dots\) 是 \([0, 1]\) 上的一个收敛到 \(\frac{\sqrt{2}}{2}\) 的有理数数序列, 相应的值 \(f(a_n) = (-1)^n\) 不能对应于任何连续函数. 于是 \(C[0, 1]\) 与 \(\mathbb{R}^{\mathbb{N}}\) 的真子集对等. 由 Cantor-Bernstein 定理, 有 \(C[0, 1]\) 与 \(\mathbb{R}\) 对等, 从而它的势为 \(\aleph\).

这里, 我们还需要说明 \(\mathbb{R}^{\mathbb{N}}\) 与 \(\mathbb{R}\) 对等, 或者等价地, \((0, 1)^{\mathbb{N}}\) 与 \((0, 1)\) 对等:

\[(0.a_{11}a_{12}a_{13} \cdots, 0.a_{21}a_{22}a_{23} \cdots, \dots) \mapsto 0.a_{11}a_{12}a_{21}a_{13}a_{22}a_{31} \cdots.\]

12. 设用 \(M\) 表示 \((-\infty, +\infty)\) 上一切单调函数所成的集, 试讨论它的势.

解

任一单调函数 \(f\) 至多有可数个间断点, 而且每个间断点都是第一类间断点, 所以单调函数 \(f\) 可以表示为 \(f = f_1 + f_2\), 其中 \(f_1\) 是连续函数, \(f_2\) 是有至多可数个第一类间断点的阶跃函数. \(f_2\) 完全由间断点的值以及相应的阶跃的量决定, 所以可视为 \(\mathbb{R}^{\mathbb{N}} \times \mathbb{R}^{\mathbb{N}}\) 的一个元素, 故其全体具有势 \(\aleph\). 再结合 上题 的结论, 有 \(M\) 的势为 \(\aleph\).

13. 设 \(A\) 是势大于 \(1\) 的集, \(A\) 上的一一映射称为 \(A\) 的置换. 试证存在 \(A\) 的一个置换 \(f\) 使对一切 \(x \in A\), \(f(x) \neq x\).

解

若 \(A\) 是有限集, 记为 \(A = \{ a_0, a_2, \dots, a_{n-1} \}\), \(n > 1\), 那么 \(a_{k} \mapsto a_{k + 1} \mod n\) 就是一个满足条件的置换. 以下我们考虑 \(A\) 是无限集的情况.

由于 \(A\) 为无限集, 那么 :math`A` 与 \(A \times \mathbb{F}_2\) 对等, 其中 \(\mathbb{F}_2 = \{ \bar{0}, \bar{1} \}\) (此结论非平凡), 即有双射 \(\varphi: A \to A \times \mathbb{F}_2\). 容易看出

\[g: A \times \mathbb{F}_2 \rightarrow A \times \mathbb{F}_2, \quad (x, y) \mapsto (x, y + 1 \mod 2)\]

是一个没有不动点的置换, 从而复合映射 \(f = \varphi^{-1} \circ g \circ \varphi\) 就是集 \(A\) 的一个没有不动点的置换.

备注

利用选择公理 (或者 Zorn 引理) 的证明方法: 考虑集 \(A\) 的所有满足如下条件的子集族

\[\{ S_i \}_{i \in I}: \quad S_i \subset A, \quad \lvert S_i \rvert = 2, \quad \forall ~ i \in I; \quad S_i \cap S_j = \emptyset, \quad i \neq j.\]

由包含关系定义偏序关系, 那么任一全序子集都是上界, 从而根据 Zorn 引理, 存在极大元素 \(\mathcal{S} = \{ S_i \}_{i \in I}\). 那么 \(\bigcup_{i \in I} S_i\) 要么等于 \(A\), 要么等于 \(A \setminus \{ x \}\), 其中 \(x\) 是 \(A\) 中的一个元素. 由于 \(A\) 与 \(A \setminus \{ x \}\) 对等, 所以只要对 \(\bigcup_{i \in I} S_i = A\) 的情况证明即可. 记 \(S_i = \{ a_{i0}, a_{i1} \}\), 那么可以通过如下的映射给出一个没有不动点的置换:

\[f: A \to A, \quad a_{ij} \mapsto a_{i (j+1 \mod 2)}.\]

其实, 以上我们 (利用选择公理) 也证明了 \(A\) 与 \(A \times \mathbb{F}_2\) 对等. 但是要注意的是,

每一个无限集 \(A\) 都与 \(A \times \mathbb{F}_2\) 对等

要严格弱于选择公理, 即不能从这个结论推出选择公理.

14. 设 \(f: X \to Y\) 是满射, \(A \subset X, B \subset Y\). 问下列四个关系中哪些是正确的, 哪些不是:

    (1). \(f^{-1}(f(A)) = A\);

    (2). \(f^{-1}(f(A)) \supset A\);

    (3). \(f(f^{-1}(B)) \subset B\);

    (4). \(f(f^{-1}(B)) = B\).

解

由于对任意 \(x \in A \subset X\), \(x\) 是 \(f(x) \in f(A) \subset Y\) 的原像, 所以有 \(A \subset f^{-1}(f(A))\), 即 (2) 正确. 一般来说, 相等的关系不一定成立, 例如考虑 \(f: \mathbb{R} \to \mathbb{R}_{\geqslant 0}, x \mapsto x^2\), \(A = \mathbb{R}_{\geqslant 0}\), 那么 \(f(A) = \mathbb{R}_{\geqslant 0}\), 但是 \(f^{-1}(f(A)) = \mathbb{R} \supsetneq A\), 所以 (1) 错误.

另一方面, 对于一般的映射 \(f: X \to Y\), 任取 \(x \in f^{-1}(B)\), 那么有 \(f(x) \in B\), 从而有 \(f(f^{-1}(B)) \subset B\). 由于 \(f\) 是满射, 所以对任意 \(y \in B\), \(f^{-1}(y) \neq \emptyset\), 即存在 \(x \in f^{-1}(y) \subset f^{-1}(B)\), 使得 \(f(x) = y\), 从而有 \(B \subset f(f^{-1}(B))\), 于是有 \(f(f^{-1}(B)) = B\), 即 (3) 和 (4) 正确.

15. 设给定映射 \(f: X \to Y\). 试证对 \(Y\) 中的任意集族 \(\{ B_{\alpha} \}_{\alpha \in I}\) 有

\[\begin{split}\begin{gather*} f^{-1} \left( \bigcup_{\alpha \in I} B_{\alpha} \right) = \bigcup_{\alpha \in I} f^{-1} (B_{\alpha}), \quad f^{-1} \left( \bigcap_{\alpha \in I} B_{\alpha} \right) \subset \bigcap_{\alpha \in I} f^{-1} (B_{\alpha}), \\ f^{-1} (\mathscr{C} B) = \mathscr{C} f^{-1} (B). \end{gather*}\end{split}\]

证明

任取 \(x \in f^{-1} \left( \bigcup\limits_{\alpha \in I} B_{\alpha} \right)\), 那么有 \(f(x) \in \bigcup\limits_{\alpha \in I} B_{\alpha}\), 这意味着存在 \(\alpha \in I\), 使得 \(f(x) \in B_{\alpha}\), 从而有 \(x \in f^{-1} (B_{\alpha})\), 于是有 \(x \in \bigcup\limits_{\alpha \in I} f^{-1} (B_{\alpha})\). 反过来, 任取 \(x \in \bigcup\limits_{\alpha \in I} f^{-1} (B_{\alpha})\), 那么存在 \(\alpha \in I\), 使得 \(x \in f^{-1} (B_{\alpha})\), 于是有 \(f(x) \in B_{\alpha}\), 从而有 \(f(x) \in \bigcup\limits_{\alpha \in I} B_{\alpha}\), 于是有 \(x \in f^{-1} \left( \bigcup\limits_{\alpha \in I} B_{\alpha} \right)\). 综上所述, 有 \(f^{-1} \left( \bigcup\limits_{\alpha \in I} B_{\alpha} \right) = \bigcup\limits_{\alpha \in I} f^{-1} (B_{\alpha})\).

任取 \(x \in f^{-1} \left( \bigcap\limits_{\alpha \in I} B_{\alpha} \right)\), 那么有 \(f(x) \in \bigcap\limits_{\alpha \in I} B_{\alpha}\), 这意味着对任意 \(\alpha \in I\), 都有 \(f(x) \in B_{\alpha}\), 从而有 \(x \in f^{-1} (B_{\alpha})\), 于是有 \(x \in \bigcap\limits_{\alpha \in I} f^{-1} (B_{\alpha})\). 反过来, 任取 \(x \in \bigcap\limits_{\alpha \in I} f^{-1} (B_{\alpha})\), 那么对任意 \(\alpha \in I\), 都有 \(x \in f^{-1} (B_{\alpha})\), 于是有 \(f(x) \in B_{\alpha}\), 从而有 \(f(x) \in \bigcap\limits_{\alpha \in I} B_{\alpha}\), 于是有 \(x \in f^{-1} \left( \bigcap\limits_{\alpha \in I} B_{\alpha} \right)\).

若 \(f^{-1} (\mathscr{C} B) = \emptyset\), 即 \(\forall ~ x \in X, f(x) \not\in \mathscr{C} B\), 那么有 \(\forall ~ x \in X, f(x) \in B\), 这意味着 \(f^{-1} (B) = X\), 于是有 \(\mathscr{C} f^{-1} (B) = \emptyset\). 若 \(f^{-1} (\mathscr{C} B) \neq \emptyset\), 任取 \(x \in f^{-1} (\mathscr{C} B)\), 那么有 \(f(x) \in \mathscr{C} B\), 于是有 \(f(x) \not\in B\), 从而有 \(x \not\in f^{-1} (B)\), 于是有 \(x \in \mathscr{C} f^{-1} (B)\). 反过来, 任取 \(x \in \mathscr{C} f^{-1} (B)\), 那么有 \(x \not\in f^{-1} (B)\), 于是有 \(f(x) \not\in B\), 从而有 \(f(x) \in \mathscr{C} B\), 于是有 \(x \in f^{-1} (\mathscr{C} B)\). 综上所述, 有 \(f^{-1} (\mathscr{C} B) = \mathscr{C} f^{-1} (B)\).

注

[1]

这是根据本节例1的结论得到的: “设集 \(A\) 与 \([0, 1]\) 对等, \(B\) 是可列集, 则 \(A \cup B\) 与 \(A \setminus B\) 均与 \([0, 1]\) 对等. ” 而 \([0, 1]\) 又与 \([0, 1)\) 对等, 所以 \(A\) 与 \([0, 1)\) 对等.