A Mathematical Introduction to Logic -- Section 1.7

发表于 2020-06-14 更新于 2021-11-28 分类于数学，数理逻辑阅读次数：

$\def\tauequ{\mathbin{\vDash\style{display: inline-block; transform: scaleX(-1)}{\vDash}}}$ $\def\Dashv{\mathbin{\style{display: inline-block; transform: scaleX(-1)}{\vDash}}}$ $\def\DEF{\sf{D\scriptsize EF}.\quad}$ $\def\DEFi{\sf{D\scriptsize EF}^*.\quad}$ $\def\DEFn{\sf{D\scriptsize EF}_*.\quad}$ $\def\DEFin{\sf{D\scriptsize EF}^*_*.\quad}$ $\def\llbracket{\unicode{x27E6}}$ $\def\rrbracket{\unicode{x27E7}}$ $\def\PROOF{\sf{P\scriptsize ROOF}.\quad}$ $\def\MYNOTE{\sf{M\scriptsize{Y}}\sf{N\scriptsize{OTE}}.\quad}$ $\def\EXAMPLE{\bf\sf{E\scriptsize{XAMPLES}}\quad}$ 这是一个关于数理逻辑的读书笔记和学习总结, 书名是A Mathematical Introduction to Logic (以下简称AMIL), 作者Herbert B. Enderton, University of California

点击这里进入AMIL的目录

本文是Chapter 1, Section 1.7, 介绍能行性, 可判定性和可计算性

由于中文版错误太多, 大部分章节读的是英文第二版, 所以笔记也是中英文夹杂着写的. 英文一般是关键原文. 中文有的是原文的翻译, 有的是我自己的理解, 还有的是为了做练习写的证明和计算过程.

前缀关键字的含义:

$\DEF$ : 表明后面是概念定义.
$^*$ : 表明后面内容并不是数学上的精确表达.
$_*$ : 表明后面的内容并不来自于这本书.
$\MYNOTE$ : 后面的内容是我用自己的话做的总结,或心得体会

Chapter One. Sentential Logic 命题逻辑

1.7 Compactness and Effectiveness 紧致性和能行性

Comactness 紧致性

Compactness Theorem 紧致性定理

A set of wffs is satisfiable iff every finite subset is satisfiable.

$\DEF$ Finitely Satisfiable 有限可满足

We say that $\Sigma$ is finitely satisfiable iff every finite subset of $\sigma$ is satisfiable.

Corollary 17A

If $\Sigma\vDash\tau$, then there is a finite $\Sigma_0\subseteq\Sigma$ such that $\Sigma_0\vDash\tau$.

Effectiveness and Computability 能行性和可计算性

$\DEFi$ effective procedure 能行的程序

There must be exact finite instructions(i.e. a program) explaining how the execute the procedure.
The instructions must be mechanically implemented. They must not demand any brilliance or originality. The procedure must avoid random devices or any such device that can, in practice, only be approximated.
The procedure must be an algorithm for determining the answer. The procedure produces a "yes" or "no" answer.

Theorem 17B$^*$

There is an effective procedure that, give any expression $\varepsilon$, will decide whether or not it is a wff.

$\DEFi$ Decidable 可判定的

A set $\Sigma$ of expression is decidable iff there exists an effective procedure that, given an expression $\alpha$, will decide whether or not $\alpha \in \Sigma$

$\MYNOTE$ 可判定主语是集合, 即一个集合是可判定的, 当且仅当有一个能行的程序决定某一个元素是否属于该集合.

Theorem 17C$^*$

There is an effective procedure that, given a finite set $\Sigma;\tau$ of wffs, will decide whether or not $\Sigma\vDash\tau$

Corollary 17D$^*$

For a finite set $\Sigma$, the set of tautological consequences of $\Sigma$ is decidable. In particular, the set of tautologies is decidable.

$\DEFi$ Effectively Enumerable 能行可枚举

Say that a set $A$ of expressions is effectively enumerable iff there exists an effective procedure that lists, in some order, the members of $A$

$\MYNOTE$ 能行可枚举的主语是集合, 即一个集合是能行可枚举的, 当且仅当有一个能行的程序能狗列出(枚举出)该集合所有的元素.

