歌德尔不完全定理

1、歌德尔不完全定理 定理：如果形式算术系统是简单无矛盾的，那么它就是简单不完全的；这就是说，在系统中存在具有形式(x)Ax的公式(或称命题)B，使得B和B都不是系统的定理，这样的B称为不可判定的命题。§1.歌德尔定理的直观说明 歌德尔从说谎者悖论(我正在说的这句话是假的)得到启发，领悟到“真实性”与“可证性”是两种不同的概念。歌德尔巧妙地用“可证性”代替“真实性”，把形式算术系统中的可证性表达在该系统中，避免了悖论，得到不完全性结论。不完全性定理的直观证明：设形式算术系统是简单完全的，即命题B或B 是可证的。若B可证，则它所表达的元数学命题“B在系统中不是可证的”就是真的，这就是说B不

2、是可证的，与题设矛盾。如果B 是可证的，则“并非B在系统中不是可证的”这一命题真，即B是可证的，这与题设“B 是可证的”相矛盾。由上可得：系统不是简单无矛盾的。所以，如果形式算术系统是简单无矛盾的，那么它就是简单不完全的。B就是一个不可判定命题，即B与B 都不可证。由于B确实不可证，因而“B在系统中不是可证的”这一元数学命题就是真的，在系统中表达它的命题B也就是真的。因此，在系统中存在真的但又不可证的命题。(以下红色字符表示公式，绿色字符表示歌德尔数，兰色字符表示自由变项，粉红色字符表示与歌德尔数相应的数字)§2.歌德尔配数法把自然数114依次配给如下符号：、 、=、+、·

3、 、0、(、)。对每一个不同的自然数变项配以大于14的不同素数。因此，我们在初始符号和自然数的一个子集之间建立了一一对应的关系。规定：自然数的有穷序列k1,k2,kn,对应于单个的自然数：2k1·3k2·5k3·Pnkn,这里Pi是第i个素数(按数量大小的顺序排列)。一个公式是符号的有穷序列，对每个公式配以一个数，该数对应于配给其构成公式的符号的自然数序列。例如公式 (C)(C+a=b)中，该公式的歌德尔数为：213·37·523·714·1113·1323·1711·199·2317

4、·298·3119·3714 因构成该公式的12个初始符号对应的歌德尔数是： ( C ) ( C + a = b ) 13 7 23 14 13 23 11 9 17 8 19 14一个证明是公式的有穷序列，对每一个证明配以一数，它对应于配给其构成证明的公式的自然数序列。例如，以下两个公式的序列：(a)(a=b)，(a)(a=0)，构成一个证明，设已求出第一式的歌德尔数为m，第二式的歌德尔数为n，则该证明的歌德尔数为：2m·3n。由此，在公式和自然数的一个子集之间，证明和自然数的一个子集之间建立了一一对应的关系。这样，我们就为形式算术系统建立了一种完全算

5、术化的方法，使系统中的初始符号、公式和证明同自然数的子集之间建立起一一对应的关系。§3.歌德尔不完全性定理的证明在歌德尔原来的证明中，需要引用无矛盾性的概念。一个形式系统是无矛盾的，如果有一个公式F使得： F(Z0)，F(Z1)，F(Z2)，; ()F()并非全都可证。否则，F(Z0)，F(Z1)，F(Z2)，; ()F()全都可证，系统就是矛盾的。显然，无矛盾性蕴涵简单无矛盾性。严格陈述的歌德尔不完全性定理：如果形式算术系统是简单无矛盾的，则U(Zm)不是可证的；如果系统是无矛盾的，则U(Zm)不是可证的。因此，如果系统是无矛盾的，则它就是不完全的，U(Zm)就是一个不可判定的命题

6、。§4.U(Zm)的形式构造设公式(a)(a=b)的歌德尔数为m，而自由变项b有歌德尔数为19。在公式中，以m的相应的数字Zm替代b，得公式 (a)(a= Zm )；该公式亦有一个歌德尔数，它是从歌德尔数为m的公式中，以m的数字Zm 替代歌德尔数为19的自由变项所得公式的歌德尔数。这就唯一地确定了一个数，该数是m和19的一个算式函数。假定原公式为A，包含自由变项b，所得公式记为SubStAZmb,该公式的歌德尔数记为Sb(mm19),简记为Sb(m,m)。函数Sb(m,m)称之为“代入函数”。该函数是能行可计算的，即它是一个递归函数。一般的，用Sb(x,y)表示代入函数，它是在歌德尔

7、数为x的公式(含自由变项)中，以y的数字Zm代替自由变项所得的公式的歌德尔数。如果原公式无自由变项，则代入的结果等于不代入，即Sb(x,y)=x。由于Sb(x,y)是递归函数，因而在系统中是数字可表示的，令表示Sb(x,y)的形式函数表达式是S (1，2)。Pf(y,a)相应于元数学谓词“Y是公式A的一个证明”是递归谓词，因而在形式算术系统中是数字可表达的，令表达Pf(y,a)的公式为B (1，2)。在形式算术系统中构造以下公式： U(a):( b) B(b,S(a,a),令该公式的歌德尔数为m。在上述公式中，以m的数字Zm替代自由变项a，得到公式：U(Zm):( b) B(b,S(Zm, Z

8、m)，根据代入函数Sb(x,y)的定义，U(Zm)的歌德尔数为Sb(m,m)。U(Zm)就是不可判定的命题，即：对所有b而言，B(b,S(Zm, Zm)是假的。由于S(Zm, Zm)表示Sb(m,m)，B (1，2)表达Pf(y,a)，因而U(Zm)即 ( b) B(b,S(Zm, Zm)表达了直观的算术命题：对所有自然数x而言，Pf(x,Sb(m,m)是假的，可记为( x) Pf(x,Sb(m,m),即所有自然数x都不是歌德尔数为Sb(m,m)的公式的证明的歌德尔数。即：歌德尔数为Sb(m,m)的公式不是可证的，但U(Zm)的歌德尔数正是Sb(m,m)，因此，与上述算术命题相应的元数学命题就

9、是：“U(Zm)在系统中不是可证明的”。 U(Zm)在系统中表达了这个元数学命题，是一个断定自身不可证的公式。歌德尔定理证明：如果形式算术系统是简单无矛盾的，则U(Zm)不是可证的。假设U(Zm)可证，它就有一个证明，其歌德尔数为k,则有Pf(k,Sb(m,m).因为S (1，2)表示Sb(x,y)，B (1，2)表达Pf(y,a)，所以可得B(Zk,S(Zm,Zm)是可证的。又由假设U(Zm)即( b) B(b,S(Zm, Zm)可证，根据系统中的全称消去规则可得：B(Zk,S(Zm, Zm)是可证的。这样，系统中有矛盾。根据归谬法，假设是不成立的。如果系统是无矛盾的(从而也是简单无矛盾的)，则U(Zm)不是可证的。据，U(Zm)不可证，即没有一个数是U(Zm)的证明的歌德尔数，而U(Zm)的歌德尔数为Sb(m,m),因此Pf(0,Sb(m,m),Pf(1,Sb(m,m),皆假，表达在系统中即为： B(Z0,S(Zm, Zm)， B(Z1,S(Zm, Zm)， B(Z2,S(Zm, Zm)，皆可证。根据系统的无矛盾性，可得 ：( b) B(b,S(Zm, Zm)即U(Zm)不是可证的。歌德尔第二不完全性定理：如果形式算术系统是简单无矛