离散数学-4

设 $A$ 为由序列

$$a_1, a_2, \cdots, a_n, \cdots$$

的所有项组成的集合,则是否是可数的？为什么？

[解]：

因为序列是可以重复的,故若 $A$ 是由有限个数组成的集合,则是有限的集合;
若 $A$ 是由无限个数组成的集合,则是可数的.
故是至多可数的.

证明：直线上互不相交的开区间的全体所构成的集合至多可数.

[证]:

在每个开区间中取一个有理数,则这些有理数构成的集合是整个有理数集合 $Q$ 的子集,因此是至多可数的.

证明：单调函数的不连续点的集合至多可数.

[证]:

设 $A$ 是所有不连续点的集合, $f$ 是一个单调函数,则 $\forall x_0 in A$ , $x_0$ 对应着一个区间 $(f(x_0 - 0), f(x_0 + 0))$ ,于是由上题便得到证明.

任一可数集 $A$ 的所有有限子集构成的集族是可数集合

[证]

设 $ A = {a_1, a_2, \cdots, a_n, \cdots} $, $ B = {a_{i_1}, a_{i_2}, \cdots, a_{i_k}} $, 则 $ B \subseteq A $ 且 $ |B| = k < \infty $

令 $ B = {B \mid B \subseteq A, |B| < \infty} $, 设 $ \varphi: A \to {0,1} $,则 $ \varphi $ 是 $ A $ 的子集的特征函数

$ \forall B \in B, \varphi(B) = {0,\ 1\text{ 的有穷序列}} $,即 $ \forall a_i \in A $

若 $ a_i \in B $,则对应 1;若 $ a_i \notin B $ 则对应 0

于是 $ \forall B \in B, \varphi(B) $ 就对应着一个由 0,1 组成的有限序列 $ 0, 1, 1, 0, \ldots, 0, 1 $

此序列对应着一个二进制小数,而此小数是有理数

于是,可数集 $ A $ 的所有有限子集 $ B $ 对应着有理数的一个子集

又 $ \forall B_1, B_2 \in B, B_1 \ne B_2, B_1, B_2 $ 对应的小数也不同,故 $ \varphi $ 是单射.而可数集 $ A $ 的所有有限子集 $ B $ 是无穷的,故 $ B $ 是可数的.

判断下列命题之真伪：

(1)若 $f: X \to Y$ 且 $f$ 是满射,则只要 $X$ 是可数的,那么 $Y$ 是至多可数的; (2)若 $f: X \to Y$ 且 $f$ 是单射,那么只要 $Y$ 是可数的,则 $X$ 也是可数的; (3)可数集在任一映射下的像也是可数的;

[解]：对,错,错.

设 $A=\{a_1,a_2,a_3\cdots\}$ 是可数集,令:

$$A_1 = \{ a_n \mid n = 2(2t - 1), t = 1,2,\cdots \}\\ A_2 = \{ a_n \mid n = 2^2(2t - 1), t = 1,2,\cdots \}\\ \cdots\cdots\\ A_k = \{ a_n \mid n = 2^k(2t - 1), t = 1,2,\cdots \}\\ \cdots\cdots$$

证明：$i\ne j$ 时, $A_i \cap A_j = \Phi, i,j = 1,2,3,\cdots$

[证]:

采用反证法,假设 $i\ne j$ 时存在 $a_x \in A_i$ 且 $a_x \in A_j$ 则:

$$x=2^i(2t_i-1)=2^j(2t_j-1)$$

为了方便,不妨假设 $i<j$ 则:

$$2t_i-1=2^{j-i}(2t_j-1)$$

这是不可能的,因为 $2t_i-1$ 总是一个奇数,而 $2^{j-i}(2t_j-1)$ 总是一个偶数,因此不可能存在这样的元素.

设 $A$ 是有限集,$B$ 是可数集,证明：$B^A = \{ f \mid f: A \to B \}$ 是可数的.

[证]:

令 $A = \{1,2,\cdots,n\}, B = \{b_1,b_2,\cdots,b_n,\cdots\}$,$B$ 可数

设 $f: A \to B, \forall i \in A, f(i) \in B$

$$(f(k_1), f(k_2), \cdots, f(k_n)) \in B \times B \times \cdots \times B = B^n$$

因此用数学归纳法可知其是可数的

$B^A$ 中的每个 $f$ 实际上就是 $B$ 的一个有限子集,可数集的有限子集是可数的.于是由 4 题即可证明）

