\[ \def\Th{\mathrm{Th}} \def\Cn{\mathrm{Cn}} \def\Mod{\mathrm{Mod}} \def\A{\mathfrak{A}} \def\B{\mathfrak{B}} \def\N{\mathfrak{N}} \def\K{\mathcal{K}} \]
本节知识点
理论是逻辑蕴涵意义下封闭的句子集合，\(T\) 是一个理论当且仅当 \(T\) 是一些句子的集合，该集合使得语言中的任意句子 \(\sigma\)， \[ T \models \sigma \Rightarrow \sigma \in T \] 注意：我们仅指句子，而不是带有自由变量的公式。
对语言的结构类 \(\K\)，定义其理论为（记作 \(\Th \ \K\)） \[ \Th \ \K = \set{ \sigma | \sigma \ 在 \ \K \ 的每个元素中都是真的} \] 这一概念由先前的特殊情况 \(\K = \set{\A}\) 而来。
对于句子集合 \(\Sigma\)，定义 \(\Mod \ \Sigma\) 为 \(\Sigma\) 所有模型的类。\(\Th \ \Mod \ \Sigma\) 则是在 \(\Sigma\) 的所有模型中都是真的的所有句子的集合。称此集合为 \(\Sigma\) 的推论集，记作 \(\Cn \ \Sigma\)，这样 \[ \Cn \Sigma = \set{\sigma | \Sigma \models \sigma} \\ = \Th \ \Mod \ \Sigma \] 一个句子集合是一个理论当且仅当 \(T = \Cn \ T\)。
一个理论 \(T\) 称为完备的，当且仅当对每个句子 \(\sigma\)，或者 \(\sigma \in T\)，或者 \((\lnot \sigma) \in T\)，
理论 \(T\) 是有限可公理化的当且仅当对于某个有限句子集合 \(\Sigma\)，\(T = \Cn\ \Sigma\)。
定义 \(L_0\) 在 \(T_1\) 中的解释 \(\pi\) 是 \(L_0\) 的参数集上的一个函数，满足
- \(\pi\) 把 \(L_1\) 中的一个公式 \(\pi_\forall\) 指派给 \(\forall\)，\(\pi_\forall\) 中至多只有 \(v_1\) 是自由出现的，使得
\[ T_1 \models \exists v_1 \pi_\forall \]
其中的思想是，
- $ T_1 v_1 v_n (_v(v_1) v(v_n) $ $ x (v(x) v{n+1} (f(v_1,,v{n+1}) v{n+1}=x))) . $ (2) \(\pi\) 为每个 \(n\) 元谓词参量 \(P\) 指派了 \(L_1\) 中的一个公式 \(\pi_P\), 公式中至多只有 \(v_1,\cdots,v_n\) 是自由出现的. (3) \(\pi\) 为每个 \(n\) 元函数符号 \(f\) 指派了 \(L_1\) 中的一个公式 \(\pi_f\), 公式中至多只有 \(v_1,\cdots,\) \(v_n,v_{n+1}\) 是自由出现的，使得 $ T_1 v_1 v_n (_v(v_1) v(v_n) $ $ x (v(x) v{n+1} (f(v_1,,v{n+1}) v{n+1}=x))) . $ 换句话说，\(\pi_c\) 定义了一个单点，它也在 \(\pi_v\) 定义的集合中。
紧致性定理：
- 如果 \(\Gamma \vdash \varphi\)，那么存在某个有限的 \(\Gamma_0 \subseteq \Gamma\)，有 \(\Gamma_0 \vdash \varphi\)；
- 如果 \(\Gamma\) 的每个有限子集 \(\Gamma_0\) 都是可满足的，那么 \(\Gamma\) 是可满足的。特别地，句子集 \(\Sigma\) 有模型当且仅当其每个有限子集有模型。
教材 2.6 理论的模型
习题 5（不考）：给出与如下公式等价的前束公式 \[ (a) (\exists x A x \land \exists x B x) \to Cx \]
其前束公式为： \[ \exists y \exists z ((Ay \land Bz) \to Cx) \]
习题 7：考虑带有二元谓词符号 \(<\) 的语言，设 \(\N = (\mathbb{N}; <)\) 是包含（通常序的）自然数的结构。证明：存在某个初等等价于 \(\N\) 的 \(\A\)，使得 \(<^\A\) 具有降序链。（即在 \(|\A|\) 中存在 \(a_0, a_1, \cdots\)，使得对所有 \(i\) 有 \(\langle a_{i+1}, a_i \rangle \in <^\A\)。）
提示：应用紧致性定理。
说明：该习题的目的在于说明在这个语言中无法表达“不存在降序链。”
证明：构造 \(<^\A\)：\(\langle a^\A, b^\A \rangle \in <^\A\) 当且仅当 \(\langle b^\N, a^\N \rangle \in <^\N\)。显然 \(\A \equiv \N\)，且在 \(\A\) 中存在 \(<^\A\) 的降序链，该降序链 \(a_0, a_1, \cdots\) 对应的正是 \(\N\) 中的升序链。
\(Q.E.D.\)
习题 10：设有一个不带函数符号的有限语言，
（a）（不考）证明：可满足的 \(\exists_2\) 句子集是可判定的（术语及相关背景见 2.2 节的习题 19）；
（b）证明：恒真的 \(\forall_2\) 句子集是可判定的。（\(\forall_2\) 公式是指具有形式 \[\forall x_1 \dots \forall x_m \exists y_1 \dots \exists y_n \theta\] 的公式，其中 \(\theta\) 是无量词的公式。）
说明：在一阶逻辑中，“判定问题”（Entscheidungs 问题）就是在给定一个公式后判定其是否恒真。由于丘奇定理（3.5 节），这一问题通常是无解的。这个习题给出的是判定问题中的一个可解的情形。
证明：我们知道 \(\exists_2\) 句子是可满足的，当且仅当其在一个有限模型内是可满足的。在先前的习题中，我们可以判定它是否有任意模型，即其是否可满足。
证明：\(\sigma\) 是一个可行的 \(\forall_2\) 句子，当且仅当 \(\lnot \sigma\) 是不可满足的。通过 (a)，我们知道它是可判定的。
教材 2.7 理论之间的解释（不考）
习题 1：假设 \(L_0\) 和 \(L_1\) 含有相同参量的语言，但 \(L_0\) 中有一个 \(n\) 元函数符号 \(f\) 不在 \(L_1\) 中，同时 \(L_1\) 中有一个 \((n + 1)\) 元谓词符号 \(P\) 不在 \(L_0\) 中。证明对于 \(L_0\) 的任意理论 \(T\)，存在一个忠实解释将 \(T\) 解释到 \(L_1\) 上。
证明：简单来说，忠实解释是指能够保持理论 \(T\) 中所有公式的真假值不变的解释。
要证明对于 \(L_0\) 的任意理论 \(T\)，存在一个忠实解释将 \(T\) 解释到 \(L_1\) 上，我们可以通过构造一个从 \(L_0\) 到 \(L_1\) 的忠实解释来实现。
构造过程
定义解释映射：首先，我们需要定义一个映射，将 \(L_0\) 中的项和公式转换为 \(L_1\) 中对应的项和公式。对于 \(L_0\) 中的项，如果它们不涉及函数符号 \(f\)，则直接对应到 \(L_1\) 中相同的项。对于涉及 \(f\) 的项，如 \(f(t_1, t_2, ..., t_n)\)，我们定义其在 \(L_1\) 中的对应项为 \(t\)，其中 \(P(t_1, t_2, ..., t_n, t)\) 成立。这实际上是在说，对于 \(L_0\) 中的每一组输入 \(t_1, t_2, ..., t_n\)，在 \(L_1\) 中存在一个输出 \(t\)，使得 \(P\) 关系成立。
定义公式转换：接下来，我们需要定义如何将 \(L_0\) 中的公式转换为 \(L_1\) 中的公式。对于不涉及 \(f\) 的原子公式，可以直接对应到 \(L_1\) 中相同的原子公式。对于形如 \(f(t_1, t_2, ..., t_n) = s\) 的原子公式，我们将其转换为 \(L_1\) 中的公式 \(P(t_1, t_2, ..., t_n, s)\)。对于复合公式，按照标准的逻辑运算符的转换规则进行转换。
验证忠实性：最后，我们需要验证这个解释是忠实的，即它保持了 \(L_0\) 中的所有公式的真假值。这意味着，如果一个公式在 \(L_0\) 下是真（或假）的，那么经过解释后，在 \(L_1\) 下它也应该保持同样的真假值。这可以通过结构归纳法来证明，首先证明对于原子公式这一点成立，然后逐步扩展到所有复杂的公式。
忠实性的证明
- 对于原子公式，如 \(f(t_1, t_2, ..., t_n) = s\)，在 \(L_0\) 下它为真意味着 \(f\) 在输入 \(t_1, t_2, ..., t_n\) 时确实产生输出 \(s\)。在 \(L_1\) 下，这意味着存在一个元素 \(s\) 使得 \(P(t_1, t_2, ..., t_n, s)\) 为真，这与原始的原子公式在 \(L_0\) 下的意义是一致的。
- 对于复合公式，忠实性可以通过逻辑运算符的性质和原子公式的忠实性来保证。例如，如果一个合取式在 \(L_0\) 下为真，那么它的每个组成部分在 \(L_0\) 下也为真，根据忠实性，这些组成部分在 \(L_1\) 下也应为真，因此整个合取式在 \(L_1\) 下也为真。
综上所述，通过这种方式构造的解释是一个忠实的解释，它可以将 \(L_0\) 的任意理论 \(T\) 解释到 \(L_1\) 上，而不会改变公式的真假值。
\(Q.E.D.\)
习题 2：设 \(L_0\) 是含有等号及二元函数符号 \(+\) 和 \(\cdot\) 的语言，\(L_1\) 也一样，只不过用三元谓词符号表示加法和乘法。令 \(\mathfrak{M}_i = (\mathbb{N};+, \cdot)(i = 0, 1)\) 分别是包含自然数和加法、乘法的语言 \(L_i\) 的结构。证明在 \(\mathfrak{M}_0\) 中由 \(L_0\) 公式定义的任何关系都能在 \(\mathfrak{M}_1\) 中由 \(L_1\) 公式定义。
证明：假设非空的 \(n\) 元关系 \(R\) 可以由 \(L_0\) 公式 \(\phi\) 在 \(\N_0\) 中定义（对于空关系结论显而易见）。
考虑 \(\pi\) 从 \(L_0\) 参数集到 \(L_1\) 公式集中的映射，使得 \(\pi_\vee = v_1 = v_1\) ，\(\pi_+ = +v_1v_2v_3\) 和 \(\pi_\cdot = \cdot v_1v_2v_3\) 。因为 \(\exists v_1v = v_1\) ，\(\forall v_1\forall v_2\exists x\forall v_3 +v_1v_2v_3 \leftrightarrow v_3 = x\) ，以及 \(\forall v_1\forall v_2\exists x\forall v_3 \cdot v_1v_2v_3 \leftrightarrow v_3 = x\) 在 \(\N_1\) 中为真，所以 \(\pi\) 是 \(\N\) 的 \(L_0\) 到 \(\Th \N_1\) 的解释，并且 \(\N_1\) 是 \(\Th\N_1\) 的模型。
于是，\(|^\pi\N_1| = \mathbb{N}\) ，\(a + ^{^\pi\N_1} b = c\) 当且仅当 \(+^{\N_1}abc\) 当且仅当 \(a + b = c\) ，以及 \(a \cdot^{^\pi\N_1} b = c\) 当且仅当 \(\cdot^{\N_1}abc\) 当且仅当 \(a \cdot b = c\) ，表明 \(^\pi\N_1 = \N_0\) 。但是，对于每一个 \(s:V \to \mathbb{N}\) ，\(\models_{\N_0} \phi[s]\) 当且仅当 \(\models_{^\pi\N_1}[s]\) 当且仅当 \(\models_{\N_1} \phi^n[s]\) （引理 27B）。这意味着 \(R\) 可以在 \(\N_1\) 中由 \(\phi^n\) 定义。
\(Q.E.D.\)
