附录：下卷思考题参考提示

兔狲教授注：这些提示不是答案，是思考的脚手架。真正的理解发生在你用自己的语言重构论证的过程中。

---

第14章：形式系统——给推理一个地基

★ 热身：合法命题公式判断

提示： 合法的命题公式由命题变元、连接词、括号按语法规则组合而成。连接词是二元或一元的运算符，不能单独出现在末尾。

思考方向：

1. $P\to Q\wedge R$：注意连接词优先级，$\wedge$ 通常比 $\to$ 结合更紧，但括号可以消除歧义
2. $\mathrm{\neg }\mathrm{\neg }P$：否定是一元连接词，可以连续应用
3. $\wedge PQ$：连接词的位置——二元连接词需要放在两个操作数之间
4. $(P\to Q)\to (\mathrm{\neg }Q\to \mathrm{\neg }P)$：括号明确优先级，这是逆否命题的形式
5. $P\to$：连接词缺少右操作数

关键点： 形式语言的语法规则是机械的，不依赖"含义"，只依赖符号排列。

---

★★ 推导：三个断言分析

提示：

1. 若 $\mathrm{\Gamma }⊢P\wedge Q$，则 $\mathrm{\Gamma }⊢P$。

   • 依赖：合取消去规则（$\wedge$-elimination）
   • 思考：从"$P$ 且 $Q$"能推出 $P$，这是系统内部的推断规则

2. 若 $\mathrm{\Gamma }⊢P$ 且 $\mathrm{\Gamma }⊢Q$，则 $\mathrm{\Gamma }⊢P\wedge Q$。

   • 依赖：合取引入规则（$\wedge$-introduction）
   • 思考：从 $P$ 和 $Q$ 能推出"$P$ 且 $Q$"，同样是系统内规则

3. 若 $\mathrm{\Gamma },P⊢Q$，则 $\mathrm{\Gamma }⊢P\to Q$。

   • 依赖：演绎定理（Deduction Theorem）
   • 思考：这是元定理，不是系统内规则。它说的是：如果在假设 $P$ 下能推出 $Q$，那么不用这个假设就能推出"$P$ 蕴含 $Q$"。这个"吸收"是在句法层面发生的，但需要元层次的论证来证明。

关键区分： 系统内规则（如 $\wedge$-elim）和元定理（如演绎定理）的区别。前者是形式系统的一部分，后者是关于形式系统的陈述。

---

★★★ 挑战：元定理与系统内定理的区别

提示：

• 系统内定理：形式系统 $\mathcal{F}$ 内部可证的命题，记作 $\mathcal{F}⊢A$
• 元定理：关于形式系统 $\mathcal{F}$ 的陈述，在元语言中证明，记作"$\mathcal{F}$ 满足性质 $X$"

精确写出区别：

1. 语言层面：系统内定理用 $\mathcal{F}$ 的语言表达；元定理用元语言（通常是自然语言加数学符号）表达
2. 证明层面：系统内定理的证明是 $\mathcal{F}$ 内的符号序列；元定理的证明是对 $\mathcal{F}$ 的结构分析（如数学归纳法）
3. 演绎定理本身：它是关于 $\mathcal{F}$ 的陈述："如果 $\mathrm{\Gamma },P⊢Q$，那么 $\mathrm{\Gamma }⊢P\to Q$"

进一步思考： 演绎定理能在 $\mathcal{F}$ 内被证明吗？不能——它需要对证明长度做归纳，这超出了 $\mathcal{F}$ 的表达能力。这与第15章"系统无法证明自身一致性"的关联：两者都说明，关于系统的某些全局性质，无法在系统内部被完全捕捉。

---

第15章：一致性与完备性——形式系统的两堵墙

★ 热身：对角化引理判断

提示：

1. $\mathsf{sub}(m,n)$ 的输入是两个自然数，输出也是一个自然数。

   • 对：$\mathsf{sub}$ 是算术函数，输入输出都是自然数

2. $\mathsf{sub}(⌜D⌝,⌜D⌝)$ 的结果，是把公式 $D$ 里的自由变量替换为公式 $D$ 本身之后的哥德尔编号。

   • 对：这是 $\mathsf{sub}$ 函数的定义

3. 哥德尔编号的具体方式（比如用质数幂乘积还是别的编码）会影响第一不完备定理的结论。

   • 错：定理的结论不依赖具体编码方式，只依赖"存在一种编码"这个事实。不同编码给出不同的哥德尔编号，但定理的结构不变。

关键点： 哥德尔编号是算术操作的具体实现，但定理的结论是结构性的，不依赖实现细节。

---

★★ 推导：加入 $G$ 作为公理

提示：

1. ${\mathcal{F}}^{\prime }=\mathcal{F}+\{G\}$ 还是一致的吗？

   • 思考：$G$ 在 $\mathcal{F}$ 中不可证，意味着 $\mathcal{F}$ 无法推出 $G$。把 $G$ 加为公理，只是增加了一个新公理，不会与 $\mathcal{F}$ 的原有定理矛盾（除非 $\mathcal{F}$ 能推出 $\mathrm{\neg }G$，但第一定理说在一致的前提下 $\mathrm{\neg }G$ 也不可证）。所以 ${\mathcal{F}}^{\prime }$ 很可能一致。