设 $\Sigma$ 为一个有限字母表,$\Sigma$ 上所有字（包括空字）之集记为 $\Sigma^*$.证明 $\Sigma^*$ 是可数集.

[证]:

证法 1：设有有限字母 $\Sigma$ 上所有字（包括空字 $\varepsilon$）所形成的集 $\Sigma^*$,则 $\Sigma^*$ 是可数的.

$$A_1 = \{\text{长度为 } 1 \text{ 的字符串}\} \\ A_2 = \{\text{长度为 } 2 \text{ 的字符串}\} \\ \vdots \quad \quad \quad \vdots \\ A_n = \{\text{长度为 } n \text{ 的字符串}\} \\ \vdots \quad \quad \quad \vdots$$

因为 $A_i$ 中每个长度都是有限的,而 $\Sigma^* = \bigcup_{i=1}^{\infty} A_i$,故 $\Sigma^*$ 是至多可数的,又 $\Sigma^*$ 显然是无穷的,故 $\Sigma^*$ 是可数的.

证法 2：

不妨假设 $\Sigma = \{a,b,c\}$（令 $\Sigma = \{0,1\}$ 也可以）,则可按字典序排序为： $ \varepsilon, a, b, c, aa, ab, ac, ba, bb, bc, \cdots, aaa, aab, \cdots $ 由于 $\Sigma^*$ 的全部元素可以排成无重复项的无穷序列,故 $\Sigma^*$ 是可数的.

定理1:

设 $A_1, A_2, \cdots, A_n$ 是 $n$ 个两两不相交的连续统，则 $ \bigcup_{i=1}^{n} A_i $ 是连续统，即

$$\bigcup_{i=1}^{n} A_i \sim [0,1]$$

定理2:

设 $A_1, A_2, \cdots, A_n, \cdots$ 为两两不相交的集序列。如果 $A_k \sim [0,1], k = 1,2,\cdots$，则:

$$\bigcup_{n=1}^{\infty} A_n \sim [0,1]$$

上面两个定理中两两不相交的条件能否去掉?为什么?

[解]:

能去掉.原定理增加此条件仅为了方便证明.

找一个初等可数 $f(x)$，使得它是 $(0,1)$ 到实数 $R$ 的一一对应。

[解]:

$\mathrm{cot}\,x$ 或 $\mathrm{tan}\,x$

试给出一个具体的函数，使得它是从 $(0,1)$ 到 $[0,1]$ 的一一对应

[解]:

$(0,1)$ 中包含一个可数子集 $A = \left\{\dfrac{1}{2}, \dfrac{1}{2^2}, \dfrac{1}{2^3}, \cdots\right\}$ 可数。 $A_1 = A \cup \{0,1\} = \left\{0,1,\dfrac{1}{2},\dfrac{1}{2^2},\dfrac{1}{2^3},\cdots\right\}$——可数的，故 $A : A_1$

令 $\varphi : (0,1) \to [0,1], \forall x \in (0,1)$

$$\varphi(x) = \begin{cases} x & \text{当 } x \notin A \\ 0 & \text{当 } x = \dfrac{1}{2} \\ 1 & \text{当 } x = \dfrac{1}{4} \\ \dfrac{1}{2^{i-2}} & \text{当 } x = \dfrac{1}{2^i}, i \geq 3 \end{cases}$$

$\varphi(x)$ 即为所求。

证明：若 $A$ 可数，则 $2^A$ 不可数。（用对角线方法）

[证]:

$A$ 可数，则令 $A = \{1,2,3,\cdots\}$。 假设 $2^A$ 可数，则 $A$ 的子集（即 $2^A$ 的元素）是可数的，故 $2^A$ 中元素可排成一个无重复项的无穷序列：

$$A_1, A_2, \cdots, A_n, \cdots$$

而 $2^A \sim Ch(A) = \{f \mid f: A \to \{0,1\}\}$，于是特征函数 $Ch(A)$ 可数，即 $Ch(A)$ 可写成下列无穷序列形式：

$$\begin{aligned}&f_1, f_2, \cdots, f_n, \cdots \\\\ &f_1: a_{11}a_{12}a_{13}\cdots \\ &f_2: a_{21}a_{22}a_{23}\cdots \\ &f_3: a_{31}a_{32}a_{33}\cdots \\ &\vdots \quad \vdots \quad \vdots \\ &f_n: a_{n1}a_{n2}a_{n3}\cdots \\ &\vdots \quad \vdots \quad \vdots \end{aligned} \quad$$

