(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