我们必须知道，我们终将知道。

ignoramus et ignorabimus

A Mathematical Introduction to Logic第二章-一阶逻辑(模型论角度)-学习笔记

• 笔记来自于 Enderton (2001) A Mathematical Introduction to Logic

课本纠错

以下错误均已经与英文原版作对比

P36. 最后一行 $\neg$ 应改为$\rightarrow$

• image-20231121112116386

P70. 同态定理 (a) $h \circ s(t)$应改为 $\overline {h \circ s}(t)$

• image-20231121112504911

P84错误 ，$\forall x \varphi$应改为$\forall x \psi$

• image-20231112204951151

P85 错误，$\varphi$应改为$\psi$

• image-20231112205031189

P86 错误，$\Gamma \vdash y \psi_{y}^{x}$ 应改为 $\Gamma \vdash \forall y \psi_{y}^{x}$

image-20231112205102530

P97错误 “完备性定理的证明”应改为”可靠性定理的证明”

• image-20231114114209539

P106错误， $\sigma$ 应改为 $\varGamma$

• image-20231115174017090

一阶逻辑定义/重点总结

一阶逻辑的意义：

• 人们很容易想到直觉上正确的推论的例子，而这些推论不能充分反映在命题逻辑模型中。
• 本章介绍了一个能力更强的逻辑系统：一阶逻辑。事实上，当“数学家”找到一个证明时，几乎总是意味着一个可以反映在一阶逻辑中的证明

Section 2.1: First-Order Languages

语言符号整理:

一阶语言的不同之处在于

• (a) 是否存在相等符号（相等符号是逻辑符号而不是参数）
• (b) 存在参数

表达式：符号的有限序列。表达式有几种特殊类型：

• 项。对于每个 n 位函数符号 f，我们定义了一个 n 位项构建操作$\mathcal{F}_{f}(\epsilon_{1},\ldots,\epsilon_{n})=f\epsilon_{1}\ldots\epsilon_{n}$.。通过应用零次或多次 n 位项构建运算，从常量符号和变量中构建项。
  • 项通过对已构建的对象取函数，从常量和变量中归纳出对象。
• 原子公式。一个原子公式是形式为$Pt_{1}\ldots t_{n}$的表达式，其中 P 是一个 n 位谓词符号，每个$t_{i}$都是一个项。
  • 原子公式是公式中被赋予真值的最小部分，由项和谓词组成。
  • 它们在一阶逻辑中扮演着类似于自然语言中句子的角色。
• 合式公式。合式公式（wff）是一个表达式，可以通过应用零次或多次以下公式构建操作来从原子公式中构建：
  • $\mathcal{E}_{\neg}(\gamma)=(\neg\gamma)$
  • $\mathcal{E}_{\rightarrow}(\gamma,\delta)=(\gamma\rightarrow\delta)$
  • $\mathcal{Q}_{i}(\gamma)=\forall v_{i}\gamma$.

自由出现：递归定义。在 合式公式wff 中，变量 x 被称为自由出现（x 是自由变量），当满足以下条件之一时：

​ (a) $\alpha$ 是原子公式并且 x 自由出现于 $\alpha$中 ,

​ (b) $\alpha=(\neg\beta)$ 并且x自由出现于 $\beta$,

​ (c) $\alpha=(\beta\rightarrow\gamma)$ 并且“ x 自由出现于 $\beta$ 或者 x 自由出现于 $\gamma$”

​ (d) $\alpha=\forall v_{i}\beta$ 并且 $x\neq v_{i}$ 并且 x 自由出现于 $\beta$.

• 或者，我们定义 $h(\alpha)$ 其中$\alpha$是原子的，是其所有变量的集合，并将其扩展到在所有 合式公式wff 的集合上定义:

  • $\overline{h}(\mathcal{E}_{\neg}(\alpha))=\overline{h}(\alpha)$
  • $\overline{h}(\mathcal{E}_{\rightarrow}(\alpha,\beta))=\overline{h}(\alpha)\cup\overline{h}(\beta)$
  • $\overline{h}(\mathcal{Q}_{i}(\alpha))=\overline{h}(\alpha)-\{v_{i}\}$.

• $\alpha$ 是句子当且仅当 $\overline{h}(\alpha)=\emptyset$. 即没有自由出现的变量

转换/缩写习惯总结：

• $(\alpha\vee\beta)$ 可写为 $((\neg\alpha)\rightarrow\beta)$.
• $(\alpha\wedge\beta)$ 可写为 $(\neg(\alpha\rightarrow(\neg\beta)))$.
• $(\alpha\leftrightarrow\beta)$ 可写为 $(\neg((\alpha\rightarrow\beta)\rightarrow(\neg(\beta\rightarrow\alpha))))$.
• $\exists x\alpha$ 可写为$(\neg\forall x(\neg\alpha))$.
• $t=u$ 可写为 $=tu$ (对于其他一些两位谓词和函数符号也一样)
• $t\neq u$ 可写为 $(\neg=tu)$ (对于其他一些两位谓词和函数符号也一样)
• 最外面的括号可以去掉
• 尽可能少用$\neg$, $\forall$, and $\exists$ 的缩写
• 向右的优先级： $\alpha\square\beta\square\gamma$ 被理解为 $(\alpha\square(\beta\square\gamma))$.
  • 为了便于阅读，可以将括号添加或更改为 []

字母表

