习题5.1 (1)前面说过,公式aVB,aAB和彐a是分别作为(-a)→B),(-(a→(-B)和 (-Vx(-a)的缩写而引入的。根据定义找出(a,s)}(aB),(a,s)}(a∧B)和 (Ql,s)=3ra的意义 (2)证明:卜xyp(x)→彐rp(x)。[注:这似乎是“无中生有”。你在证明中用到结构是 非空的吗? (3)判断下列命题的对错并给出证明或反例。固定一个一阶语言L。 (a)对于任意L的结构纵和闭语句σ,或者}a或者}-σ (b)对任意的闭语句a,或者a或者}o。 (4)证明rU{a}φ当且仅当r(a→y) (5)举例说明:在}a当且仅当}B的条件下,不一定有卡a+B。 (6)证明下列的任何语句都不被其它两个语义蕴涵。 (a) Var'Vyva(Pxy→(Pyz→Prz) (b)avgy(Pry→(Pyx→x≈y) (c) rdy pry→3 yVa Pay (你可以构造结构,使得一个语句在该结构为假,但其它两个语句为真。 (7)假定n1是公式y(n1)中唯一的自由变元并且d是论域|w|中的元素。我们用符 号划=d表示对所有赋值函数s,(2,s2)y(1)。证明 =2Q1t22当且仅当a=2Qc2 这里Q为一个二元谓词符号并且c为常数符号。[本题的目的是适应一下新的符号, 它是模型论中常用的,我们在谈论可定义性时也会用到。 (8)证明{wr(α→),vra}}ⅥrB。[这是后面可靠性定理证明的一部分。]
习题 5.1. (1) 前面说过，公式 α ∨ β，α ∧ β 和 ∃xα 是分别作为 ((¬α) → β)，(¬(α → (¬β))) 和 (¬∀x(¬α)) 的缩写而引入的。根据定义找出 (A, s) |= (α ∨ β)，(A, s) |= (α ∧ β) 和 (A, s) |= ∃xα 的意义。 (2) 证明：|= ∀xφ(x) → ∃xφ(x)。[注：这似乎是“无中生有”。你在证明中用到结构是 非空的吗?] (3) 判断下列命题的对错并给出证明或反例。固定一个一阶语言 L。 (a) 对于任意 L 的结构 A 和闭语句 σ，或者 A |= σ 或者 A |= ¬σ。 (b) 对任意的闭语句 σ，或者 |= σ 或者 |= ¬σ。 (4) 证明 Γ ∪ {α} |= φ 当且仅当 Γ |= (α → φ)。 (5) 举例说明：在 |= α 当且仅当 |= β 的条件下，不一定有 |= α ↔ β。 (6) 证明下列的任何语句都不被其它两个语义蕴涵。 (a) ∀x∀y∀z(P xy → (P yz → P xz))。 (b) ∀x∀y(P xy → (P yx → x ≈ y))。 (c) ∀x∃yP xy → ∃y∀xP xy。 （你可以构造结构，使得一个语句在该结构为假，但其它两个语句为真。） (7) 假定 v1 是公式 φ(v1) 中唯一的自由变元并且 d 是论域 | A | 中的元素。我们用符 号 A |= φ[d] 表示对所有赋值函数 s，(A, sv1 d ) |= φ(v1)。证明 A |= ∀v2Qv1v2[c A ] 当且仅当 A |= ∀v2Qcv2。 这里 Q 为一个二元谓词符号并且 c 为常数符号。[本题的目的是适应一下新的符号， 它是模型论中常用的，我们在谈论可定义性时也会用到。] (8) 证明 {∀x(α → β), ∀xα} |= ∀xβ。[这是后面可靠性定理证明的一部分。] 1
(9)证明:如果x不在a中自由出现,则a上ra[这也是后面可靠性定理证明的一部 分。] (10)证明:公式x≈y→PJfx→Pzfy是普遍有效的,其中∫是一个一元函数符号并 且P是一个二元谓词符号。 (11)证明公式θ是普遍有效的当且仅当ⅵrθ是普遍有效的。[这也是后面可靠性定理证 明的一部分 (12)证明:}彐x(Px→xPx)。[在习题??中,我们证明了它在语法中相应的命题 彐r(Px→arPx),这种语义和语法的对应是可靠性和完全性定理的一个特例。 习题52. (1)证明满足下列闭语句的结构为一个群 VrVyVz(ro(yora(roy)oz); vry3z(xoz≈y (2)找出一个闭语句σ使得对任何正整数n,σ都有具有恰好2n个元素的模型;并且σ 没有恰好奇数个元素的有穷模型。你可以假定语言中含有等词,并可随意挑选其它 符号 (3)假定语言L中有等词,并且有两个二元函数符号+和×。对下列的集合和关系,分 别找出在结构(N,+,×)中定义它的公式。 (a) (b){1}。 (c){(m,n):n是m在N中的后继} (d){(m,n):m<n},其中<是N上的自然序。 (4)假定语言L中包含等词并且有一个二元谓词P。对下列条件分别找出L中的闭语句 a使得结构(=(,P3)是a的一个模型当且仅当该条件成立。 (a)|有且仅有两个元素
(9) 证明：如果 x 不在 α 中自由出现，则 α |= ∀xα。[这也是后面可靠性定理证明的一部 分。] (10) 证明：公式 x ≈ y → P zfx → P zfy 是普遍有效的，其中 f 是一个一元函数符号并 且 P 是一个二元谓词符号。 (11) 证明公式 θ 是普遍有效的当且仅当 ∀x θ 是普遍有效的。[这也是后面可靠性定理证 明的一部分。] (12) 证明：|= ∃x(P x → ∀xP x)。[在习题 ?? 中，我们证明了它在语法中相应的命题 ⊢ ∃x(P x → ∀xP x)，这种语义和语法的对应是可靠性和完全性定理的一个特例。] 习题 5.2. (1) 证明满足下列闭语句的结构为一个群： ∀x∀y∀z (x ◦ (y ◦ z) ≈ (x ◦ y) ◦ z); ∀x∀y∃z (x ◦ z ≈ y); ∀x∀y∃z (z ◦ x ≈ y)。 (2) 找出一个闭语句 σ 使得对任何正整数 n，σ 都有具有恰好 2n 个元素的模型；并且 σ 没有恰好奇数个元素的有穷模型。你可以假定语言中含有等词，并可随意挑选其它 符号。 (3) 假定语言 L 中有等词，并且有两个二元函数符号 + 和 ×。对下列的集合和关系，分 别找出在结构 (N, +, ×) 中定义它的公式。 (a) {0}。 (b) {1}。 (c) {(m, n) : n 是 m 在 N 中的后继}。 (d) {(m, n) : m < n}，其中 < 是 N 上的自然序。 (4) 假定语言 L 中包含等词并且有一个二元谓词 P。对下列条件分别找出 L 中的闭语句 σ 使得结构 A(= (| A |, P A )) 是 σ 的一个模型当且仅当该条件成立。 (a) | A | 有且仅有两个元素。 2
(b)P是一个从|到||的函数。 (c)P是||到自身的一个一一对应。 习题5.3 (1)证明同态定理中的(a)部分。 (2)找出所有在结构(R,<)中可定义的(a)R的子集;(b)R上的二元关系。并证明你的 结论。 (3)证明加法函数的图像{(m,n,p):p=m+n}(作为三元关系)在结构(N,)中不可 定义。提示:找一个结构(N,)上的把两个素数“互换”的自同构 (4)令L={≈,}其中。为一个二元函数符号。对下列L的结构分别给出一个闭语句, 使其在一个结构内成立,而在另三个结构中不成立。因此它们两两互不初等等价。 (a)(R;x)其中x是实数上通常的乘法; (b)(歐*;×")其中R*是非零实数的集合,x*是×在R*上的限制 (c)(N:+)其中+是自然数上通常的加法 (d)(P;+*)其中P是正整数的集合,+*是+在P上的限制 (5)令L={≈,P}其中P为一个二元谓词符号。考察结构(P,|)其中P是正整数的集 合,并且|为整除关系。 (a)所有素数的集合在该结构中可定义吗?为什么? (b)通常的小于关系a<b在该结构中可定义吗?为什么? (6)(a)假定语言L中除了等词之外仅有一个二元谓词P。证明如果是一个L上的 有穷结构,并且W≡男,则与9同构 (b)证明(a)对任何包含等词的语言都成立 [注:这说明我们有能力“完全刻画”有穷的结构。]
(b) P A 是一个从 | A | 到 | A | 的函数。 (c) P A 是 | A | 到自身的一个一一对应。 习题 5.3. (1) 证明同态定理中的 (a) 部分。 (2) 找出所有在结构 (R, <) 中可定义的 (a) R 的子集；(b) R 上的二元关系。并证明你的 结论。 (3) 证明加法函数的图像 {(m, n, p) : p = m + n} （作为三元关系）在结构 (N, ·) 中不可 定义。提示：找一个结构 (N, ·) 上的把两个素数“互换”的自同构。 (4) 令 L = {≈, ◦} 其中 ◦ 为一个二元函数符号。对下列 L 的结构分别给出一个闭语句， 使其在一个结构内成立，而在另三个结构中不成立。因此它们两两互不初等等价。 (a) (R; ×) 其中 × 是实数上通常的乘法； (b) (R ∗ ; ×∗ ) 其中 R ∗ 是非零实数的集合，×∗ 是 × 在 R ∗ 上的限制； (c) (N; +) 其中 + 是自然数上通常的加法； (d) (P; +∗ ) 其中 P 是正整数的集合，+∗ 是 + 在 P 上的限制。 (5) 令 L = {≈, P} 其中 P 为一个二元谓词符号。考察结构 (P, |) 其中 P 是正整数的集 合，并且 | 为整除关系。 (a) 所有素数的集合在该结构中可定义吗？为什么？ (b) 通常的小于关系 a < b 在该结构中可定义吗？为什么？ (6) (a) 假定语言 L 中除了等词之外仅有一个二元谓词 P。证明如果 A 是一个 L 上的 有穷结构，并且 A ≡ B，则 A 与 B 同构。 (b) 证明 (a) 对任何包含等词的语言都成立。 [注：这说明我们有能力“完全刻画”有穷的结构。] 3
(7)令C为一个固定的语言、为C的一个结构并且B是论域||的一个子集。我们 称||的一个子集D为以中用B里的参数可定义的如果存在一个自然数k 个C公式p(x,,,…,k-1)其中x,v,y,……,孙k-1为的全部自由变元,和元素 bo,b1,…,bk-1∈B使得 D={a∈|{a,bo,b1 l]} 考察结构(R,<)。固定R的一个子集B。证明一个集合A是(R,<)中用B里的参数 可定义的当且仅当A是有穷多个以B里的元素为端点的区间的并。注意:这里“区 间”和“端点”的定义留给读者。证明中如果需要某些自同构的性质,也希望读者 自行将其表达清楚并证明。 (8)假定X为||的一个子集并且在结构%的所有自同构下不变,X一定是上可定 义的吗?
(7) 令 L 为一个固定的语言、A 为 L 的一个结构并且 B 是论域 | A | 的一个子集。我们 称 | A | 的一个子集 D 为A 中用 B 里的参数可定义的 如果存在一个自然数 k、一 个 L-公式 φ(x, y0, y1, · · · , yk−1) 其中 x, y0, y1, · · · , yk−1 为 φ 的全部自由变元，和元素 b0, b1, · · · , bk−1 ∈ B 使得 D = {a ∈| A |:|=A φ[a, b0, b1, · · · , bk−1]}。 考察结构 (R, <)。固定 R 的一个子集 B。证明一个集合 A 是 (R, <) 中用 B 里的参数 可定义的当且仅当 A 是有穷多个以 B 里的元素为端点的区间的并。注意: 这里“区 间”和“端点”的定义留给读者。证明中如果需要某些自同构的性质，也希望读者 自行将其表达清楚并证明。 (8) 假定 X 为 | A | 的一个子集并且在结构 A 的所有自同构下不变，X 一定是 A 上可定 义的吗? 4