後繼函數

维基百科,自由的百科全书

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

概述[编辑]

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

这可以用来计算任意两自然数的加法,例如

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

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

另见[编辑]

参考文献[编辑]

  1. ^ Halmos, Chapter 11
  2. ^ Rubtsov, C.A.; Romerio, G.F. Ackermann's Function and New Arithmetical Operations (PDF). 2004. 
  • Paul R. Halmos. Naive Set Theory. Nostrand. 1968.