CS70Disc 05B

1 Countability: True or False

1. 不同陈述的真伪

(a) 所有无理数的集合 $ $ 是不可数的。

判断：真。
证明： 反证法。假设无理数集合是可数的。根据第10讲，我们知道有理数集合 $ $ 是可数的。两个可数集合的并集仍然是可数的，因此如果无理数可数，那么实数集合 $ $ 也是可数的。但根据第10讲，我们知道这是不对的，得出矛盾！

(b) 整数 $ x $ 满足方程 $ 3x ( 10) $ 是可数无限的。

判断：真。
证明： 将方程两边都乘以 7（3 对 10 的乘法逆元），我们得到 $ x ( 10) $。解这个方程的整数集合为 $ S = {10k + 4 : k } $。可以看出，映射 $ k $ 到 $ 10k + 4 S $ 是双射。因此，由于整数集合 $ $ 是可数无限的，集合 $ S $ 也是可数无限的。

(c) 方程 $ x + y = 1 $ 的实数解集是可数的。

判断：假。
证明： 设 $ S $ 为方程的所有实数解。对于任意 $ x' $，有 $ (x', y') S $ 当且仅当 $ y' = 1 - x' $。因此，$ S = {(x, 1 - x) : x } $。此外，映射 $ x $ 到 $ (x, 1 - x) $ 是从 $ $ 到 $ S $ 的双射。由于 $ $ 是不可数的，所以 $ S $ 也是不可数的。

2. 函数的组合性质

对于任意两个函数 $ f: Y Z $ 和 $ g: X Y $，它们的复合函数 $ f g: X Z $ 定义为 $ (f g)(x) = f(g(x)) $ 对于所有 $ x X $。以下是对不同陈述的判断。

(d) 如果 $ f $ 和 $ g $ 是单射（即一对一），则 $ f g $ 是单射。

判断：真。
证明： 记住，函数 $ h: A B $ 是单射当且仅当 $ a_1 a_2 h(a_1) h(a_2) $ 对于所有 $ a_1, a_2 A $。令 $ x_1, x_2 X $ 为任意选择，且 $ x_1 x_2 $。由于 $ g $ 是单射，我们有 $ g(x_1) g(x_2) $。因为 $ f $ 也是单射，因此我们有 $ f(g(x_1)) f(g(x_2)) $。因此 $ f g $ 是单射。

我们想要证明的是，如果 $ f $ 和 $ g $ 都是单射（即一对一），那么它们的复合函数 $ f g $ 也是单射。

定义

单射（Injective）：一个函数 $ h: A B $ 是单射，如果对于 $ A $ 中的任意两个不同的元素 $ a_1 $ 和 $ a_2 $，都有 $ h(a_1) h(a_2) $。也就是说，$ h $ 的输出不会把不同的输入映射到相同的输出。

步骤解析

设定条件：

我们有两个函数：$ f: Y Z $ 和 $ g: X Y $。

假设 $ f $ 和 $ g $ 都是单射。

我们要证明的目标：

我们需要证明复合函数 $ f g: X Z $ 也是单射。这意味着，对于任意 $ x_1, x_2 X $ 如果 $ x_1 x_2 $，那么必须有 $ (f g)(x_1) (f g)(x_2) $。

选择任意两个不同的输入：

让 $ x_1, x_2 X $ 且 $ x_1 x_2 $（我们假设这两个输入是不同的）。

应用函数 $ g $：

由于 $ g $ 是单射，我们可以得出结论： $ g(x_1) g(x_2) $

这表示 $ g $ 会把不同的输入 $ x_1 $ 和 $ x_2 $ 映射到不同的输出。

应用函数 $ f $：

由于 $ f $ 也是单射，利用 $ g(x_1) $ 和 $ g(x_2) $ 的不同，我们可以进一步得出： $ f(g(x_1)) f(g(x_2)) $

这意味着 $ f $ 会把 $ g(x_1) $ 和 $ g(x_2) $ 这两个不同的输出也映射到不同的输出。

总结：

综上所述，从 $ x_1 x_2 $ 推导出 $ (f g)(x_1) = f(g(x_1)) $ 和 $ (f g)(x_2) = f(g(x_2)) $ 之间也有不同，因此： $ (f g)(x_1) (f g)(x_2) $