2. ${\mathcal{F}}^{\prime }$ 有自己的哥德尔句 $G^{\prime }$ 吗？$G^{\prime }$ 和 $G$ 是同一个命题吗？

   • ${\mathcal{F}}^{\prime }$ 比 $\mathcal{F}$ 更强，所以它有新的哥德尔句 $G^{\prime }$，说"我在 ${\mathcal{F}}^{\prime }$ 中不可证"。$G^{\prime }$ 不是 $G$，因为 $G$ 说的是"我在 $\mathcal{F}$ 中不可证"，而 ${\mathcal{F}}^{\prime }$ 包含了 $G$ 作为公理。

3. 把所有哥德尔句全部加入，得到的极限系统是否完备？

   • 否。极限系统 ${\mathcal{F}}_{\omega }$ 仍然足够强（能表达算术），所以它有自己的哥德尔句 $G_{\omega }$，不在 ${\mathcal{F}}_{\omega }$ 中。完备性逃不掉。

关键洞察： 哥德尔句的层级没有顶端。每当你把当前的 $G$ 加入公理，系统就变得更强，产生新的 $G^{\prime }$。

---

★★★ 挑战：外部论证的依赖链条

提示： 外部论证 $\mathcal{F}$ 一致性的典型方法：构造一个模型 $M$，使 $\mathcal{F}$ 的所有公理在 $M$ 中为真。

这个论证本身在哪个系统里进行？假设在系统 ${\mathcal{F}}_1$ 中进行。

那么 ${\mathcal{F}}_1$ 的一致性如何保证？需要另一个外部论证，在 ${\mathcal{F}}_2$ 中进行。

链条：$\mathcal{F}$ 的一致性由 ${\mathcal{F}}_1$ 证明，${\mathcal{F}}_1$ 的一致性由 ${\mathcal{F}}_2$ 证明，${\mathcal{F}}_2$ 的一致性由 ${\mathcal{F}}_3$ 证明……

无穷退回的结构：

$$\mathcal{F}\text{ 的一致性 }\leftarrow {\mathcal{F}}_1\leftarrow {\mathcal{F}}_2\leftarrow {\mathcal{F}}_3\leftarrow \cdots$$

对"数学有没有最终的基础"的意味： 没有顶端。任何声称是"最终基础"的系统，其一致性都需要外部系统担保。数学的地基不是一块被证明无误的磐石，而是一个被反复压测、至今未裂的支撑结构。

---

第16章：线性逻辑与资源——每个假设只能用一次

★ 热身：资源推断判断

提示： 用"五元钱买咖啡"的资源直觉：

1. $A\otimes B⊢A$（同时拥有 $A$ 和 $B$，可以单独推出 $A$）

   • 成立：如果你同时拥有 $A$ 和 $B$，你当然拥有 $A$。但注意：消耗 $A\otimes B$ 得到 $A$ 后，$B$ 去哪了？在线性逻辑里，$A\otimes B$ 被消耗，你得到 $A$，但 $B$ 消失了——这合理吗？实际上，从 $A\otimes B$ 推出 $A$ 需要丢弃 $B$，这对应弱化规则，在线性逻辑里需要显式操作。

2. $A\mathrm{\&}B⊢A$（拥有"$A$ 或 $B$ 的选择权"，可以推出 $A$）

   • 成立：$\mathrm{\&}$ 表示选择权，你可以选择 $A$。但只能选一个，选了 $A$ 就不能同时选 $B$。

3. $!A⊢A$（无限可用的 $A$，可以取出一份 $A$）

   • 成立：$!A$ 是无限资源，当然可以取出一份。

4. $A⊢!A$（一份 $A$，可以变成无限可用的 $A$）

   • 不成立：这是收缩规则，在线性逻辑里被拿掉了。一份资源不能自动变成无限份。

关键区分： $\otimes$（同时拥有）和 $\mathrm{\&}$（可以选择）在资源意义上是不同的。

---

★★ 推导：三个推断分析

提示：

1. $A⊸B,A⊸B⊢A⊸B$（两份"$A$ 变为 $B$"的能力，可以合并为一份？）

   • 思考：线性逻辑里，两份 $A⊸B$ 意味着你可以用 $A$ 换 $B$ 两次。但 $A⊸B$ 本身不是资源，是转换规则。这个推断涉及收缩——两份相同的规则能否合并？在线性逻辑里，规则本身不是资源，所以这个推断可能成立，但需要仔细分析。

2. $!(A⊸B),!A⊢!B$（无限可用的转换规则，加上无限可用的输入，可以产生无限可用的输出？）

   • 思考：$!(A⊸B)$ 是无限可用的转换规则，$!A$ 是无限可用的输入。每次应用规则消耗一份 $A$ 产生一份 $B$，但 $!(A⊸B)$ 和 $!A$ 都是无限的，所以可以产生无限份 $B$，即 $!B$。这对应感叹号的推广规则。

3. $A\otimes B⊸C⊢A⊸(B⊸C)$（消耗 $A$ 和 $B$ 产生 $C$，等价于先消耗 $A$、再消耗 $B$ 产生 $C$？）

   • 思考：这是线性逻辑版本的柯里化。在资源意义上：左边是"同时给 $A$ 和 $B$，得到 $C$"；右边是"先给 $A$，得到一个函数，再给 $B$，得到 $C$"。两者在资源消耗上是等价的：都是消耗 $A$ 和 $B$ 各一份，产生 $C$。所以成立。

---

★★★ 挑战：Rust所有权对应

提示： Rust 所有权系统的核心概念：

• 移动语义：所有权转移，原变量失效
• 不可变借用：只读引用，不消耗所有权
• 可变借用：读写引用，消耗独占访问权

对应线性逻辑：

