递归过程与递归不变量公理

fxl810 2018-06-21

展开全文

先从最简单又不易理解的空集开始说起。不含任何元素的集合称为空集，这是现在对空集的一般定义，这个定义不能从无中生出有来所以我采用下面的定义：

空集合存在公理，既在某集合x内又在该集合外，亦即：

〆x彐y（y∈x∧y∈﹁x）式中的y不存在，{y}称为空集，记作φ。此前只定义了集合存在，所以集合的元素也是集合。空集φ存在，空集为元素的集合{φ}也存在，把它记为1，即1={φ}。1为元素的集合{1}也存在，称为1的后继，记为2，即2={1}={ {φ}}，一般的x的后继记为{x，﹁x}。就有{2，﹁2}=3.这样就得到一个递归过程的概念。由递归过程可以得到任何自然数。

递归过程是一个可排序的类，其中每一元素都称为项，有一个元素排在最前面，称为首项或称第一项，每一项都有后继项，即x∈﹁y→{x，﹁x}∈﹁y。最简单的递归过程是自然数组成的加法递归过程，首项是1，n的后继是n+1。由1不断加1构成，即{n，﹁n}=n+1。但自然数既是序数又是基数，所以自然数递归过程就分成两个，序数递归过程n→n+1，和基数递归过程(n)。其次是乘法递归过程，例如首项是2，逐项乘2，得到的，{2″，﹁2″}=2″*2。数列An=f（n），{An，﹁An}=f（n+1）。也构成递归过程。所以递归过程也常用An或f（n）表示。f（n）可以看成是由基数递归过程（n）导出的递归过程，是以（n）为自变量的函数值组成的递归过程。

随着（n）的不断增加，f（n）的值不断变化，一定存在这样一个值，它不再随（n）的增加而变化，这样一个值称为递归不变量。递归不变量的存在是用公理形式规定的。有递归过程就一定有递归不变量，一般情况递归不变量可能很复杂，但良序递归过程存在递归不变量，就比较简单。递归不变量存在公理是如下叙述的。

递归不变量存在公理：若有一递归过程x∈﹁y→{x，﹁x}∈﹁y，（意思是：x，x的继数，继数的继数等等组成一个类﹁y，称为递归过程）则一定存在一个集合满足条件z≈{z，﹁z}，亦即：

〆{x，﹁x}彐﹁y（（x∈﹁y→{x，﹁x}∈﹁y）→彐z（z≈x∧z≈{x，﹁x}））

z称为递归不变量。（上式意思是：对任何一个x的继数{x，﹁x}都存在递归过程﹁y，按﹁y中递归继数的规定，一定存在不变量z使得z与其继数，继数的继数等等基相等。）以上“=”是说=号两边的序数相等，“≈”是说≈号两边的数的基数相等。

最简单的基数是如下规定的：与A基相等的序数中，最小的一个作为A的基数。序数A的基数记为┆A┆。符号┆A┆内的数A是序数，┆A┆称为序数A的基数。

基数又是序数，每类基相等的序数中，都有一个基数，就是每个序数的基数，这个数就是递归不变量。递归不变量用符号“lim”表示。例如lim（n）表示自然数作基数时的递归不变量。

首先我们讨论limN等于甚么？按规定①，即 1≈2≈……≈n≈n+1其中最小的序数1，就叫作序数n的基数，所以limN=1。意思是自然数作序数时，每个序数都有基数，序数的基数是1。虽然自然数既是序数又是基数，不要认为序数n的基数就是n，前面强调序数与基数是两个不同概念，充分体现在这里。可按规定证明，任意有理数的基数都是1。

其次讨论lim（n）等于甚么？它是递归过程，就存在不变量，不变量记为ω，按自然数继数的规定。则有ω≈ω+1≈……≈ω+n，按规定②，基数n和n+1是基不相等的，所以ω不可能等于任何一个有限基数。称为无限大基数。作基数时常写作∞，作序数时是序数ω，ω+1，ω+2，……ω+n中最小的一个，排在任何一个自然数之后。因为┆ω┆≈┆ω+n┆，所以引入负数时可得∞-∞≈n称为不定式。加法运算要求结果唯一，规定作为序数计算时ω-ω=0，所以计算中遇到ω-ω时要，要按序数进行运算，不能取不变量。（n）取不变量∞也记作n→ω，即当n→ω，limf（n）=┆f（ω）┆。1/ω常用ε表示，ε=1/ω，称为无限小，排列在任何一个正有限小数之前。ω也称为加法递归不变量。（下文采用的指数表示方法为：e?=e/a，2″=2/n。/n表示n为上标，指数。）

最后求基数lim2/n，当n→ω时的不变量。它是递归过程，就存在不变量，不变量记为∫，就有∫≈2*∫≈2/2*∫≈2/3*∫≈……≈2/n *∫，∫作为基数它比任何数n*ω/n都大，作为序数排在任何一个，实数域上关于ω的N次多项f（ω）之后的第一个序数。

因为 ∫≈2/n *∫，引入倒数时，按基数算∫/∫≈2/n，∫/∫是个不定式，但序数乘法运算，一般规定，∫/∫=1。∫作为基数，理论上规定∫/∫可以等于任何数a，即规定a/∫为∫的倒数，理论是和谐的，一般使用∫/∫≈1。1/∫是∫的倒数，是比ε更小的无限小，记作d=1/∫，称为有限序数的微分，因为ω＜∫，所以ε＞d。∫也称为乘法递归不变量。