• 变量：小写斜体字母 $v_{i}$, $u$, $v$, $x$, $y$, $z$.
• 谓词符号：大写斜体字母，以及特定符号，如 $\in$, $<$, etc.
• 常量符号：小写斜体字母 $a$, $b$, $c$, $\ldots$, 以及特定符号，如 $0$, etc.
• 函数符号：小写斜体字母 $f$, $g$, $h$, and specific symbols such as $\mathbb{S}$, $+$, etc.
• 项：小写斜体字母 $t$, $u$.
• 公式：小写希腊字母 $\alpha$, $\beta$, $\gamma$, $\ldots$
• 句子：小写希腊字母 $\sigma$, $\tau$.
• 公式集：大写希腊字母 $\Gamma$
• 结构：大写德语（花体）字母 $\mathfrak{A}$

Section 2.2: Truth and Models 真值与模型

语言：

• 语言是一些有实际用处的参数集合，通常可以用等号来讨论．

结构 ：

• 对于给定的一阶语言，结构 $\mathfrak{A}$ 是参数集合上的一个函数，是一阶语言到自然语言的翻译
  • 例子; $(\mathbb{C};0,1,+,\cdot)$

1. 全称量词 $\forall$ 对应的所有元素$|\mathfrak{A}|$ 叫做 $\mathfrak{A}$ 的论域.
2. 每个 n 位谓词符号 P 都在 $|\mathfrak{A}|$上有一个 n 元关系 $P^{\mathfrak{A}}$
3. 每个常数符号 c 都在 $|\mathfrak{A}|$上有成员 $c^{\mathfrak{A}}$
4. 每个 n 位函数符号$f$ 都在 $|\mathfrak{A}|$上有一个 n次运算 $f^{\mathfrak{A}}$ .

满足：设 $\phi$ 为合式公式, 并且 $s:V\rightarrow\mathfrak{A}$, $V$ 是所有变量的集合. 那么 $\mathfrak{A}$ 用$s$满足$\phi$, （$\vDash_{\mathfrak{A}}\phi[s]$）, 当且仅当

• 项满足的定义：首先扩展 $s$ 到 $\overline{s}$ ，定义如下

  • a）对所有变量$x$, $\overline{s}(x)=s(x)$
  • b) 对所有常量 $\overline{s}(c)=c^{\mathfrak{A}}$,
  • c) 对所有项 $\overline{s}(ft_{1}\ldots t_{n})=f^{\mathfrak{A}}(\overline{s}(t_{1}),\ldots,\overline{s}(t_{n}))$.

• 原子公式的满足定义：

  • a) $\vDash_{\mathfrak{A}}=t_{1}t_{2}[s]$ iff $\overline{s}(t_{1})=\overline{s}(t_{2})$
  • b) $\vDash_{\mathfrak{A}}Pt_{1}\ldots t_{n}[s]$ iff $<\overline{s}(t_{1}),\ldots,\overline{s}(t_{n})>\in P^{\mathfrak{A}}$.

• 最后，我们将满足的概念扩展到所有合式公式:

  • a) $\vDash_{\mathfrak{A}}\neg\phi[s]$ iff $\not\vDash_{\mathfrak{A}}\phi[s]$,

  • b) $\vDash_{\mathfrak{A}}(\phi\rightarrow\psi)[s]$ iff $\not\vDash_{\mathfrak{A}}\phi[s]$ or $\vDash_{\mathfrak{A}}\psi[s]$,

  • c) $\vDash_{\mathfrak{A}}\forall x\phi[s]$ iff 对任意 $d\in|\mathfrak{A}|$, $\vDash_{\mathfrak{A}}\phi[s(x|d)]$

    • （其中 $s(x|d)$在除 $s(x| d)(x)=d$ 之外的所有地方都是 s）

  • 另一种方法是，给定 $\mathfrak{A}$, 递归地定义函数 $\overline{h}(\phi)$ 为函数集 $s$ ，使得 $\mathfrak{A}$ 用$s$满足$\phi$