• 移动变量 x 给函数 f：$x⊸\text{返回值}$（消耗 $x$，产生返回值）
• 不可变借用 &x 传给函数 g：$!x⊸\text{返回值}$（$!x$ 表示 $x$ 的只读视图，可多次使用）
• 函数返回值：$\text{输入}⊸\text{输出}$（消耗输入，产生输出）

具体推断式示例：

• let y = f(x); 对应 $x⊸y$
• let z = g(&x); 对应 $!x⊸z$
• fn add(a: i32, b: i32) -> i32 对应 $a\otimes b⊸\text{结果}$

对应不上的地方： Rust 的生命周期检查、借用检查器的具体规则，比线性逻辑更复杂（涉及作用域、引用有效期等）。

---

第17章：概率作为逻辑的扩张——真值从 {0,1} 到 [0,1]

★ 热身：医学检测计算

提示： 已知：

• 灵敏度 $P(\text{阳性}\mid \text{患病})=0.9$
• 特异度 $P(\text{阴性}\mid \text{健康})=0.95$，所以 $P(\text{阳性}\mid \text{健康})=0.05$
• 患病率 $P(\text{患病})=0.01$，$P(\text{健康})=0.99$

直觉估计： 很多人会高估，因为 90% 的灵敏度听起来很高。

计算：

$$P(\text{患病}\mid \text{阳性})=\frac{0.9\times 0.01}{0.9\times 0.01+0.05\times 0.99}=\frac{0.009}{0.009+0.0495}=\frac{0.009}{0.0585}\approx 0.154$$

只有约 15.4%！即使检测阳性，实际患病概率仍不高，因为患病率很低。

贝叶斯更新的教训： 先验（患病率）对后验的影响巨大。

---

★★ 推导：两次检测与高风险群体

提示：

1. 第一次检测阳性后，后验概率 $P(\text{患病}\mid {\text{阳性}}_1)\approx 0.154$ 以这个为新的先验，第二次独立检测仍阳性：

   $$P(\text{患病}\mid {\text{阳性}}_1,{\text{阳性}}_2)=\frac{0.9\times 0.154}{0.9\times 0.154+0.05\times (1-0.154)}\approx 0.77$$

2. 高风险群体患病率 10%：

   $$P(\text{患病}\mid \text{阳性})=\frac{0.9\times 0.1}{0.9\times 0.1+0.05\times 0.9}=\frac{0.09}{0.09+0.045}=\frac{0.09}{0.135}\approx 0.667$$

3. 比较：

   • 两次阳性（低风险）：约 77%
   • 一次阳性（高风险）：约 67%

   两次阳性在低风险群体中，比一次阳性在高风险群体中，给出更高的患病概率。

说明： 证据（检测结果）的强度，需要结合先验（患病率）一起评估。多次独立证据可以强烈改变先验。

---

★★★ 挑战：Cox定理前提质疑

提示： Cox 定理第一条前提：信念可用实数线性序表示。

可能的反例场景：

1. 区间信念：对命题 $A$ 的信念不是单个值 $p$，而是一个区间 $[p_{min},p_{max}]$，表示"至少 $p_{min}$，至多 $p_{max}$"。
2. 不可比信念：对某些命题 $A$ 和 $B$，无法比较相信程度——既不是 $A$ 更可信，也不是 $B$ 更可信，也不是一样可信。
3. 语境依赖信念：对 $A$ 的信念依赖其他命题的真值，无法用单个实数捕捉。

两种可能性：

• Cox 定理前提不够普遍：确实存在合理的信念形式不满足实数线性序
• 这只是"信念的精确化"不适用：也许在这些场景下，用实数表达信念本身就不合适

关键问题： 如果我们放弃实数表示，还能建立一致的推断规则吗？Cox 定理的价值在于：它告诉我们，如果你要用实数表达信念，那么必须用概率。

---

第18章：因果结构的形式化——三层阶梯与 do-calculus

★ 热身：因果阶梯分类

提示：

1. "吸烟者的肺癌发生率比不吸烟者高多少？"

   • 关联层：比较两组观测到的发生率，$P(\text{肺癌}\mid \text{吸烟})$ vs $P(\text{肺癌}\mid \text{不吸烟})$

2. "如果强制推行禁烟令，肺癌发生率会下降多少？"

   • 干预层：问的是 $\mathsf{do}(\text{禁烟令})$ 的效果，$P(\text{肺癌}\mid \mathsf{do}(\text{禁烟令}))$

3. "这位肺癌患者如果当年没有吸烟，他现在会患癌吗？"

   • 反事实层：对特定个体，在另一个可能世界里的结果

4. "在检测到高血压的人群中，使用降压药的比例是多少？"

   • 关联层：条件概率 $P(\text{用药}\mid \text{高血压})$

5. "给这名高血压患者开降压药，他未来10年的心血管事件风险会减少多少？"

   • 干预层：个体处理效应，但用 $\mathsf{do}$ 算子表达：$P(\text{事件}\mid \mathsf{do}(\text{用药}))-P(\text{事件}\mid \mathsf{do}(\text{不用药}))$

关键： 区分"看到"（条件化）和"设置"（干预）。

---

★★ 推导：$Z\to X\to Y$ 图分析

提示： 图：$Z\to X\to Y$，且 $Z\to Y$

1. 从 $X$ 到 $Y$ 的路径：

   • 因果路径：$X\to Y$（直接效应）
   • 后门路径：$X\leftarrow Z\to Y$（通过共同原因 $Z$）

