EagleBear2002 的博客

这里必须根绝一切犹豫,这里任何怯懦都无济于事

数理逻辑-第 6 次作业

\[ \def\A{\mathfrak{A}} \def\B{\mathfrak{B}} \]

教材 2.2 真值与模型

习题 13:证明同态定理的 (a)。

\(h\) 是从 \(\A\)\(\B\) 中的同态,\(s\) 将变量的集合映射到 \(|\A|\) 中。

  1. 对每个项 \(t\),我们有 \(h(\overline{s}(t)) = \overline{h \circ s}(t)\),其中 \(\overline{s}(t)\) 是在 \(\A\) 中计算的,而 \(\overline{h \circ s}(t)\) 是在 \(\B\) 中计算的;

影印版教材中同态定理的横线印刷不清晰,本题中的表述是正确的。

证明:对于常量 \(c\)\(h(\overline{s}(c)) = h(c^\A) = c^\B = \overline{h \circ s}(c)\)

对于变量 \(x\)\(h(\overline{s}(t)) = h(s(x)) = h \circ s(x) = \overline{h \circ s}(x)\)

对于 \(n\) 元函数函数 \(f\),按照归纳,

\[ h(\overline{s}(f t_1 \dots t_n)) = h(f^\A(\overline s(t_1), \dots, \overline s(t_n))) \\ = f^\B(h(\overline{s}(t_1)), \dots, h(\overline{s}(t_n))) \\ = f^\B(\overline{h \circ s}(t_1), \dots, \overline{h \circ s}(t_n)) \\ = \overline{h \circ s}(ft_1 \dots t_n) \]

\(Q.E.D.\)

习题 18:全称公式 (\(\forall_1\)) 是形式为 \(\forall x_1 \cdots x_n \theta\) 的公式,存在公式 (\(\exists_1\)) 是形式为 $ x_1 x_n $ 的公式,其中 $ $ 是无量词。设 $ $ 是 \(\B\) 的子结构,$ s: V || $。

  1. 证明:如果 \(\vDash_\A \psi[s]\)\(\psi\) 是存在公式,那么 \(\vDash_\B \psi[s]\)。如果 \(\vDash_\B \varphi[s]\)\(\varphi\) 是全称公式,那么 \(\vDash_\A \varphi[s]\)

说明:(a) 的意思是(当 \(\varphi\) 是句子时)任何全称句子 \(\varphi\) 在子结构中都可以保持。由于全称是语法性质,其必定与符号串相关。反过来,在子结构中保持则是语义性质,其必定与结构相关。但是这一语义性质保持了逻辑等价的语法性质(这正是我们所需要的)。即,如果句子 \(\sigma\) 在子结构中总是成立,那么 \(\sigma\) 逻辑等价于全称句子(这一点要归功于洛斯和塔斯基)。

证明:我们假设 $_x_1 x_n $,于是对于每个 \(d_1, \dots, d_n \in |\B|\)\(\vDash_\B \theta[s(x_i|d_i)_{i=1}^n]\)

这意味着,对于每个 \(d_1, \dots, d_n \in |\A|\)\(\vDash_\B \theta[s(x_i|d_i)_{i=1}^n]\)。因此,对每个 \(d_1, \dots, d_n \in |\A|\)\(\vDash_\A \theta[s(x_i|d_i)_{i=1}^n]\)。等价地,\(\vDash_\A \forall x_1 \dots \forall x_n \theta [s]\)

用同样的证明方法,我们假设 \(\vDash_\A \exists x_1 \dots \exists x_n \theta [s]\),则存在 \(d_1, \dots, d_n \in |\A|\)\(\vDash_\A \theta[s(x_i|d_i)_{i=1}^n]\)。进而存在 \(d_1, \dots, d_n \in |\B|\)\(\vDash_\B \theta[s(x_i|d_i)_{i=1}^n]\)。可推出 \(\vDash_\B \exists x_1 \dots \exists x_n \theta [s]\)

\(Q.E.D.\)

习题 20:设语言有等号和二元谓词符号 \(P\)。考虑两个结构 \((\mathbb{N}, <), (\mathbb{R}, <)\)。试找出一个句子,它在一个结构中是真的,在另外一个中是假的。

直观来说,\((\mathbb{N}, <)\) 中存在“相邻”的两个数而 \((\mathbb{R},<)\) 中不存在。“相邻”可以被形式化描述为“这两个数之间没有其他的数”。我们使用公式来表达这一性质:

\[ \forall x \exists y \forall z \lnot(x < z \land z < y) \]

