Gödel的不完备性定理（四）

Gödel数

Gödel的巧妙之处，就是给系统中的每个字母或符号x都赋予一个不同的数，叫做x的Gödel数，用$\mathcal{G}$(x)表示。在MIU系统中，比如 $\mathcal{G}$(M)=1, $\mathcal{G}$(I)=2, $\mathcal{G}$(U)=3, $\mathcal{G}$($\rightarrow$)=4。为了简化我们的叙述，再把分号“；”引进系统，并且赋值$\mathcal{G}$(;)=5。

一旦系统中的每个字母或者符号都安排了一个数，接下来就可给每个字符串安排一个数，具体做法如下。

假设$x=x_1x_2\cdots x_n$是个长度为$n$的字符串，其中$x_i$ 是系统中的一个字母或符号，我们定义 $\mathcal{G}(x)=p_1^{\mathcal{G}(x_1)}p_2^{\mathcal{G}(x_2)}\cdots p_n^{\mathcal{G}(x_n)}$， 其中 $p_1,p_2,\cdots, p_n$是前$n$个素数。 比如$p_1=2,p_2=3,p_3=5,p_4=7,p_5=11,p_6=13,p_7=17, p_8=19, p_9=23,\cdots$。

下面先看几个例子。

$\mathcal{G}(MI)=2^{\mathcal{G}(M)}3^{\mathcal{G}(I)}=2^13^2=18$,
$\mathcal{G}(IM)=2^{\mathcal{G}(I)}3^{\mathcal{G}(M)}=2^23^1=12$,
$\mathcal{G}(MIU)=2^{\mathcal{G}(M)}3^{\mathcal{G}(I)}5^{\mathcal{G}(U)}=2^13^25^3=2250$,
$\mathcal{G}(MIUIU)=2^{\mathcal{G}(M)}3^{\mathcal{G}(I)}5^{\mathcal{G}(U)}7^{\mathcal{G}(I)}(11)^{\mathcal{G}(U)}=2^13^25^37^{2}(11)^3=2994750$,
$\mathcal{G}(MI\rightarrow MIU)=2^{\mathcal{G}(M)}3^{\mathcal{G}(I)}5^{\mathcal{G}(\rightarrow)}7^{\mathcal{G}(M)}(11)^{\mathcal{G}(I)}(13)^{\mathcal{G}(U}$ $=2^13^25^47^1(11)^2(13)^3=a$,
$\mathcal{G}(MI;MI\rightarrow MIU)=2^{\mathcal{G}(M)}3^{\mathcal{G}(I)}5^{\mathcal{G}(;)}7^{\mathcal{G}(M)}(11)^{\mathcal{G}(I)}(13)^{\mathcal{G}(\rightarrow)}(17)^{\mathcal{G}(M)}(19)^{\mathcal{G}(I)}(23)^{\mathcal{G}(U)}$ $=2^13^25^57^1(11)^2(13)^4(17)^1(19)^2(23)^3=b,$

最后两个数有点大，就分别用a和b表示了。数字b是字符串“MI；MI$\rightarrow$MIU”的Gödel数。MIU 的Gödell数是2250。因为“MI；MI$\rightarrow$MIU”证明了“MIU”是定理，所以也可以简化成数字“b”证明了数字“2250”是个定理。

假如表达式P是个定理，我们就说它所对应的Gödel数$\mathcal{G}(P)$是一个定理数。我们前面问过：MU是定理吗？因为 $\mathcal{G}(MU)=2^{\mathcal{G}(M)}3^{\mathcal{G}(U)}=2^13^3=54$，所以也相当于问：54是定理数吗？

通过Gödel数，每个字符串都对应唯一一个数字，不同的字符串对应不同的数字。根据数论中的因子分解定理，我们可以反过来确定一个数字是不是一个字符串的Gödel数。如果是，它对应的符号串又是什么？

比如 $15=3^15^1$就不是系统中的Gödel数， $420=2^23^15^17^1$就是IMMM的Gödel数。

MIU是一个非常简单的形式系统，但通过它我们可以了解Gödel数的精髓。任意一个形式系统，Gödel数的定义是类似的，无非是字母和符号多些，公理和推导规则复杂些，加上定义表达式和规范表达式，如此而已。

最后，我们来回答一下，MU是不是MIU系统中的一个定理？回答是否定的：不是！

如何证明呢？在MIU系统内无法证明，跳出系统之外才能证明。
我们要证明的是，如果一个表达式是个定理，表达式中I的数目一定不是3的倍数。
观察系统中的4条推导规则，规则1和4不会改变I的数目。如果原定理中I的数目是n，根据规则3，新定理中的I的数目就是n-3；根据规则2，新定理中I的数目就是2n。所以如果原定理中I的数目不是3的倍数，则新定理中I的数目也不可能是3的倍数。由于公理MI中I的数目是1，不是3的倍数，所以任何一个定理中I的数目都不是3的倍数。

由于MU中I的数目是0，所以MU不是定理。又由于$\mathcal{G}(MU)=54$，所以54不是定理数。

（未完待续）

山里的小孩

卢小云

同学印象(1)

卢小云

在近海的河边

卢小云

犹他行（4）

卢小云

卢小云：幸福童年（20）

卢小云

埃德夫神庙

卢小云

卢克索

卢小云

数学中的悖论

卢小云

同学印象(2)

卢小云

数学家的故事（19） Gauss

卢小云

数学家的故事 （22）Dedekind

卢小云

有你就春暖花开

卢小云

1 2 3 4 5 … 7 8 9 10 Next »

• About
• Latest Posts

卢小云

1978年16岁入江西冶金学院数学师资班。毕业后入中国科学院应用数学研究所读研。1986入美国Rutgers大学数学系攻读博士学位，研究方向组合数学。现在美国人口普查局(Census Bureau)工作。在工作和数学研究以外，对数学史也很有兴趣。

Latest posts by 卢小云 (see all)

• 山里的小孩 - 11/04/24
• 同学印象(1) - 09/30/24
• 在近海的河边 - 08/08/24

相关文章：

奇妙的无穷大世界 Gödel的不完备性定理（三） Gödel的不完备性定理（六） Gödel的不完备性定理（五） 有趣的找怪球问题 (4) Gödel的不完备性定理（二）