2. 调整公式： $Z$ 满足后门准则（$Z$ 不是 $X$ 的后代，且阻断了后门路径）：

   $$P(Y\mid \mathsf{do}(X=x))=\sum _{z}P(Y\mid X=x,Z=z)P(Z=z)$$

3. 如果 $Z$ 不可观测：

   • 调整公式无法使用（需要知道 $P(Z=z)$）
   • $P(Y\mid \mathsf{do}(X=x))$ 不可识别——无法从观测数据计算
   • 需要其他方法（如工具变量、前门准则等）

关键： 可识别性依赖是否有可观测的变量阻断所有后门路径。

---

★★★ 挑战：直接效应与间接效应

提示： 图：$Z\to X\to Y$，加入 $M$：$X\to M\to Y$，同时保留 $X\to Y$ 的直接路径。

直接效应：$X$ 对 $Y$ 不经过 $M$ 的部分。 间接效应：$X$ 对 $Y$ 经过 $M$ 的部分。

用 $\mathsf{do}$ 算子定义：

• 受控直接效应（CDE）：固定 $M=m$ 时，$X$ 对 $Y$ 的效应

  $$CDE(m)=P(Y\mid \mathsf{do}(X=1),\mathsf{do}(M=m))-P(Y\mid \mathsf{do}(X=0),\mathsf{do}(M=m))$$

  这是干预层（同时干预 $X$ 和 $M$）

• 自然直接效应（NDE）：让 $M$ 保持其在 $X=0$ 时的自然值，改变 $X$

  $$NDE=P(Y_{X=1,M_{X=0}})-P(Y_{X=0})$$

  这是反事实层（涉及 $M_{X=0}$，即"如果 $X=0$ 时 $M$ 的值"）

• 自然间接效应（NIE）：固定 $X=1$，比较 $M$ 在 $X=1$ 和 $X=0$ 时的值对 $Y$ 的影响

  $$NIE=P(Y_{X=1,M_{X=1}})-P(Y_{X=1,M_{X=0}})$$

  这也是反事实层

关键洞察： 间接效应的定义必须诉诸反事实，因为它涉及"保持 $X$ 不变，只让 $M$ 变化"——这在实际中无法操作，只能在反事实层面定义。

---

第19章：复杂度作为推理的几何——为什么有些推理根本不能被加速

★ 热身：问题分类

提示：

1. 给定一个有序整数数组和一个目标值，判断目标值是否在数组里（二分搜索）

   • P：二分搜索是 $O(\log n)$

2. 给定一个布尔公式，判断它是否可满足（SAT）

   • NP（NP完全）：验证一个赋值是多项式的，但找到赋值未知是否多项式

3. 给定一个程序，判断它是否永远不输出任何内容

   • 不可判定：这是停机问题的变体（程序永不输出 $\iff$ 程序永不停机）

4. 给定一个图，判断它是否存在哈密顿回路

   • NP（NP完全）：哈密顿回路问题是 NP 完全的

5. 给定两个程序，判断它们对所有输入是否产生相同的输出

   • 不可判定：等价性问题不可判定（停机问题的推论）

关键： P ⊆ NP ⊆ 可判定 ⊂ 全部问题

---

★★ 推导：归约方向与停机变体

提示：

1. 归约的方向：

   • 已知 $A{\le }_{p}B$ 且 $B\in \mathsf{P}$，则 $A\in \mathsf{P}$（因为可以用 $B$ 的算法加上多项式时间变换解 $A$）
   • 如果 $A{\le }_{p}B$ 且 $A$ 是 NP 完全的：
     • 若 $B\in \mathsf{NP}$，则 $B$ 也是 NP 完全的（因为所有 NP 问题可归约到 $A$，再归约到 $B$）
     • 若 $B\notin \mathsf{NP}$，则 $B$ 至少和 NP 完全问题一样难，可能更难

2. 停机问题的变体：

   • 给定程序 $P$ 和输入 $I$，$P$ 在 $I$ 上是否在 ${10}^{100}$ 步内停机？
     • 可判定：模拟 ${10}^{100}$ 步，看是否停机。步数有界，所以可判定。
   • 给定程序 $P$，$P$ 是否对所有输入都停机？
     • 不可判定：这是全域停机问题，比普通停机问题更难。
   • 给定程序 $P$，$P$ 是否对某个输入停机？
     • 不可判定：这是存在性停机问题，也不可判定。

关键： 步数有界的问题通常可判定；涉及"所有输入"或"某个输入"的量词使问题更难。

---

★★★ 挑战：P=NP 对数学证明的意义

提示：

1. "给定命题 $\phi$，判断 $\phi$ 是否是定理"在 NP 里吗？

   • 证书：一个证明序列
   • 验证：检查证明序列的每一步是否合法（多项式时间）
   • 所以在 NP 里

2. SAT 和"是定理"的关系：

   • 在命题逻辑里，$\phi$ 是定理 $\iff$ $\mathrm{\neg }\phi$ 不可满足
   • 所以"$\phi$ 是定理"和"$\mathrm{\neg }\phi$ 不可满足"是同一个问题
   • 而"$\mathrm{\neg }\phi$ 不可满足"是 co-SAT（SAT 的补问题）

3. 如果 P = NP：

   • 那么 co-SAT 也在 P 里（因为 P 对补封闭）
   • 所以"$\phi$ 是定理"可以在多项式时间内判定
   • 意味着：数学定理的发现可以自动化——给定一个命题，机器可以在多项式时间内判断它是否有证明（但注意：这不等同于找到证明，只是判断存在性）