假设 $s$ 和 $s’$在 $\phi$ 中自由出现的所有变量上有相同的映射，则 $\vDash_{\mathfrak{A}}\phi[s]$ iff $\vDash_{\mathfrak{A}}\phi[s']$.

• 类似地，如果结构$\mathfrak{A}$ 和 $\mathfrak{B}$在 $\phi$ 中出现的所有参数上一致，那么对任意$s$有 $\vDash_{\mathfrak{A}}\phi[s]$ iff $\vDash_{\mathfrak{B}}\phi[s]$

对一个句子 $\sigma$ ，要么 $\vDash_{\mathfrak{A}}\sigma[s]$ ,要么 $\not\vDash_{\mathfrak{A}}\sigma[s]$。$s$是任意的函数。

模型：$\mathfrak{A}$ 是句子$\sigma$的模型：当且仅当 $\sigma$ 在 结构$\mathfrak{A}$中是真的,

• $\vDash_{\mathfrak{A}}\sigma$, 意味着对任意$s$ $\vDash_{\mathfrak{A}}\sigma[s]$ .
• $\mathfrak{A}$ 是一组句子的模型当且仅当它是该集合中每个句子的模型。

Logical Implication 逻辑蕴涵

逻辑蕴涵：一组合式公式 $\Gamma$ 逻辑蕴涵 一个合式公式 $\phi$, 表示为$\Gamma\vDash\phi$, 当且仅当对任意结构 $\mathfrak{A}$ 中的所有 $s:V\rightarrow|\mathfrak{A}|$，有 $\vDash_{\mathfrak{A}}\Gamma[s]$ 蕴含$\vDash_{\mathfrak{A}}\phi[s]$

蕴含：（满足前者时，后者也满足）

• 合式公式 $\phi$ 和 $\psi$ 逻辑等价 当且仅当 $\phi\vDash\psi$ and $\psi\vDash\phi$.
  • $\Gamma;\phi\vDash\psi$ iff $\Gamma\vDash(\phi\rightarrow\psi)$.
• 合式公式 $\phi$ 被称作 恒真的, ($\vDash\phi$), 当且仅当$\emptyset\vDash\phi$.
  • $\phi$ 和 $\psi$ 逻辑等价 iff $(\phi\leftrightarrow\psi)$ 恒真.
  • $\phi$ 恒真 iff $\forall x\phi$ 恒真.

对句子而言: $\Sigma\vDash\tau$ iff $\Sigma$ 的每个模型也是 $\tau$的模型.

• $\tau$ 恒真 iff 它在每个模型中都被满足.

Homomorphisms 同态

同态：

• $h:|\mathfrak{A}|\rightarrow|\mathfrak{B}|$ 是 $\mathfrak{A}$ 到 $\mathfrak{B}$ 的同态映射，当且仅当它在谓词关系和函数（包括常数）方面保持不变。

同构：

• 如果 $h$ 是 $\mathfrak{A}$ 到 $\mathfrak{B}$ 的同构（同构嵌入）：那么它是一对一的同态映射。

• $\mathfrak{A}$ 和 $\mathfrak{B}$ 被称为同构，记作 $\mathfrak{A}\cong\mathfrak{B}$，当且仅当存在 $\mathfrak{A}$ 到 $\mathfrak{B}$ 的同构映射。

同态定理。 如果 $h$ 是 $\mathfrak{A}$ 到 $\mathfrak{B}$ 的同态映射，并且 $s:V\rightarrow|\mathfrak{A}|$，那么

• (a) 对于任何项 $t$，$\overline{h\circ s}(t)=h(\overline{s}(t))$。
• (b) 对于任何无全称量词和等式的公式 $\alpha$，$\vDash_{\mathfrak{A}}\alpha[s]$ 当且仅当 $\vDash_{\mathfrak{B}}\alpha[h\circ s]$。
• (c) 在 (b) 中，如果 $h$ 是一对一的（同构），则 $\alpha$ 可能包含等式符号，如果 $h$ 是满射（同态），则可能包含量词符号。

子结构：$\mathfrak{A}$ 是 $\mathfrak{B}$ 的子结构，或者说 $\mathfrak{B}$ 是 $\mathfrak{A}$ 的扩充，当且仅当 $|\mathfrak{A}|\subseteq|\mathfrak{B}|$，并且从 $|\mathfrak{A}|$ 到 $|\mathfrak{B}|$ 的恒等映射是同构的。

• 如果 a) 对于每个谓词 $P$，$P^{\mathfrak{A}}$ 是 $P^{\mathfrak{B}}$ 对 $|\mathfrak{A}|$ 的限制，b) 对于每个常数 $c$，$c^{\mathfrak{A}}=c^{\mathfrak{B}}$，并且 c) 对于每个函数 $f$，$f^{\mathfrak{A}}$ 是 $f^{\mathfrak{B}}$ 对 $|\mathfrak{A}|$ 的限制，则恒等映射是同构的。
• 对于每个结构 $\mathfrak{A}$ 和函数 $h$，使得 $\text{ran}h=|\mathfrak{A}|$，存在一个结构 $\mathfrak{B}$，使得 $h$ 是 $\mathfrak{B}$ 到 $\mathfrak{A}$ 的同态映射。
• 对于每个结构 $\mathfrak{A}$ 和一对一函数 $h$，使得 $\text{dom}h=|\mathfrak{A}|$，存在唯一的结构 $\mathfrak{B}$，使得 $h$ 是 $\mathfrak{A}$ 到 $\mathfrak{B}$ 的同构映射。
• 如果 $h$ 是 $\mathfrak{A}$ 到 $\mathfrak{B}$ 的同构，则存在一个结构 $\mathfrak{C}$，使得 $\mathfrak{A}$ 是 $\mathfrak{C}$ 的子结构，并且 $\mathfrak{C}$ 同构于 $\mathfrak{B}$。

自同构：$\mathfrak{A}$ 到 $\mathfrak{A}$ 的同构映射被称为自同构。

• 恒等映射是自同构的。如果还有其他自同构，则 $\mathfrak{A}$ 被称为固化的。
• 如果 $R$ 是 $\mathfrak{A}$ 中可在 $\mathfrak{A}$ 中定义的 $n$ 元关系，则自同构会保持它。
  • 一些关系在结构中不可定义的例子：$\mathbb{N}$ 在 $(\mathbb{R},<)$ 中是不可定义的，$h(x)=x/2$ ；长度在向量空间中通过加法和标量乘法是不可定义的，$h(v)=2v$。

Elementarily equivalent structures 初等等价

$\mathfrak{A}$ 和 $\mathfrak{B}$ 是初等等价的，$\mathfrak{A}\equiv\mathfrak{B}$，当且仅当对于任何句子 $\sigma$，$\vDash_{\mathfrak{A}}\sigma$ 当且仅当 $\vDash_{\mathfrak{B}}\sigma$。

• 同构的结构是初等等价的：$\mathfrak{A}\cong\mathfrak{B}$ 意味着 $\mathfrak{A}\equiv\mathfrak{B}$。
  • 如果 $\mathfrak{A}$ 是有限的，$\mathfrak{A}\equiv\mathfrak{B}$ 意味着 $\mathfrak{A}\cong\mathfrak{B}$。
  • 反方向不一定成立：$(\mathbb{R};<_{R})$ 和 $(\mathbb{Q};<_{Q})$ 是初等等价的但不同构。
• $(\mathbb{N};<_{N})$ 和 $(\mathbb{R};<_{R})$ 不是初等等价的，但在 $(\mathbb{R};<_{R})$ 中对每个 $\exists_{2}$ 句子为真的 $\sigma$ 也在 $(\mathbb{N};<_{N})$ 中为真。

初等等价类

• 结构 $\mathfrak{A}$ 的初等等价类是与 $\mathfrak{A}$ 初等等价的所有结构的类。