这说明复合函数 $ f g $ 是单射。

(e) 如果 $ f $ 是满射（即到达），则 $ f g $ 是满射。

判断：假。
证明： 记住，函数 $ h: A B $ 是满射当且仅当 $ b B, a A $ 使得 $ h(a) = b $。设 $ g: {0,1} {0,1} $ 为 $ g(0) = g(1) = 0 $。设 $ f: {0,1} {0,1} $ 为 $ f(0) = 0 $ 且 $ f(1) = 1 $。因此 $ f g: {0,1} {0,1} $ 的结果为 $ (f g)(0) = (f g)(1) = 0 $。在这种情况下，$ f $ 是满射，但 $ f g $ 不是满射，因为它没有到达 1。

满射（Surjective）：一个函数 $ h: A B $ 是满射，当且仅当对于 $ B $ 中的每个元素 $ b $，都存在 $ A $ 中的某个元素 $ a $，使得 $ h(a) = b $。

步骤解析

设定条件：

设 $ g: {0,1} {0,1} $ 是一个函数，我们定义 $ g $ 的输出为： $ g(0) = 0 g(1) = 0 $

这意味着，无论输入是 0 还是 1，输出总是 0。

定义满射函数 $ f $：

设 $ f: {0,1} {0,1} $ 为： $ f(0) = 0 f(1) = 1 $

在这个情况下，$ f $ 是满射，因为对于输出 0 和 1，均有对应的输入。

计算复合函数 $ f g $：

现在计算复合函数 $ f g $，其定义为：$ (f g)(x) = f(g(x)) x {0, 1} $

我们分别计算： $ (f g)(0) = f(g(0)) = f(0) = 0 $ $ (f g)(1) = f(g(1)) = f(0) = 0 $

所以复合函数的结果为： $ f g: {0, 1} {0, 1}, (f g)(0) = 0 (f g)(1) = 0 $

检查 $ f g $ 是否是满射：

现在我们检查 $ f g $ 是否是满射。对于输出 1，我们要检查是否存在输入使得 $ (f g)(x) = 1 $。

但在这种情况下，无论我们选择 $ x = 0 $ 还是 $ x = 1 $，输出总是 0。因此，$ f g $ 没有覆盖输出空间中的 1。

结论：

由于 $ f g $ 没有到达输出 1，我们得出结论 $ f g $ 不是满射。

虽然 $ f $ 是满射，但 $ g $ 映射了所有输入到同一个输出（即 0），导致 $ f g $ 无法覆盖目标空间中的所有元素。因此，即使一个函数 $ f $ 是满射，复合函数 $ f g $ 也可能不是满射。

Counting Cartesian Products

1. 笛卡尔积的定义

对于两个集合 $ A $ 和 $ B $，笛卡尔积定义为：$ A B = {(a, b) : a A, b B} $

(a) 可数集合的笛卡尔积是可数的

证明：

我们首先知道自然数集合 $ $ 是可数的，即存在一个双射（bijection）将 $ $ 映射到 $ A $ 和 $ B $ 中的元素。
由于 $ A $ 和 $ B $ 都是可数的，因此可以找到函数 $ f: A $ 和 $ g: B $。
我们可以将 $ A $ 和 $ B $ 映射为 $ $ 的子集。
通过将 $ A B $ 中的元素 $ (a, b) $ 映射到 $ $ 中的点，可以构造一个交错的遍历方法（zigzag map），例如：
- 先访问 $ (0, 0) $，然后是 $ (1, 0) $，接着是 $ (0, 1) $，再是 $ (2, 0) $，以此类推。
这样我们可以为 $ A B $ 中的每一对 $ (a, b) $ 建立一个对应的自然数，从而证明 $ A B $ 是可数的。

(b) 有限多个可数集合的笛卡尔积是可数的

证明：

我们使用归纳法证明这一结论。

基础情况：

当 $ n = 2 $ 时，我们已经在 (a) 中证明了 $ A_1 A_2 $ 是可数的，因为两个集合都是可数的。

归纳假设：

假设对于某个 $ n $，$ A_1 A_2 A_n $ 是可数的。

归纳步骤：