4. 如果 P ≠ NP：

   • 某些数学定理即使有证明，也可能原则上找不到（因为找到证明可能需要指数时间）
   • 区分"证明存在但找不到"和"证明不存在"：
     • 前者是计算困难：证明存在，但所有算法都需要超多项式时间
     • 后者是逻辑不可证：证明不存在（如哥德尔句）

关键： P=NP 问的是"判断存在性"的复杂度，不是"构造证明"的复杂度。即使 P=NP，构造证明可能仍然困难。

---

第20章：启发式的形式合同——"差不多对"的精确数学定义

★ 热身：A*启发函数可采纳性

提示：

1. $h(n)=0$（零启发）

   • 可采纳：$0\le h^{\ast }(n)$ 永远成立（低估所有代价）

2. $h(n)=$ 从 $n$ 到目标的直线距离（欧几里得距离）

   • 可采纳（在欧几里得空间中）：直线距离是两点间最短距离，所以 $h(n)\le h^{\ast }(n)$

3. $h(n)=$ 从 $n$ 到目标的直线距离 $\times 2$

   • 不可采纳：可能高估（如果实际路径接近直线，$2\times \text{直线距离}>\text{实际距离}$）

4. $h(n)=$ 从 $n$ 到目标的实际最短路径长度（假设已知）

   • 可采纳：$h(n)=h^{\ast }(n)$，等于真实代价

5. $h(n)=$ 从 $n$ 到目标沿曼哈顿距离（仅允许上下左右移动时）

   • 可采纳：在网格世界中，曼哈顿距离是实际距离的下界

关键： 可采纳性要求 $h(n)\le h^{\ast }(n)$（永远不高估）。

---

★★ 推导：可采纳性代价与 PAC 比较

提示：

1. 可采纳性的代价示例： 构造一个图：起点 $S$，目标 $G$，中间节点 $A,B$。

   • 路径1：$S\to A\to G$，代价 10
   • 路径2：$S\to B\to G$，代价 12

   设 $h_1(A)=5,h_1(B)=5$（可采纳，都小于真实代价 10 和 12） 设 $h_2(A)=5,h_2(B)=15$（不可采纳，$h_2(B)$ 高估）

   A* 展开顺序：

   • 用 $h_1$：可能先展开 $A$，再展开 $B$，最后找到最优路径 $S\to A\to G$
   • 用 $h_2$：$f(B)=g(B)+h_2(B)=1+15=16$，$f(A)=1+5=6$，先展开 $A$，找到路径 $S\to A\to G$（代价10），$B$ 不会被展开（因为 $f(B)=16>10$）

   说明：不可采纳的 $h_2$ 用更少节点找到了同一个解，但不保证总是找到最优解。

2. PAC 与贝叶斯比较：

   • PAC：对最坏分布的保证，不需要先验
   • 贝叶斯：对给定先验的保证，依赖先验正确性

   假设更少：PAC 对假设更少（不假设先验）

   先验完全错误时：贝叶斯会崩溃（后验被错误先验带偏）；PAC 仍然保证以高概率近似正确（对最坏分布）

关键： 可采纳性保证最优性但可能低效；PAC 是最坏情况保证，不依赖先验。

---

★★★ 挑战：TSP 不可近似性归约思路

提示：目标：证明如果存在 TSP 的 $\rho$-近似算法，就能解决哈密顿回路问题（NP完全）。

归约思路：

1. 给定一个图 $G$（哈密顿回路问题的实例），构造一个 TSP 实例：

   • 城市 = $G$ 的顶点
   • 距离：如果 $(u,v)$ 是 $G$ 中的边，则 $d(u,v)=1$；否则 $d(u,v)=\rho \cdot n+1$（其中 $n$ 是顶点数）

2. 分析：

   • 如果 $G$ 有哈密顿回路：则 TSP 的最优解代价 = $n$（每条边代价1）
   • 如果 $G$ 没有哈密顿回路：则 TSP 的任何回路至少包含一条"长边"（代价 $\rho \cdot n+1$），所以最优解代价 $\ge (\rho \cdot n+1)+(n-1)\cdot 1=\rho \cdot n+n$

3. 用 $\rho$-近似算法：

   • 如果算法返回的回路代价 $\le \rho \cdot n$：则 $G$ 有哈密顿回路（因为无哈密顿回路时最小代价 $\ge \rho \cdot n+n>\rho \cdot n$）
   • 如果算法返回的回路代价 $>\rho \cdot n$：则 $G$ 无哈密顿回路

4. 因此：$\rho$-近似算法可以判断哈密顿回路是否存在。

关键洞察：通过设置距离，使得"有哈密顿回路"和"无哈密顿回路"两种情况的最优解差距超过 $\rho$ 倍，这样近似算法就无法模糊这个差距。

---

第21章：学习作为逆推断——泛化是压缩的另一种说法

★ 热身：Kolmogorov 复杂度比较

提示：

1. 0101010101010101010101010101010101010101（40个字符，01交替）

   • Kolmogorov 复杂度低：可以用短程序描述，如"输出'01'重复20次"

2. 1101001000011010110101010001010001000010（40个随机字符）

   • Kolmogorov 复杂度高：没有明显规律，需要几乎原样存储

3. 一个"完全随机"的字符串：

   • 它的 Kolmogorov 复杂度大约等于字符串本身的长度
   • 因为最短的描述就是字符串本身

关键： Kolmogorov 复杂度衡量的是"描述难度"，不是字符串长度。

