完备性、非完备性定理简介*

哥德尔完备性定理: 每一个为真的逻辑公式是可证明的。

其等价表述是: 每一个逻辑公式或者是可满足的(Satisfiable)，或者是可证否的(Refutable). 如果一个逻辑公式为真，那么必存在一个形式化证明(Formal Proof).

完备性定理的重要意义在于建立了一阶逻辑的语义真值与语法可证明性之间的联系。同时，也建立了模型论与证明理论之间的联系。

哥德尔的证明(梗概):

哥德尔首先引入Hilbert和Ackermann 1928年论文中的结论: 任意一阶逻辑公式可以转化为前束范式${\pi }_n$$\pi_n$(若干个$\mathrm{\forall }\cdots \mathrm{\exists }\cdots$$\forall\cdots\exists\cdots$块).

哥德尔又认为前束范式${\pi }_2$$\pi_2$（度为1）的完备性等同于前束范式${\pi }_n$$\pi_n$的完备性。

最后,哥德尔证明前束范式${\pi }_2$$\pi_2$的完备性, 即:任何前束范式${\pi }_2$$\pi_2$,要么是可满足的,要么是可证否的。

以稍简单的实例来证明:

$\phi =\mathrm{\forall }{x}_0\mathrm{\exists }{x}_1\psi (x_0,x_1).$${\varphi}= {\forall}x_0{\exists}x_1{\psi}(x_0, x_1).$

定义:

${\phi }_0:\psi (x_0,x_1)$${\varphi}_0: {\psi}(x_0, x_1)$ ${\phi }_1:\psi (x_0,x_1)\wedge \psi (x_1,x_2)$${\varphi}_1: {\psi}(x_0, x_1) {\land} {\psi}(x_1, x_2)$ $\cdots$${\cdots}$ ${\phi }_n:\psi (x_0,x_1)\wedge \cdots \wedge \psi (x_n,x_{n+1}).$${\varphi}_n: {\psi}(x_0, x_1) {\land} {\cdots}{\land} {\psi}(x_n, x_{n+1}).$

对于任意的$n$$n$, 可以分析$\mathrm{\exists }{x}_0\cdots \mathrm{\exists }{x}_{n+1}{\phi }_n$${\exists}x_0{\cdots}{\exists}x_{n+1}\varphi_n$的可满足性。

第一种情况：

如果对于某个$n$$n$, ${\phi }_n$$\varphi_n$不可满足。 根据命题逻辑的完备性, 可得$\mathrm{\neg }{\phi }_n$$\lnot\varphi_n$是可证明的。 也就是说$\phi$$\varphi$是可证否的。

第二种情况:

如果${\phi }_n$$\varphi_n$始终是可满足的, 那么在$\{x_0,\cdots ,x_{n+1}\}$$\{x_0,\cdots,x_{n+1}\}$中可构造出可数个模型(Model)满足所有的${\phi }_n$$\varphi_n$, 于是$\phi$$\varphi$是可满足的。

哥德尔的完备性证明本质上有个前提, 是紧致性(Compactness)定理。

关于哥德尔的完备性定理, 当前流行的证明方法是亨金(Henkin)的证明。

此外, 哥德尔证明中的可满足情形下的模型是可数的, 所以,这个哥德尔的证明本质上也证明了勒文海姆–斯科伦(Löweheim-Skolem)定理。

勒文海姆–斯科伦定理是模型论最基本的定理之一:任何可数的理论如果有一个模型,那么这是一个可数的模型。

哥德尔第一非完备性定理:

任何一致的(Consistent)形式系统$P$$P$,总是存在$P$$P$语言中的若干语句不能在$P$$P$中被证明或证否。

If $P$$P$ is ω-consistent, then there is a sentence which is neither provable nor refutable from $P$$P$.

换个具体的说法是:

没有一致的公理系统可以证明算术中的所有真命题。

也就是说, 任意支持算术的理论中, 一致性和完备性不可能同时满足。

哥德尔的ω一致概念: $P$$P$是ω一致的(ω-consistent),如果$\mathrm{\forall }nP⊢\mathrm{\neg }\phi (n)$${\forall}nP{\vdash}\lnot\varphi(n)$ 蕴含 $P⊬\mathrm{\exists }x\phi (x)$$P{\nvdash}{\exists}x{\varphi}(x)$.

另一个重要的工具是哥德尔数(G?del Numbering),提供一种将公式转换成自然数的机制。

核心思想是: 公式一旦能转换成自然数,就可以作为参数传递给公式了。

