![](https://lar-blog.oss-cn-nanjing.aliyuncs.com/gallery/gallery/%E9%A3%8E%E5%85%89/5D4F56FB9E1CB22675B95332AE79BE23.png)
数理逻辑-一阶逻辑(模型论角度)-学习笔记
我们必须知道,我们终将知道。
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
语言符号整理:
逻辑符号logical symbols | ||
---|---|---|
连接符 | $\neg$ | |
$\rightarrow$ | ||
标点符号 | ( | |
) | ||
变量 | $v_n$ | |
参数 | ||
全称量词quantifier symbols | $\forall$ | |
谓词符号predicate symbols | $P,Q$;作用于n个参数 | |
常量constant symbols | $c$;不可变 | |
函数符号function symbols |
一阶语言的不同之处在于
- (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)$
- 全称量词 $\forall$ 对应的所有元素$|\mathfrak{A}|$ 叫做 $\mathfrak{A}$ 的论域.
- 每个 n 位谓词符号 P 都在 $|\mathfrak{A}|$上有一个 n 元关系 $P^{\mathfrak{A}}$
- 每个常数符号 c 都在 $|\mathfrak{A}|$上有成员 $c^{\mathfrak{A}}$
- 每个 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$,使得 $\mbox{ran}h=|\mathfrak{A}|$,存在一个结构 $\mathfrak{B}$,使得 $h$ 是 $\mathfrak{B}$ 到 $\mathfrak{A}$ 的同态映射。
- 对于每个结构 $\mathfrak{A}$ 和一对一函数 $h$,使得 $\mbox{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)$ 中,集合是可定义的,当且仅当它是具有端点的区间的有限并集、
- 在 $\mathfrak{N}=(\mathbb{N};<,+,\cdot)$ 中,所有可判定的关系都是可定义的,但还有许多其他关系。
结构类的可定义性
对于一组句子 $\Sigma$,$\mbox{Mod}\Sigma$ 是 $\Sigma$ 的所有模型的类。
对于语言的结构类 $\mathcal{K}$,如果对于某个句子 $\tau$, $\mathcal{K}=\mbox{Mod}\tau$ ,则称其为初等类($EC$)。
对于语言的结构类 $\mathcal{K}$,如果对于某个句子集 $\Sigma$, $\mathcal{K}=\mbox{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}$。
逻辑公理:所有逻辑公理它们都是以下公理的所有可能的_概化_。
永真式(重言式)。
基本公式 要么是一个原子公式,要么是形式为 $\forall x\alpha$ 的公式。
非基本公式是任何其他公式(由使用 $\neg$ 和 $\rightarrow$ 构建的不同于主要公式的任何其他公式)。
给定任何合式公式,它由使用 $\mathcal{E}{\neg}$ 和 $\mathcal{E}{\rightarrow}$ 构建的基本公式构成
因此,可以将其视为命题逻辑的句子,其中所有基本公式都被视为命题符号。当它在命题逻辑中是永真式时,它在一阶逻辑中也是永真式。
如果 $\Gamma$ 重言蕴含 $\phi$,则 $\Gamma$ 逻辑蕴含 $\phi$,但反之未必成立。
$\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}$)。
- $\forall x(\alpha\rightarrow\beta)\rightarrow(\forall x\alpha\rightarrow\forall x\beta)$。
- $\alpha\rightarrow\forall x\alpha$,其中 $x$ 在 $\alpha$ 中没有自由出现。
- (如果语言有 $=$ )$x=x$。
- (如果语言有 $=$ )$x=y\rightarrow\alpha\rightarrow\alpha’$,其中 $\alpha$ 是原子的,$\alpha’$ 是通过将 $\alpha$ 中的零个或更多但不一定是全部的地方替换为 $y$ 而得到的。
Rules of Inference 推理规则
- 假言推理:从 $\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$,一些逆向思考的方式:
- 如果 $\phi$=($\alpha\rightarrow\beta$),证明 $\Gamma$;$\alpha\vdash\beta$ 就足够了(演绎定理)。
- 如果 $\phi$=$\forall x\alpha$,
- 如果 $x$ 在 $\Gamma$ 中不自由出现,证明 $\Gamma\vdash\alpha$ 就足够了(概化定理)。
- 如果 $x$ 在 $\Gamma$ 中自由出现,使用再替换引理,证明 $\Gamma\vdash\alpha_{y}^{x}$ 就足够了。
- 如果 $\phi$=($\neg\alpha$),
- 如果 $\alpha$=($\beta\rightarrow\gamma$),证明 $\Gamma\vdash${$\beta$,$\neg\gamma$} 就足够了(并且总是可能的)。
- 如果 $\alpha$=$\neg\beta$,证明 $\Gamma\vdash\beta$ 就足够了。
- 如果 $\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$
- 可判定的:是或否
(可枚举性定理) 对于一个合理的语言,可以有效枚举合式公式的集合。
合理语言:
- 合理语言参数的集合可以能行枚举,并且关系 ${<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}$中每个结构中为真的句子集。
$\mbox{Th}\mathcal{K}$ 是一个理论。
证明step 1: 如果 $\mbox{Th}\mathcal{K}\vDash\sigma$,那么 $\sigma$ 在 $\mbox{Th}\mathcal{K}$ 的所有模型中都为真,但每个结构 $\mathfrak{A}\in\mbox{Th}\mathcal{K}$ 都是 $\mbox{Th}\mathcal{K}$ 的模型。
证明step 2: 我们可以将 $\mbox{Th}\mathcal{K}$ 看作 $\cap_{\mathfrak{A}\in\mathcal{K}}\mbox{Th}\mathfrak{A}$。$\mathfrak{A}$ 是 $\mbox{Th}\mathfrak{A}$ 的模型,因此 $\mathfrak{A}$ 也是 $\mbox{Th}\mathcal{K}$ 的模型,因此,如果 $\mbox{Th}\mathcal{K}\vDash\sigma$,那么 $\sigma$ 在 $\mathfrak{A}$ 中为真(对于所有 $\mathfrak{A}\in\mathcal{K}$)。
推论集:
- $\mbox{Cn}$ $\Sigma$ $= \mbox{Th}\mbox{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}$,$\mbox{Th}\mathfrak{A}$ 是完备的。
- 对于每个结构类 $\mathcal{K}$,$\mbox{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$ 没有无限模型。
公理化:
- 一个理论 $T$ 是公理化的,当且仅当存在一个可判定的句子(公理)集 $\Sigma$,使得 $T=\mbox{Cn}\Sigma=\mbox{Th}\mbox{Mod}\Sigma$。
- 一个理论 $T$ 是有限公理化的,当且仅当存在一个有限句子(公理)集 $\Sigma$,使得 $T=\mbox{Cn}\Sigma=\mbox{Th}\mbox{Mod}\Sigma$。
- 跟推论集的定义很像
如果 $\mbox{Cn}\Sigma$ 是有限公理化的,则存在 $\Sigma$ 的有限子集 $\Sigma_{0}\subseteq\Sigma$,使得 $\mbox{Cn}\Sigma_{0}=\mbox{Cn}\Sigma$。
- 例子(不是数学系的,域还没完全理解…):
- 域的理论是(有限)公理化的:如果 $\Phi$ 是域公理的(有限)集合,则域的类是 $\mbox{Mod}\Phi$,域的理论是 $\mbox{Th}\mbox{Mod}\Phi$。
- 特征为0的域的理论是公理化的:其公理 $\Phi_{0}$ 由 $\Phi$ 和对于每个 $n$ 都有 $1+\ldots+1_{n}\neq0$ 组成。
- 特征为0的代数闭域的理论是公理化的:其公理包括 $\Phi_{0}$ 和 $\forall x_{0}\ldots\forall x_{n}x_{n}\neq0\rightarrow\exists xx_{n}\cdot\underbrace{x\cdot\ldots\cdot x}{n}+\ldots+x{1}\cdot x+x_{0}=0$
Decidability 可判定性
- 对于有限语言,如果 $\mathfrak{A}$ 是有限的,则 $\mbox{Th}\mathfrak{A}$ 是可判定的。
- 对于有限语言,${\sigma|\sigma$ 有一个有限模型$}$ 是能行可枚举的。
重新表述可判定性:
- 如果 $\Gamma$ 是可判定的,语言是合理的,则 $\mbox{Th}\Gamma$ 和 ${\phi|\Gamma\vDash\phi}$ 是能行可枚举的。
- 合理语言中的可公理化的理论是能行可枚举的。
- 可公理化理论是可判定的
- 反之亦然。在合理语言中是能行可枚举的理论是可公理化的。
- 合理语言中的可公理化的理论是能行可枚举的。
- 如果 $\Gamma$ 是可判定的,语言是合理的 (对于每个句子 $\sigma$,$\Gamma\vDash\sigma$ 或 $\Gamma\vDash\neg\sigma$) ,则 ${\sigma|\Gamma\vDash\sigma}$ 是可判定的。
- 合理语言中的完备的 可公理化的 理论是可判定的。
- 例子:
- 集合论(如果一致)是不可判定的,因此也不是完备的。
- 数论是完备的,但是不可判定(甚至不是能行可枚举的),因此也不可公理化。
- 特征为0的代数闭域的理论是可判定的。
- 复数域的理论 $(\mathbb{C};0,1,+,\cdot)$ 是可判定的。
- 实数域的理论 $(\mathbb{R};0,1,+,\cdot)$ 也是可判定的
- 无端点的稠密线性序理论是可判定的。
Prenex Normal Form 前束范式
前束范式 是形式为 $Q_{1}x_{1}\ldots Q_{n}x_{n}\alpha$ 的公式,其中 $Q_{i}\in{\forall,\exists}$,$\alpha$ 是不含量词的公式。
(前束范式定理) 对于每个合式公式$\phi$,都存在一个逻辑等价的前束范式。
Section 2.7: Theories之间的解释
符号表示
对于给定的公式$\varphi$,通过$\varphi(t_{1},…,t_{k})$表示$((\psi_{t_{1}}^{v_{1}})…){t{k}}^{v_{k}}$,其中$\psi$是$\varphi$的字母变体(参见第2.4节),使得所有$t_{i}$都可以替代$v_{i}$。
语言的解释
解释是将$L$翻译为$L’$和$T’$的一种方式。我们需要将$L$的每个参数翻译成$L’$的语言,还需要考虑一个特定的理论$T’$,因为我们必须确保,例如,$\forall$的翻译指定一个非空集合,并且函数符号$f$的翻译确实指定了一个函数,即$T’$中存在一个句子,说明我们的翻译确实是一个函数(在$T’$的每个模型中都如此)。
一个**$L$到$T’$的解释$\pi$*是一个函数,它为$L$的每个参数分配一个$L’$的公式$\pi_{*}$,使得以下要求成立($free(\varphi)$是$\varphi$的自由变量集):
- $free(\pi_{\forall}) \subseteq {v_{1}}$,且$T’ \models \exists v_{1}\pi_{\forall}$。
- 对于$n$元谓词符号$P$,$free(\pi_{P}) \subseteq {v_{1},…,v_{n}}$。
- 对于$n$元函数符号$f$,$free(\pi_{f}) \subseteq {v_{1},…,v_{n},v_{n+1}}$,且$T’ \models \forall v_{1}…\forall v_{n}(\pi_{\forall} \rightarrow \pi_{\forall}(v_{2}) \rightarrow … \rightarrow \pi_{\forall}(v_{n}) \rightarrow \exists x(\pi_{\forall}(x)\land\forall v_{n+1}(\pi_{f}\leftrightarrow v_{n+1}=x)))$。
- 对于常量符号$c$,$free(\pi_{c}) \subseteq {v_{1}}$,且$T’ \models \exists x(\pi_{\forall}(x)\land\forall v_{1}(\pi_{c}\leftrightarrow v_{1}=x))$。
其中:
- 1表示对于$T’$的任何模型$B$,$\pi_{\forall}$定义了$|^{π}B|$的非空子集(我们对$L$的解释中的宇宙)和该子集上的所有$L$的参数,即$^{π}B$是$L$的结构,使得对于$L$的每个公式$\varphi$,我们可以验证它是否在$^{π}B$中的一些$s$:$V\to|^{π}B|$上为真。
- 2表示$\pi_{P}$定义了一个$n$元关系(可以进一步限制到1中定义的宇宙中)。
- 3表示对于$T’$的任何模型$B$,$\pi_{f}$定义了一个$(n+1)$元关系,使得在1中定义的宇宙中它的限制是一个函数(最后一个元素根据其他所有元素唯一定义)。
- 4表示$\pi_{c}$定义了一个$L$的常量,它是在1中定义的宇宙中的元素。
$L$到$T’$解释的正当性
现在我们需要证明任何$L$到$T’$解释的正当性。我们的证明将依赖于两个关键事实:
- 对于$L$的每个$\varphi$,$T’ \models \exists v_{1}…\exists v_{k}\pi_{\forall}(v_{1})\land…\land\pi_{\forall}(v_{k}) \rightarrow \pi_{\forall}(\varphi)$。这是因为$L$的每个$\varphi$都是$L$的参数的组合,这一事实在$\pi_{\forall}$的限制下成立。
- 对于$L$的每个$\varphi$,$T’ \models \pi_{\forall}(\varphi) \rightarrow \exists v_{1}…\exists v_{k}\pi_{\forall}(v_{1})\land…\land\pi_{\forall}(v_{k})$。这是因为$\pi_{\forall}(\varphi)$是在$L’$中的一个公式,它的参数是$\pi_{\forall}$的限制下的元素,这一事实在$T’$的每个模型下成立。
有了这两个事实,我们可以证明对于任何$L$的公式$\phi$,$T’ \models \pi_{\forall}(\phi)$。证明是通过对$\phi$的结构进行归纳的,基本情况是原子公式,归纳步骤涵盖了复合公式,包括$\forall$、$\exists$、$\rightarrow$、$\neg$等。对于每一种情况,我们使用1和2,或者2和1,以及归纳假设,来推导所需的结论。
$T’$的强度
最终,我们证明了$T \subseteq \pi^{-1}(T’)$,这意味着$L$中的理论$T$的任何模型都可以被嵌入到$L’$中的理论$T’$的模型中。这意味着$T’$至少与$T$一样强大,如果我们认为$T$是强大的,那么我们也可以认为$T’$是强大的。这种证明方法为我们提供了一种比较不同理论之间强度的方式,通过研究它们之间的解释关系。
跳过可消去部分。
Section 2.8 跳过
Section 3.1
我们选择数论(而不选择其他理论,比如群论)进行学习是因为:
- 我们能证明数论的某个子理论是一个不可判定的句子集.
- 我们也能得到,任何一个可满足的理论如果包含数论(例如,完全数论或者集合论)的这个子理论,那么这个理论一定是不可判定的.
- 特别地,这样的一个理论不可能既是完全的又是可公理化的.
为了证明我们所找到的数论的子理论是不可判定的,我们还将证明这个子理论足以表示数字序列、数字序列与数之间的编码运算以及判定过程等.在最后一部分内容中,我们将利用对角线法证明我们所选择的子理论是不可判定的.