---

★★ 推导：压缩与泛化、归纳偏置显化

提示：

1. 压缩与泛化：

   • 过拟合模型：描述长度 ≈ 训练数据本身长度（记忆数据）
     • $L(h)$ 可能小，但 $L(\text{数据}\mid h)$ 大（因为模型不能完美拟合数据，需要记录残差）
     • 或者 $L(h)$ 大（复杂模型），$L(\text{数据}\mid h)$ 小（完美拟合）
   • 泛化良好模型：总描述长度 $L(h)+L(\text{数据}\mid h)$ 小
     • $L(h)$ 适中（不太复杂），$L(\text{数据}\mid h)$ 小（捕捉了规律）

2. 归纳偏置显化：

   • 线性回归：偏向"规律是线性的"；在非线性数据上失败
   • 决策树：偏向"规律是轴对齐的分段常数"；在需要平滑决策边界的数据上失败
   • 神经网络（带L2正则化）：偏向"规律是平滑函数，参数值小"；在需要非平滑变化或极端参数值的数据上失败

关键： 每种算法隐含地承诺了"世界是什么样的"。

---

★★★ 挑战：MDL 可计算近似方案

提示：两种可计算的"描述长度"近似方案：

1. 基于特定编码方案的 MDL：

   • 用固定编码方案（如 Huffman 编码、算术编码）计算 $L(h)$ 和 $L(\text{数据}\mid h)$
   • 隐含偏置：编码方案本身的选择就是偏置（如，偏好被该编码压缩得好的假设）

2. 贝叶斯信息准则（BIC）：

   • $BIC=-2\ln L+k\ln n$，其中 $L$ 是似然，$k$ 是参数个数，$n$ 是样本量
   • 隐含偏置：假设参数是连续值，且先验是正态分布

不同近似方案何时给出不同"最优假设"：

• 当两个假设在一种编码下长度相近，在另一种编码下差异大时
• 当假设空间包含不同"类型"的假设（如决策树 vs 线性模型），不同编码方案对不同类型友好度不同

对机器学习"客观性"的看法： 没有"无偏"的学习算法——选择算法就是选择归纳偏置。所谓的"客观性"只是把主观选择藏进了工具选择里。

---

第22章：自指与涌现——当推理系统开始推理关于自身

★ 热身：Curry-Howard 对应

提示：

1. $A\to A$（同一律）

   • 类型：$A\to A$
   • 程序：$\lambda x:A.x$（恒等函数）

2. $A\to (B\to A)$（弱化）

   • 类型：$A\to (B\to A)$
   • 程序：$\lambda x:A.\lambda y:B.x$（忽略第二个参数，返回第一个）

3. $A\wedge B\to A$（合取消去）

   • 类型：$A\times B\to A$
   • 程序：$\lambda p:A\times B.\text{fst}(p)$（取第一分量）

4. $A\to A\vee B$（析取引入）

   • 类型：$A\to A+B$
   • 程序：$\lambda x:A.\text{inl}(x)$（左注入）

验证 $A\to A$： 程序 $\lambda x:A.x$ 的类型是 $A\to A$，它接受一个 $A$ 类型的输入，返回同一个值。这正好对应"从 $A$ 推出 $A$"的证明。

---

★★ 推导：不动点展开与哥德尔句对比

提示：

1. 不动点展开： 设 $F=\lambda f.\lambda n.\text{if }n=0\text{ then }1\text{ else }n\times f(n-1)$（阶乘的"模板"） $YF$ 展开：

   • $YF=(\lambda x.F(xx))(\lambda x.F(xx))$
   • 令 $\mathrm{\Omega }=(\lambda x.F(xx))(\lambda x.F(xx))$
   • $\mathrm{\Omega }=F(\mathrm{\Omega })$（因为 $(\lambda x.F(xx))(\lambda x.F(xx))=F((\lambda x.F(xx))(\lambda x.F(xx)))$）
   • 所以 $YF=F(YF)$，即 $YF$ 是 $F$ 的不动点

2. 哥德尔句与 Y 组合子的对比：

   • 自指机制：
     • 哥德尔句：通过对角化引理，构造 $G\equiv \mathrm{\neg }\mathsf{Prov}(⌜G⌝)$
     • Y 组合子：通过自应用，构造 $Yf=f(Yf)$
   • 自指后果：
     • 哥德尔句：导致不可判定性（在一致系统中既不可证也不可驳）
     • Y 组合子：导致递归/无限循环（计算不动点）
   • 解决方式：
     • 哥德尔句：无法在系统内"解决"，只能接受不完备性
     • Y 组合子：在计算中展开，可能终止（如果函数有不动点）

关键： 两者都是自指构造，但一个在逻辑层面导致边界，一个在计算层面实现递归。

---

★★★ 挑战：依赖类型命题对应

提示：

1. 命题："对所有自然数 $n$，$n$ 的后继不等于 $0$"，即 $\mathrm{\forall }n\in \mathbb{N}.S(n)\ne 0$

   • 依赖类型对应：$\mathrm{\Pi }$-类型 $\prod _{n:\mathbb{N}}(S(n)\ne 0)$
   • 读作：对每个 $n:\mathbb{N}$，有一个 $S(n)\ne 0$ 的证明

2. 证明（程序）：

   • 类型：$\prod _{n:\mathbb{N}}(S(n)\ne 0)$
   • 程序：一个函数，输入自然数 $n$，输出 $S(n)\ne 0$ 的证明
   • 具体实现依赖皮亚诺公理（特别是"$0$ 不是任何自然数的后继"）

