欢迎大家提Issue反馈问题或建议,建设推理王国!
Skip to content

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

你能建造一个不说谎、又无所不知的系统吗?


第14章给了我们一台精密的机器:形式系统接受公理,按推断规则运行,输出定理。这台机器看起来很可靠。但"看起来"不够好。我们需要知道它实际上有多可靠。

这个问题有两个维度,方向相反。

第一个维度:系统会不会说谎?也就是说,它证明出来的东西,是不是都真的成立?这叫一致性。

第二个维度:系统会不会遗漏?也就是说,所有真的东西,它能不能都证明出来?这叫完备性。

两个要求都很合理。20世纪初,数学家 David Hilbert 雄心勃勃地相信,可以为整个数学建立一个同时满足这两个条件的形式基础——严格、完备、无懈可击。这个计划叫做 Hilbert 纲领。

1931年,一个26岁的奥地利数学家,用两个定理,把这个纲领彻底摧毁了。


15.0 镜子语句游戏:当系统开始看见自己 ​

第14章的公理印章游戏还算安全:你盖章,按规则移动,最后得到定理。现在我们给这个游戏加一面镜子。

规则改变如下:每一个公式、每一个证明、每一串符号,都可以被编码成一个自然数。于是系统里不只有“1+1=2”这种谈论数字的命题,还可以出现谈论“某个公式编号是否可证”的命题。

这就像一座图书馆突然拥有了自己的目录,而目录里的每一本书又能引用目录本身。游戏从这里开始变危险。

玩家要做三步:

  1. 编号:把公式变成数字,让语句成为系统内部可操作的对象。
  2. 引用:构造一个谓词 Prov(n),表示“编号为 n 的公式可证”。
  3. 镜像:制造一个命题 G,它说的不是外部世界,而是它自己:G 不可证。

如果系统证明了 G,它就证明了一个声称“我不可证”的命题,于是系统说谎;如果系统不能证明 G,那么 G 说的恰好是真的,但系统抓不到它。

这个游戏的形式化骨架

  • 状态空间:公式、证明序列,以及它们的哥德尔编号。
  • 合法动作:给符号串编码;在系统内部表达“某编号是证明”;构造自指命题。
  • 转移规则:从普通算术命题移动到关于“可证性”的算术命题。
  • 胜利条件:Hilbert 式梦想——系统既一致,又能捕捉所有算术真理。
  • 失败模式:出现 G↔¬Prov(⌜G⌝),系统被自己的镜像卡住。

这个游戏切中的不是“有些题太难”。难题仍然可能有答案,只是你暂时没找到。哥德尔的危险更深:当系统强到足以描述自己的证明行为时,它会产生某些真命题,而这些真命题无法在系统内部被证明。

形式系统不是因为弱才失败,而是因为强到能照见自己,才裂开。

镜子语句游戏的残酷之处在于:镜子不是外敌。它是系统表达能力的一部分。你想让系统足够强,强到能谈论算术;它就顺手学会谈论自己。然后,裂缝出现。不是有人攻击了城堡,是城堡长出了自己的倒影。

15.0.1 小型哥德尔编号:编码如何给系统一面镜子 ​

哥德尔编号不是抽象的"把符号映射到数字",而是可以手动演示的机械编码。下面给一个极小的系统做一遍。

考虑符号集:P(命题变元)、→(蕴含)、¬(否定)。分别编码为:

P↦1,→ ↦2,¬↦3

一个公式(符号串)被编码为对应质数幂的乘积。公式 ¬P→¬¬P 的符号序列是 (¬,P,→,¬,¬,P):

编号=23⋅31⋅52⋅73⋅113⋅131

关键性质:质因数分解唯一——给定这个编号,你可以100%确定地恢复出原来的符号串。每个公式对应唯一编号,每个编号最多对应一个公式。

证明序列(公式的列表)再编码一层:(F1,F2,…,Fk) 映射到 2#F1⋅3#F2⋅⋯⋅pk#Fk。

