习题91. (1)证明引理?。 (2)(a)证明对任一自然数n∈N,Qhwa日2(x+z≈n)+30(+x≈n)]。 (b)证明: QHVrVyl3a(x+2≈y)+(+x≈y) (c)证明:QHⅵrvy(x+y≈y+x)。 注:在自然数标准模型中,关系x≤y既可以定义成彐x(x+z=y)也可以定义成 彐u(+x=y)。但由于Q不满足加法交换律,我们必须更加小心。 (3)证明教材中的断言:P在Th(9)中被p表示当且仅当P在结构9中被ρ定义 (4)教材中的Q的Σ1完备性(定理??)的证明用了模型论的方法,你能不能给一个直 接的证明? (5)证明引理??。 (6)令T=Q和f(x)=9(h(x),其中h(x)=0是由公式y(x,y)=dy+y≈y表示、 9()=2是由公式v(u,2) (≈0Vu+u米u)Az≈2][u≈0Aa+u≈Az≈1 来表示,都作为关系来表示。验证定理??证明中使用的公式 vu(yp(x,)→v(u,z) 并不作为关系表示f(x)=9(h(x)=2。 (7)令P≤Ⅳ为一个k-元关系。证明P作为一个关系是可表示的当且仅当它的特征函 数xP作为一个函数是可表示的。[这是可表示性定理证明的一部分。] 习题92 (1)证明替换函数Sb(a,b,c)是原始递归的。 (2)给出“a是=b”、“a是b→c”和“a是yb”的定义,并验证它们可以是原始递归 的
习题 9.1. (1) 证明引理 ??。 (2) (a) 证明对任一自然数 n ∈ N，Q ⊢ ∀x[∃z(x + z ≈ n) ↔ ∃w(w + x ≈ n)]。 (b) 证明：Q ̸⊢ ∀x∀y[∃z(x + z ≈ y) ↔ ∃w(w + x ≈ y)]。 (c) 证明：Q ̸⊢ ∀x∀y(x + y ≈ y + x)。 注：在自然数标准模型中，关系 x ≤ y 既可以定义成 ∃z(x + z = y) 也可以定义成 ∃w(w + x = y)。但由于 Q 不满足加法交换律，我们必须更加小心。 (3) 证明教材中的断言：P 在 Th (N) 中被 ρ 表示当且仅当 P 在结构 N 中被 ρ 定义。 (4) 教材中的 Q 的 Σ1 完备性（定理 ??）的证明用了模型论的方法，你能不能给一个直 接的证明？ (5) 证明引理 ??。 (6) 令 T = Q 和 f(x) = g(h(x))，其中 h(x) = 0 是由公式 φ(x, y) =df y + y ≈ y 表示、 g(u) = 2 是由公式 ψ(u, z) [(u ≈ 0 ∨ u + u ̸≈ u) ∧ z ≈ 2] ∨ [u ̸≈ 0 ∧ u + u ≈ u ∧ z ≈ 1] 来表示，都作为关系来表示。验证定理 ?? 证明中使用的公式 ∀u(φ(x, u) → ψ(u, z)) 并不作为关系表示 f(x) = g(h(x)) = 2。 (7) 令 P ⊆ N k 为一个 k-元关系。证明 P 作为一个关系是可表示的当且仅当它的特征函 数 χP 作为一个函数是可表示的。[这是可表示性定理证明的一部分。] 习题 9.2. (1) 证明替换函数 Sb(a, b, c) 是原始递归的。 (2) 给出“a 是 ¬b”、“a 是 b → c”和“a 是 ∀yb”的定义，并验证它们可以是原始递归 的。 1
(3)定义关系“a是b的一个全称概括”并验证它可以是原始递归的。 习题93. (1)令B(v1)为Ca中表达“n1是素数”的公式。具体找出B(1)的一个不动点,即,找 到一个闭语句σ,使得QσB(a)。 (2)任给两个公式A0(1,t)和B1(1,),其中只有变元n1和t自由出现。证明我们可 以能行地找到两个闭语句a和o1使得 Q+a分(o03,「a12)并且 Q}a1+B1(03,a1) 提示:模仿不动点引理的证明。你可以从下列公式着手:θ(v1,v2,v3,t4),它作为函 数表示递归函数(址a,n,m)→ta(n,m)并对i=0,1,考察 r(v1,t2):=Vta3t4[(1,t1,,t3)→(t2,t1,t2,)→A(tv3,v) 习题9.4 (1)证明集合{a:Q∪{}是心-相容的}是一个I3-集合 (2)证明不存在递归的集合R使得{a:Qha}sR并且{to:Q-a}≤N\R (3)假如有人宣称证明了哥德巴赫猜想是独立于PA(哥德巴赫猜想可以叙述为:任何 大于4的偶数都是两个素数之和)。证明该人事实上已经证明了(在标准自然数模 型上)哥德巴赫猜想成立。 习题10.1. (1)证明:如果T是∽-相容的,则(D1)的逆命题也成立。 习题10.2 (1)验证下列事实。 (a)(强归纳法) PAVr(y<x)y(y)→g(x)→ry(x) (b)(最小数原理) PA彐r(x)→r(v(x)∧(wy<x)=t(y)
(3) 定义关系“a 是 b 的一个全称概括”并验证它可以是原始递归的。 习题 9.3. (1) 令 β(v1) 为 Lar 中表达“v1 是素数”的公式。具体找出 β(v1) 的一个不动点，即，找 到一个闭语句 σ，使得 Q ⊢ σ ↔ β(pσq)。 (2) 任给两个公式 β0(v1, v2) 和 β1(v1, v2)，其中只有变元 v1 和 v2 自由出现。证明我们可 以能行地找到两个闭语句 σ0 和 σ1 使得 Q ⊢ σ0 ↔ β0(pσ0 q, pσ1 q) 并且 Q ⊢ σ1 ↔ β1(pσ0 q, pσ1 q)。 提示: 模仿不动点引理的证明。你可以从下列公式着手：θ(v1, v2, v3, v4)，它作为函 数表示递归函数 (♯α, n, m) 7→ ♯ α(n, m) 并对 i = 0, 1，考察 τi(v1, v2) := ∀v3∀v4 [θ(v1, v1, v2, v3) → θ(v2, v1, v2, v4) → βi(v3, v4)]。 习题 9.4. (1) 证明集合 {♯σ : Q ∪ {σ} 是 ω-相容 的 } 是一个 Π3-集合。 (2) 证明不存在递归的集合 R 使得 {♯σ : Q ⊢ σ} ⊆ R 并且 {♯σ : Q ⊢ ¬σ} ⊆ N \ R。 (3) 假如有人宣称证明了哥德巴赫猜想是独立于 PA （哥德巴赫猜想可以叙述为：任何 大于 4 的偶数都是两个素数之和）。证明该人事实上已经证明了（在标准自然数模 型 N 上）哥德巴赫猜想成立。 习题 10.1. (1) 证明：如果 T 是 ω-相容的，则 (D1) 的逆命题也成立。 习题 10.2. (1) 验证下列事实。 (a) （强归纳法） ⊢PA ∀x((∀y < x)φ(y) → φ(x)) → ∀xφ(x)。 (b) （最小数原理） ⊢PA ∃xψ(x) → ∃x(ψ(x) ∧ (∀y < x)¬ψ(y))。 2
(c)(有界性原理) HPA (Va u3ye(, y)-+3z (Vr vey 2)0(a, y) 这里的φ、ψ和θ都是算术语言Car中的公式。[显然我们的目的不是考察机械证明, 因此可以不必太形式化。 (2)验证PA+(pme(p)Apab)→( plav plb)。 (3)(a)对每个自然数x,令E表示由所有的满足下列条件的∑1公式(vn,v2)所构成 的集合:在PA中存在一个编码小于x的关于13t2(1,v2)的证明。证明 f(ar)=max(uz)(Vu a)02 <2)001, 02)1 是一个递归(全)函数 (b)证明(在N上)存在非可证递归的递归函数。 习题10.3. (1)验证下列断言 (a)}su≈t→口r{Su≈t (b)u×t≈→口r{u×v≈ (c)假定φ+口回并且口证明yVp口ryV [这是引理??证明的一部分。] 习题10. (1)假定a和?为Ca中的闭语句,满足≡r口→a。证明 (a)口≡r口a (b)y≡ra→a [注:本题在第二不完全性定理和勒布定理的证明中都被隐含地用到。有些教科书 (如 Rautenberg[?])把它所为一个引理。] (2)证明:对任何公式a,+r-conr→口a。[这可以看作是“如果T是不相容的 则T可以证明任何公式a”的形式化版本。]
(c) （有界性原理） ⊢PA (∀x < v)∃yθ(x, y) → ∃z(∀x < v)(∃y < z)θ(x, y)。 这里的 φ、ψ 和 θ 都是算术语言 Lar 中的公式。[显然我们的目的不是考察机械证明， 因此可以不必太形式化。] (2) 验证 PA ⊢ (prime(p) ∧ p|ab) → (p|a ∨ p|b)。 (3) (a) 对每个自然数 x，令 Ex 表示由所有的满足下列条件的 Σ1 公式 θ(v1, v2) 所构成 的集合：在 PA 中存在一个编码小于 x 的关于 ∀v1∃!v2θ(v1, v2) 的证明。证明： f(x) = max θ∈Ex {(µz) (∀v1 ≤ x) (∃v2 < z) θ(v1, v2)} 是一个递归（全）函数。 (b) 证明（在 N 上）存在非可证递归的递归函数。 习题 10.3. (1) 验证下列断言： (a) ⊢ Su ≈ v → T[Su ≈ v]； (b) ⊢ u × v ≈ w → T[u × v ≈ w]； (c) 假定 φ ⊢ T[φ] 并且 ψ ⊢ T[ψ]。证明 φ ∨ ψ ⊢ T[φ ∨ ψ]。 [这是引理 ?? 证明的一部分。] 习题 10.4. (1) 假定 α 和 γ 为 Lar 中的闭语句，满足 γ ≡T γ → α。证明： (a) γ ≡T α。 (b) γ ≡T α → α。 [注：本题在第二不完全性定理和勒布定理的证明中都被隐含地用到。有些教科书 （如 Rautenberg [?]）把它所为一个引理。] (2) 证明：对任何公式 α，⊢T ¬conT → Tα。[这可以看作是“如果 T 是不相容的， 则 T 可以证明任何公式 α”的形式化版本。] 3
(3)证明:PAH一 Ipaconpa。[尽管“ conPA在PA中是不可证的”,它不能按以上方式形 式化在PA中。] (4)证明形式化的演绎定理:令T"=T+a。则 rr+口r(a→y)
(3) 证明：PA ̸⊢ ¬PAconPA。[尽管“conPA 在 PA 中是不可证的”，它不能按以上方式形 式化在 PA 中。] (4) 证明形式化的演绎定理：令 T ′ = T + α。则 ⊢T T′φ ↔ T (α → φ)。 4