成为VIP
这一篇文章是接着之前的“u算子（最小数算子）保持可表示性的证明”，在那里面证明了u算子保持可表示性，这篇文章是要证明递归函数具有可表示性，这个结论是“哥德尔不完备性定理”里最重要的结论之一，完成了这个证明相当于翻越了抵达“哥德尔不完备性定理”的一座高山，后面再证明哥德尔不完备性定理就很简单了。而中国剩余定理在证明递归函数具有可表示性的过程中具有举足轻重的作用。中国剩余定理在前面的“数论基础（四）”里证明过，它之所以与递归函数具有可表示性有关，是因为peano形式算术就是描述数论的，所以只要是包含了peano形式算术的谓词演算，都具有这个结论，于是是不完备的。在证明哥德尔不完备性定理的最后一步余数定理，是构造了一个具有自相关性的闭式，它的意思是“我从算术公理集不可证”，于是找到了一个不可判定的公式。而这个闭式之所以存在，是因为有一个二元关系，它是递归的，所以是可表示的。下面就来证明递归函数具有可表示性。
现在先给出递归函数的定义：基本函数以及由它们经有限次使用下面规则一、二、三得到的函数叫做递归函数。
这个函数就是对应于数论里的同余，正是由于这个函数的存在，递归函数可表示性的证明需要用到中国剩余定理。由于基本函数都属于REC*,而且REC*与REC相比只是缺少规则二（递归），所以要证明REC*包含REC只需证明REC*中的函数对于规则二封闭。现在通过两个引理来证明最后的结论。
这个中国剩余定理在“数论基础（四）”已经证明过，它们是一样的，只是在这里用了rem余数函数的记号。
引理2的证明是根据中国剩余定理推导出来的，在此略。接下来证明REC*中的函数对于规则二封闭。
可以证明（1）（2）（3）是等价的余数定理，可以看到对于（3），f 就等于等式左边的函数。如果等式的左边这个函数是属于REC*的，那么f就属于REC*。即如果等式左边的函数中的x,y可以写成REC*里的函数，根据函数的复合规则，就能推出等式左边的函数属于REC*，那么f就属于REC*。
限时特惠：本站每日持续更新海量设计资源，一年会员只需29.9元，全站资源免费下载
站长微信：ziyuanshu688
htebazile