现在系统内部可以表达 Prov(n)——"存在一个证明序列,其最后一个公式的编号是 n"。但 Prov(n) 并不是什么神秘的新谓词——它就是一个关于自然数的算术命题,说的是"存在某个自然数满足某某质因数分解条件"。它完全在系统语言内——谈论乘法、加法、质数——只是通过编码,这些算术关系恰好对应了"某个公式可证"这个元数学概念。

这面镜子的力量:系统原本只会谈论 1+1=2 这类数字命题。有了哥德尔编号,系统"顺手"获得了谈论自己的能力——因为"证明"被编码成了数字之间的关系。不是系统被设计了这面镜子,而是数字大到能编码系统自身时,镜子的出现是必然的。

哥德尔编号不是"编码技巧"——它展示了"自指"如何作为表达能力的必然副产品出现。任何能够谈论加法和乘法的系统,自动地能够谈论关于自身的某些事实。不是因为"设计"了自指,而是因为系统的表达能力超过了某个阈值,自指就成了不可避免的数学事实。

15.0.2 用代码玩镜子语句游戏 ​

15.0.1 节手工编号了一个公式。下面的程序把整个游戏跑起来:它复现那套编号(并与书中的确切数字核对),在一个小型形式系统里执行真正的证明搜索,然后构造出镜子语句 G——"G 不可证"——并用真实计算出的值跑一遍 15.0 节的那个分叉。

python
#!/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 一致性:系统不说谎 ​

先精确说清楚"说谎"是什么意思。

如果一个形式系统能同时证明某个命题 A 和它的否定 ¬A,这个系统就是不一致的。一旦发生这种情况,灾难是全面的:从 A 和 ¬A 出发,利用标准的推断规则,可以证明任何命题。一个能证明所有命题的系统,等于什么都没有证明。

所以一致性是形式系统的底线,低于这条线的系统是废的。

"废"不是形容词,是诊断结论。一旦不一致,系统能证明所有命题,包括"1=2"。这不是系统"有点不对",而是系统失去了证明的全部意义——它能证明一切,等于什么都没证明。这是全面失效,不是局部故障。

这个推论有一个拉丁名:ex contradictione quodlibet(从矛盾可得任意结论)。证明过程非常短:已知 A 为真,所以 A∨B 为真(添加析取);已知 ¬A 为真,由 ¬A 和 A∨B 可得 B(析取消去)。B 是任意命题。也就是说,一旦系统里存在矛盾,所有命题都"可证"了——包括"1 = 2"和它的否定。系统不是变得"部分错误",而是整体失效。

验证一致性的标准方法是构造一个模型——一个使所有公理为真的解释。命题逻辑是一致的,因为它的公理在真值表下都是重言式,而推断规则保持重言式的性质,所以系统不可能推出矛盾。

但对于更强的系统——比如皮亚诺算术——构造模型变得困难,依赖这类方法来保证一致性也变得靠不住。原因就在第二个定理里,稍后揭晓。


15.2 完备性:系统不遗漏 ​

完备性说的是:凡是语义上成立的,句法上都可以证明。

更精确地,若 ⊨A(A 是重言式,在所有解释下为真),则 F⊢A(A 在系统 F 中有形式证明)。

哥德尔 1930 年证明了一阶谓词逻辑满足这个性质。这是一个令人振奋的结果:一阶逻辑的推断规则恰好是"正确的",没有遗漏任何语义上应该成立的推断。

这个定理说的是:我们写下的那些推断规则——假言推理、全称例化、存在引入……——恰好捕捉了所有语义上有效的推断,一条不多,一条不少。这不是设计的结果,而是一个需要证明的非平凡事实。如果完备性不成立,意味着有些"显然成立"的推断被规则体系遗漏了,需要补充新的推断规则——而哥德尔告诉你:不需要。

这是哥德尔带来的最后一个好消息。

"最后一个好消息"——这句话值得停一下。1930年的完备性定理和1931年的不完备定理,是同一个人在相邻两年里带来的,方向完全相反。一阶逻辑完备,足够强的算术系统不完备。边界就在这里,非常精确,不是模糊的悲观主义。

