数学逻辑和可计算性II(续)

这个wiki页面是另一个wiki的延续:数学逻辑和可计算性．在本章的最后，我将回顾这两篇文章。

这一节不仅对数学逻辑的研究有意义，对一般的研究也有意义。在本章中，除其他事项外，我们将看到四色问题(已经解决了，这已经是一个定理)对任何无限映射都有正解，如果它对任何有限映射都有解，这是对的(我们将证明它)

1.4.1定义。

一组 $\总和$形式良好的公式可以满足的是否存在真值评估 $v$满足每一个WFF的 $\总和$．据说有限可以满足的的任意有限子集 $\总和$是可以满足的。

$\总和$可以满足的 $\ Rightarrow$ $\总和$有限可以满足的。

1.4.2定义。

一组 $\δ$WFFS是说完整的如果为每个WFF $\α$我们有: $\alpha \在\Delta$或 $\neg \alpha \在\Delta$．

引理3。

如果一个集合 $\总和$是有限可满足的，那么存在一个集合 $\δ$有限地满足的和完整的，包含的 $\总和$．

---

Proof. -我们要做两个证明，第二个用的是索恩的引理定理。

$\盒装{1}$由断言符号组成的集合是可数的，也就是说，它是有限的，或者存在从断言符号组成的集合到的双射 $\ mathbb {N}$， $\ Rightarrow$ $\text{W =格式良好的公式集(wffs)}$由有限序列元素构成的可数集合是可数的。

让 $\{\alpha_1， \alpha_2，…\}$的枚举 $W$，即双射应用 $Z \ mathbb {} ^ {+}$来 $W$．

让我们定义一个序列 $\ delta {0}， \Delta_{1}， \Delta_{2}，…，$的WFFS集合的递归 $\ mathbb {N}$这样的:

• $\Delta_{0} = \sum$．

• 已知的 $\ Delta_ {n}$，让我们定义 $\Delta_{n + 1} = \Delta_{n} \cup \alpha {n + 1}$,如果 $\ delta {n} \cup \alpha {n + 1}$是有限可满足的。如果集合 $\ delta {n} \cup \alpha {n + 1}$不是有限可满足的，而是有定义的 $\ Delta_ {n + 1} = \ Delta_ {n} \杯\ neg \ alpha_ {n + 1}$．

通过归纳 $\ mathbb {N}$， $\Delta_{0} = \sum$是有限可满足的。让我们假设 $\ Delta_ {n}$是有限可满足的，那么如果 $\ delta {n} \cup \alpha {n + 1}$是有限可满足的，根据定义也是 $\Delta_{n + 1}$有限可以满足的。

如果 $\ delta {n} \cup \alpha {n + 1}$不是有限可满足的，存在一个有限子集 $J_1 \subseteq \Delta_{n}$这样 $J_1 \cup \alpha_{n + 1}$不是有限可以满足的，而是现在 $\ Delta_ {n + 1} = \ Delta_ {n} \杯\ neg \ alpha_ {n + 1}$，让 $J_2$的任意有限子集 $\ delta {n} \cup \neg \alpha {n + 1}$．如果 $J_2 \subseteq \Delta_n$， $J_2$被归纳假设所满足。如果 $J_2 \not\subseteq \Delta_n$,然后 $J_2 = J_3 \cup \neg \alpha_{n + 1}$, $J_3 \subseteq \Delta_n$．自 $J_1 \cup J_3 \subseteq \Delta_n$是一个有限子集，它是可满足的或有限可满足的， $\ Rightarrow$存在一个真理评估 $v$满足 $J_1$而且 $J_3$，这意味着 $\overline{v} (\alpha_{n + 1}) = \text{F}$由于 $J_1 \cup \alpha_{n + 1}$不是有限可满足的，因此 $\overline{v} (\neg \alpha_{n + 1}) = \text{T}$因此 $v$满足 $J_3 \cup \neg \alpha_{n + 1} = J_2$．由此证明 $\ Delta_ {n + 1} = \ Delta_ {n} \杯\ neg \ alpha_ {n + 1}$是有限可满足的。