习题 22:设 \(\A\) 是结构且 \(h\) 是函数,\(\mathrm{ran} h = |\A|\)。证明存在结构 \(\B\) 使得 \(h\) 是一个从 \(\B\)\(\A\) 上的同态。提示:取 \(|\B| = \mathrm{dom} h\)。一般地,需要使用选择公理在 \(\B\) 中定义函数,除非 \(h\) 是一对一的。

证明:取 \(|\B| = \mathrm{ran} h\),则 \(h:|\B| \to |\A|\) 是满射。对每个 \(a \in \A\),使用选择公理定义 \(G(a) = \set{b \in |\B| | h(b) = a}\),定义 \(g(a)\)\(G(a)\) 中的任意一个元素(例如,某个全序下的最小元素)。接下来,我们可以根据对同态的定义构造 \(\B\) 中的谓词参数、常数符号函数符号对应的元素:

\[ \langle b_1, \dots, b_n\rangle \in P^\B \iff \langle h(b_1), \dots, h(b_n)\rangle \in P^\A \\ c^\B = g(c^\A) \\ f^\B(b_1, \dots, b_n) = g(f^\A(h(b_1), \dots, h(b_n))) \]

以上定义的 \(\B\) 显然使得 \(h\) 为同态。

\(Q.E.D.\)

教材 2.3 解析算法

习题 1:对于合式公式 \(\alpha\) 的任意真的初始段 \(\alpha'\)\(K(\alpha) < 1\)

证明:对波兰记法下的 \(\alpha\) 使用归纳法。

  1. \(\alpha = (\lnot \beta)\),有以下几种情况:
    • \(\alpha' = (\)\(K(\alpha') = -1\)
    • \(\alpha' = (\lnot\)\(K(\alpha') = 0\)
    • \(\alpha' = (\lnot \beta'\)\(K(\alpha') \le -1\)
    • \(\alpha' = (\lnot \beta\)\(K(\alpha') = -1\)
  2. \(\alpha = (\beta \land \gamma)\),有以下几种情况:
    • \(\alpha' = (\)\(K(\alpha') = -1\)
    • \(\alpha' = (\beta'\)\(K(\alpha') \le -1\)
    • \(\alpha' = (\beta\)\(K(\alpha') = 0\)
    • \(\alpha' = (\beta \land\)\(K(\alpha') = -1\)
    • \(\alpha' = (\beta \land \gamma'\)\(K(\alpha') \le -1\)
    • \(\alpha' = (\beta \land \gamma\)\(K(\alpha') \le 0\)

因此,总有 \(K(\alpha') \le 0\)

\(Q.E.D.\)

习题 2:设 \(\varepsilon\) 是包含变量、常数符号和函数符号的表达式。证明:\(\varepsilon\) 是项当且仅当 \(K(\varepsilon) = 1\) 且对 \(\varepsilon\) 的任意终段 \(\varepsilon'\),我们有 \(K(\varepsilon') > 0\)。提示:证明更强一些的结果:如果对 \(\varepsilon\) 的任意终段 \(\varepsilon'\)\(K(\varepsilon') > 0\),那么 \(\varepsilon\)\(K(\varepsilon)\) 个项的连接。

证明:先证充分性。由引理 23A,\(K(\varepsilon) = 1\)。由引理 23B,对 \(\varepsilon\) 的任意终段 \(\varepsilon'\),我们有 \(K(\varepsilon') > 0\)

再证必要性。

\(\varepsilon\) 归纳。若 \(\varepsilon\) 长度为 1,则为变量或常数符号,命题显然成立。

\(\varepsilon\) 长度超过 1,由 \(K(\varepsilon) = 1\) 且对 \(\varepsilon\) 的任意终段 \(\varepsilon'\)\(K(\varepsilon') > 0\),可知必然存在至少一个 \(n\) 元函数符号 \(f\)

若只存在一个 \(n\) 元函数符号 \(f\),则由 \(K(\varepsilon) = 1\)\(\varepsilon\) 中必然存在 \(n\) 个变量或常数符号,由 \(K(\varepsilon') \ge 1\) 知这些变量符号必然都出现在 \(\varepsilon\) 右端。命题成立。

\(\varepsilon\) 中函数符号的个数归纳,由 \(K(\varepsilon) = 1\) 且对 \(\varepsilon\) 的任意终段 \(\varepsilon'\)\(K(\varepsilon') > 0\),可知 \(\varepsilon\) 必然以 \(n\) 元函数符号开始,且函数符号后恰好有 \(n\) 项。

\(Q.E.D.\)