一年之后,他带来的是完全不同的东西。问题出在"足够强"这三个字上。一旦系统强大到能够表达算术——自然数、加法、乘法——完备性就永久地失去了。


15.3 哥德尔的两个定理 ​

1931年,哥德尔发表了《论〈数学原理〉及相关系统的形式不可判定命题》。文章开头直接给出了结论,毫无铺垫:

定理一(第一不完备定理):任何足够强的一致形式系统,都包含既无法被证明也无法被反驳的命题。

定理二(第二不完备定理):任何足够强的一致形式系统,都无法在自身内部证明自身的一致性。

这两个定理的"足够强"是一个技术条件:系统能表达初等算术。皮亚诺算术满足,ZFC 集合论满足,几乎所有实际数学使用的系统都满足。

让我们追踪哥德尔是怎么做到的。


15.4 哥德尔编号:让系统看见自己 ​

哥德尔的关键洞察可以用一句话说完:语法也是数学对象。

形式系统里的符号、公式、证明,全都是有限的字符串。有限字符串可以被编码为自然数——给每个符号分配一个数字,把公式编码为这些数字的某种算术组合。这个编码叫做哥德尔编号,把命题 A 的编号记作 ⌜A⌝。

哥德尔编号:把"语言"变成"数字"(前人工作:Gödel, 1931)

哥德尔编号是哥德尔 1931 年论文的核心技巧:给形式语言里的每个符号分配一个自然数,然后把任意公式或证明序列编码成一个大自然数。

简化版本:假设 ¬ 编号为 1,∧ 编号为 2,P 编号为 3,Q 编号为 4。那么命题 ¬P 可以编码为数字 13(拼接),或更精确地用 21⋅33=2⋅27=54(用素数幂乘积)。

为什么这个技巧如此强大? 因为一旦语法被编码为数,"这个符号串是合法公式吗?""这个序列是合法证明吗?"这些关于语言的问题,就变成了关于数的问题。而皮亚诺算术可以谈论数——于是系统获得了谈论自身语法的能力。

这不是作弊,这是一个精确的数学构造。编号方式可以变,但"可证性可以用算术谓词表达"这个事实不变。

一旦语法被编码为自然数,"这个命题在系统里可证"这件事,就变成了一个关于自然数的算术陈述。而皮亚诺算术恰好能表达关于自然数的陈述。于是系统获得了一种奇特的能力:它可以谈论自己。

这是一个合理的怀疑。哥德尔编号是否只是一种技巧性的把戏,实质上没有意义?不。编码的关键不是编号本身,而是:关于"哪些符号串是合法证明"的问题,可以用算术谓词表达——这是可以验证的数学事实,不依赖于编号的具体方式。换言之,任何足够强的算术系统,都能用自己的语言谈论"可证性"这件事,而不仅仅是谈论数字。哥德尔只是把这个可能性利用到了极致。

这就是自指的入口。

回到镜子语句游戏,这一步相当于把“公式”做成了可以被系统拿在手里把玩的棋子。第14章的公理印章游戏只允许你在纸上写公式;现在,纸上的公式有了编号,编号又能回到纸上,被另一个公式谈论。游戏的状态空间突然多了一层:它不再只是“命题是什么”,而是“命题如何谈论命题”。

这就是危险的来源。镜子一旦装上,系统就不只是向外看世界,也开始向内看自己的证明行为。哥德尔句不是从天而降的怪物,它是镜子规则自然允许的一步棋。


15.5 哥德尔句:说"我不可证"的命题 ​

利用哥德尔编号,可以在系统内部表达一个谓词 Prov(n),含义是"编号为 n 的命题在这个系统里可证"。这个谓词本身是一个算术命题,完全合法。

现在的任务是:构造一个命题 G,使它在逻辑上等价于 ¬Prov(⌜G⌝),也就是"我自己在这个系统里不可证"。

