数理逻辑之究极抽象魔幻

Posted on Edited on In
Symbols count in article: 3.1k Reading time ≈ 3 mins.
这门课就是一个搞笑的课，至少我上的那一位老师，水平堪忧，试卷质量差，甚至出现了绝对不应该出现的现象，给分非常随意，总而言之，这门课大体上就是个乐子课，能避开就避开吧，不要让乐子课在那继续乐乐乐...

由于这门课的老师说不要公开声明其犯下的错误，我就只在该文章的内容前喷一下

参考的教材为宋公的《数理逻辑十二讲》，这本书挺一言难尽的

完全性定理

描述

在一阶逻辑和其对应的自然推理系统，\(\Gamma \vdash \Delta \Leftrightarrow \Gamma \models \Delta\)

证明

分为两部分证明

\(Soundness\)：\(\Gamma \vdash \Delta \Rightarrow \Gamma \models \Delta\)

\(\Gamma \vdash \Delta\)即可证，那么存在一个证明树\(T\)，我们按照该证明树证明\(\Gamma \models \Delta\)有效

引理4.8：\(G\)的公理有效

引理4.9：对于除Cut以外的规则，所有上矢列有效，当且仅当下矢列有效

对于Cut规则，上矢列有效，则下矢列有效，反之不然

利用引理4.8和4.9，我们就能证明\(Soundness\)

\(Completeness\)：\(\Gamma \models \Delta \Rightarrow \Gamma \vdash \Delta\)

可以选择利用和上面差不多的说辞来证明，说明存在一个不利用Cut规则的证明树即可，这里不选择这条路

书中选择了从协调性的理论出发，具体而言，需要利用定理6.19：若\(\Gamma\)协调，则\(\Gamma\)可满足

定理6.17：如果\(\Gamma\)协调，那么存在\(\Gamma \subseteq \Phi\)，使得\(\Phi\)为Henkin集

定理6.18：若\(\Phi\)为Henkin集，那么\(\Phi\)为Hintikka集

定理3.26：若\(\Phi\)为Hintikka集，那么\(\Phi\)可满足

根据上述三条定理，我们就足以证明定理6.19

利用定理6.19和协调的定义，我们可以证明completeness（定理6.20）

紧性定理

描述

设\(\Gamma\)为命题的集合，若\(\Gamma\)的任何有穷子集可满足，那么\(\Gamma\)可满足

可满足与协调

定理6.19实际上告诉我们：可满足性等价于协调性

因此，我们可以说明\(Con(\Gamma)\)，反设不协调，那么存在一个有限子集不可满足，矛盾

语义证明

我们先给出上滤和超滤的定义

  • 对于集合\(E\)，记其幂集为\(\mathscr{P}(E)\)，称\(F \subseteq \mathscr{P}(E)\)当且仅当

    • \(E \in F\)
    • \(A, B \in F \Rightarrow A \cap B \in F\)
    • \(A \in F, A \subseteq B \Rightarrow B \in F\)
    • \(\emptyset \notin F\)

  • \(F\)为\(E\)超滤指\(F\)为\(E\)的极大上滤

  • 对于幂集的一个子集，\(C \subseteq \mathscr{P}(E)\)，称\(C\)有有穷交性质（也称\(C\)有f.i.p.），当且仅当

    \(\forall A_1, ..., A_n \in C, A_1 \cap A_2 ... \cap A_n \neq \emptyset\)

在下文中，我们将使用小写字母来指代公式，\(\Delta\)来指代公式的集合，大写字母来指代公式的集合的幂集的元素，花体来指代公式的集合的幂集的子集

设\(\Gamma\)是一个有穷可满足的命题集，我们设\(\mathscr{O}(\Gamma) = \{\Delta | \Delta 为\Gamma的有穷子集\}\)

对于\(\Delta \in \mathscr{O}(\Gamma)\)，我们记\(v_{\Delta}\)为满足满足\(\Delta\)的赋值

令\(A^{\subseteq} = \{\Delta \in I| a \in \Delta \}\)，也即所有包含公式\(a\)的集合构成的集合

令\(\mathscr{C}(\Gamma) = \{A^{\subseteq} | a \in \Gamma\}\)

命题11.8：\(\mathscr{C}(\Gamma)\)有f.i.p.

注意到\(\{a_1, a_2, ..., a_n\} \in A_1^\subseteq \cap A_2^\subseteq ... \cap A_n^\subseteq\)

命题11.4：如果\(C\)有f.i.p.，那么存在一个包含\(C\)的超滤\(U\)，（且\(U\)保持了f.i.p.）

不难想象，命题11.4的正确性和AC等价

根据命题11.4，我们取一个包含\(\mathscr{C}(\Gamma)\)的超滤\(\mathscr{U}\)

命题11.9：若\(a \in \Gamma\)，那么\(\{\Delta \in \mathscr{O}(\Gamma) | v_{\Delta} \models a\} \in \mathscr{U}\)

\(a \in \Gamma\)，因此\(A^{\subseteq} \in \mathscr{C}(\Gamma) \subseteq\mathscr{U}\)

由于\(A^{\subseteq}\)中的子集都是有穷的，从而是可满足的，因此\(A^{\subseteq} \subseteq \{\Delta \in \mathscr{O}(\Gamma) | v_{\Delta} \models a\}\)

根据上滤的性质，\(\{\Delta \in \mathscr{O}(\Gamma) | v_{\Delta} \models a\} \in \mathscr{U}\)

命题11.3：\(U\)为上滤，且有f.i.p.，那么\(U\)为超滤当且仅当\(\forall X \subseteq E\)，\(X \in U \leftrightarrow (E-X) \notin U\)

按定义证明

命题11.10：对于\(\Gamma\)，和其由上定义的\(\mathscr{U}\)，\(\mathscr{O}(\Gamma)\)

定义赋值\(v\)为：\(v(P) = T \Leftrightarrow \{\Delta \in \mathscr{O}(\Gamma) | v_{\Delta}(P) = T\} \in \mathscr{U}\)，那么，\(v \models \Gamma\)

证明：首先，我们要给出这个赋值的一些性质

  • \(v(P) = F \Leftrightarrow \{\Delta \in \mathscr{O}(\Gamma) | v_{\Delta}(P) = F\} \in \mathscr{U}\)

注意到如果\(v(P) = F\)，那么\(\{\Delta \in \mathscr{O}(\Gamma) | v_{\Delta}(P) = T\} \notin \mathscr{U}\)，根据命题11.3，我们有\(\{\Delta \in \mathscr{O}(\Gamma) | v_{\Delta}(P) = F\} \in \mathscr{U}\)，反之同理

根据赋值的以上的性质，我们有

  • 对任何公式\(a\)，\(v(a) = T(F) \Leftrightarrow \{\Delta \in \mathscr{O}(\Gamma) | v_{\Delta}(a) = T(F)\} \in \mathscr{U}\)

现在，对于任何公式\(a \in \Gamma\)，根据命题11.9，有\(\{\Delta \in \mathscr{O}(\Gamma) | v_{\Delta} \models a\} \in \mathscr{U}\)，根据以上的结论，有\(v \models T\) \(\square\)