$\DEFi$ Semidecidable 半可判定的

A set A of expressions is Semidecidable iff there exists an effective procedure that, given any expression $\varepsilon$, procedures the answer yes iff $\varepsilon\in A$.

If $\varepsilon\notin A$, procedure might produce the answer "no"; more likely it will go on forever without producing any answer, but it must not lie to use and produce the answer "yes".

Theorem 17E$^*$

A set is effectively enumerable iff it is semidecidable.

Theorem 17F$^*$

A set of expressions is decidable iff both it and its complement (relative to the set of all expressions) are effectively enumerable. This sometimes called "Kleene's theorem."

Theorem 17G$^*$

If $\Sigma$ is decidable set of wffs, then the set of tautological consequences of $\Sigma$ is effectively enumerable.

$\DEFi$ Effectively Computable 能行可计算的

We will say that a function $f$ is effectively computable (or simply computable) iff there exists an effective procedure that given an input $x$, will eventually produce the correct output $f(x)$.

$\MYNOTE$ 能行可计算主语是函数.

Exercises 1.7

Problem 1

Assume that every finite subset of $\Sigma$ is satisfiable. Show that the same is true of at least one of the sets $\Sigma;\alpha$ and $\Sigma;\lnot\alpha$. (This is part of the proof of the compactness theorem.)

证明:

假设有两个有限子集$\Sigma_1\subseteq\Sigma$和$\Sigma_2\subseteq\Sigma$, 再假设$\Sigma_1;\alpha$和$\Sigma_2;\lnot\alpha$都是不可满足的.

那么考虑$\Sigma'=\Sigma_1\cup\Sigma_2\subseteq\Sigma$, $\Sigma'$也是$\Sigma$的有限子集. 则必然存在一个真值分配$v$能够满足$\Sigma'$, 那么

或者$\overline{v}(\alpha)=T$, 从而$v$能够满足$\Sigma;\alpha$

或者$\overline{v}(\lnot\alpha)=T$, 从而$v$能够满足$\Sigma;\lnot\alpha$

这就产生了矛盾. 所以 $\blacksquare$

Problem 2