结构中的可定义性

可定义的：

• 如果存在定义（区分）关系的一个公式 $\phi$ ，则 $|\mathfrak{A}|$ 上的 $k$ 元关系是在 $\mathfrak{A}$ 中可定义的。

• 例子：

  • 在 $\mathfrak{N}=(\mathbb{N};<,+,\cdot)$ 中，所有可判定的关系都是可定义的，但还有许多其他关系。
    • 素数集、序关系是可定义的
  • 在 $\mathfrak{R}=(\mathbb{R};<,+,\cdot)$ 中，集合是可定义的，当且仅当它是具有端点的区间的有限并集、

结构类的可定义性

对于一组句子 $\Sigma$，$\text{Mod}\Sigma$ 是 $\Sigma$ 的所有模型的类。

对于语言的结构类 $\mathcal{K}$，如果对于某个句子 $\tau$， $\mathcal{K}=\text{Mod}\tau$ ，则称其为初等类（$EC$）。

对于语言的结构类 $\mathcal{K}$，如果对于某个句子集 $\Sigma$， $\mathcal{K}=\text{Mod}\Sigma$ ，则称其为广义初等类（$EC{}_{\Delta}$）。

Section 2.3: A Parsing Algorithm解析算法

对于递归的论证和定义，有必要论证分解项和合式公式的唯一性。

Terms 项

对于变量、常量和函数符号的字符串，我们定义一个函数 $K$ 如下：

• $K(x)=1$（$x$本身就是一个项，因此它在字符串中的出现增加了一个完整的项）。

• $K(c)=1$（常量也是如此）。

• $K(f)=1-n$，其中 $f$ 是一个 $n$ 元函数符号（函数符号意味着一旦找到字符串中的所有 $n$ 个项（$f$ 的参数），就会有一个完整的项）。

• $K(s_{1}\ldots s_{n})=K(s_{1})+\ldots+K(s_{n})$。

对于项 $t$，$K(t)=1$。 对于项 $t$ 的任何终端片段 $t_{1}$，$t_{1}$ 是项的连接，特别是 $K(t_{1})\ge1$。 对于项 $t$ 的任何适当的初始片段 $t_{0}$，$K(t_{0})\le0$，特别是 $t_{0}$ 不是项。

项解析算法

略。唯一分解算法

（项的唯一可读性） 项的集合是由变量和常量符号的集合通过 $\mathcal{F}_{f}$ 操作自由生成的。

Formulas 合式公式

我们可以进一步为其他符号定义 $K$：

• $K(()=-1$。
• $K())=1$。
• $K(\forall)=-1$。
• $K(\neg)=0$。
• $K(\rightarrow)=-1$。
• $K(P)=1-n$，其中 $P$ 是一个 $n$ 元谓词符号。
• $K(=)=-1$。

对于 wff $\alpha$，$K(\alpha)=1$。 对于 wff $\alpha$ 的任何适当的初始片段 $\alpha_{0}$，$K(\alpha_{0})\le0$，特别是 $\alpha_{0}$ 不是 wff。

合式公式解析算法

略。唯一分解算法

（公式的唯一可读性） 从原子公式的集合通过操作 $\mathcal{E}_{\neg}$、$\mathcal{E}_{\rightarrow}$ 和 $\mathcal{Q}_{i}$，其中 $i=1,2,\ldots$ 自由生成的 wff 集合。

Section 2.4: A Deductive Calculus 演绎计算

此章节有利于重新建立对推理的数学直觉！！！

假设 $\Sigma\vDash\tau$。

• 证明这一事实需要什么证明方法？

• 是否一定存在证明？

什么是证明？

• 有限性。这是由于一阶逻辑的紧致性定理，可以保证只需要 $\Sigma$ 的一个有限子集来证明 $\Sigma\vDash\tau$。
• 可验证性。证明的每一步都应该是可以验证的，这意味着可以从空集假设（$\Sigma=\emptyset$）中可验证地推导出来。
  • 这将意味着所有恒真的集合是可以能行可枚举的。这是由于可枚举性定理在合理的假设下证明了能行可枚举性。

证明的上限和局限：

• 紧致性定理和可枚举性定理意味着对于每个 $\Sigma\vDash\tau$ 都存在一个可以在有限步内找到的有限证明。

• 哥德尔的不完备定理是关于数理逻辑中的形式系统的性质的结果。第一不完备定理说明，对于足够强大的自包含系统，总存在一个在该系统内无法证明或证伪的陈述。
• 紧致性和可枚举性定理是积极的性质，而哥德尔不完备定理揭示了系统的局限性。

Deductions 演绎

给 合式公式 $\phi$，$\phi$的概化是一个公式 $\forall x_{1}\ldots\forall x_{n}\phi$，其中 $n\ge0$，且变量为 $x_{1},\ldots,x_{n}$。

逻辑公理：所有逻辑公理它们都是以下公理的所有可能的_概化_。

1. 永真式（重言式）。

   • 基本公式 要么是一个原子公式，要么是形式为 $\forall x\alpha$ 的公式。

   • 非基本公式是任何其他公式（由使用 $\neg$ 和 $\rightarrow$ 构建的不同于主要公式的任何其他公式）。

   • 给定任何合式公式，它由使用 $\mathcal{E}_{\neg}$ 和 $\mathcal{E}_{\rightarrow}$ 构建的基本公式构成

     • 因此，可以将其视为命题逻辑的句子，其中所有基本公式都被视为命题符号。当它在命题逻辑中是永真式时，它在一阶逻辑中也是永真式。

     • 如果 $\Gamma$ 重言蕴含 $\phi$，则 $\Gamma$ 逻辑蕴含 $\phi$，但反之未必成立。