具体地，为每个符号$s$$s$赋一个固定值$\mathrm{\#}(s)$$\#(s)$.

$\mathrm{\#}(0)=1,\mathrm{\#}(=)=5,\mathrm{\#}(\mathrm{\neg })=9,$$\#(0)=1,\#(=)=5,\#(\lnot)=9,$

$\mathrm{\#}(1)=2,\mathrm{\#}(()=6,\mathrm{\#}(\mathrm{\forall })=10,$$\#(1)=2,\#(()=6,\#(\forall)=10,$

$\mathrm{\#}(+)=3,\mathrm{\#}())=7,\mathrm{\#}(v_i)=11+i,$$\#(+)=3,\#())=7,\#(v_i)=11+i,$

$\mathrm{\#}(\times )=4,\mathrm{\#}(\wedge )=8,$$\#(\times)=4,\#(\land)=8,$

符号串(或公式)$w=⟨w_0,\cdots ,w_k⟩$$w={\langle}w_0,\cdots,w_k\rangle$对应于

$[w]=2^{\mathrm{\#}(w_0)}\cdot 3^{\mathrm{\#}(w_1)}\cdot \cdots \cdot p_k^{\mathrm{\#}(w_k)}$$[w]=2^{\#(w_0)}{\cdot}3^{\#(w_1)}{\cdot}\cdots{\cdot}p_k^{\#(w_k)}$

其中$p_k$$p_k$是第$k+1$$k+1$个素数.

哥德尔的不动点(Fixed-Point)定理

如果$\varphi (v_0)$${\phi}(v_0)$是一个公式,那么一定存在一个公式$\psi$${\psi}$使得$P⊢\psi \leftrightarrow \varphi (\lceil \psi \rceil )$$P{\vdash}{\psi}{\leftrightarrow}{\phi}(\lceil{\psi}\rceil)$, 此处 $\lceil \psi \rceil$$\lceil{\psi}\rceil$是个对应于$\psi$${\psi}$自然数编码的公式。

证明(梗概): 令Prf(x,y)(哥德尔原文中用B(x,y))是一个$P$$P$理论中的公式。

1.$n$$n$是关于$\varphi \Rightarrow P⊢Prf(n,\lceil \varphi \rceil )$$\phi\Rightarrow\,P\vdash\,Prf(n, \lceil\phi\rceil)$的证明(编码)。

2.那么$n$$n$一定不是$\varphi \Rightarrow P⊢\mathrm{\neg }Prf(n,\lceil \varphi \rceil )$$\phi\Rightarrow\,P\vdash\,{\lnot}Prf(n, \lceil\phi\rceil)$的证明(编码)。

现在令$Prov(y)$$Prov(y)$(哥德尔原文中用$Bew(y)$$Bew(y)$)表示公式$\mathrm{\exists }xPrf(x,y)$${\exists}x\,Prf(x,y)$. 根据哥德尔的不动点定理,有这样一个语句$\varphi$$\phi$满足:

3.$P⊢(\varphi \leftrightarrow \mathrm{\neg }(n,\lceil \varphi \rceil ))$$P\vdash(\phi\leftrightarrow{\lnot}(n, \lceil\phi\rceil))$. 这里$\varphi$$\phi$可以理解成"我是不可证明的".

如果$P⊢\varphi$$P\vdash\phi$, 那么根据第1式,存在 $n$$n$使得$P⊢Prf(n,\lceil \varphi \rceil )$$P\vdash\,Prf(n, \lceil\phi\rceil)$,于是$P⊢Prov(\lceil \varphi \rceil )$$P\vdash\,Prov(\lceil\phi\rceil)$, 再看第3式,就不一致了。

所以,

4.$P⊬\varphi$$P\nvdash\phi$.

或者说(结合第4式和第2式), $P⊢\mathrm{\neg }Prf(n,\lceil \varphi \rceil )$$P\vdash{\lnot} Prf(n,\lceil\phi\rceil)$.

后来, 布鲁斯(George Boolos)简化了哥德尔第一非完备性定理的证明。

哥德尔第二非完备性定理是第一非完备性定理的扩展, 一个简单的表述是:

语言的一致性不能在该语言中被证明。

If $P$$P$ is consistent, then Con($P$$P$) is not provable from $P$$P$.

严谨的哥德尔第二非完备性定理证明由希尔伯特和伯尼斯(Bernays)于1939年给出。

此外, 费弗曼(Feferman)于1960-1961年给出了更简洁的哥德尔第一、第二非完备性定理的严谨证明。