\[ \def\Th{\mathrm{Th}} \def\A{\mathfrak{A}} \def\B{\mathfrak{B}} \]
本节知识点
可靠性定理：如果 \(\Gamma \vdash \varphi\)，那么 \(\Gamma \models \varphi\)。
引理 25A：逻辑公理都是恒真的。
完备性定理（哥德尔 1930）：
- 如果 \(\Gamma \models \varphi\)，那么 \(\Gamma \vdash \varphi\)。
- 任意和谐的公式集都是可满足的。
紧致性定理：
- 如果 \(\Gamma \vdash \varphi\)，那么存在某个有限的 \(\Gamma_0 \subseteq \Gamma\)，有 \(\Gamma_0 \vdash \varphi\)。
- 如果 \(\Gamma\) 的每个有限子集 \(\Gamma_0\) 都是可满足的，那么 \(\Gamma\) 是可满足的。特别地，句子集 \(\Sigma\) 有模型当且仅当其每个有限子集有模型。
可枚举定理：
对合理的语言，恒真（valid）合式公式的集合是能行可枚举的。
定理 26A：如果句子集合 \(\Sigma\) 有任意大的计数的有限模型，那么就有一个无限模型。
定理 26C：对有限语言中的有限结构 \(\A\)，\(\Th \ \A\) 是可判定的。
教材 2.5 可靠性与完备性理论
习题 1：（语义规则 EI）假设常数符号 \(c\) 不在 \(\varphi\)、\(\psi\) 和 \(\Gamma\) 中出现，\(\Gamma; \varphi_c^x \models \psi\)，证明：\(\Gamma; \exists x \varphi \models \psi\)。（不使用可靠性定理和完备性定理。）
证明：该规则将推论 24H 中的 \(\vdash\) 换成了 \(\models\)，该题应该从语义方面证明而不是从语法方面。
\(\Gamma ; \varphi^{x}_c \models \psi \iff\) 对任意 \(\A\) 和 \(s\)，如果 \(\models_{\A} \Gamma[s]\) 且 \(\models_{\A} \varphi^{x}_{c}[s]\)，则 \(\models_{\A} \psi[s]\)；
\(\iff\) 对任意 \(\A\) 和 \(s\)，如果 \(\models_{\A} \Gamma[s]\) 且 \(\nvDash_{\A} \psi[s]\)，则 \(\models_{\A} \neg \varphi[s(x|c^{\A})]\)
\(\iff\) 对任意 \(\A\) 和 \(s\)，如果 \(\models_{\A} \Gamma[s]\) 且 \(\nvDash_{\A} \psi[s]\)，则对所有 \(d \in |\A|\) 有 \(\models_{\A} \neg \varphi[s(x|d)]\)
\(\iff\) 对任意 \(\A\) 和 \(s\)，如果 \(\models_{\A} \Gamma[s]\) 且 \(\nvDash_{\A} \psi[s]\)，则 \(\models_{\A} \forall x \neg \varphi[s]\)
\(\iff\) \(\Gamma ; \neg \forall x \neg \varphi \models \psi\)
\(\iff \Gamma; \exists x \varphi \models \psi\)；
上述证明完成了“在 \(\A\) 中把 \(x\) 替换成 \(c^\A\)” 这件事。
\(Q.E.D.\)
习题 2：证明完备性定理 (a) 与 (b) 等价。提示：\(\Gamma \vdash \varphi\) 当且仅当 \(\Gamma \cup \{\neg \varphi\}\) 是不可满足的，且 \(\Delta\) 是可满足的当且仅当 \(\Delta \nvDash \bot\)，其中 \(\Delta\) 是某个不可满足的、可批驳的公式集，如 \(\neg \forall x x = x\)。
说明：类似地，可靠性定理也适用于每个可满足的公式集是和谐的。
证明：在计算机学科中，consistent 被翻译为“一致的”。
先证充分性。若 (a) 成立。若 \(\Gamma\) 不可满足，则 \(\Gamma \models \set{\phi, \lnot \phi}\)，因此 \(\Gamma \vdash \set{\phi, \lnot \phi}\)，即 \(\Gamma\) 不和谐。推出 (b) 的逆否命题。
再证必要性。若 (b) 成立。若 \(\Gamma \models \phi\)，则对任意 \(\A, s\)，\(\models_\A \Gamma[s] \implies \models_\A \phi[s]\) 即 \(\not\models_\A \lnot\phi[s]\)。即 \(\Gamma ; \lnot \phi\) 是不可满足的，也因此是不和谐的。导出矛盾，因此 \(\Gamma \vdash \phi\)。
\(Q.E.D.\)
习题 3：设 \(\Gamma \vdash \varphi\)，且 \(P\) 是不在 \(\Gamma\) 和 \(\varphi\) 中出现的谓词符号。是否存在不出现 \(P\) 的从 \(\Gamma\) 到 \(\varphi\) 的演绎？提示：这个问题有两种不同的方法。“软”方法使用两个不同的语言，一个含有 \(P\)，另一个不含 \(P\)；“硬”方法则考虑是否能够可以从 \(\Gamma\) 到 \(\varphi\) 的演绎中消去 \(P\)。
必然存在不出现 \(P\) 的从 \(\Gamma\) 到 \(\varphi\) 的演绎。
证明：使用“软”方法完成证明。
对于一个不含 \(P\) 的语言，在该语言中 \(\Gamma \vdash \varphi\)，存在不出现 \(P\) 的从 \(\Gamma\) 到 \(\varphi\) 的演绎，设该演绎为 \(q\)。对于包含 \(P\) 的语言，\(q\) 同样是该语言中一个从 \(\Gamma\) 到 \(\varphi\) 的演绎。
\(Q.E.D.\)
习题 4：设 \(\Gamma = \{ \neg \forall v_1 Pv_1, Pv_2, Pv_3, \dots \}\)，\(\Gamma\) 是否和谐？是否可满足？
证明：假设 \(\A = (\set{0,1};P)\)，其中 \(P^\A = \set{\langle 1 \rangle}\)，且 \(s :V \to |\A|\) 使得 \(\forall i>0s(v_i) = 1\)。于是 \(\models_\A Pv_i[s], \models_\A P v_1[s(v_1|1)]\) 并且 \(\not\models_\A P v_1[s(v_1|0)]\)。
因此 \(\Gamma\) 可满足。由可靠性和完备性定理得，\(\Gamma\) 是和谐的。
\(Q.E.D.\)
教材 2.6 理论的模型
习题 1：证明下述句子是有限恒真的（即在每个有限结构中是真的）： \[ (a) \exists x \exists y \exists z [(Pxf x \rightarrow Pxx) \lor (Pxy \land Pyz \land \lnot Pxz)] \] 提示：这些句子的逆的任意模型都是无限的。
证明：题中的 negation 在计算机科学中一般被翻译为“否定”而不是“逆”。
题中公式的含义是，在论域中存在一个 \(x\)，使得 \(Pxfx \rightarrow Pxx\) 或者“\(P\) 在 \(x\) 处不传递”。
本题的证明中反复使用了 6 条公理和概化公理。
我们按照一阶逻辑的规则对句子的逆进行恒等变形：
\[ \neg \exists x \exists y \exists z \big((Pxf x \to Pxx) \lor (Pxy \land Pyz \land \neg Pxz)\big)\\ \iff \neg \exists x \exists y \exists z \big[\lnot (Pxf x \to Pxx) \rightarrow (Pxy \land Pyz \land \neg Pxz) \big]\\ \iff \neg \exists x \big[\neg (Pxf x \to Pxx) \rightarrow \exists y \exists z (Pxy \land Pyz \land \neg Pxz \big]\\ \iff \forall x \neg \big[\lnot (Pxf x \to Pxx) \rightarrow \exists y \exists z (Pxy \land Pyz \land \neg Pxz) \big]\\ \iff \forall x \big[\neg (Pxf x \to Pxx) \land \neg \exists y \exists z (Pxy \land Pyz \land \neg Pxz)\big]\\ \iff \forall x \big[Pxf x \land \neg Pxx \land \forall y \forall z (\neg Pxy \lor \neg Pyz \lor Pxz)\big]\\ \iff \forall x \big[Pxf x \land \neg Pxx \land \forall y \forall z (Pxy \to (Pyz \to Pxz))\big] \]
如果 \(\A\) 是该句子的模型，我们有：
\[ \Th \ \A \vdash \{Pxf x; \neg Pxx; \forall y \forall z (Pxy \to Pyz \to Pxz)\} \]
只要证符合上述条件的 \(\A\) 必是无限的。
由子集 \(\set{Pxfx, \lnot Pxx}\) 可知，\(\Th \ \A \vdash \set{x \neq fx}\)。由 \(Pxfx \vdash \set{Pfxffx, Pffxfffx , \dots}\)。由传递性 \(\forall y \forall z (Pxy \to Pyz \to Pxz)\) 可知，\(\Th \ \A \vdash \set{Pf^nxf^mx}\) 对任意 \(0 \le n \lt m\) 都成立。因此，\(\A\) 是无限的。
\(Q.E.D.\)
特别地，\(\A = (\mathbb{N};P=<,f=S)\) 即自然数上的后继函数和小于关系是该 (a) 的逆的一个模型。
习题 2：设 \(T_1\) 和 \(T_2\) 是（同一语言的）理论，使得：(i) \(T_1 \subseteq T_2\) (ii) \(T_1\) 是完备的 (iii) \(T_2\) 是可满足的。证明：\(T_1 = T_2\)。
证明：对任意句子 \(\sigma\)，\(\sigma \in T_2 \Rightarrow \lnot \sigma \notin T_2 \Rightarrow \lnot \sigma \notin T_1 \Rightarrow \sigma \in T_1\)，又 \(T_1 \subseteq T_2\)，由外延公理，有 \(T_1 = T_2\)。
\(Q.E.D.\)
