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

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

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

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

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

思考方向：

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

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

★★ 推导：三个断言分析

提示：

1. 若 \Gamma \vdash P \land Q，则 \Gamma \vdash P。

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

2. 若 \Gamma \vdash P 且 \Gamma \vdash Q，则 \Gamma \vdash P \land Q。

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

3. 若 \Gamma, P \vdash Q，则 \Gamma \vdash P \to Q。

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

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

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

提示：

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

精确写出区别：

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

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

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

★ 热身：对角化引理判断

提示：

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

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

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

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

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

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

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

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

提示：

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

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

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

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

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

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

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

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

提示：
外部论证 \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 证明……

无穷退回的结构：

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

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

★ 热身：资源推断判断

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

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

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

2. A \,\&\, B \vdash A（拥有"A 或 B 的选择权"，可以推出 A）

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

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

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

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

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

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

★★ 推导：三个推断分析

提示：

1. A \multimap B,\ A \multimap B \vdash A \multimap B（两份"A 变为 B"的能力，可以合并为一份？）

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

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

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

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

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

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

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

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

对应线性逻辑：

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

具体推断式示例：

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

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

第17章：概率作为逻辑的扩张——真值从 到 [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% 的灵敏度听起来很高。

计算：

只有约 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. 给定一个程序，判断它是否永远不输出任何内容

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

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

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

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

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

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

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

提示：

1. 归约的方向：

   • 已知 A \leq_p B 且 B \in \mathsf{P}，则 A \in \mathsf{P}（因为可以用 B 的算法加上多项式时间变换解 A）
   • 如果 A \leq_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. "给定命题 \varphi，判断 \varphi 是否是定理"在 NP 里吗？

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

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

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

3. 如果 P = NP：

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

4. 如果 P ≠ NP：

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

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

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

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

提示：

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

   • 可采纳：0 \leq h^*(n) 永远成立（低估所有代价）

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

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

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

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

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

   • 可采纳：h(n) = h^*(n)，等于真实代价

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

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

关键： 可采纳性要求 h(n) \leq h^*(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），所以最优解代价 \geq (\rho \cdot n + 1) + (n-1) \cdot 1 = \rho \cdot n + n

3. 用 \rho-近似算法：

   • 如果算法返回的回路代价 \leq \rho \cdot n：则 G 有哈密顿回路（因为无哈密顿回路时最小代价 \geq \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 \land B \to A（合取消去）

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

4. A \to A \lor 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)（阶乘的"模板"）
   Y\,F 展开：

   • Y\,F = (\lambda x.\, F\,(x\,x))\,(\lambda x.\, F\,(x\,x))
   • 令 \Omega = (\lambda x.\, F\,(x\,x))\,(\lambda x.\, F\,(x\,x))
   • \Omega = F\,(\Omega)（因为 (\lambda x.\, F\,(x\,x))\,(\lambda x.\, F\,(x\,x)) = F\,((\lambda x.\, F\,(x\,x))\,(\lambda x.\, F\,(x\,x)))）
   • 所以 Y\,F = F\,(Y\,F)，即 Y\,F 是 F 的不动点

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

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

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

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

提示：

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

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

2. 证明（程序）：

   • 类型：\prod_{n : \mathbb{N}} (S(n) \neq 0)
   • 程序：一个函数，输入自然数 n，输出 S(n) \neq 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} \leq 0，且 \dot{V} = 0 当且仅当 x = 0
   • 系统稳定，收敛到原点

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

   • V(x) = D_{\text{KL}}(x \| 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} \| A) \leq D_{\text{KL}}(x_t \| A)
   • 利用 KL 散度的凸性：D_{\text{KL}}(\lambda x + (1-\lambda) y \| A) \leq \lambda D_{\text{KL}}(x \| A) + (1-\lambda) D_{\text{KL}}(y \| A)
   • 令 \lambda = 1-\alpha，y = A，注意 D_{\text{KL}}(A \| A) = 0，即得 D_{\text{KL}}(x_{t+1} \| A) \leq (1-\alpha) D_{\text{KL}}(x_t \| A) \leq D_{\text{KL}}(x_t \| A)

2. 多吸引子的 V 设计：

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

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

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

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

• 设 F(x) = x - \nabla V(x)，其中 V(x) = D_{\text{KL}}(x \| 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}_{\geq 0} 的终结对象与初始对象：

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

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

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

提示：

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

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

2. 伴随的存在性条件：

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

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

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

提示：

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

   • 如果信念空间 \mathcal{P} 构成一个完备格（complete lattice）（例如，信念分布按某种偏序排列），且自函子 F: \mathcal{P} \to \mathcal{P} 是单调的（即 x \leq y \Rightarrow F(x) \leq 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 定理将自指、不动点与范畴论深层结构联系起来。

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

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