3. 类型检查的可判定性：

   • 简单类型系统：类型检查可判定（多项式时间）
   • 依赖类型系统：类型检查变得更难
     • 有些依赖类型系统（如 Martin-Löf 类型论）的类型检查是不可判定的
     • 因为要检查 $\prod _{n:\mathbb{N}}P(n)$ 类型的项，需要验证它对所有 $n$ 都成立——这等价于验证一个全称命题
   • 实践中的妥协：限制依赖类型的表达能力，使类型检查可判定（如 Coq、Agda 的做法）

最后的问题： 精确的形式工具，在边界处，开始触碰那些超出形式化射程的问题。在那个边界上，逻辑和直觉、证明和猜想、形式和意义，以一种我们尚未完全理解的方式彼此纠缠。

这正是《推理王国》全书试图捕捉的张力：推理既有精确的骨架，又有模糊的血肉。骨架可以被形式化，血肉只能被体验。

---

第23章：永霖-李雅普诺夫联立——推理系统的稳定性与收敛边界

★ 热身：李雅普诺夫函数判断与永霖先验

提示：

1. 李雅普诺夫函数 $V(x)=x^2$ 对系统 $\dot{x}=-x$：

   • 计算 $\dot{V}=\frac{dV}{dt}=\frac{\partial V}{\partial x}\dot{x}=2x\cdot (-x)=-2x^2$
   • $\dot{V}\le 0$，且 $\dot{V}=0$ 当且仅当 $x=0$
   • 系统稳定，收敛到原点

2. 训练数据完全平衡时，先验锚点 $A$ 是均匀分布（如二分类时 $A=0.5$）：

   • $V(x)=D_{\text{KL}}(x\parallel A)=x\ln \frac{x}{A}+(1-x)\ln \frac{1-x}{1-A}$，其中 $A=0.5$
   • 当 $A=0.5$ 时，$V(x)$ 简化为 $x\ln (2x)+(1-x)\ln (2(1-x))$，这是一个对称函数，在 $x=0.5$ 时最小

关键点： 李雅普诺夫函数的验证是直接的微分计算；平衡数据下先验锚点是无偏的均匀分布。

---

★★ 推导：离散时间 KL 散度递减与多吸引子难题

提示：

1. 离散时间李雅普诺夫：

   • 已知 $x_{t+1}=(1-\alpha )x_t+\alpha A$
   • 要证 $D_{\text{KL}}(x_{t+1}\parallel A)\le D_{\text{KL}}(x_t\parallel A)$
   • 利用 KL 散度的凸性：$D_{\text{KL}}(\lambda x+(1-\lambda )y\parallel A)\le \lambda D_{\text{KL}}(x\parallel A)+(1-\lambda )D_{\text{KL}}(y\parallel A)$
   • 令 $\lambda =1-\alpha$，$y=A$，注意 $D_{\text{KL}}(A\parallel A)=0$，即得 $D_{\text{KL}}(x_{t+1}\parallel A)\le (1-\alpha )D_{\text{KL}}(x_t\parallel A)\le D_{\text{KL}}(x_t\parallel A)$

2. 多吸引子的 $V$ 设计：

   • $V(x)=min(D_{\text{KL}}(x\parallel A_1),D_{\text{KL}}(x\parallel A_2))$ 在 $A_1$ 和 $A_2$ 处为零，其他处为正
   • 问题：$min$ 函数不可微，难以验证 $V(F(x))\le V(x)$（需要全局比较）
   • 更深的困难：如果系统轨道可能被两个吸引子“拉扯”，$V$ 可能不单调递减（系统可能在两个吸引子间振荡，$V$ 值跳变）

关键洞察： 线性插值更新保证 KL 散度递减；多吸引子系统破坏了传统李雅普诺夫函数的简单构造。

---

★★★ 挑战：动力系统的自指与不完备性

提示：动力系统的自指构造： 定义函数 $F$ 使其吸引子满足方程 $A=G(F,A)$，其中 $G$ 是一个涉及 $F$ 本身的函数。例如：

• 设 $F(x)=x-\mathrm{\nabla }V(x)$，其中 $V(x)=D_{\text{KL}}(x\parallel A)$，但 $A$ 又定义为 $F$ 的不动点
• 这形成一个自指循环：$A$ 是 $F$ 的不动点，$F$ 的定义又依赖 $A$

会不会导致不完备性？

• 在逻辑中，自指导致“真”无法在系统内定义（塔斯基不可定义定理）
• 在动力系统中，自指可能使“稳定性”无法从系统内部判定
• 具体例子：考虑 $F$ 的定义包含“如果系统稳定，则吸引子为 $A_1$；否则为 $A_2$”。要判断吸引子是 $A_1$ 还是 $A_2$，需要先判断系统是否稳定——这可能导致循环

动力系统的不完备性猜想： 某些系统的稳定性、吸引子位置等性质，无法从系统自身的微分方程中判定，需要一个外部视角（如数值模拟、外部观测）。这与哥德尔不完备类似：系统内部无法证明自身的某些真命题（如一致性）。

与第23章主题的联系： 永霖-李雅普诺夫联立试图从观测（外部）推导能量函数，再用于内部稳定性分析。如果系统本身有自指结构，这个“外部推导”可能也无法完全确定系统的行为——观测本身可能干扰系统，或观测的有限性导致不确定性。