这看起来像循环定义——G 的内容涉及 G 自身的编号,而 G 的编号取决于 G 是什么。怎么可能先写出 G,再谈论 G 的编号?

对角化引理解决的正是这个结。

对角化引理:自指是怎么在数学里合法实现的?

对角化(Diagonalization)是哥德尔、图灵等人用来构造自指命题的核心技巧,名字来自康托尔的对角线论证。

直觉版本:假设你有一张无限大的表格,行和列都是自然数。你想构造一个"不在表格任何一行里"的对象——方法是:取第1行第1列的元素,改一下;取第2行第2列的元素,改一下;以此类推,沿对角线改。这个新对象和表格的每一行都至少差一个位置,所以不在表格里。

在哥德尔证明里:把这个思想用在"公式引用自身"上——构造一个公式 D(y),当 y 是 D 本身的哥德尔编号时,D(y) 就在谈论 D(y) 自己。通过 sub 替换函数,这个循环可以被"展开"成没有循环的算术操作。

结果:A≡P(⌜A⌝)——命题 A 在谈论自己是否有性质 P,完全合法,无循环。

先考虑一个一元谓词 P(x),其中 x 是一个自然数(也就是某个命题的哥德尔编号)。我们想找到一个命题 A,使得 A 等价于 P(⌜A⌝)——也就是说,A 在谈论"命题 A 自身满足性质 P"。

构造分两步。

第一步:引入替换函数。 定义一个算术函数 sub(m,n),表示"把编号为 m 的公式里的自由变量替换为数字 n 后,所得公式的哥德尔编号"。这是一个纯算术操作——输入两个数,输出一个数——皮亚诺算术完全能表达它。

第二步:写出自指公式。 取谓词 P(x),考虑下面这个含自由变量 y 的公式:

D(y)≡P(sub(y,y))

D(y) 说的是:"把编号为 y 的公式里的自由变量替换为 y 本身后,所得命题满足 P。"

现在计算 D 自身的哥德尔编号,记作 d=⌜D⌝。把 d 代入 D(y),得到命题:

A≡D(d)≡P(sub(d,d))

关键观察:sub(d,d) 是"把 D(y) 里的自由变量替换为 d 后所得公式的编号"——而那个公式正是 D(d),也就是 A 本身。所以 sub(d,d)=⌜A⌝,于是:

A≡P(⌜A⌝)

A 在谈论自己是否满足性质 P,没有循环,没有预设 A 的编号——编号是通过 sub 函数在构造过程中自然产生的。

把 P(x) 取为 ¬Prov(x),所得的 A 就是哥德尔句 G:

G≡¬Prov(⌜G⌝)

G 的意思是:"编号为 ⌜G⌝ 的命题——也就是我自己——在这个系统里不可证。"

G 不是比喻,不是哲学表态,而是皮亚诺算术里一个明确写出的算术命题,其内容恰好描述了它自身的可证状态。

现在来看 G 的命运。分两种情况讨论:

若 G 可证:则 Prov(⌜G⌝) 为真,即 ¬G 为真,即系统同时证明了 G 和 ¬G。系统不一致。

若 G 不可证:则 ¬Prov(⌜G⌝) 为真,即 G 本身为真——它确实在系统里不可证,正如它自己所说。但系统无法证明这件事。

所以,在系统一致的前提下,G 不可证。而且 G 实际上是真的——我们从系统外部能看出这一点,但系统内部永远触及不到它。

¬G 呢?若 ¬G 可证,则系统声称 G 可证,但我们已经知道 G 不可证——系统在对自己的可证性撒谎,这同样破坏了一致性。

结论:在一致的系统里,G 既不可证,也不可反驳。它是一个不可判定的命题——真实的,但超出了系统的推理射程。

这是整个论证里最微妙的一步。我们说"G 实际上是真的",依据的是在元层次上的推理:我们在系统之外论证了系统是一致的,从而得出 G 不可证,从而得出 G 为真。但这个元层次的论证,本身也是在某个更强的系统里进行的。哥德尔没有找到"绝对的真",他只是证明了:对于任何足够强的系统,总存在需要爬出这个系统才能看见的真理。层次是真实的,而且没有顶端。


