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

形式系统

先看一个叫做MIU系统的具体例子，该例子是从
文献[1]中移植过来的。[1]: Hofstader, R. Douglas Gödel, Escher, Bach: an Eternal Golden Braid. Basic Books, Inc., New York, 1979.

MIU系统：
字母表：{M，I，U}
公理：MI
规则：

xI $\rightarrow$xIU.
Mx$\rightarrow$Mxx.
xIIIy$\rightarrow$xUy.
xUUy$\rightarrow$xy.

其中符号“$\rightarrow$”表示推出，导出的意思。换言之，上面规则用文字表达就是如下的规则：

如果xI是定理，则xIU也是。
如果Mx是定理，则Mxx也是。
一个定理中如有III出现，将III换成U后也是定理。
一个定理中如有UU，把UU去掉后也是定理

这是一个简单的例子，但包含了形式系统的基本要素。第一，它有一个有限的字母和符号表，这里是三个字母和一个符号”$\rightarrow$”；第二，它有给定的公理，这里只有一条MI；第三，它有推导出新定理的规则。注意规则中的x 和y不属于系统中的字母，这里仅用它们表示已有的字符串。比如在MI中，如写成xI，则x就是M；如写成Mx则x就是I。又比如MIIII若写成xIIIy，则视三个I是前三个或后三个而定，分别为x=M，y=I和x=MI以及y为空字符了。再比如MIIIIIIII若写成xIIIy，就更要小心了，这时的x和y就要根据x和y中间的三个I的位置而有更多的取值了。比如x可以分别取值M； MI； MII； MIII；等等。

在复杂的形式系统中还要定义表达式(formula)以及规范表达式(well-formed formula)。MIU系统比较简单，任何一个字母串都是合乎规范的表达式。为了说明如何定义Gödel 数，MIU系统就能胜任。

该系统有哪些定理呢？首先，公理MI是一个定理，从它和规则1可以导出MIU也是定理。由于MIU是定理，根据规则2又可导出MIUIU，MIUIUIUIU都是定理。

下面分别给出了MIU，MIUIU和MIUIUIUIU三个定理的逻辑链证明。

MI；MI$\rightarrow$MIU。
MIU；MIU$\rightarrow$MIUIU。
MIUIU；MIUIU$\rightarrow$MIUIUIUIU。

注意在证明中句号“。”表示证明结束，分号“；”用来分开证明的不同步骤；每一步要么引用某个定理，要么引用某个规则。

下面的证明是直接从公理出发证明MIUIUIUIU是定理。

MI；MI$\rightarrow$MIU；MIU$\rightarrow$MIUIU；MIUIU$\rightarrow$MIUIUIUIU。

同样从公理MI可以导出MII，MIIII也是定理。从MIIII和规则3又导出MUI也是定理。还可以从MIII导出MIIIIIIII也是定理，从而MIUIIII进而MIUUI都是定理。从后者还可导出MII又是定理。
因为我们已经知道MII是定理了，这里给出的是该定理的另一个证明。

比如下面给出了MUUII是定理的一个证明：
MI；MI$\rightarrow$MII；MII$\rightarrow$MIIII；MIIII$\rightarrow$MIIIIIII；
MIIIIIIII$\rightarrow$MUIIIII；MUIIIII$\rightarrow$MUUII。

不难看出，该系统可以导出无穷多的定理。

这么多的定理，都有些什么意思呢？没有意思，真的没有意思。这正是形式系统的关键所在：形式系统不谈意思，只谈形式。天知道MI有啥意思？

形式系统虽然不谈意思，整个系统还是非常有意思的。比如Russel他们建立的系统，就能建立起整个数论体系。在他们的那套体系中就可讨论费尔马大猜想，孪生素数猜想，哥德巴赫猜想等等有意思的问题。

比如，在MIU系统中，MU是定理吗？这个问题好像就有点意思了。

（未完待续）