最后的问题： 动力系统的不完备性，如果存在，会如何改变我们对“理解一个系统”的期望？我们是否必须接受，某些系统的长期行为，即使原则上由微分方程完全确定，也无法被任何有限观测或推理完全预测？

---

第24章：范畴论眼中的推理收敛——链表、指针与伴随函子

★ 热身：链表2-环与偏序集范畴

提示：

1. 链表2-环的范畴论对应：

   • 如果 0xAAAA 指向 0xBBBB，0xBBBB 指向 0xAAAA，形成2-环，这在范畴论中对应两个对象之间的同构（isomorphism）——存在可逆的态射对。
   • 系统不会收敛到单一不动点，而是在两个状态之间振荡，形成一个极限环（limit cycle）。收敛到不动点的条件被打破，因为自函子 $F$ 的迭代会在两个对象之间交替。

2. 偏序集范畴 ${\mathbb{R}}_{\ge 0}$ 的终结对象与初始对象：

   • 终结对象：$0$。因为对于任意 $a\in {\mathbb{R}}_{\ge 0}$，存在唯一态射 $a\to 0$ 当且仅当 $a\ge 0$（总是成立），且态射的唯一性由偏序范畴的性质保证（任意两对象间至多一个态射）。
   • 初始对象：${\mathbb{R}}_{\ge 0}$ 中没有初始对象。因为初始对象 $I$ 需要对于任意 $b$ 存在唯一态射 $I\to b$，即 $I\ge b$ 对所有 $b$ 成立，这要求 $I$ 是最大元，但 ${\mathbb{R}}_{\ge 0}$ 无最大元（除非引入 $\mathrm{\infty }$）。

关键点： 环状结构破坏收敛性；偏序范畴的终结对象是最小元，初始对象不一定存在。

---

★★ 推导：函子保持极限与伴随的存在性

提示：

1. 函子保持极限（终结对象）：

   • 李雅普诺夫函子 $V:\mathcal{P}\to {\mathbb{R}}_{\ge 0}$ 把 $\mathcal{P}$ 的终结对象 $A$ 映射为 ${\mathbb{R}}_{\ge 0}$ 的终结对象 $0$，这是必然的，因为 $V$ 的具体构造（KL散度）满足 $V(A)=D_{\text{KL}}(A\parallel A)=0$。
   • 如果 $V$ 是任意函子（不一定用 KL 散度），则不一定保持终结对象。例如，定义 $V(x)=\text{常数}$，则 $V(A)$ 可能不是 $0$。保持终结对象需要函子满足额外的条件（如反射极限）。

2. 伴随的存在性条件：

   • 要构造伴随函子 $L⊣R$ 连接 $\mathcal{P}$（内部信念范畴）和 $\mathcal{R}$（外部真实世界范畴），需要满足单位元（unit） 和余单位元（counit） 的条件：
     • 单位元 $\eta :{\text{id}}_{\mathcal{P}}\to R\circ L$
     • 余单位元 $\epsilon :L\circ R\to {\text{id}}_{\mathcal{R}}$
   • 如果 $\mathcal{R}$ 是“真实世界”范畴，其对象可以是物理状态或事实，态射可以是物理过程或逻辑蕴含。哲学困难在于：
     • 真实世界的“对象”和“态射”如何形式化？（观察者依赖？）
     • 真实世界范畴可能不是小范畴，甚至不是良定义的集合。
     • 伴随的存在相当于要求内部信念与外部真实之间存在一种“最优翻译”，这本身就是一个强假设。

关键洞察： 保持终结对象依赖函子的具体构造；伴随函子的存在性涉及内部与外部范畴的深刻对齐。

---

★★★ 挑战：自函子不动点定理与范畴论版哥德尔

提示：

1. 自函子的不动点定理（Knaster-Tarski）：

   • 如果信念空间 $\mathcal{P}$ 构成一个完备格（complete lattice）（例如，信念分布按某种偏序排列），且自函子 $F:\mathcal{P}\to \mathcal{P}$ 是单调的（即 $x\le y\Rightarrow F(x)\le F(y)$），则 Knaster-Tarski 定理保证 $F$ 有不动点，且全体不动点也构成一个完备格。
   • 永霖公式可以看作这个定理的特例：$A$ 是 $F$ 的最小不动点（或某个不动点）。收敛到 $A$ 是由 $F$ 的单调性与空间的完备性保证的。

2. 范畴论版哥德尔（Lawvere不动点定理）：

   • Lawvere 定理：若范畴 $\mathcal{C}$ 有终结对象 $1$ 且每个对象 $A$ 有指数对象 $B^A$，则每个态射 $f:B\to B$ 有不动点。
   • 与永霖公式的联系：将 $B$ 视为信念空间 $\mathcal{P}$，$f$ 视为自函子 $F$ 的“底层态射”。如果 $\mathcal{P}$ 满足定理条件（笛卡尔闭范畴），则 $F$ 必有不动点。这从更高层面解释了为什么收敛到不动点是结构性必然。
   • 但注意：信念空间 $\mathcal{P}$ 可能不是笛卡尔闭的，因此 Lawvere 定理不一定直接适用。然而，该定理揭示了自指与不动点之间的普遍联系，与哥德尔不完备、永霖收敛共享同一抽象结构。

关键点： 不动点定理提供了收敛的结构性保证；Lawvere 定理将自指、不动点与范畴论深层结构联系起来。

---

后记：兔狲教授的最后一句话

这本书写完了，但问题没有完。推理的边界不是终点，是起点。知道哪里不能去，才知道哪里还能去。就这样。