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 2 3 4 5 6 7 8 9 10
卢小云
Latest posts by 卢小云 (see all)
Total Page Visits: 1260 - Today Page Visits: 1

6人评论了“Gödel的不完备性定理(四)”

  1. 网站的编辑平台是 WordPress,非常 high-level。我曾和编辑讨论如何到 low-level 去调用 HTML 和 JavaScript 进行文字/页面界面处理,没有找到途径。从页面的源代码看,这里的数学符号展示是通过 MathJax 现实的。请教一下,G 的哥特字体的 MathJax 代码 $\mathcal{G}$ 是如何被 WordPress 接受的?它接受 TeX/LaTeX、HTML 和 JavaScript 吗?

  2. 原问是:请教一下,G 的哥特字体的 MathJax 代码 \mathcal{G} 是如何被 WordPress 接受的?

    1. 这个问题得问老板王赤了。我给他的是Latex文件,不知他是如何做的。

  3. 这个网站用的wordpress支持的MathJax。它直接支持\mathcal{G}。一般数学相关的 latex command 都行。只是不支持非数学的text format 指令,比如\section{ }, \noindent, \ol, \ul 一类的。

发表评论

您的邮箱地址不会被公开。 必填项已用 * 标注