如何从哥德尔完备性定理推导一阶逻辑的紧致性定理？紧致性又怎样用来构造皮亚诺算术的非标准模型？
How does one derive the compactness theorem of first-order logic from Gödel's completeness theorem, and how does compactness produce a nonstandard model of Peano arithmetic?
完备性定理断言 Γ⊨φ 当且仅当 Γ⊢φ，而形式证明只动用 Γ 中有限多条前提；于是若 Γ 的每个有限子集皆可满足而 Γ 本身不可满足，便有一条无前提不足的无效推理获得了证明，矛盾，故 Γ 可满足——此即紧致性。向 PA 添加无穷多语句 c>0, c>1, c>S(1), …（c 为新常元），其任一有限子集都可把 c 解释成足够大的自然数而满足，紧致性保证整体有模型，其中 c 的解释必然落在所有标准自然数之外。
The completeness theorem states that Γ entails φ if and only if φ is provable from Γ, and a formal proof consumes only finitely many premises of Γ; hence if every finite subset of Γ were satisfiable while Γ itself were unsatisfiable, an invalid entailment would have a proof—a contradiction—so Γ is satisfiable, which is precisely compactness. Adjoin to PA infinitely many sentences c>0, c>1, c>S(1), … with a fresh constant c; any finite subset is satisfied by interpreting c as a large enough natural number, so compactness yields a model of the whole set in which the interpretation of c lies beyond every standard natural number.
难度 专业 · 适合 高中(15-18)
CC BY 4.0 · 已核验 · Verified 2026-10-04
来源 · Source
Herbert B. Enderton《A Mathematical Introduction to Logic》第 2 版，Academic Press，2001，第 2.5–2.6 节
Herbert B. Enderton, A Mathematical Introduction to Logic, 2nd ed., Academic Press, 2001, Sec. 2.5-2.6
独立核验依据 · Independent verification: 核验依据 1 ISBN 9780122384523 (2001)
#数理逻辑 #完备性与紧致性
在命题逻辑中,怎样判定一个公式是否为重言式?真值表方法的代价会随变元个数如何增长?
In propositional logic, how do you decide whether a formula is a tautology, and how does the cost of the truth-table method grow with the number of variables?
逐一枚举公式中每个命题变元的真假赋值,并对每种组合计算公式的真值:若所有行均为真,该公式即为重言式。n 个变元共有 2^n 种赋值,真值表的规模因此随变元个数呈指数膨胀。这一指数代价并非偶然:Cook 与 Levin 证明,判定命题公式的可满足性(SAT)是 NP 完全问题,迄今没有已知的多项式时间算法。
Enumerate every truth assignment of the propositional variables and evaluate the formula for each combination: the formula is a tautology exactly when all rows come out true. With n variables there are 2^n assignments, so the table grows exponentially in size. That exponential cost is no accident—Cook and Levin proved that deciding satisfiability of propositional formulas (SAT) is NP-complete, and no polynomial-time algorithm is known.
难度 进阶 · 适合 初中(12-15)
CC BY 4.0 · 已核验 · Verified 2026-10-04
来源 · Source
Enderton, H. B., 《逻辑的数学导引》(第2版), Academic Press
Enderton, H. B., 'A Mathematical Introduction to Logic' (2nd ed.), Academic Press
独立核验依据 · Independent verification: 核验依据 1 ISBN 9780122384523 (2001)
#数理逻辑 #计算复杂性
哥德尔第一不完备定理为何必须以“系统是一致的”为前提？它揭示了哪类命题的不可判定性？
Why does Gödel's first incompleteness theorem require the premise that the formal system is consistent, and what kind of proposition does it reveal to be undecidable?
该定理构造了自指语句 G,其直观含义是“G 在本系统中不可证明”。在系统能表达初等算术且满足 ω-一致性(哥德尔原始定理的条件)时,G 与其否定都无法被证明,G 因而是一个真而不可证的命题。1936 年 Rosser 改进证明,把所需前提减弱为单纯的一致性。一致性前提用于排除平凡反例:不一致的系统里一切命题皆可证,上述二分随即失效。
The theorem constructs the self-referential sentence G whose intuitive content is “G is not provable in this system.” Provided the system expresses elementary arithmetic and satisfies omega-consistency (the condition of Goedel's original proof), neither G nor its negation is provable, making G true yet unprovable. In 1936 Rosser sharpened the argument so that mere consistency suffices. Consistency excludes the trivial counterexample: in an inconsistent system every proposition is provable, and the dichotomy collapses.
难度 进阶 · 适合 初中(12-15)
CC BY 4.0 · 已核验 · Verified 2026-10-04
来源 · Source
K. Gödel, Monatshefte für Mathematik und Physik 38 (1931), S. 173–198
K. Gödel, “Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I”, Monatshefte für Mathematik und Physik 38 (1931), pp. 173–198
独立核验依据 · Independent verification: 核验依据 1 DOI 10.1007/bf01700692
#数理逻辑 #哥德尔不完备定理