第15章:一致性与完备性——形式系统的两堵墙
你能建造一个不说谎、又无所不知的系统吗?
第14章给了我们一台精密的机器:形式系统接受公理,按推断规则运行,输出定理。这台机器看起来很可靠。但"看起来"不够好。我们需要知道它实际上有多可靠。
这个问题有两个维度,方向相反。
第一个维度:系统会不会说谎?也就是说,它证明出来的东西,是不是都真的成立?这叫一致性。
第二个维度:系统会不会遗漏?也就是说,所有真的东西,它能不能都证明出来?这叫完备性。
两个要求都很合理。20世纪初,数学家 David Hilbert 雄心勃勃地相信,可以为整个数学建立一个同时满足这两个条件的形式基础——严格、完备、无懈可击。这个计划叫做 Hilbert 纲领。
1931年,一个26岁的奥地利数学家,用两个定理,把这个纲领彻底摧毁了。
15.0 镜子语句游戏:当系统开始看见自己
第14章的公理印章游戏还算安全:你盖章,按规则移动,最后得到定理。现在我们给这个游戏加一面镜子。
规则改变如下:每一个公式、每一个证明、每一串符号,都可以被编码成一个自然数。于是系统里不只有“
这就像一座图书馆突然拥有了自己的目录,而目录里的每一本书又能引用目录本身。游戏从这里开始变危险。
玩家要做三步:
- 编号:把公式变成数字,让语句成为系统内部可操作的对象。
- 引用:构造一个谓词
,表示“编号为 的公式可证”。 - 镜像:制造一个命题
,它说的不是外部世界,而是它自己: 不可证。
如果系统证明了
这个游戏的形式化骨架
- 状态空间:公式、证明序列,以及它们的哥德尔编号。
- 合法动作:给符号串编码;在系统内部表达“某编号是证明”;构造自指命题。
- 转移规则:从普通算术命题移动到关于“可证性”的算术命题。
- 胜利条件:Hilbert 式梦想——系统既一致,又能捕捉所有算术真理。
- 失败模式:出现
,系统被自己的镜像卡住。
这个游戏切中的不是“有些题太难”。难题仍然可能有答案,只是你暂时没找到。哥德尔的危险更深:当系统强到足以描述自己的证明行为时,它会产生某些真命题,而这些真命题无法在系统内部被证明。
形式系统不是因为弱才失败,而是因为强到能照见自己,才裂开。
镜子语句游戏的残酷之处在于:镜子不是外敌。它是系统表达能力的一部分。你想让系统足够强,强到能谈论算术;它就顺手学会谈论自己。然后,裂缝出现。不是有人攻击了城堡,是城堡长出了自己的倒影。
15.0.1 小型哥德尔编号:编码如何给系统一面镜子
哥德尔编号不是抽象的"把符号映射到数字",而是可以手动演示的机械编码。下面给一个极小的系统做一遍。
考虑符号集:
一个公式(符号串)被编码为对应质数幂的乘积。公式
关键性质:质因数分解唯一——给定这个编号,你可以100%确定地恢复出原来的符号串。每个公式对应唯一编号,每个编号最多对应一个公式。
证明序列(公式的列表)再编码一层:
现在系统内部可以表达
这面镜子的力量:系统原本只会谈论
哥德尔编号不是"编码技巧"——它展示了"自指"如何作为表达能力的必然副产品出现。任何能够谈论加法和乘法的系统,自动地能够谈论关于自身的某些事实。不是因为"设计"了自指,而是因为系统的表达能力超过了某个阈值,自指就成了不可避免的数学事实。
15.0.2 用代码玩镜子语句游戏
15.0.1 节手工编号了一个公式。下面的程序把整个游戏跑起来:它复现那套编号(并与书中的确切数字核对),在一个小型形式系统里执行真正的证明搜索,然后构造出镜子语句 G——"G 不可证"——并用真实计算出的值跑一遍 15.0 节的那个分叉。
#!/usr/bin/env python3
"""
mirror_sentence_game.py -- a runnable simulation of the Mirror-Sentence
Game (Volume 2, Chapter 15, Sec. 15.0 and 15.0.1).
The game has three steps, and this module runs all three:
1. NUMBERING -- encode symbol strings as natural numbers (Goedel
numbering), exactly the scheme of Sec. 15.0.1:
P->1, ->->2, not->3 (the machine adds Q->4 so the
toy system has two atoms).
2. REFERENCING -- build a real toy formal system (Lukasiewicz's three
axiom schemas plus modus ponens), run an actual proof
search, and implement Prov(n).
3. MIRRORING -- diagonalize: build a sentence G whose content is
"G is not provable", then run the fork from Sec. 15.0
on real computed values.
Honest scope: the toy system is propositional logic -- sound, complete,
and decidable. No incompleteness fires inside it (its language has no
word for "provable"); the crack is derived in Part 3 at the level of the
machine's own code, where the fixed point genuinely exists. The full
theorem needs arithmetic; this shows the mechanism, not a faked theorem.
Proof searches are bounded; the caps below are generous for every formula
shown. Style: functional -- no classes, formulas are immutable tuples.
Run: python3 mirror_sentence_game.py
"""
from __future__ import annotations
import functools
import itertools
import math
import string
import sys
from typing import Dict, FrozenSet, Iterator, List, Optional, Tuple
# Python 3.11+ caps int-to-string conversion; Part 3 prints a 7000-digit number.
if hasattr(sys, "set_int_max_str_digits"):
sys.set_int_max_str_digits(0)
# The book's scheme (P=1, ->=2, not=3) extended to Q and plain ASCII so
# Part 3 can quote sentences; real Goedel numbering covers every symbol
# of the formal language the same way.
CHARSET = "".join(
dict.fromkeys(
"P→¬Q" + string.ascii_letters + string.digits
+ " (){}[]:;,'\"+-*/<>=!._%" + "\\" + "\n" + "\t"
)
)
EXPONENT_OF: Dict[str, int] = {ch: i + 1 for i, ch in enumerate(CHARSET)}
# ---------------------------------------------------------------------------
# Primes and unique factorization
# ---------------------------------------------------------------------------
@functools.cache
def prime(k: int) -> int:
"""The k-th prime, 1-indexed."""
if k == 1:
return 2
n = prime(k - 1) + 1
while not _is_prime(n):
n += 1
return n
def _is_prime(n: int) -> bool:
if n < 2:
return False
limit = math.isqrt(n)
i, p = 1, prime(1)
while p <= limit:
if n % p == 0:
return False
i += 1
p = prime(i)
return True
def factorize(n: int, i: int = 1) -> Tuple[Tuple[int, int], ...]:
"""Unique prime factorization of n >= 1, ascending primes."""
if n <= 1:
return ()
p = prime(i)
if n % p != 0:
return factorize(n, i + 1)
exponent, rest = 0, n
while rest % p == 0:
rest //= p
exponent += 1
return ((p, exponent),) + factorize(rest, i + 1)
# ---------------------------------------------------------------------------
# Part 1 -- NUMBERING
# ---------------------------------------------------------------------------
def encode_symbols(text: str) -> int:
"""Goedel-number a symbol string: product of prime(i)^EXPONENT_OF[sym_i].
The empty string encodes to 1 (the empty product)."""
return functools.reduce(
lambda acc, pair: acc * prime(pair[0]) ** EXPONENT_OF[pair[1]],
enumerate(text, start=1),
1,
)
def decode_number(n: int) -> Optional[str]:
"""Inverse of encode_symbols; None when n names no symbol string."""
if n <= 0:
return None
try:
symbols = [CHARSET[exponent - 1] for _, exponent in factorize(n)]
except IndexError:
return None
return "".join(symbols)
def encode_proof(formulas: Tuple[str, ...]) -> int:
"""Second level: (F1,...,Fk) -> product of prime(i)^encode_symbols(Fi)."""
return functools.reduce(
lambda acc, pair: acc * prime(pair[0]) ** encode_symbols(pair[1]),
enumerate(formulas, start=1),
1,
)
def decode_proof(n: int) -> Tuple[str, ...]:
"""Inverse of encode_proof."""
return tuple(decode_number(exponent) for _, exponent in factorize(n))
# ---------------------------------------------------------------------------
# The toy formal language: formulas as immutable tuples
# Grammar: F := P | Q | not F | (F -> F); not binds tightest, -> right-assoc.
# ---------------------------------------------------------------------------
def parse_formula(text: str):
"""Parse a symbol string into a formula tuple; ValueError if not well-formed."""
formula, i = _parse_implication(text, 0)
if i != len(text):
raise ValueError(f"trailing symbols at position {i}: {text[i:]!r}")
return formula
def _parse_implication(text: str, i: int):
left, i = _parse_negation(text, i)
if i < len(text) and text[i] == "→":
right, i = _parse_implication(text, i + 1)
return ("→", left, right), i
return left, i
def _parse_negation(text: str, i: int):
if i < len(text) and text[i] == "¬":
inner, i = _parse_negation(text, i + 1)
return ("¬", inner), i
if i < len(text) and text[i] == "(":
left, i = _parse_implication(text, i + 1)
if i >= len(text) or text[i] != "→":
raise ValueError("expected '→' inside parentheses")
right, i = _parse_implication(text, i + 1)
if i >= len(text) or text[i] != ")":
raise ValueError("expected ')'")
return ("→", left, right), i + 1
if i < len(text) and text[i] in ("P", "Q"):
return text[i], i + 1
raise ValueError(f"cannot parse at position {i}: {text[i:]!r}")
def show(formula) -> str:
"""Canonical, fully parenthesized symbol string of a formula tuple."""
if isinstance(formula, str):
return formula
if formula[0] == "¬":
return "¬" + show(formula[1])
return "(" + show(formula[1]) + "→" + show(formula[2]) + ")"
def complexity(formula) -> int:
if isinstance(formula, str):
return 0
if formula[0] == "¬":
return 1 + complexity(formula[1])
return 1 + complexity(formula[1]) + complexity(formula[2])
def variables(formula) -> FrozenSet[str]:
if isinstance(formula, str):
return frozenset({formula})
if formula[0] == "¬":
return variables(formula[1])
return variables(formula[1]) | variables(formula[2])
def subformulas(formula) -> FrozenSet:
if isinstance(formula, str):
return frozenset({formula})
if formula[0] == "¬":
return subformulas(formula[1]) | {formula}
return subformulas(formula[1]) | subformulas(formula[2]) | {formula}
def evaluate(formula, assignment: Dict[str, bool]) -> bool:
if isinstance(formula, str):
return assignment[formula]
if formula[0] == "¬":
return not evaluate(formula[1], assignment)
return (not evaluate(formula[1], assignment)) or evaluate(formula[2], assignment)
def is_tautology(formula) -> bool:
vs = sorted(variables(formula))
return all(
evaluate(formula, dict(zip(vs, bits)))
for bits in itertools.product((False, True), repeat=len(vs))
)
# ---------------------------------------------------------------------------
# Part 2 -- REFERENCING: the toy formal system and a real Prov
# Lukasiewicz's three axiom schemas plus modus ponens; sound and complete
# for classical propositional logic.
# ---------------------------------------------------------------------------
def axiom_instances(subfs: FrozenSet, max_complexity: int = 8) -> List:
"""All axiom instances built from formulas in `subfs`, under the cap.
(By the subformula property of Hilbert systems, a normal proof of F
only needs instances built from parts of F -- that is what keeps the
search fast without losing completeness.)"""
subfs = tuple(sorted(subfs, key=lambda f: (complexity(f), show(f))))
out: List = []
for x in subfs:
for y in subfs:
a1 = ("→", x, ("→", y, x))
if complexity(a1) <= max_complexity:
out.append(a1)
a3 = ("→", ("→", ("¬", x), ("¬", y)),
("→", y, x))
if complexity(a3) <= max_complexity:
out.append(a3)
for z in subfs:
a2 = ("→",
("→", x, ("→", y, z)),
("→", ("→", x, y), ("→", x, z)))
if complexity(a2) <= max_complexity:
out.append(a2)
return out
def _candidate_space(goal, max_complexity: int) -> FrozenSet:
"""Subformulas of the goal plus subformulas of all admissible axiom
instances -- the only formulas a normal proof of the goal can need."""
base = subformulas(goal)
instances = axiom_instances(base, max_complexity)
return functools.reduce(
lambda acc, f: acc | subformulas(f), instances, frozenset(base)
)
def _bfs_closure(candidates: FrozenSet, start: List, max_rounds: int = 24):
"""Forward proof search: the axiom-stamp game played honestly.
Start from axioms, apply modus ponens among derived formulas, never
leave the candidate space. Returns (parent, order); parent maps each
formula to None (axiom) or (a, b) (MP on a and b)."""
implications: Dict = {}
for c in candidates:
if isinstance(c, tuple) and c[0] == "→":
implications.setdefault(c[1], []).append(c)
parent: Dict = {}
order: List = []
def add(f, src) -> None:
if f not in parent:
parent[f] = src
order.append(f)
for ax in start:
add(ax, None)
for _ in range(max_rounds):
grown = False
for a in list(order):
for b in implications.get(a, ()):
if b not in parent:
continue # the major premise must be derived
c = b[2]
if c in candidates and c not in parent:
add(c, (a, b))
grown = True
if not grown:
break
return parent, order
def _rebuild(parent: Dict, goal) -> List:
"""Recover a proof of `goal` from parent pointers, premises first."""
steps: List = []
seen = set()
def visit(f) -> None:
if f in seen:
return
src = parent[f]
if src is not None:
visit(src[0])
visit(src[1])
seen.add(f)
steps.append(f)
visit(goal)
return steps
def search_proof(goal, max_complexity: int = 8, max_rounds: int = 24) -> Optional[List]:
"""A proof of `goal` in the toy system, or None if the bounded search
closes without reaching it."""
candidates = _candidate_space(goal, max_complexity)
axioms = axiom_instances(subformulas(goal), max_complexity)
parent, _ = _bfs_closure(candidates, axioms, max_rounds)
if goal in parent:
return _rebuild(parent, goal)
return None
def provable(n: int, max_complexity: int = 8, max_rounds: int = 24) -> bool:
"""Prov(n): is the formula numbered n provable in the toy system?
Numbers that decode to no symbol string, or to a string that is not a
well-formed formula, are simply not provable."""
text = decode_number(n)
if text is None:
return False
try:
formula = parse_formula(text)
except ValueError:
return False
return search_proof(formula, max_complexity, max_rounds) is not None
# ---------------------------------------------------------------------------
# Part 3 -- MIRRORING: the diagonal sentence and the fork
# ---------------------------------------------------------------------------
QUINE_TEMPLATE = "q = %r; result = not provable(encode(q %% q))"
def make_mirror_sentence() -> str:
"""Fill the template with its own source, so the sentence's content
becomes 'not provable(encode(G))' where G is the sentence itself.
G is a fixed point of F(phi) = not Prov(<<phi>>) -- the same diagonal
as the Goedel sentence (Ch. 22.2.5 reads it as the fixed point of an
inference transformation)."""
return QUINE_TEMPLATE % QUINE_TEMPLATE
def evaluate_mirror(sentence: str) -> bool:
"""Run the mirror sentence and return what it says (its truth value).
Evaluating G computes: not provable(encode(G))."""
scope: Dict[str, object] = {"provable": provable, "encode": encode_symbols}
exec(compile(sentence, "<mirror-sentence>", "exec"), {"__builtins__": {}}, scope)
return bool(scope["result"])
# ---------------------------------------------------------------------------
# The demonstration
# ---------------------------------------------------------------------------
@functools.cache
def _forms_at(c: int):
"""All formulas of exactly complexity c over {P, Q}."""
if c == 0:
return ("P", "Q")
out = [("¬", f) for f in _forms_at(c - 1)]
for i in range(c):
for f in _forms_at(i):
for g in _forms_at(c - 1 - i):
out.append(("→", f, g))
return tuple(out)
def _all_formulas(max_complexity: int) -> Iterator:
for c in range(max_complexity + 1):
yield from _forms_at(c)
def _completeness_sweep(max_complexity: int = 2, max_rounds: int = 24) -> Dict:
"""One shared proof search over {P, Q}, then compare 'tautology?'
against 'derived?' for every formula up to the given complexity."""
islands = list(_all_formulas(max_complexity))
base = functools.reduce(
lambda acc, f: acc | subformulas(f), islands, frozenset()
)
axioms = axiom_instances(base, max_complexity=8)
candidates = functools.reduce(
lambda acc, f: acc | subformulas(f), axioms, frozenset(base)
)
parent, _ = _bfs_closure(candidates, axioms, max_rounds)
derived = frozenset(parent)
taus = [f for f in islands if is_tautology(f)]
return {
"islands": islands,
"derived": derived,
"tautologies": taus,
"derived_tautologies": [f for f in taus if f in derived],
"derived_non_tautologies": [f for f in islands
if f in derived and not is_tautology(f)],
}
def demo() -> None:
banner = "=" * 70
print(banner)
print(" THE MIRROR-SENTENCE GAME -- a runnable simulation")
print(" The Reasoning Kingdom, Volume 2, Chapter 15 (Sec. 15.0, 15.0.1)")
print(banner)
# Part 1
print("\nPART 1 -- NUMBERING (the book's scheme, run for real)")
print(" scheme: P->1, ->->2, not->3 (this machine adds Q->4)")
book_number = encode_symbols("¬P→¬¬P")
expected = 2 ** 3 * 3 ** 1 * 5 ** 2 * 7 ** 3 * 11 ** 3 * 13 ** 1
assert book_number == expected, "book example mismatch"
print(f" encode(\"¬P→¬¬P\") = {book_number}")
print(" = 2^3 * 3^1 * 5^2 * 7^3 * 11^3 * 13^1 (matches Sec. 15.0.1)")
print(f' decode({book_number}) = "{decode_number(book_number)}"')
print(f' decode(32) = "{decode_number(32)}" -- not a formula: some')
print(" numbers name no formula at all (as the book promises)")
print(' encode("") = 1, decode(1) = "" (the empty string lives at 1)')
proof_number = encode_proof(("P", "Q", "¬P"))
print(f" proof level: encode_proof((P, Q, ¬P)) = {proof_number}")
print(f" decode_proof -> {decode_proof(proof_number)}")
print(" honest note: encoding the real 5-step proof below would need a")
print(" number with ~10^160 digits. Nobody ever multiplies it out --")
print(" the encoding exists to be expressible, not computed.")
# Part 2
print("\nPART 2 -- REFERENCING (a real toy formal system)")
print(" system: Lukasiewicz's A1/A2/A3 schemas + modus ponens, over {P, Q}.")
goal = parse_formula("P→P")
proof = search_proof(goal)
assert proof is not None
n_pp = encode_symbols("P→P")
print(f" Prov(⌈P→P⌉) = Prov({n_pp}) = True. The machine's actual proof:")
parent, _ = _bfs_closure(
_candidate_space(goal, 8), axiom_instances(subformulas(goal), 8), 24
)
index = {f: i + 1 for i, f in enumerate(proof)}
for i, f in enumerate(proof, start=1):
src = parent[f]
how = "axiom" if src is None else f"MP: {index[src[0]]}, {index[src[1]]}"
print(f" {i}. {show(f):<42} [{how}]")
n_p = encode_symbols("P")
print(f" Prov(⌈P⌉) = Prov({n_p}) = False: the search closed with no")
print(" derivation (and P is not a tautology).")
sweep = _completeness_sweep()
islands, derived = sweep["islands"], sweep["derived"]
print(f" soundness: all {len(derived)} formulas the machine derived are")
print(" tautologies (checked by truth tables). The system does not lie.")
n_taut = len(sweep["tautologies"])
n_ok = len(sweep["derived_tautologies"])
n_bad = len(sweep["derived_non_tautologies"])
print(f" completeness sweep: {len(islands)} formulas of complexity <= 2:")
print(f" {n_ok}/{n_taut} tautologies derived; {n_bad} non-tautology derived")
print(" (the second number must be 0).")
assert n_ok == n_taut and n_bad == 0
print(" sound and complete on this little island -- exactly why the")
print(" mirror cannot crack it YET: its language has no word for")
print(' "provable". (Ch. 15.1: a complete decidable system never lies.)')
# Part 3
print("\nPART 3 -- MIRRORING (the fork, run live)")
sentence = make_mirror_sentence()
n = encode_symbols(sentence)
content = evaluate_mirror(sentence)
proven = provable(n)
print(" the machine builds a sentence G whose content is 'G is not provable':")
print(f" G = {sentence}")
print(f" n = encode(G) has {len(str(n))} digits, starting {str(n)[:40]}...")
print(f" what G says, computed: {content}")
print(f" can the toy system prove G: {proven}")
print(" the fork from Sec. 15.0, with real values:")
print(" G's claim is true, and the system cannot prove it. Here the")
print(" failure is visible: the toy's proof search cannot even parse G")
print(" -- a decidable system's language is too poor to mention")
print(' "provable".')
print(" why the crack must come once the system grows rich enough:")
print(" assume the system can vouch for itself (Prov sound and complete):")
print(" (1) provable*(G) <=> G is true")
print(" (2) G is true <=> not provable*(G) [by G's own content]")
print(" (1) + (2) => provable*(G) <=> not provable*(G) -- contradiction.")
print(" fixed-point reading (Ch. 22.2.5): G is a fixed point of")
print(" F(phi) = not Prov(<<phi>>) -- the same diagonal as the Goedel")
print(" sentence.")
print("\n Professor Pallas says:")
print(' "The cruelty of the mirror-sentence game: the mirror is no external')
print(" enemy. It is part of the system's expressive power. ... No one")
print(' attacked the castle -- the castle grew its own reflection."')
print("\n" + banner)
print(" end of simulation -- every printed value came from a real computation")
print(banner)
if __name__ == "__main__":
demo()15.1 一致性:系统不说谎
先精确说清楚"说谎"是什么意思。
如果一个形式系统能同时证明某个命题
所以一致性是形式系统的底线,低于这条线的系统是废的。
"废"不是形容词,是诊断结论。一旦不一致,系统能证明所有命题,包括"1=2"。这不是系统"有点不对",而是系统失去了证明的全部意义——它能证明一切,等于什么都没证明。这是全面失效,不是局部故障。
这个推论有一个拉丁名:ex contradictione quodlibet(从矛盾可得任意结论)。证明过程非常短:已知
验证一致性的标准方法是构造一个模型——一个使所有公理为真的解释。命题逻辑是一致的,因为它的公理在真值表下都是重言式,而推断规则保持重言式的性质,所以系统不可能推出矛盾。
但对于更强的系统——比如皮亚诺算术——构造模型变得困难,依赖这类方法来保证一致性也变得靠不住。原因就在第二个定理里,稍后揭晓。
15.2 完备性:系统不遗漏
完备性说的是:凡是语义上成立的,句法上都可以证明。
更精确地,若
哥德尔 1930 年证明了一阶谓词逻辑满足这个性质。这是一个令人振奋的结果:一阶逻辑的推断规则恰好是"正确的",没有遗漏任何语义上应该成立的推断。
这个定理说的是:我们写下的那些推断规则——假言推理、全称例化、存在引入……——恰好捕捉了所有语义上有效的推断,一条不多,一条不少。这不是设计的结果,而是一个需要证明的非平凡事实。如果完备性不成立,意味着有些"显然成立"的推断被规则体系遗漏了,需要补充新的推断规则——而哥德尔告诉你:不需要。
这是哥德尔带来的最后一个好消息。
"最后一个好消息"——这句话值得停一下。1930年的完备性定理和1931年的不完备定理,是同一个人在相邻两年里带来的,方向完全相反。一阶逻辑完备,足够强的算术系统不完备。边界就在这里,非常精确,不是模糊的悲观主义。
一年之后,他带来的是完全不同的东西。问题出在"足够强"这三个字上。一旦系统强大到能够表达算术——自然数、加法、乘法——完备性就永久地失去了。
15.3 哥德尔的两个定理
1931年,哥德尔发表了《论〈数学原理〉及相关系统的形式不可判定命题》。文章开头直接给出了结论,毫无铺垫:
定理一(第一不完备定理):任何足够强的一致形式系统,都包含既无法被证明也无法被反驳的命题。
定理二(第二不完备定理):任何足够强的一致形式系统,都无法在自身内部证明自身的一致性。
这两个定理的"足够强"是一个技术条件:系统能表达初等算术。皮亚诺算术满足,ZFC 集合论满足,几乎所有实际数学使用的系统都满足。
让我们追踪哥德尔是怎么做到的。
15.4 哥德尔编号:让系统看见自己
哥德尔的关键洞察可以用一句话说完:语法也是数学对象。
形式系统里的符号、公式、证明,全都是有限的字符串。有限字符串可以被编码为自然数——给每个符号分配一个数字,把公式编码为这些数字的某种算术组合。这个编码叫做哥德尔编号,把命题
哥德尔编号:把"语言"变成"数字"(前人工作:Gödel, 1931)
哥德尔编号是哥德尔 1931 年论文的核心技巧:给形式语言里的每个符号分配一个自然数,然后把任意公式或证明序列编码成一个大自然数。
简化版本:假设
为什么这个技巧如此强大? 因为一旦语法被编码为数,"这个符号串是合法公式吗?""这个序列是合法证明吗?"这些关于语言的问题,就变成了关于数的问题。而皮亚诺算术可以谈论数——于是系统获得了谈论自身语法的能力。
这不是作弊,这是一个精确的数学构造。编号方式可以变,但"可证性可以用算术谓词表达"这个事实不变。
一旦语法被编码为自然数,"这个命题在系统里可证"这件事,就变成了一个关于自然数的算术陈述。而皮亚诺算术恰好能表达关于自然数的陈述。于是系统获得了一种奇特的能力:它可以谈论自己。
这是一个合理的怀疑。哥德尔编号是否只是一种技巧性的把戏,实质上没有意义?不。编码的关键不是编号本身,而是:关于"哪些符号串是合法证明"的问题,可以用算术谓词表达——这是可以验证的数学事实,不依赖于编号的具体方式。换言之,任何足够强的算术系统,都能用自己的语言谈论"可证性"这件事,而不仅仅是谈论数字。哥德尔只是把这个可能性利用到了极致。
这就是自指的入口。
回到镜子语句游戏,这一步相当于把“公式”做成了可以被系统拿在手里把玩的棋子。第14章的公理印章游戏只允许你在纸上写公式;现在,纸上的公式有了编号,编号又能回到纸上,被另一个公式谈论。游戏的状态空间突然多了一层:它不再只是“命题是什么”,而是“命题如何谈论命题”。
这就是危险的来源。镜子一旦装上,系统就不只是向外看世界,也开始向内看自己的证明行为。哥德尔句不是从天而降的怪物,它是镜子规则自然允许的一步棋。
15.5 哥德尔句:说"我不可证"的命题
利用哥德尔编号,可以在系统内部表达一个谓词
现在的任务是:构造一个命题
这看起来像循环定义——
对角化引理解决的正是这个结。
对角化引理:自指是怎么在数学里合法实现的?
对角化(Diagonalization)是哥德尔、图灵等人用来构造自指命题的核心技巧,名字来自康托尔的对角线论证。
直觉版本:假设你有一张无限大的表格,行和列都是自然数。你想构造一个"不在表格任何一行里"的对象——方法是:取第1行第1列的元素,改一下;取第2行第2列的元素,改一下;以此类推,沿对角线改。这个新对象和表格的每一行都至少差一个位置,所以不在表格里。
在哥德尔证明里:把这个思想用在"公式引用自身"上——构造一个公式
结果:
先考虑一个一元谓词
构造分两步。
第一步:引入替换函数。 定义一个算术函数
第二步:写出自指公式。 取谓词
现在计算
关键观察:
把
现在来看
若
若
所以,在系统一致的前提下,
结论:在一致的系统里,
这是整个论证里最微妙的一步。我们说"
15.6 第二定理:系统无法为自己担保
第二不完备定理是第一个定理的一个推论,但它的冲击力不亚于第一个。
把"系统
第一定理的证明过程本身可以在系统内部被形式化——因为证明过程是有限的符号操作,而系统能表达算术。形式化之后,得到:
也就是说,系统自己能证明:"如果我是一致的,那么
现在假设系统还能证明自身一致,即
因此,系统不可能证明自身的一致性。
这不是谦虚,也不是能力不足。这是逻辑的结构性事实:你无法用一把尺子测量这把尺子本身是否准确。任何关于系统一致性的证明,都必须来自一个更强的外部系统,而那个更强系统的一致性又是一个悬而未决的问题——这个层级没有顶端。
真正震撼的是第二定理说的不是"很难",而是"原则上不可能"——不是工程问题,是逻辑结构问题。一个系统对自身一致性的证明,永远需要一个更强的外部系统背书。没有顶端。这才是重点,不是那把尺子的比喻。
实话实说:我们不能证明。数学界接受 ZFC 的理由是:它用了将近一百年,产生了大量相互一致的结果,没有出现矛盾。这是归纳推理,不是演绎证明。哥德尔第二定理告诉我们,这也是我们能做到的最好程度。数学的地基不是一块被证明无误的磐石,而是一个被反复压测、至今未裂的支撑结构。这个区别,比大多数数学课承认的要重要。
15.7 Hilbert 纲领的终结与遗产
Hilbert 的目标是建立一个完备、一致、可判定的数学基础。两个不完备定理说明了:
- 完备性:在足够强的一致系统里,不可能实现。
- 一致性的自我保证:不可能在系统内部完成。
- 可判定性:图灵 1936 年证明了不可能,这是第19章的故事。
三项目标,全军覆没。
Hilbert 纲领的失败是科学史上最有价值的失败之一。正是因为他把目标定得足够精确,哥德尔和图灵才能精确地证明那些目标不可达。如果 Hilbert 说的是"数学应该有个好的基础",就没有什么可以反驳,也没有什么可以学习。精确的问题,才能得到精确的否定答案——而精确的否定答案,比模糊的肯定答案更有价值。
但这不是悲剧的终点,而是一个更清醒认识的起点。Hilbert 纲领的失败没有让数学崩溃,而是让数学家更精确地知道了边界在哪里。边界之内,形式系统依然是人类历史上最可靠的知识建构工具。边界之外,是永久的开放问题——有些命题的真假,永远取决于你选择接受哪些公理。
这种清醒,比盲目的乐观更有价值。
15.8 动手实践:算术被形式化是什么感觉
本章一直在说"足够强的系统"——强到能表达算术。这不是抽象的描述。皮亚诺算术(PA)是这样一个系统,它有五条关于自然数的公理。在进入"悬而未决"之前,先花几分钟真实接触它。
皮亚诺公理(非形式版本):
是自然数。 - 每个自然数
都有唯一的后继 ,也是自然数。 不是任何自然数的后继(即不存在 使得 )。 - 不同的自然数有不同的后继:若
,则 。 - 数学归纳原理:若某个性质对
成立,且对任意 成立时对 也成立,则它对所有自然数成立。
在这五条公理里,加法可以被定义出来:
这不是约定,是定义——加法的全部行为由这两条递归方程决定。
练习:用这个定义,推出
首先约定符号:
每一步用了哪条定义?第一步是展开符号,第二步用了加法的第二条定义(
这就是
现在感受一下这个系统"足够强"是什么意思:它能表达所有关于自然数的初等陈述——"存在无穷多个质数"、"每个偶数是两个质数之和(哥德巴赫猜想)"、甚至"这个系统本身是否一致"——都可以在 PA 的语言里被写成公式。正是这种表达能力,让哥德尔的对角化引理得以发挥。一个系统能谈论自己,是因为它能谈论所有足够复杂的数论陈述——而关于自身的陈述,是数论陈述的一个特例。
悬而未决
不完备性与停机问题是同一件事吗? 哥德尔和图灵都通过自指构造建立了边界,两者在结构上高度相似。递归函数论给出了部分答案——它们确实是同一枚硬币的两面——但这个故事的全貌在第19章才会展开。
能否逃出不完备性? 把
不完备性是由哪条结构规则造成的? 第14章列出了三条在后台默默运行的结构规则:弱化、收缩、交换。哥德尔定理的存在,根植于系统足够强——而"足够强"依赖于假设可以被任意重复使用。如果我们质疑这一点——如果每个假设只能用一次——推理会变成什么?这是第16章的起点。
思考题
★ 热身
对角化引理的核心是替换函数
的输入是两个自然数,输出也是一个自然数。(对/错?) 的结果,是把公式 里的自由变量替换为公式 本身之后的哥德尔编号。(对/错?) - 哥德尔编号的具体方式(比如用质数幂乘积还是别的编码)会影响第一不完备定理的结论。(对/错?)
(这三道题的目的是确认:哥德尔编号是算术操作,不依赖编码方式的选择。)
★★ 推导
把哥德尔句
还是一致的吗?(提示: 在 中不可证意味着什么?把 加进去会和 的其他定理矛盾吗?) 有自己的哥德尔句 吗? 和 是同一个命题吗?为什么不是? - 这个过程可以无限重复。把所有这样的哥德尔句全部加入,得到的极限系统是否完备?试着用自然语言解释为什么答案是否定的——完备性逃不掉。
★★★ 挑战
第二不完备定理说:
试着用本章的语言写出:这个"外部论证"本身依赖什么?它用了哪个更强系统的一致性?这个更强系统的一致性,又依赖什么?
这个问题没有终点,但试着把无穷退回的结构写清楚——用
不需要解决这些问题——只需要想清楚为什么每个问题都比看起来的更难。