2. $\forall x\alpha\rightarrow\alpha_{t}^{x}$，其中 $t$ 在 $\alpha$ 中可以替代 $x$。（难点）

   $\alpha_{t}^{x}$的定义如下：

   • a）如果 $\alpha$ 是原子的，则 $t$ 替代每个 $x$，
   • b）($\neg\alpha$)$_{t}^{x}$=($\neg\alpha$)$_{t}^{x}$，
   • c）($\alpha\rightarrow\beta$)$_{t}^{x}$=($\alpha_{t}^{x}\rightarrow\beta_{t}^{x}$)，
   • d）($\forall x\alpha$)$_{t}^{x}$=$\forall x\alpha$，$y=x$
   • e）($\forall y\alpha$)$_{t}^{x}$=$\forall y\alpha_{t}^{x}$，其中 $y\neq x$。

   合式公式$\alpha$ 中$x$可以被$t$替换当且仅当：（否则替换后可能不再满足）

   • a）如果 $\alpha$ 是原子公式，无量词，不受限制，
   • b）如果 $\alpha$=($\neg\beta$) 并且 $t$ 在 $\beta$ 中可以替代 $x$，
   • c）$\alpha$=($\beta\rightarrow\gamma$) 并且 $t$ 在 $\beta$ 和 $\gamma$ 中可以替代 $x$，
   • d）如果 $\alpha$=($\forall y\beta$) 并且（［ $x$ 在 $\alpha$ 中没有自由出现 ］或［ $y$ 在 $t$ 中没有出现且 $t$ 在 $\beta$ 中可以替代 $x$ ］）。

注意：$x$ 总是可以替代 $x$，不包含在 $\alpha$ 中的任何变量的 $t$ 总是可以替代 $\alpha$ 中的任何 $x$。

对于任何 $\alpha$，$t$ 和 $x$，总是存在 $\alpha'$ 等效于 $\alpha$，使得 $t$ 可以替代 $\alpha'$ 中的 $x$（参考下面的字母变换式)

• 举例：在一些 $\forall y\beta$ 的情况下，其中 $y\neq x$，$x$ 在 $\beta$ 中是自由的，$t$ 可以在 $\beta$ 中替代 $x$ ，但 $y$ 出现在 $t$ 中。在这种情况下，我们将其重写为 $\forall z\beta_{z}^{y}$）。

3. $\forall x(\alpha\rightarrow\beta)\rightarrow(\forall x\alpha\rightarrow\forall x\beta)$。
4. $\alpha\rightarrow\forall x\alpha$，其中 $x$ 在 $\alpha$ 中没有自由出现。
5. （如果语言有 $=$ ）$x=x$。
6. （如果语言有 $=$ ）$x=y\rightarrow\alpha\rightarrow\alpha'$，其中 $\alpha$ 是原子的，$\alpha'$ 是通过将 $\alpha$ 中的零个或更多但不一定是全部的地方替换为 $y$ 而得到的。

Rules of Inference 推理规则

1. 假言推理：从 $\alpha$，$\alpha\rightarrow\beta$ 推导出 $\beta$。

给定公式集 $\Gamma$（以及逻辑公理集 $\Lambda$，参考上面六条）。如果 $\phi$ 可以通过使用推理规则（有限次数）从 $\Gamma\cup\Lambda$ 得到，则 $\phi$ 是$\Gamma$的定理（$\phi$是从$\Gamma$推导出的），表示为 $\Gamma\vdash\phi$。从$\Gamma$推导出$\phi$的描述说明了如何从 $\Gamma$（和 $\Lambda$）中获得 $\phi$，即它是一系列有限的公式 <$\alpha_{0}$，$\ldots$，$\alpha_{n}$>，满足

​ a) $\alpha_{n}$= $\phi$，

​ b) 对于 $k\le n$，$\alpha_{k}$ 要么在 $\Gamma\cup\Lambda$ 中，要么由一些 $\alpha_{i}$ 和 $\alpha_{j}$=($\alpha_{i}\rightarrow\alpha_{k}$) 的假言三段论得到，其中 $i,j<k$。

• 如果 $\Gamma\vdash\alpha$，则 $\Gamma\cup\Lambda$ 逻辑蕴含 $\alpha$。
• 如果 $\alpha$ 重言蕴含 $\beta$，那么 $\alpha$ 逻辑蕴含 $\beta$。

其他推理规则

（概化定理） 如果 $\Gamma\vdash\alpha$，并且 $x$ 不在 $\Gamma$ 的任何合式公式wff中自由出现，则 $\Gamma\vdash\forall x\alpha$。

• （常量的概化） 如果 $\Gamma\vdash\alpha$，并且常量符号 $c$ 不在 $\Gamma$ 的任何 wff 中出现，则存在一个变量 $x$ 不在 $\alpha$ 中出现，使得 $\Gamma\vdash\forall x\alpha_{x}^{c}$（以及从 $\Gamma$ 推导出 $\forall x\alpha_{x}^{c}$ 而不使用 $c$）。
  • 如果 $\Gamma\vdash\alpha_{c}^{x}$，其中常量符号 $c$ 在 $\Gamma$ 的任何 wff 中或 $\alpha$ 中都没有出现，则 $\Gamma\vdash\forall x\alpha$（从 $\Gamma$ 推导出 $\forall x\alpha$ 而不使用 $c$）。
  • （规则EI ： 存在某个实例） 如果 $\Gamma$;$\alpha_{c}^{x}\vdash\beta$，其中常量符号 $c$ 在 $\Gamma$ 的任何 wff 或 $\alpha$ 中都没有出现，则 $\Gamma$;$\exists x\alpha\vdash\beta$（从 $\Gamma$;$\exists x\alpha$ 推导出 $\beta$ 而不使用 $c$）。