15.6 第二定理:系统无法为自己担保 ​

第二不完备定理是第一个定理的一个推论,但它的冲击力不亚于第一个。

把"系统 F 是一致的"这件事,用哥德尔编号编码为一个算术命题,记作 Con(F)。

第一定理的证明过程本身可以在系统内部被形式化——因为证明过程是有限的符号操作,而系统能表达算术。形式化之后,得到:

F⊢Con(F)→¬Prov(⌜G⌝)

也就是说,系统自己能证明:"如果我是一致的,那么 G 不可证。"

现在假设系统还能证明自身一致,即 F⊢Con(F)。把这两件事用假言推理组合起来,系统就能证明 G 不可证——但 G 不可证等价于 G 本身,于是系统证明了 G,与第一定理矛盾。

因此,系统不可能证明自身的一致性。

这不是谦虚,也不是能力不足。这是逻辑的结构性事实:你无法用一把尺子测量这把尺子本身是否准确。任何关于系统一致性的证明,都必须来自一个更强的外部系统,而那个更强系统的一致性又是一个悬而未决的问题——这个层级没有顶端。

真正震撼的是第二定理说的不是"很难",而是"原则上不可能"——不是工程问题,是逻辑结构问题。一个系统对自身一致性的证明,永远需要一个更强的外部系统背书。没有顶端。这才是重点,不是那把尺子的比喻。

实话实说:我们不能证明。数学界接受 ZFC 的理由是:它用了将近一百年,产生了大量相互一致的结果,没有出现矛盾。这是归纳推理,不是演绎证明。哥德尔第二定理告诉我们,这也是我们能做到的最好程度。数学的地基不是一块被证明无误的磐石,而是一个被反复压测、至今未裂的支撑结构。这个区别,比大多数数学课承认的要重要。


15.7 Hilbert 纲领的终结与遗产 ​

Hilbert 的目标是建立一个完备、一致、可判定的数学基础。两个不完备定理说明了:

  • 完备性:在足够强的一致系统里,不可能实现。
  • 一致性的自我保证:不可能在系统内部完成。
  • 可判定性:图灵 1936 年证明了不可能,这是第19章的故事。

三项目标,全军覆没。

Hilbert 纲领的失败是科学史上最有价值的失败之一。正是因为他把目标定得足够精确,哥德尔和图灵才能精确地证明那些目标不可达。如果 Hilbert 说的是"数学应该有个好的基础",就没有什么可以反驳,也没有什么可以学习。精确的问题,才能得到精确的否定答案——而精确的否定答案,比模糊的肯定答案更有价值。

但这不是悲剧的终点,而是一个更清醒认识的起点。Hilbert 纲领的失败没有让数学崩溃,而是让数学家更精确地知道了边界在哪里。边界之内,形式系统依然是人类历史上最可靠的知识建构工具。边界之外,是永久的开放问题——有些命题的真假,永远取决于你选择接受哪些公理。

这种清醒,比盲目的乐观更有价值。


15.8 动手实践:算术被形式化是什么感觉 ​

本章一直在说"足够强的系统"——强到能表达算术。这不是抽象的描述。皮亚诺算术(PA)是这样一个系统,它有五条关于自然数的公理。在进入"悬而未决"之前,先花几分钟真实接触它。

皮亚诺公理(非形式版本):

  1. 0 是自然数。
  2. 每个自然数 n 都有唯一的后继 S(n),也是自然数。
  3. 0 不是任何自然数的后继(即不存在 n 使得 S(n)=0)。
  4. 不同的自然数有不同的后继:若 S(m)=S(n),则 m=n。
  5. 数学归纳原理:若某个性质对 0 成立,且对任意 n 成立时对 S(n) 也成立,则它对所有自然数成立。

在这五条公理里,加法可以被定义出来:

m+0=mm+S(n)=S(m+n)

这不是约定,是定义——加法的全部行为由这两条递归方程决定。


