Tarski 不可定义定理

Tarski 不可定义定理大致说的是, 在足够强的形式系统里, 语义上的真理是不可以被这个系统本身所定义的. 它可以被视作说谎者悖论, Russell 悖论等 “自指” 的思想在形式语言里的产物.

1历史

(...)

2定理与证明

定理 2.1 (Tarski). 如果一个带否定连接词 $\neg$, Gödel 编号 $\#$ 的形式系统 $T$ 以及其上的一个模型 $\mathcal{M}$ 满足如下的对角线引理:

对于任意只含一个自由变元 $x$ 的公式 $\phi (x)$, 存在语句 $\gamma$ 使得 $\mathcal{M}\models \gamma \leftrightarrow \phi (\#\gamma )$,

则集合 $\#\mathrm{Th}(\mathcal{M})$ 不是可定义集.

证明. 若否, 设 $\mathrm{True}(x)$ 定义此集合, 即 $\mathcal{M}\models \mathrm{True}(\#\phi )$ 等价于 $\mathcal{M}\models \phi$. 但在对角线引理中取 $\phi =\neg \mathrm{True}$, 得到对某个 $\gamma$, $\mathcal{M}\models \gamma \leftrightarrow \neg \mathrm{True}(\#\gamma )$.

如果 $\mathcal{M}\models \gamma$, 则 $\mathcal{M}\models \mathrm{True}(\#\gamma )$, 与 $\mathcal{M}\models \gamma \leftrightarrow \neg \mathrm{True}(\#\gamma )$ 矛盾! 反之亦然, 得到矛盾.

$\square$

3应用

一个足够强的形式系统是 $1$ 阶 Peano 算术 ${\mathsf{PA}}_1$, 它带有标准的 Gödel 编号.

命题 3.1. 如果 $\mathbb{N}$ 是 ${\mathsf{PA}}_1$ 的模型, 那么它就满足对角线引理.

证明. 首先, 如下的函数可以延拓到某个可定义函数: $$\begin{array}{rlrl}d:\#& \mathrm{Free}(x)& \to & \mathbb{N}\\ & \#\varphi & \mapsto & \#\varphi (\#\varphi ).\end{array}$$这是因为它是递归可枚举函数, 从而在算术阶层里属于 ${\Sigma }_1^0$ (Post 定理), 故它可定义. 取 $\gamma$ 为 $\chi (\#\chi )$, 其中$$\chi (x)=\exists y(y=d(x)\wedge \phi (y)).$$下验证 $\mathbb{N}\models \gamma \leftrightarrow \phi (\#\gamma )$.

•	一方面, 如果 $\mathbb{N}\models \gamma$, 则 $\mathbb{N}\models \phi (d(\#\chi ))$, 即 $\mathbb{N}\models \phi (\#\chi (\#\chi ))$, 即 $\mathbb{N}\models \phi (\#\gamma )$.
•	另一方面, 假设 $\mathbb{N}\models \phi (\#\gamma )$. 我们有 $x=\#\chi$, $y=\#\gamma$ 满足 $\mathbb{N}\models y=d(x)$. 结合 $\mathbb{N}\models \phi (\#\gamma )$, 得到 $\mathbb{N}\models \exists y(y=d(\#\chi )\wedge \phi (y))$, 即 $\mathbb{N}\models \gamma$.

综合两方面得到命题.

$\square$

注 3.2. 由 Tarski 定理 (2.1) 得到 $\#\mathrm{Th}(\mathbb{N})$ 是不可定义集. 但是 Gödel 编号本身给出 $\#\mathrm{Th}({\mathsf{PA}}_1)$ 是可定义集, 这说明 ${\mathsf{PA}}_1$ 有非标准模型, 证明了 Gödel 第一不完备定理.

术语翻译

Tarski 不可定义定理 • 英文 Tarski’s undefinability theorem • 德文 Tarskis Undefinierbarkeitssatz • 法文 théorème de Tarski