（规则T） 如果 $\Gamma\vdash\alpha_{i}$，$i$=1,$\ldots$,$n$，并且{$\alpha_{1}$，$,\ldots$，$\alpha_{n}$} 逻辑蕴含 $\beta$，那么 $\Gamma\vdash\beta$。

（演绎定理） 如果 $\Gamma$;$\alpha\vdash\beta$，那么 $\Gamma\vdash(\alpha\rightarrow\beta)$。

（反证法） 如果 $\Gamma$;$\alpha\vdash\neg\beta$，那么 $\Gamma$;$\beta\vdash\neg\alpha$。

(不和谐) 一组 wffs $\Gamma$ 不和谐 当且仅当对于某个 wff $\phi$，$\Gamma\vdash${$\phi$，$\neg\phi$}。

• 最大和谐集：对于每个和谐的 $\Gamma$，都存在和谐的 $\Delta\supseteq\Gamma$，使得对于每个 wff $\alpha$，要么 $\alpha\in\Delta$ 要么 ($\neg\alpha$)$\in\Delta$。

（归谬法） 如果 $\Gamma$;$\alpha$ 不和谐 ，则 $\Gamma\vdash\neg\alpha$。

（再替换引理） 如果 $y$ 在 $\alpha$ 中没有出现，那么 $x$ 在 $\alpha_{y}^{x}$ 中可以替代 $y$，且 ($\alpha_{y}^{x}$)$_{x}^{y}$=$\alpha$。

（字母变换式的存在性） 对于 wff $\alpha$，项 $t$ 和变量 $x$，总存在 wff $\alpha'$，满足

​ a) $\alpha'$ 仅在量化变量的选择上与 $\alpha$ 不同，

​ b) $\alpha'$ 可以从 $\alpha$ 推导出来，反之亦然，

​ c) $t$ 可以替代 $\alpha'$ 中的 $x$。

• 定理中描述的公式 $\alpha'$ 称为 $\alpha$ 的字母变换式。

  等式的规则：

• Eq1：$\vdash\forall xx=x$（自反性）。
• Eq2：$\vdash\forall x\forall y(x=y\rightarrow y=x)$（对称性）。
• Eq3：$\vdash\forall x\forall y\forall z(x=y\rightarrow y=z\rightarrow x=z)$（传递性）。
• Eq4：$\vdash\forall x_{1}\forall x_{2}\forall y_{1}\forall y_{2}(x_{1}=y_{1}\rightarrow x_{2}=y_{2}\rightarrow Px_{1}x_{2}\rightarrow Py_{1}y_{2})$（对于 $n$ 元谓词符号也是类似的）。
• Eq5：$\vdash\forall x_{1}\forall x_{2}\forall y_{1}\forall y_{2}(x_{1}=y_{1}\rightarrow x_{2}=y_{2}\rightarrow fx_{1}x_{2}=fy_{1}y_{2})$（对于 $n$ 元函数符号也是类似的）。

推理策略

假设我们想要推导 $\Gamma\vdash\phi$，一些逆向思考的方式：

1. 如果 $\phi$=($\alpha\rightarrow\beta$)，证明 $\Gamma$;$\alpha\vdash\beta$ 就足够了（演绎定理）。
2. 如果 $\phi$=$\forall x\alpha$，
   1. 如果 $x$ 在 $\Gamma$ 中不自由出现，证明 $\Gamma\vdash\alpha$ 就足够了（概化定理）。
   2. 如果 $x$ 在 $\Gamma$ 中自由出现，使用再替换引理，证明 $\Gamma\vdash\alpha_{y}^{x}$ 就足够了。
3. 如果 $\phi$=($\neg\alpha$)，
   1. 如果 $\alpha$=($\beta\rightarrow\gamma$)，证明 $\Gamma\vdash${$\beta$，$\neg\gamma$} 就足够了（并且总是可能的）。
   2. 如果 $\alpha$=$\neg\beta$，证明 $\Gamma\vdash\beta$ 就足够了。
   3. 如果 $\alpha$=$\forall x\beta$，则需要证明 $\Gamma\vdash\neg\beta_{t}^{x}$，其中 $t$ 可以在 $\beta$ 中替代 $x$ ，但归谬法不总是成立的。

Section 2.5: Soundness and Completeness Theorems 可靠性和完备性定理

Soundness 可靠性

每个逻辑公理A1-A6都是恒真的。

• 证明见书习题

一组合式公式集合 $\Gamma$ 被称为可满足的，当且仅当存在 $\mathfrak{A}$ 和 $s:V\rightarrow|\mathfrak{A}|$，使得 $\mathfrak{A}$ 用 $s$ 满足 $\Gamma$ 中的每个成员。

(可靠性定理) 如果 $\Gamma\vdash\phi$，那么 $\Gamma\vDash\phi$。

• 另一种表述：如果 $\Gamma$ 是可满足的，则 $\Gamma$ 是和谐的。
• 如果 $\vdash\phi\leftrightarrow\psi$ （等价于$\phi\vdash\psi$ 且 $\psi\vdash\phi$），那么 $\phi$ 和 $\psi$ 是逻辑等价的。
  • 字母变换式是逻辑等价的。

Completeness 完备性

(完备性定理; Gödel, 1930) 如果 $\Gamma\vDash\phi$，那么 $\Gamma\vdash\phi$。

