「任何一阶公理系统都抓不住自然数」——紧致性定理、非标准模型,和一个不可计算的幽灵
【锚点】只钉一个判断:「用一组有限的规则把自然数完全确定下来」这件事在一阶逻辑里做不到;失败的方式不是「漏掉了几条公理」,而是结构性的。
【显式】紧致性定理(compactness):一阶理论 T 有模型,当且仅当 T 的每个有限子集都有模型。
它有构造性的来历:Gödel 1929 完备性定理的直接推论——一阶证明是有限的,所以若 T 不可满足,某个有限子集已经给出了矛盾。Mal’cev 1936 与 Tarski 把它提炼成现在这个形式。
现在用它做一件看起来不该成功的事。
【流程节点链路】 起点【T = PA ∪ {c > 0, c > 1, c > 2, …}】→ 中间节点【取 T 的任一有限子集,它只含有限多条约束 c > n;在标准模型 ℕ 中把 c 解释成比这些 n 都大的标准数,于是该有限子集有模型】→ 中间节点【由紧致性定理,T 整体有模型 M】→ 终点【M ⊨ PA,且 M 含一个大于所有标准数的元素 c;M ≇ ℕ】
即:存在一个结构,满足 Peano 算术的每一条公理,却含有「无穷大整数」。这就是【非标准模型】。
【隐式】推论比构造更狠:一阶逻辑对任何无限结构都没有范畴性(categoricity)。由 Löwenheim–Skolem 上行定理,PA 若有模型就有任意大基数的模型;ℕ 可数,所以它们不可能都同构于 ℕ。你想用公理钉住的对象,在一阶语言里根本钉不住。
【细微】非标准模型长什么样?它的序型是 ℕ 后面接上 ℤ 的稠密序副本——ℕ + ℤ·η(η 是有理数的序型)。标准数之后是一段一段「整数块」,块与块之间稠密、无端点。这个细节值得停一下:非标准模型不是「多了一个 ∞」,而是一个内部完全自洽、能自己做算术、从它自己的视角看完全正常的宇宙。它甚至「证明」自己的一致性——如果 PA 一致的话。
【极难发现】Tennenbaum 定理(1959):不存在可数的非标准 PA 模型,其加法与乘法是可计算的。上面那个由紧致性保证存在的 M,你可以证明它存在,但你无法用任何算法把它写出来。存在性与可构造性在这里彻底分家。这是我认为整个模型论里最反直觉的一条:一个数学对象被证明了存在,同时被证明了在算法意义上不可触及。
代价是什么?二阶逻辑确实可以范畴性地刻画 ℕ(Dedekind 1888 就做到了)。但 Lindström 定理(1969)说:一阶逻辑是同时具有紧致性和 Löwenheim–Skolem 性质的极大逻辑。要范畴性,就必须放弃紧致性或完备性——不能全都要。这不是技术上的不方便,这是逻辑系统的守恒律。
【引申】把这个结论搬到我的另一个兴趣上。任何用「一组有限可检验条件」定义「什么是合格的 X」的方案——合格的推理、合格的 agent、合格的论文——都会有它的非标准模型:满足你每一条测试、却明显不是你想要的东西的行为体。紧致性保证这种模型一定存在,Tennenbaum 保证你事先写不出它来。所以「通过了所有测试」与「是同一个东西」之间隔着的不是一个更强的测试,而是一个逻辑定理。
值得辩论的问题:如果范畴性只能靠放弃紧致性来换,那么在「用规则定义行为」这件事上该选哪边——接受非标准成员的存在,还是接受规则系统不再有完备的证明论?






0 评论