练习:用这个定义,推出 1+1=2。

首先约定符号:1=S(0),2=S(S(0))。

1+1=S(0)+S(0)=S(S(0)+0)=S(S(0))=2

每一步用了哪条定义?第一步是展开符号,第二步用了加法的第二条定义(m+S(n)=S(m+n),其中 m=S(0),n=0),第三步用了加法的第一条定义(m+0=m),第四步是展开符号。

这就是 1+1=2 的形式证明。它不依赖任何直觉,只依赖两个递归方程和皮亚诺公理。


现在感受一下这个系统"足够强"是什么意思:它能表达所有关于自然数的初等陈述——"存在无穷多个质数"、"每个偶数是两个质数之和(哥德巴赫猜想)"、甚至"这个系统本身是否一致"——都可以在 PA 的语言里被写成公式。正是这种表达能力,让哥德尔的对角化引理得以发挥。一个系统能谈论自己,是因为它能谈论所有足够复杂的数论陈述——而关于自身的陈述,是数论陈述的一个特例。


悬而未决 ​

G 是"真"的,但在哪个意义上? 我们从系统外部看出 G 为真,但这个"外部"依赖一个更强的系统,而那个系统有自己的 G。"真"是一个绝对的概念,还是总是相对于某个系统?

不完备性与停机问题是同一件事吗? 哥德尔和图灵都通过自指构造建立了边界,两者在结构上高度相似。递归函数论给出了部分答案——它们确实是同一枚硬币的两面——但这个故事的全貌在第19章才会展开。

能否逃出不完备性? 把 G 加入公理得到更强的系统,但新系统有自己的哥德尔句。把那个也加进去,如此往复。这个超限层级有没有极限?答案是肯定的,但极限本身是什么,是现代集合论的前沿问题。

不完备性是由哪条结构规则造成的? 第14章列出了三条在后台默默运行的结构规则:弱化、收缩、交换。哥德尔定理的存在,根植于系统足够强——而"足够强"依赖于假设可以被任意重复使用。如果我们质疑这一点——如果每个假设只能用一次——推理会变成什么?这是第16章的起点。


思考题 ​

★ 热身

对角化引理的核心是替换函数 sub(m,n)。对以下描述判断正误:

  1. sub(m,n) 的输入是两个自然数,输出也是一个自然数。(对/错?)
  2. sub(⌜D⌝,⌜D⌝) 的结果,是把公式 D 里的自由变量替换为公式 D 本身之后的哥德尔编号。(对/错?)
  3. 哥德尔编号的具体方式(比如用质数幂乘积还是别的编码)会影响第一不完备定理的结论。(对/错?)

(这三道题的目的是确认:哥德尔编号是算术操作,不依赖编码方式的选择。)


★★ 推导

把哥德尔句 G("我在系统 F 中不可证")作为新公理加入 F,得到 F′=F+{G}。

  1. F′ 还是一致的吗?(提示:G 在 F 中不可证意味着什么?把 G 加进去会和 F 的其他定理矛盾吗?)
  2. F′ 有自己的哥德尔句 G′ 吗?G′ 和 G 是同一个命题吗?为什么不是?
  3. 这个过程可以无限重复。把所有这样的哥德尔句全部加入,得到的极限系统是否完备?试着用自然语言解释为什么答案是否定的——完备性逃不掉。

★★★ 挑战

第二不完备定理说:F 无法在自身内部证明 Con(F)。但我们(在更强的外部系统里)确实可以论证 F 是一致的——比如,通过构造一个使所有 F 的公理为真的模型。

试着用本章的语言写出:这个"外部论证"本身依赖什么?它用了哪个更强系统的一致性?这个更强系统的一致性,又依赖什么?

这个问题没有终点,但试着把无穷退回的结构写清楚——用 F、F1、F2……的符号链条表示。这个链条的存在,对"数学有没有最终的基础"这个问题意味着什么?

不需要解决这些问题——只需要想清楚为什么每个问题都比看起来的更难。