第9章哥德尔第一不完全性定理 第1节可表示性 引理92.对所有m,n∈N,我们有 1)+var(Sx+n≈x+Sn) (2)+m+n≈Smn+0并且}mn≈Sm"0 (3)如果n≠m则+nm。 4)如果m≤n则}m≤n 5)如果mxn则+mzn 6+vr(x≤n4x≈0V…Vr≈n) 7)+vx(x≤nvn≤x)o 证明:见习题 引理92告诉我们一些有关Q模型的事实,后面我们会用到。令9为任意一个Q的 模型。 ·由引理92(2)和(3)我们有:函数n→n是从标准模型9到模型9的一个嵌入。 因此,我们可以不失一般性地假设9c9t ·还有(6)告诉我们:如果b∈9并且a<b,则a∈9。换句话说,9中所有的新 元素都是缀在9后面的;表述这种情形的术语为9是9的一个尾节扩张。 912可表示性 令T为一个包含Q的理论。在下面的讨论中,如果不加说明,则可隐含地假定理论 T为Q。 定义91.我们称一个自然数上的k元关系P为在T中数码逐点可表示的3或简称为可表 示的,如果存在一个公式p(),称为P的一个表示公式,使得 (m1,n2,…,nk)∈P→Thp(n1,n2,…,nk);并且 (m1,n2,…,nk)gP→T=p(n,n2,…,nk) 例9.2.(1)自然数上的等同关系{(m,m):n∈N}被公式x≈y所表示:显然,m=n蕴 涵}m≈n,并且根据引理9.2(3),m≠n蕴涵}m≠n (2)类似地,引理9.2(4和(5告诉我们关系≤可以被公式x≤y表示 数码逐点可表示的, numeralwise representable;可表示的, representable第 9 章 哥德尔第一不完全性定理 第 1 节 可表示性 引理 9.2. 对所有 m, n ∈ N，我们有 (1) ⊢ ∀x(Sx + n ≈ x + Sn)。 (2) ⊢ m + n ≈ S m+n 0 并且 ⊢ m · n ≈ S m·n 0。 (3) 如果 n ̸= m 则 ⊢ n ̸≈ m。 (4) 如果 m ≤ n 则 ⊢ m ≤ n。 (5) 如果 m ̸≤ n 则 ⊢ m ̸≤ n。 (6) ⊢ ∀x(x ≤ n ↔ x ≈ 0 ∨ · · · ∨ x ≈ n)。 (7) ⊢ ∀x(x ≤ n ∨ n ≤ x)。 证明: 见习题。 引理 9.2 告诉我们一些有关 Q 模型的事实，后面我们会用到。令 M 为任意一个 Q 的 模型。 • 由引理 9.2 (2) 和 (3) 我们有：函数 n 7→ n M 是从标准模型 N 到模型 M 的一个嵌入。 因此，我们可以不失一般性地假设 N ⊆ M。 • 还有 (6) 告诉我们：如果 b ∈ N 并且 a ≤M b，则 a ∈ N。换句话说，M 中所有的新 元素都是缀在 N 后面的；表述这种情形的术语为 M 是 N 的一个尾节扩张。 9.1.2 可表示性 令 T 为一个包含 Q 的理论。在下面的讨论中，如果不加说明，则可隐含地假定理论 T 为 Q。 定义 9.1. 我们称一个自然数上的 k-元关系 P 为在 T 中数码逐点可表示的 3 或简称为可表 示的 ，如果存在一个公式 ρ(⃗x)，称为 P 的一个表示公式，使得 (n1, n2, · · · , nk) ∈ P ⇒ T ⊢ ρ(n1, n2, · · · , nk); 并且 (n1, n2, · · · , nk) ̸∈ P ⇒ T ⊢ ¬ρ(n1, n2, · · · , nk)。 例 9.2. (1) 自然数上的等同关系 {(n, n) : n ∈ N} 被公式 x ≈ y 所表示：显然，m = n 蕴 涵 ⊢ m ≈ n，并且根据引理 9.2 (3)，m ̸= n 蕴涵 ⊢ m ̸≈ n。 (2) 类似地，引理 9.2 (4) 和 (5) 告诉我们关系 ≤ 可以被公式 x ≤ y 表示。 3数码逐点可表示的，numeralwise representable；可表示的，representable。 3