习题8.1. (1)令∑1和Σ2为两个闭语句集,使得没有模型能够同时满足∑1和Σ2。证明存在一个 闭语句r使得Mod∑1 C t并且Mod∑2Modr。[这说明:不相交的广义 初等类可以被一个初等类分开。 (2)证明pAx<y分Sx≤y,并且卜pAx≤y∨y≤x。[这里关于PA的练习,请不要 利用任何其它的知识。] (3)(假定读者了解一些集合论)令为ZFC的一个模型。证明存在ZFC的一个模 型使得|是|的一个子集,并且存在一个U属于1使得对所有的中的 元素a,都有a∈U 习题8.2. (1)证明引理??。 (2)证明康托尔定理:任何可数的无端点的稠密线序都同构于(Q,<Q),换言之, Th(Q,<)是N0-范畴的 (3)证明有端点的稠密线序理论Th(Q∩0,1),<)、Th(Qn(0,1,<)和Th(Q∩0,1,<)都 分别是No-范畴的,因而也是完全的。此外,再验证它们和Th(Q,<)是稠密线序理 论仅有的四个完全扩张 (4)证明:特征为0的域的理论是可公理化的,但不可有穷公理化。 (5)假定两个理论T1和T2满足(i)n1T2,(i)T是完备的,还有(i)T2是可满足的。 证明T1=T2 习题83. (1)证明塔尔斯基引理(引理??)。 (2)证明:理论Ts被下列公理公理化:(S1)和(S2)加上对语言Cs={0,s}的归纳公理 模式 (0)Ar(yp(x)→y(S) 其中p是任意的语言Cs上的公式
习题 8.1. (1) 令 Σ1 和 Σ2 为两个闭语句集，使得没有模型能够同时满足 Σ1 和 Σ2。证明存在一个 闭语句 τ 使得 Mod Σ1 ⊆ Mod τ 并且 Mod Σ2 ⊆ Mod ¬τ。[这说明：不相交的广义 初等类可以被一个初等类分开。] (2) 证明 ⊢PA x < y ↔ Sx ≤ y，并且 ⊢PA x ≤ y ∨ y ≤ x。[这里关于 PA 的练习，请不要 利用任何其它的知识。] (3) （假定读者了解一些集合论）令 A 为 ZFC 的一个模型。证明存在 ZFC 的一个模 型 B 使得 |A| 是 |B| 的一个子集，并且存在一个 U 属于 |B| 使得对所有的 |A| 中的 元素 a，都有 a ∈ B U。 习题 8.2. (1) 证明引理 ??。 (2) 证明康托尔定理：任何可数的无端点的稠密线序都同构于 (Q, <Q)，换言之， Th (Q, <) 是 ℵ0-范畴的。 (3) 证明有端点的稠密线序理论 Th (Q∩[0, 1), <)、Th (Q∩(0, 1], <) 和 Th (Q∩[0, 1], <) 都 分别是 ℵ0-范畴的，因而也是完全的。此外，再验证它们和 Th (Q, <) 是稠密线序理 论仅有的四个完全扩张。 (4) 证明：特征为 0 的域的理论是可公理化的，但不可有穷公理化。 (5) 假定两个理论 T1 和 T2 满足 (i) T1 ⊆ T2，(ii) T1 是完备的，还有 (iii) T2 是可满足的。 证明 T1 = T2。 习题 8.3. (1) 证明塔尔斯基引理（引理 ??）。 (2) 证明：理论 TS 被下列公理公理化：(S1) 和 (S2) 加上对语言 LS = {0, S} 的归纳公理 模式: [φ(0) ∧ ∀x(φ(x) → φ(Sx))] → ∀xφ(x), 其中 φ 是任意的语言 LS 上的公式。 1
(3)证明T5不能被有穷公理化。 (4)证明:自然数N的一个子集在结构9s中可定义当且仅当或者它是有穷的或者它 在N中的补集是有穷的。 (5)证明序关系{m,n):mn,证明T5+Smx≈S"xsm-)x≈0。再用等式的性 质证明断言1对7s成立。 (b)如果a是形如Smx≠t,其中m为自然数,t1为不含变元x的项,则 Tsh+r(a1A…∧an) 即断言2对Ts成立。 (c)Tsh丑r(Smx≈t)+(t0A…At≠Sm-10)。再证明断言3对Ts成立 习题8 (1)证明:对任意基数λ,Thξ都不是λ-范畴的。[所以,我们无法使用乌什-沃特判 别法 (2)证明定理??中的断言4 (3)给出一个具体的反例,说明子情形23中v的后半句∧S0<v是不能少的。提 示:适当选择项α使得满足前半句的x是负数。 (4)证明:加法函数的图像{(m,m,p):m+n=p}在结构9中是不可定义的。 (5)证明下列的闭语句属于公理集A<的定理集T<。 (a)V.(e<Sc) (b)var(x大x) (c)vvgy(x大y+y≤x) (d)rwgy(x<y分Sx<Sy) (e)(S1):0≈Sr
(3) 证明 TS 不能被有穷公理化。 (4) 证明：自然数 N 的一个子集在结构 NS 中可定义当且仅当或者它是有穷的或者它 在 N 中的补集是有穷的。 (5) 证明序关系 {⟨m, n⟩ : m n，证明 TS ⊢ S mx ≈ S n x ↔ S (m−n) x ≈ 0。再用等式的性 质证明断言 1 对 TS 成立。 (b) 如果 αi 是形如 S mix ̸≈ ti，其中 mi 为自然数，ti 为不含变元 x 的项，则 TS ⊢ ∃x(α1 ∧ · · · ∧ αn)。 即断言 2 对 TS 成立。 (c) TS ⊢ ∃x(S mx ≈ t) ↔ (t ̸≈ 0 ∧ · · · ∧ t ̸≈ S m−1 0)。再证明断言 3 对 TS 成立。 习题 8.4. (1) 证明：对任意基数 λ，Th N< 都不是 λ-范畴的。[所以，我们无法使用乌什 -沃特判 别法。] (2) 证明定理 ?? 中的断言 4。 (3) 给出一个具体的反例，说明子情形 2.3 中 ψ 的后半句 ∧ j S nj 0 < uj 是不能少的。提 示：适当选择项 u 使得满足前半句的 x 是负数。 (4) 证明：加法函数的图像 {(m, n, p) : m + n = p} 在结构 N< 中是不可定义的。 (5) 证明下列的闭语句属于公理集 A< 的定理集 T<。 (a) ∀x(x < Sx)。 (b) ∀x(x ̸< x)。 (c) ∀x∀y(x ̸< y ↔ y ≤ x)。 (d) ∀x∀y(x < y ↔ Sx < Sy)。 (e) (S1)：0 ̸≈ Sx。 2
(1)(S2):Sx≈Sy→x≈y (g)对任意n≥1,(S4n):A<nSr;≈x+1→0xn 其中(S1)、(S2)和(S4n)为上一节rs的公理。特别地,TscT<。 (6)证明:T<接受量词消去
(f) (S2)：Sx ≈ Sy → x ≈ y。 (g) 对任意 n ≥ 1，(S4.n)： ∧ i<n Sxi ≈ xi+1 → x0 ̸≈ xn。 其中 (S1)、(S2) 和 (S4.n) 为上一节 TS 的公理。特别地，TS ⊂ T<。 (6) 证明：T< 接受量词消去。 3