• 另一种表述：如果 $\Gamma$ 是和谐的，则 $\Gamma$ 是可满足的。
• 证明概述（没完全懂，待看）：
  • 假设 $\Gamma$ 是和谐的。首先，我们通过添加无穷多个常数符号 $c_{\alpha}$ 扩展语言，并通过添加合式公式$\neg\forall x\phi\rightarrow\neg\phi_{c_{\alpha(\phi,x)}}^{x}$ 来扩展 $\Gamma$，其中 $x$ 是使用常数符号 $c_{\alpha(\phi,x)}$ 的 $\alpha(\phi,x)\neq\alpha(\psi,y)$，且 $c_{\alpha(\phi,x)}$ 不出现在 $\phi$ 中。生成的集合 $\Gamma'$ 是和谐的。此外，我们将 $\Gamma'$ 扩展为和谐的 $\Delta$，使得对于每个 $\phi$，要么 $\phi\in\Delta$ 要么 $\neg\phi\in\Delta$（在不可数的情况下也有$\Delta$ 是封闭的：$\Delta\vdash\phi$ 当且仅当 $\phi\in\Delta$）。
  • 其次，我们定义 a) 新的二元关系 $E$（而不是 $=$）；b) 一个结构 $\mathfrak{A}$ 其中 $|\mathfrak{A}|$ 是所有项（扩展语言的）的集合，$E^{\mathfrak{A}}=\{<u,t>|u=t\in\Delta\}$，$P^{\mathfrak{A}}=\{<t_{1},\ldots,t_{n}>|Pt_{1}\ldots t_{n}\in\Delta\}$，$c^{\mathfrak{A}}=c$；$f^{\mathfrak{A}}(t_{1},\ldots,t_{n})=ft_{1}\ldots t_{n}$，和 c) 一个函数 $s:V\rightarrow|\mathfrak{A}|$ 通过 $s(x)=x$（$\overline{s}(t)=t$）。
    • 设 $\phi^{*}$ 是将 $=$ 替换为 $E$ 的 $\phi$，$\phi\in\Delta$ 当且仅当 $\vDash_{\mathfrak{A}}\phi^{*}[s]$，
  • 第三，我们注意到 $E^{\mathfrak{A}}$ 是 $\mathfrak{A}$ 的同余关系（一个等价关系，使得 $P^{\mathfrak{A}}$ 和 $f^{\mathfrak{A}}$ 与 $E^{\mathfrak{A}}$ 兼容），因此商结构 $\mathfrak{A}/E$ 具有以下性质：a) $h(t)=[t]$ 是 $\mathfrak{A}$ 到 $\mathfrak{A}/E$ 的同态映射，其中 $[t]=\{u\in|\mathfrak{A}|<u,t>\in E^{\mathfrak{A}}\}$，b) $E^{\mathfrak{A}/E}$ 是 $|\mathfrak{A}/E|$ 上的相等关系，c) $\phi\in\Delta$ 当且仅当 $\vDash_{\mathfrak{A}/E}\phi[h\circ s]$。将 $\mathfrak{A}/E$ 限制为原始语言后，可以用 $h\circ s$ 满足 $\Gamma$ 中的每个成员。 因此$\Gamma$是可满足的

(紧致性定理) 如果 $\Gamma\vDash\phi$，那么对于某个有限的 $\Gamma_{0}\subseteq\Gamma$，$\Gamma_{0}\vDash\phi$。

• $\Gamma$ 是可满足的当且仅当 $\Gamma_{0}\subseteq\Gamma$ 中的每个有限子集都是可满足的。$\Sigma$ 有一个模型当且仅当 $\Sigma_{0}\subseteq\Sigma$ 中的每个有限子集都有一个模型。
• 不相交的 $EC_{\Delta}$ 类可以通过一个 $EC$ 类分离：如果对于两个句子集，$\text{Mod}\Sigma_{1}\cup\Sigma_{2}=\emptyset$，那么存在一个句子 $\tau$，使得 $\text{Mod}\Sigma_{1}\subseteq\text{Mod}\tau$ 且 $\text{Mod}\Sigma_{2}\subseteq\text{Mod}\neg\tau$。
  • 例子：对于 $\mathfrak{A}=(\mathbb{Z};P^{\mathfrak{A}})$： $<a,b>\in P^{\mathfrak{A}}$ 当且仅当 $|a-b|=1$，这个谓词关系存在一个分离结构$EC$ 类。

Decidability 可判定性

• 定义：表达式集合 $\Gamma$ 是可判定的，当且仅当对于给定的表达式 $\alpha$，存在能行的过程来判定 $\alpha$ 是否属于 $\Gamma$。

• 可判定的:是或否

(可枚举性定理) 对于一个合理的语言，可以有效枚举合式公式的集合。

合理语言：

• 合理语言参数的集合可以能行枚举，并且关系 $\{<P,n>|P\text{是}n\text{-位谓词符号}\}$ 和 $\{<f,n>|f\text{ 是 }n\text{-位函数符号}\}$ 是可判定的

有限语言

• 一个有限语言是只有有限多个参数的语言。有限语言是合理的。

• 一个合理的语言必须是可数的。

推论：

• 如果 $\Gamma$ 是可判定的且语言是合理的，则 $\text{Th}\Gamma$ 和 $\{\phi|\Gamma\vDash\phi\}$ 可以被有效枚举。

• 如果 $\Gamma$ 是可判定的、语言是合理的，并且对于每个句子 $\sigma$，要么$\Gamma\vDash\sigma$ 要么 $\Gamma\vDash\neg\sigma$，那么 $\{\sigma|\Gamma\vDash\sigma\}$ 是可判定的。

Section 2.6: Models of Theories 理论的模型

Finite Models 有限模型

一个句子是有限恒真的，当且仅当它在每个有限模型中都为真。

• 有限恒真句子的否定仅在无限模型中为真
• 反之亦然，如果一个句子仅在无限模型中为真，则其否定是有限恒真的。

如果一组句子有任意大的有限模型，那么它有一个无限模型。

