後繼函數

数学中，後繼函數 或 後繼運算是使$S(n)=n+1$的原始递归函数S，其中n為自然数。例如， S(1)=2， S(2)=3。后继函數也称为zeration，因為它是第零个超運算：$H_{0}(a,\ b)=1+b$。zeration的推广是加法，加法可看做反复进行一定次数的后继运算。

概述

后繼函数被用在定义自然数的皮亚诺公理，皮亚诺公理形式化了自然数的结构，当中后继函数是自然数上的一种原始运算，定义所有大於0的自然数和加法。例如，1被定义为 S(0)，自然数的加法是由递归定义：

${\begin{aligned}&m+0&=m\\&m+S(n)&=S(m+n)\\\end{aligned}}$

这可以用来计算任意两自然数的加法，例如$5+2=5+S(1)=S(5+1)=S(5+S(0))=S(S(5+0))=S(S(5))=S(6)=7$。

集合论中曾提出了集中自然数的构造，例如冯·诺依曼将0构造为空集$\{\}$，将n的后继集$S(n)$构造为集合$n\cup \{n\}$。这样，无穷公理就保证存在包含0且对S闭合的集合，最小的此种集合用$\mathbb {N}$表示，就是自然数。 后续函数在超运算的格尔泽戈茨兹克层级中属于第0级，可以构建加法、乘法、幂、迭代冪次等。1986年，一项涉及超运算模式推广的研究调查了后继函数。

后继函数是用于描述递归函数可计算性的初等函数之一。

另见

• 后继序数
• 后继基数
• 增值和减值操作符
• 序列

参考文献

• Paul R. Halmos. Naive Set Theory. Nostrand. 1968.