Let $\Delta$ be a sets of wffs such that (i) every finite subset of $\Delta$ is satisfiable, and (ii) for every wff $\alpha$, either $\alpha\in\Delta$ or $(\lnot\alpha)\in\Delta$. Define the truth assignment $v$: \[ v(A)=\left\{ \begin{array}{l} T\qquad\text{iff}\quad A\in\Delta\\ F\qquad\text{iff}\quad A\notin\Delta \end{array} \right. \] for each sentence symbol $A$. Show that for every wff $\phi$, $\overline{v}(\phi)=T$ iff $\phi\in\Delta$.

证明:

若一个合式公式$\phi$, 满足$\overline{v}(\phi)=T$当且仅当$\phi\in\Delta$, 我们称这个合式公式是成立的.

应用数学归纳法.

对于任取的命题符号(sentence symbols)$\forall A$, 根据$\overline{v}$的定义,$\overline{v}(A)=v(A)$, 显然满足$\overline{v}(A)=T$ 当且仅当 $A\in\Delta$, 所以所有的命题符号都是成立的.

只需要证明若对于两个成立的合式公式 $\alpha$和$\beta$, 那么下面5个由这两个合式公式构造的合式公式: \[ \matrix{ \varepsilon_\lnot(\alpha) = (\lnot\alpha)\cr \varepsilon_\land(\alpha,\beta) = (\alpha\land\beta)\cr \varepsilon_\lor(\alpha,\beta) = (\alpha\lor\beta)\cr \varepsilon_\rightarrow(\alpha,\beta) = (\alpha\rightarrow\beta)\cr \varepsilon_\leftrightarrow(\alpha,\beta) = (\alpha\leftrightarrow\beta) } \] 也同样是成立的, 根据归纳原理, 所有的合式公式都是成立的.

首先考察$\lnot\alpha$.

根据$\overline{v}$的定义, $\overline{v}(\lnot\alpha)=T$当且仅当$\overline{v}(\alpha)=F$.
因为$\alpha$是成立的, 所以$\overline{v}(\alpha)=F$当且仅当$\alpha\notin\Delta$.
根据条件{ii}, $\alpha\notin\Delta$当且仅当$(\lnot\alpha)\in\Delta$

所以$\overline{v}(\lnot\alpha)=T$当且仅当$(\lnot\alpha)\in\Delta$, 因为$\lnot\alpha$也是成立的.

现在考察双元构造的合式公式$\alpha\boxdot\beta$, 其中$\boxdot\in\{\land,\lor,\rightarrow,\leftrightarrow\}$ 由于条件(ii)我们可以定义$\lnot?\alpha$是$\alpha$和$\lnot\alpha$中在$\Delta$中的那个, 同样可以定义$\lnot?\beta$和$\lnot?(\alpha\boxdot\beta)$.

根据这个定义, 集合$\{\lnot?\alpha, \lnot?\beta, \lnot?(\alpha\boxdot\beta)\}\subseteq\Delta$. 根据条件(i), 这个集合是可满足的.

根据$\overline{v}$的定义, 对于任意的真值分配$u$, $\overline{u}(\lnot?(\alpha\boxdot\beta))$的真值由$\overline{u}(\alpha)$和$\overline{u}(\beta)$决定的. 而$\overline{u}(\alpha)$和$\overline{u}(\beta)$又是由$\overline{u}(\lnot?\alpha)$和$\overline{u}(\lnot?\beta)$决定的. 所以我们得到一个结论:

\[ \begin{align} \overline{u}(\lnot?\alpha)和\overline{u}(\lnot?\beta)的真值, 可以唯一决定\overline{u}(\lnot?(\alpha\boxdot\beta))的真值.\tag{$\dagger$} \end{align} \]

由于前面说的集合是可满足的, 所以

\[ \begin{align} \exists一个真值分配能够在满足\{\lnot?\alpha, \lnot?\beta\}的同时, 也满足\lnot?(\alpha\boxdot\beta) \tag{$\ddagger$} \end{align} \]

那么综合$(\dagger)$和$(\ddagger)$, $\forall$真值分配, 只要其满足$\{\lnot?\alpha, \lnot?\beta\}$, 就一定满足$\overline{u}(\lnot?(\alpha\boxdot\beta))$.

本题中的真值分配$v$, 根据前面对$\alpha$和$\beta$的假设, 已知$\overline{v}(\lnot?\alpha)=T$和$\overline{v}(\lnot?\beta)=T$, 所以一定有$\overline{v}(\lnot?(\alpha\boxdot\beta))=T$. 因而有:

或者当$(\alpha\boxdot\beta)\in\Delta$, 有$\overline{v}(\alpha\boxdot\beta)=T$
或者当$\lnot(\alpha\boxdot\beta)\in\Delta$, 有$\overline{v}(\lnot(\alpha\boxdot\beta))=T$. 根据$\overline{v}(\lnot\alpha)$的定义, $\overline{v}(\alpha\boxdot\beta)=F$.

换句话说$\overline{v}(\alpha\boxdot\beta)=T$当且仅当$(\alpha\boxdot\beta)\in\Delta$, 即$\alpha\boxdot\beta$是成立的. 正毕 $\blacksquare$

A Mathematical Introduction to Logic -- Section 1.7

Chapter One. Sentential Logic 命题逻辑

1.7 Compactness and Effectiveness 紧致性和能行性

Comactness 紧致性

Compactness Theorem 紧致性定理

\(\DEF\) Finitely Satisfiable 有限可满足

Corollary 17A

Effectiveness and Computability 能行性和可计算性

\(\DEFi\) effective procedure 能行的程序

Theorem 17B\(^*\)

\(\DEFi\) Decidable 可判定的

Theorem 17C\(^*\)

Corollary 17D\(^*\)

\(\DEFi\) Effectively Enumerable 能行可枚举

\(\DEFi\) Semidecidable 半可判定的

Theorem 17E\(^*\)

Theorem 17F\(^*\)

Theorem 17G\(^*\)

\(\DEFi\) Effectively Computable 能行可计算的

Exercises 1.7

Problem 1

Problem 2