其中 $a_{ij} = 0$或 $1$ , $j = 1,2,3,\cdots$ .

构造一个特征函数 $\beta$

令 $\beta = \{b_i\}_1^\infty$

$$b_1 = \begin{cases} 1 & \text{if } a_{11} = 0 \\ 0 & \text{if } a_{11} = 1 \end{cases}\\ b_2 = \begin{cases} 1 & \text{if } a_{22} = 0 \\ 0 & \text{if } a_{22} = 1 \end{cases}\\ \vdots \\ b_n = \begin{cases} 1 & \text{if } a_{nn} = 0 \\ 0 & \text{if } a_{nn} = 1 \end{cases} \\ \vdots$$

则 $\beta \ne f_1, f_2, f_3, \cdots, f_n, \cdots$，但 $\beta$ 确实是 $A$ 到 $\{0,1\}$ 的一个映射，即 $\beta$ 是 $A$ 的子集的特征函数，矛盾。故 $2^A$ 不可数。

令 $N = \{1,2,3,\cdots\}$，$S = \{f \mid f: N \to \{0,1\}\}$，利用康托对角线法证明 $S$ 是不可数集。

[证]:

假设从 $N$ 到 $\{0,1\}$ 的所有映射之集可数，则可排成无重复项的无穷序列：

$$f_1, f_2, f_3, \cdots$$

每个函数 $f_i$ 确定了一个 $0,1$ 序列 $a_{i1}, a_{i2}, a_{i3}, \cdots$

构造序列 $b_1, b_2, b_3, \cdots$，令:

$b_i = 1$，当且仅当 $a_{ii} = 0$ 反之 $b_i = 0$。 该序列对应的函数 $f(i) = b_i$，$i \in N$ ,不为 $f_1, f_2, \cdots$ 中任一个，矛盾。 故 $S$ 是不可数集。

设 $A=B \bigcup C,A\sim[0,1]$ ,试证: $B$ 和 $C$ 中至少有一个与 $[0,1]$ 对等.

[证]:

证法1:

基于连续统假设,采用反证法,假设 $B$ 和 $C$ 都不与 $[0,1]$ 对等则立刻得证.

证法2:

$$A\sim[0,1]\sim[0,1]\times [0,1]$$

假设:

(1) $\exist x_0 \in [0,1]$ 令 $S = \{(x_0,y) \, | \, y \in [0,1]\}$ , $S \subseteq B$,此时 $B \sim [0,1]$ ;

(2) $\forall x_0 \in [0,1]$ 令 $S = \{(x_0,y) \, | \, y \in [0,1]\}$ , $S \nsubseteq B$ .

记 $P = \{p\in A,p \notin B\}$ ,显然 $P \subseteq C$ 且 $P \sim [0,1]$,因此 $C \sim[0,1]$ .

定义在 $[0,1]$ 上的所有连续函数之集与 $[0,1]$ 对等.

注意:请学习过『4.4 康托-伯恩斯坦定理』后阅读下面证法2.

提示:请注意『连续函数』的定义.

[证]:

证法1:

原命题等价于证明定义在 $[0,1]$ 上的所有连续函数之集与 $[0,1]\times[0,1]$ 对等,后者是显然的.

证法2:

记定义在 $[0,1]$ 上的所有连续函数之集为 $\mathbb{F}$

考虑使用 Contor-Bernstein 定理,寻找两个单射:

$$h:[0,1] \rightarrow \mathbb{F} \\ g:\mathbb{F} \rightarrow [0,1]$$

对 $h$ :

$$h(x)=''y=x''$$

即对应一个常值函数,注意范围.

对 $g$ :

每个连续函数尤其在有理点上的取值唯一确定,将 $[0,1]$ 中的全部有理数写成序列:

$$Q=\mathbb{Q}\bigcap[0,1]=\{q_1,q_2,\cdots\}$$

很容易参考教材构造一个 $R \leftrightarrow [0,1]$ 的一一对应 $\tau$ ,此处不再赘述.

于是写出:

$$\forall f \in \mathbb{F},y_i = \tau \circ f(q_i)=0.a_{i1}a_{i2}\cdots,q_i\in Q\\ a_{ij}\in Z \bigcap [0,9]$$

当然,我们约定不使用无穷多个 9 的表示方法.

可以用下面的无穷矩阵来表示一个定义在 $[0,1]$ 上的连续函数.

