习题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