现在考虑 $ A_1 A_2 A_n A_{n+1} $。
根据归纳假设，$ C = A_1 A_2 A_n $ 是可数的。
由于 $ A_{n+1} $ 是可数的，并且 $ C $ 是可数的，所以根据 (a) 中的结果，$ C A_{n+1} $ 也是可数的。
因此，$ A_1 A_2 A_n A_{n+1} $ 是可数的，从而证明了对于任意有限个可数集合的笛卡尔积是可数的。

(c) 计数无限个有限集合的笛卡尔积是不可数的

证明：

假设每个集合 $ B_i $ 的大小为 2。如果其中某个集合的大小大于 2，笛卡尔积的规模会更大。
这个情况可以等价于表示无限长度的二进制字符串，已证明此类集合是不可数的。

对角线论证（Diagonalization Argument）：

假设 $ B_1 B_2 $ 是可数的，并且其元素可以列成一个列表： $ (b_{1,1}, b_{2,1}, b_{3,1}, b_{4,1}, ) $ $ (b_{1,2}, b_{2,2}, b_{3,2}, b_{4,2}, ) $ $ (b_{1,3}, b_{2,3}, b_{3,3}, b_{4,3}, ) $ 以此类推。
现在考虑元素： $ (b_{1,1}', b_{2,2}', b_{3,3}', b_{4,4}', ) $ 其中 $ b_{i,j}' $ 是 $ B_i $ 中任何与 $ b_{i,j} $ 不同的元素。
这个构造的元素 $ (b_{1,1}', b_{2,2}', b_{3,3}', b_{4,4}', ) $ 应该存在于 $ B_1 B_2 $ 中，但它并不在列出的列表中。
这就产生了矛盾，因此我们得出结论 $ B_1 B_2 $ 是不可数的。

3 Hello World!

任务描述

我们需要判断以下任务是否可计算，如果不可计算，需要提供归约或自引用证明；如果可计算，则需要写出程序。

(a) 判断程序 $ P $ 在输入 $ x $ 上是否打印“Hello World!”

判断：不可计算。
证明：
我们将通过将 TestHalt 函数归约到 PrintsHW 来证明这一点。

TestHalt 的定义： $ (P, x): $ 该程序的功能是判断程序 $ P $ 是否在输入 $ x $ 上终止。
构造程序 $ P' $：$ P'(x): $
- 运行程序 $ P(x) $，同时抑制打印语句。
- 如果 $ P $ 终止，打印“Hello World!”。
接下来，我们使用 $ PrintsHW $ 的假设：
- 如果存在程序 $ PrintsHW $，则我们可以执行以下操作：$ PrintsHW(P', x) $
- 这表明，如果 $ PrintsHW $ 存在，那么 TestHalt 也存在。
由于 TestHalt 是不可计算的（由于停机问题），因此我们得出结论 $ PrintsHW $ 也不可计算。

(b) 判断程序 $ P $ 是否在运行第 $ k $ 行之前打印“Hello World!”

判断：不可计算。
证明：
我们将从部分 (a) 的 PrintsHW 归约到 PrintsHWByK。

定义 PrintsHWByK： $ (P, x, k) $ 该程序的功能是判断程序 $ P $ 是否在执行第 $ k $ 行之前打印“Hello World!”。
使用 PrintsHW： $ (P, x): $
- 对于程序 $ P $ 的每一行 $ i $：$ PrintsHWByK(P, x, i) $
- 如果在任何行之前打印了“Hello World!”就返回 true，否则返回 false。
由于 PrintsHW 是不可计算的，因此 PrintsHWByK 也不可计算。

(c) 判断程序 $ P $ 是否在执行的前 $ k $ 步中打印“Hello World!”

判断：可计算。
证明：

我们可以简单地运行程序 $ P $ 直到执行 $ k $ 步。如果在这 $ k $ 步中打印了“Hello World!”，则返回 true；否则返回 false。

程序示例：

def prints_hello_world(P, x, k):
    for step in range(k):
        if P(x) == "Hello World!":
            return True
    return False

部分 (a) 和 (b) 是不可计算的，因为无法确定某个程序是否会在特定时刻打印特定输出，归约于停机问题。
部分 (c) 是可计算的，因为我们可以在有限步骤内直接监测输出。这表明程序的执行步骤可以被计数，而执行特定代码行的判断则与程序的逻辑相关，因此是不可计算的。