哥德尔不完备性定理

哥德尔数

我们这里构造一种对应关系，把数学中所有的东西都映射到某个数，称为 "哥德尔数"。

这样我们可以把关于数学性质的讨论，变成关于数的性质的讨论。

数学中最基础的是符号。首先，我们定义 个最基本的数学符号，并为他们分配 的哥德尔数。 , , 之类的字母的哥德尔数规定为 ， ， 等后面的质数。

在我们今天讨论的自然数范围内，这 个符号加上字母基本上能够表达一切了。

比如 "皮亚诺算术公理"

后继的数是指后面的数，比如 是 的后继， 表达为 , 就是 ， 就是 依此类推…

到此为止，基本的符号和数字都有了自己的哥德尔数。数字和符号的序列可以构成命题。比如 是一个命题。这五个符号对应的哥德尔数分别是 。

命题转化成哥德尔数

如何把命题转化成哥德尔数呢？

我们的方法是写出前几个质数 ，把五个符号的哥德尔数放到它的指数位置然后再相乘

这样命题 的哥德尔数就是

约等于 亿亿亿。

可以看出命题的哥德尔数都很大。我们小学二年级都学过质因数分解。算术分解定理：

每个大于 的自然数，要么本身就是质数，要么可以写为两个或以上的质数的积，而且这些质因子按照从小到大排列之后，写法只有一种方式。

一个整数的质因数分解方式是唯一的。

所以这种方法保证了每个命题都可以对应到唯一的哥德尔数。而你看到一个哥德尔数，也可以通过质因数分解找到它对应的命题。

到目前为止，所有的命题都有了自己对应的哥德尔数。命题序列可以构成证明过程。

比如如何证明 是存在的？

根据皮亚诺公理，每个自然数都存在后继数，因此 的后继 存在。

写出来就是因为 所以

写成哥德尔数就是因为 ，所以 。

这两个命题的哥德尔数分别是

和

分别记为 和 。

计算证明过程的哥德尔数：

到目前为止，所有的证明过程都有了自己的哥德尔数。

复杂的命题转化成哥德尔数

命题：质数有无穷多个。

等价于：不存在最大的质数。

即：

即:

存在和任意的转化

存在 不满足条件 等价于非任意 满足条件

不存在 满足条件 等价于任意 均不满足条件 .

等价于

质数：没有除 和自身外的因数。

即：

大于 :

小于 :

且 :

现在命题质数有无穷多个可以用基本数学符号来表达了。然后就可以算哥德尔数了。

讨论命题的命题转化成哥德尔数

甚至可以把一个讨论命题的命题也变成哥德尔数。

命题：

等价于

对应哥德尔数：

哥德尔数：

讨论命题的命题： 的第二个符号是加号

等价于：

命题 的哥德尔数 (G) 能被 整除，却不能被 整除。

等价于：

无法证明的命题转化成哥德尔数

元数学的 “不可证” 断言，等价于一个关于自然数关系的否定性存在命题。

命题： 哥德巴赫猜想无法证明。

等价于： 没有一个证明过程以哥德巴赫猜想收尾。

即：

不存在一个 步的证明过程使得它的哥德尔数能被 整除。

总之，各种命题，甚至是讨论命题的命题，无论真假都可以用哥德尔数表示。

函数 sub (a,b,c)

命题：

哥德尔数： 记为

用 替换 得到一个新命题：

我们定义一个特殊的函数 sub (a,b,c)：

取哥德尔数为 的命题，找到命题中哥德尔数为 的符号的位置，把它替换成数字 ，得到的新命题的哥德尔数就是 sub (a,b,c)。

sub (m,m,17) 的命题：

取哥德尔数是 的命题，也就是 。

找到命题中哥德尔数为 的符号的位置， 也就是符号 的位置。

把它替换成 。

得到的这个新命题就是 。

也就是说：命题 的哥德尔数就是 sub (m,m,17)。

"无法证明哥德尔数是 sub (n,n,17) 的命题" 的哥德尔数是 sub (n,n,17)

命题 a： 无法证明哥德尔数是 sub (y,y,17) 的命题。

哥德尔数： 记为 。

那这个哥德尔数是 sub (y,y,17) 的命题是什么呢？

取哥德尔数是 的命题，找到命题的哥德尔数是 的符号，也就是符号 的位置，把它替换成 ，所得到的命题的哥德尔数是 sub (y,y,17)。

命题 b： 无法证明哥德尔数是 sub (n,n,17) 的命题。

那这个哥德尔数是 sub (n,n,17) 的命题是什么呢？

取哥德尔数是 的命题，也就是命题 a，找到命题的哥德尔数是 的符号，也就是符号 的位置，把它替换成 ，所得到的命题（刚好就是命题 b）的哥德尔数是 sub (n,n,17)。

也就是说：命题 b 的哥德尔数就是 sub (n,n,17)。

"无法证明哥德尔数是 sub (n,n,17) 的命题" 的哥德尔数是 sub (n,n,17)。

这个命题刚好说的就是自己是无法证明的。

"无法证明哥德尔数是 sub (n,n,17) 的命题" 是真命题

反证法：

假设 "无法证明哥德尔数是 sub (n,n,17) 的命题" 是假命题。

立即得出（反命题是真命题）：

"可以证明哥德尔数是 sub (n,n,17) 的命题" 是真命题。

推出（可以证明是真的那么一定是真命题）：

"哥德尔数是 sub (n,n,17) 的命题" 是真命题。

由于 "无法证明哥德尔数是 sub (n,n,17) 的命题" 的哥德尔数是 sub (n,n,17)，所以推出：

"无法证明哥德尔数是 sub (n,n,17) 的命题" 是真命题。

这与假设矛盾，如果承认数学公理体系具有一致性则假设不成立。

"无法证明哥德尔数是 sub (n,n,17) 的命题" 是真命题。

也就是说：

"哥德尔数是 sub (n,n,17) 的命题" 是无法证明的真命题。

哥德尔第一不完备性定理

任何一个包含了足够强的算术公理的形式化系统，如果是一致的，就是不完备的。即其中必须存在一些既不能证明，也不能证否的命题。

哥德尔第二不完备性定理

任何一个包含了足够强的算术公理的形式化系统，其一致性不能在内部得到证明。

我们假设数学公理体系具有一致性，推出了 "哥德尔数是 sub (n,n,17) 的命题" 是真的且无法证明。也就是说我们证明哥德尔数是 sub (n,n,17) 的命题为真用到的唯一条件就是假设数学公理体系是一致的。但哥德尔第一不完备性定理告诉我们哥德尔数是 sub (n,n,17) 的命题是不能证明的，这与我们已经证明出了 "哥德尔数是 sub (n,n,17) 的命题" 矛盾。所以数学公理体系不具有一致性。

已知的 sub (n,n,17)

克鲁斯卡树定理

帕里斯 - 哈林顿定理

金森 - 麦卡隆定理

古德斯坦定理