$$\begin{pmatrix} a_{11} & a_{12} & a_{13} & \cdots \\ a_{21} & a_{22} & a_{23} & \cdots \\ a_{31} & a_{32} & a_{33} & \cdots \\ \vdots & \vdots & \vdots & \ddots \end{pmatrix}$$

使用康托对角线法可以得到一个 $[0,1]$ 范围内的无穷数字序列.

很容易用反证法证明 $g$ 是一个单射,因此原命题得证.

设 $A_1, A_2, \cdots$ 为集序列，每个 $A_i \sim [0,1]$，则

$$S = \{(a_1, a_2, \cdots) \mid a_i \in A_i,\ i = 1,2,\cdots\}$$

与 $[0,1]$ 对等。

[证]:

显然

$$S = \prod^{\infty}_{i=1}A_i$$

类似教材对两个集合的证明,施归纳即可.

试说明不能定义基数的除法

[解]:

因为 $a\cdot c =c$ , $c\cdot c =c$ 这就导致 $c \div c =a$ 且 $c \div c = c$ ,商不一致.

设 $\alpha_1, \alpha_2, \beta_1, \beta_2$ 都是基数，并且 $ \alpha_1 \leq \beta_1 \quad \text{且} \quad \alpha_2 < \beta_2。 $ 举例说明，下面两式未必能从上面两式推出：

$$\alpha_1 + \alpha_2 < \beta_1 + \beta_2\\ \alpha_1\alpha_2 < \beta_1\beta_2$$

[解]:

举反例即可.

令 $\alpha_1=\beta_1=c$ , $\alpha_2 = a,\beta_2=c$

设 $A \sim [0,1]$，那么 $A$ 的所有有限子集构成的集 $A_0$ 是否与 $[0,1]$ 对等，即等式 $|A_0| = c$ 成立吗？

[解]:

成立. $(0,1)$ 的每个有限子集都对应一个二进制小数。反之，每个小数对应一个只包含该小数的 $(0,1)$ 的有限子集

证明：$a^a=c$

[证]:

即证 所有自然数的无穷序列组成的集合为连续统,这是显然的.

$c^c=?$

$[0,1]$ 上的一切实函数之集与 $R\times R$ 的幂集对等,即 $c^c=2^c$,下面进行证明.

[证]:

令: $\mathbb{F}=\{f\,| \,f:R\rightarrow R\}$

往证: $\mathbb{F} \sim 2^R\sim2^{R\times R}$

如果读者感到熟悉,那是很正常的,前面的问题:

定义在 $[0,1]$ 上的所有连续函数之集与 $[0,1]$ 对等.

是类似的.

考虑采用 Contor-Bernstein 定理,构造两个单射 $g,h$:

$$g:\mathbb{F}\rightarrow2^{R\times R}\\ h:2^R\rightarrow \mathbb{F}$$

令 $g(f)=\{(x,y)\, | \, x \in R,y=f(x)\}$ , $g$ 很显然是单射.

令 $h(A)=f,A \subseteq 2^R$ 其中

$$f(x) = \left\{\begin{matrix} 1\quad\text{if}\,x\in A \\ 0\quad\text{if}\,x\notin A \end{matrix}\right.$$

$h$ 很显然是单射.问题得证.

设 $|I| = \alpha$，$\{A_k \mid k \in I\}$ 是一个集族。如果 $\forall k \in I$，$|A_k| \leq \beta$，证明：

$$\left|\bigcup_{k \in I} A_k\right| \leq \alpha \cdot \beta$$

[证]:

构造集合

$$\bigcup_{k\in I}\left(\{k\}\times A_k\right)=\{(k,x)\, | \, k\in I ,x \in A_k\}$$

因为:

$$\forall i,j \in I,i\ne j , (\{i\}\times A_i)\cap(\{j\}\times A_j)= \empty$$

所以:

$$\left| \bigcup_{k\in I}\left(\{k\}\times A_k\right)\right|=\sum_{k\in I}\left| \{k\}\times A_k \right|=\sum_{k\in I}\left| A_k \right|\le \alpha\beta$$

因此只要证明:

$$\exist \varphi:\bigcup_{k\in I}A_k \rightarrow \bigcup_{k\in I}\left(\{k\}\times A_k\right)$$

且其为单射即可.

令 $\varphi(z)=\{(k,z)\, |\,k\in I,z\in A_k\}$

很容易证明这是单射.

此处不给出悖论、公理化集合论介绍部分习题的解答