让 $\displaystyle \Delta = \bigcup_{n \ge 0} \Delta_n$．很明显 $\sum = \Delta_0 \subseteq \Delta$, ( $\Delta_0 \subseteq \Delta_1 \subseteq \Delta_2…$)．Furthemore, $\δ$是有限可满足的吗 $\δ$包含在一些 $\ Delta_n$．最后, $\δ$是否完整是因为给出了WFF $\ψ$， $\ψ$是一定的 $\ _n$，就结构而言， $\alpha_n \在\Delta$或 $\neg \alpha_n \在\Delta$． $\广场$

$\盒装{2}$让 $C = \{H \text{/} \sum \subseteq H \text{and} H \textrm{是有限可满足的$．这个集合不是空的，因为 $\sum \in C$，且由包含关系部分排序 $\ subseteq$．在这个顺序中，每个链 $\{H_0 \subseteq H_1 \子集，…\}$有一个上界 $\displaystyle H = \bigcup_{j \ge 0} H_j$；有效, $\sum \subseteq$而且 $H$是有限可满足的吗 $H$包含在一些 $H_n$．

应用佐恩引理，存在极大元素 $\Delta \在C$，也就是说，如果 $K \in C$而且 $\Delta \subseteq K \右tarrow K = \Delta$． $\δ$是否包含一组WFFS $C$这样 $\sum \subseteq \Delta$而且 $\δ$是有限可满足的。Furthemore, $\δ$是完全的，因为给定了什么 $\α$(wff)，我们有两个:

• $\Delta \cup \{\alpha\}$是有限可满足的，那么这个集合属于 $C$，和存在 $\δ$中的极大元素 $C$，可以得出结论 $\alpha \在\Delta$．

• $\Delta \cup \{\alpha\}$不是有限可满足的。然后，按照演示1的步骤进行 $\Delta \cup \{\neg \alpha\}$是有限可满足的，而存在 $\δ$中的极大元素 $C$，可以得出结论 $\neg \alpha \在\Delta$．

注意，这个演示2是有效的，即使 $W$不是可数集。 $\广场$

紧性定理1.4.4。

如果一组wffs $\总和$是有限可满足的吗 $\总和$是可以满足的。

---

Proof. -由于1.4.3。，there exists $\δ$(一组废话)，这样 $\sum \subseteq \Delta$， $\δ$有限的:有限的可满足的和完整的 $给所有\ \ψ$Wff，我们有: $\boxed{\psi \notin \Delta \iff \neg \psi \in \Delta}$，因为如果 $\psi \notin \Delta$， $\neg \psi \在\Delta$自 $\δ$就完成了。并且，由于 $\{\psi， \neg \psi\}$是不能满足的，如果 $\neg \psi \在\Delta$然后 $\psi \notin \Delta$因为 $\δ$是有限可满足的。

让 $v$是对每个断言符号给出的真值评估 $一个$， $v(A) = T \iff A \in \Delta$．

我们将用归纳法证明，对于每一个 $\ψ$我们有: $\boxed{\overline{v} (\psi) = T \iff \psi \in \Delta}$，等于 $\boxed{\overline{v} (\psi) = F \iff \psi \notin \Delta}$．

$\下划线{\文本{步骤断言符号}}$它是根据的定义满足的 $v$．

$\underline{\text{Step} \neg \text{)}}$让 $\psi = \neg \alpha$, $\α$完成论文框架。然后: $\overline{v} (\neg \alpha) = T \iff \overline{v} (\alpha) = F \iff \alpha \notin \Delta \iff \neg \alpha \in \Delta$．

$\underline{\text{Step} \wedge \text{)}}$让 $\psi = \alpha \wedge \beta$, $\α$而且 $β\$完成论文框架。然后 $\overline{v} (\alpha \wedge \beta) = T$ $\敌我识别$（ $\overline{v} (\alpha) = T$而且 $\overline{v} (\beta) = T$） $\敌我识别$（ $\alpha \在\Delta$而且 $\beta \在\Delta$)．我们来证明:( $\alpha \在\Delta$而且 $\beta \在\Delta$） $\敌我识别$ $\alpha \wedge \beta \在\Delta$．

$\ Rightarrow$如果这不是真的， $\{\alpha， \beta， \neg(\alpha \wedge \beta)\} \subseteq \Delta$ $\ Rightarrow$ $\δ$不是有限可满足的，因为 $\{\alpha， \beta， \neg(\alpha \wedge \beta)\}$是不能满足的。

$\ Leftarrow$如果这不是真的， $\{\neg \alpha， \alpha \wedge \beta\ subseteq \Delta$或 $\{\neg \beta， \alpha \wedge \beta\ subseteq \Delta$，但这是一个矛盾，因为前面的两个子集是不可满足的。

$\underline{\text{Step} \vee \text{)}}$让 $\psi = \alpha \vee \beta$, $\α$而且 $β\$完成论文框架。很容易看出: $\vDash \alpha \vee \beta \iff \neg(\neg \alpha \wedge \neg \beta)$．由于步骤 $\底片$而且 $\楔$， $\ neg \α$而且 $β\ neg \$完成论文 $\ Rightarrow$ $\neg \alpha \wedge \neg \beta$也要实现这个论点，因此 $\neg(\neg \alpha \wedge \neg \beta)$也要完成论题。对abreviate $\neg(\neg \alpha \wedge \neg \beta) = \gamma$．因此 $\overline{v} (\psi) = T \iff \overline{v} (\gamma) = T \iff \gamma \in \Delta$．然后 $\gamma \在\Delta \iff \psi \在\Delta$，相反， $\{\neg \gamma \psi\ subseteq \Delta$或 $\{\neg \psi， \gamma\} \subseteq \Delta$，因为 $\vDash \psi \iff \gamma$， $\δ$将包含一个不满足的有限子集(矛盾)。

$\underline{\text{steps} \Rightarrow，\space \iff \text{)}}$作为步骤进行测试 $\ v字形)$考虑到: $\vDash (\alpha \Rightarrow \beta) \iff \neg(\alpha \wedge \neg \beta) \text{和\vDash (\alpha \iff \beta) \iff \neg(\alpha \wedge \neg \beta) \wedge \neg(\beta \wedge \neg \alpha)$因此，真实性评估 $v$满足 $\δ$而且 $\sum \subseteq \Delta$． $\广场$．

推论1.4.5

让 $\总和$是一组WFFS和 $\τ$这样的WFF $\sum \vDash \tau$．则存在一个有限子集 $\sum_{0} \subseteq \sum$充实的 $\sum_{0} \vDash \tau$．

---

Proof. - $\sum \vDash \tau$表示每个真值评估都满足 $\总和$也满足 $\τ$，也就是说， $\sum \vDash \tau$ $\敌我识别$ $\{\sum， \neg \tau\}$是一个不可满足集。应用紧性定理，存在一个有限子集 $J \subseteq \{\sum， \neg \tau\}$这是不能满足的。因此, $J = \sum_{0} \cup \{\neg \tau\}$或 $J = \sum_{0}$在哪里 $\sum_{0} \subseteq \sum$是有限集，因此 $\sum_{0} \vDash \tau$． $\广场$

我们将用紧性定理在四色问题上的应用来结束本节。待续....

在开始之前(首先)，这很有趣参见伯特兰·罗素的悖论而且

罗素悖论,罗素悖论

让 $A = \{X ext {/} X otin X\}$,然后 $A \in A \iff A otin A$．

“语义悖论”(从某种数学角度来看，这并不是悖论，我的意思是我们不能用语言来谈论语言)。

命题逻辑的语言运用元语言这是一种使用普通语言的数学语言

• Epiménides说所有克里特人都说谎。埃庇米尼德斯是克里特人。那么埃庇米尼德斯撒谎当且仅当( $\敌我识别$) Epiménides说的是真话。
• 在某座城市里，有一个理发师为所有不自己刮胡子的人刮胡子。谁给理发师刮胡子?

注:由于临时限制，本维基已被删节，全文将很快提供。