• 如果一个句子在理论 $T$ 的所有无限模型中都为真，则对于某个 $n\in\mathbb{N}$，它在大小为 $\ge n$ 的 $T$ 的所有模型中也为真。

  • 推广性质。对阿列夫数也成立

• 所有有限模型的类不是 $EC_{\Delta}$。所有无限模型的类是 $EC_{\Delta}$。

Size of Models 模型的大小

假设语言的基数是 $\lambda$。

(Löwenheim–Skolem, 1915, 1920) 如果 $\Gamma$ 是可满足的，则 $\Gamma$ 可在基数 $\le\lambda$ 的某个结构中满足。如果 $\Sigma$ 有一个模型，则 $\Sigma$ 有一个基数 $\le\lambda$ 的模型。

(LST，即Löwenheim–Skolem-Tarski) 如果 $\Gamma$ 在无限结构中是可满足的，则对于每个 $\kappa\ge\lambda$，$\Gamma$ 在基数 $\kappa$ 的某个结构中是可满足的。如果 $\Sigma$ 有一个无限模型，则对于每个 $\kappa\ge\lambda$，$\Sigma$ 在基数 $\kappa$ 的某个模型中是可满足的。

• 对于基数 $\lambda$ 的语言，对于任意结构 $\mathfrak{A}$，存在一个在基数 $\le\lambda$ 的初等等价结构 $\mathfrak{B}$。如果 $\mathfrak{A}$ 是无限的，则对于每个 $\kappa\ge\lambda$，存在基数为 $\kappa$ 的初等等价结构 $\mathfrak{B}$。
  • 例如，代数实数集合在初等等价于 $(\mathbb{R};0,1,+,\cdot)$。
  • 即使 $\mathfrak{A}$ 和 $\mathfrak{B}$ 具有相同的基数，$\mathfrak{B}$ 也不必与 $\mathfrak{A}$ 同构：例如，对于 $(\mathbb{N};0,S,<,+,\cdot)$，存在一个在初等等价的可数结构，但不同构。
• Skolem悖论。对于集合论的公理集 $A_{ST}$，存在一个可数模型 $\mathfrak{G}$。但将$\mathfrak{G}$ 定义为一个断言存在不可数多个集合的句子的模型。
  • 悖论的解决：在 $\mathfrak{G}$ 内部观察，从 $\mathbb{N}$ 到域 $|\mathfrak{G}|$ 的函数不存在，但这并不意味着 $\mathfrak{G}$ 外部不存在这样的函数。

Theories 理论

理论：

• 理论 $T$是句子集（和语言同级），是一组在逻辑蕴涵下封闭的句子：$T\vDash\sigma\Rightarrow\sigma\in T$。
  • 结构$\mathfrak{A}$的理论，$\text{Th}\mathfrak{A}$，是在$\mathfrak{A}$中为真的句子集。
  • 一类结构$\mathcal{K}$的理论，$\text{Th}\mathcal{K}$，是在$\mathcal{K}$中每个结构中为真的句子集。

$\text{Th}\mathcal{K}$ 是一个理论。

证明step 1: 如果 $\text{Th}\mathcal{K}\vDash\sigma$，那么 $\sigma$ 在 $\text{Th}\mathcal{K}$ 的所有模型中都为真，但每个结构 $\mathfrak{A}\in\text{Th}\mathcal{K}$ 都是 $\text{Th}\mathcal{K}$ 的模型。

证明step 2: 我们可以将 $\text{Th}\mathcal{K}$ 看作 $\cap_{\mathfrak{A}\in\mathcal{K}}\text{Th}\mathfrak{A}$。$\mathfrak{A}$ 是 $\text{Th}\mathfrak{A}$ 的模型，因此 $\mathfrak{A}$ 也是 $\text{Th}\mathcal{K}$ 的模型，因此，如果 $\text{Th}\mathcal{K}\vDash\sigma$，那么 $\sigma$ 在 $\mathfrak{A}$ 中为真（对于所有 $\mathfrak{A}\in\mathcal{K}$）。

推论集：

• $\text{Cn}$ $\Sigma$ $= \text{Th}\text{Mod}\Sigma = \{\sigma|\Sigma\vDash\sigma\}$ , $\Sigma$被称为推论集

理论的完备性：

• 一个理论 $T$ 是完备的：当且仅当对于每个句子 $\sigma$，要么 $T\vDash\sigma$ 要么 $T\vDash\neg\sigma$，

等价表示：要么 $\sigma\in T$ 要么 $\neg\sigma\in T$，这时 $T$ 被称为完备。

• 对于每个结构 $\mathfrak{A}$，$\text{Th}\mathfrak{A}$ 是完备的。
• 对于每个结构类 $\mathcal{K}$，$\text{Th}\mathcal{K}$ 是完备的当且仅当对于每个 $\mathfrak{A},\mathfrak{B}\in\mathcal{K}$，$\mathfrak{A}\equiv\mathfrak{B}$。
• 如果一个理论 $T$ 是完备的并且可满足的，那么每个严格更大的理论都不可满足，而每个严格更小的理论都不完备。
• 例子：

  • 域的理论不是完备的：$1+1=0$ 在某些域中为真，而在其他域中为假。

  • 特征为0的代数闭域的理论是完备的。

  • 复数域的理论 $(\mathbb{C};0,1,+,\cdot)$ 是完备的。

范畴：

• 一组句子 $\Sigma$ 被称为范畴，当且仅当 $\Sigma$ 的任意两个模型是同构的。

• 一个理论 $T$ 是$\lambda$-范畴，当且仅当 $T$ 的所有基数为 $\lambda$ 的无限模型是同构的。

  • 根据LST，$\Sigma$ 是1-范畴当且仅当 $\Sigma$ 没有无限模型。