第1节可表示性 第9章哥德尔第一不完全性定理 我们看一些可表示性的简单性质 ·如果P是可表示的,则P是递归的。 证明:对给定的自然数组,递归地枚举所有Q(或任何递归的公理系统T)中 的证明序列,直到p(n或p()的证明出现。如果是前者,则P(n)成立;后者, 则P(可)不成立。可表示性告诉我们该证明一定会出现。 ·可表示的关系在布尔运算下是封闭的。 证明:假设P和Q分别由公式p1和P表示。则PUQ、P∩Q和Ⅳ\P分别由公 式p1VP2、p1AP2和→p1来表示 如果P在Q中被公式p表示,则P在Q的任何相容扩张(例如,PA或Th(9)中 都被p表示。 P在Th(9)中被ρ表示当且仅当P在结构?中被ρ定义。 证明:练习。 定理9(Q的∑1完备性).对任一∑1-闭语句r,我们有 9F7当且仅当Q+T。 注 我们称一个Car中的公式为△0的,如果它只包含有界量词。我们称一个形 如彐x1…丑xn6的公式为∑1的,其中θ是△0的。一个∑1公式的否定总是逻辑 等价于一个形如Vx1…VxnO的公式,我们称这样的公式是I1的。而如果一个公式 机即等价于一个∑1公式又等价于一个∏1公式,我们就称之为△1的。 ·引理9.1告诉我们对I1-闭语句,如x(Sx≈x),我们则没有这种完备性 证明:由于“←”立刻可以从犷是Q的一个模型导出,我们下面证明另一个方向“→” 断言对任何△o-闭语句σ,对任何Q的模型,我们有9a当且仅当9a 断言的证明我们对σ进行归纳。首先注意:对任何一个闭项t(即,t中不含自由变元) 我们有=。因此断言对任何的原子闭公式成立。不难证明对于不含量词(无论有界 或无界的)的闭语句r断言也成立。 给定任意的形如(wx≤t)(x)的闭公式a,其中t是一个闭项,并假定9}(wx≤ f)e(x)。则对所有的a<,都有9}6(a)。移到模型中来讨论,我们有tm第 1 节 可表示性 第 9 章 哥德尔第一不完全性定理 我们看一些可表示性的简单性质： • 如果 P 是可表示的，则 P 是递归的。 证明: 对给定的自然数组 ⃗n，递归地枚举所有 Q （或任何递归的公理系统 T）中 的证明序列，直到 ρ(⃗n) 或 ¬ρ(⃗n) 的证明出现。如果是前者，则 P(⃗n) 成立；后者， 则 P(⃗n) 不成立。可表示性告诉我们该证明一定会出现。 • 可表示的关系在布尔运算下是封闭的。 证明: 假设 P 和 Q 分别由公式 ρ1 和 ρ2 表示。则 P ∪ Q、P ∩ Q 和 N k \ P 分别由公 式 ρ1 ∨ ρ2、ρ1 ∧ ρ2 和 ¬ρ1 来表示。 • 如果 P 在 Q 中被公式 ρ 表示，则 P 在 Q 的任何相容扩张（例如，PA 或 Th (N)）中 都被 ρ 表示。 • P 在 Th (N) 中被 ρ 表示当且仅当 P 在结构 N 中被 ρ 定义。 证明: 练习。 定理 9.1 (Q 的 Σ1-完备性). 对任一 Σ1-闭语句 τ，我们有 N |= τ 当且仅当 Q ⊢ τ。 注： • 我们称一个 Lar 中的公式为 ∆0 的，如果它只包含有界量词。我们称一个形 如 ∃x1 · · · ∃xn θ 的公式为 Σ1 的，其中 θ 是 ∆0 的。一个 Σ1 公式的否定总是逻辑 等价于一个形如 ∀x1 · · · ∀xnθ 的公式，我们称这样的公式是 Π1 的。而如果一个公式 机即等价于一个 Σ1 公式又等价于一个 Π1 公式，我们就称之为 ∆1 的。 • 引理 9.1 告诉我们对 Π1-闭语句，如 ∀x(Sx ̸≈ x)，我们则没有这种完备性。 证明: 由于“⇐”立刻可以从 N 是 Q 的一个模型导出，我们下面证明另一个方向“⇒”。 断言. 对任何 ∆0-闭语句 σ，对任何 Q 的模型 M，我们有 M |= σ 当且仅当 N |= σ。 断言的证明. 我们对 σ 进行归纳。首先注意：对任何一个闭项 t （即，t 中不含自由变元）， 我们有 t N = t M。因此断言对任何的原子闭公式成立。不难证明对于不含量词（无论有界 或无界的）的闭语句 τ 断言也成立。 给定任意的形如 (∀x ≤ t)θ(x) 的闭公式 σ，其中 t 是一个闭项，并假定 N |= (∀x ≤ t)θ(x)。则对所有的 a ≤N t N，都有 N |= θ(a)。移到模型 M 中来讨论，我们有 t M = 4