查看“︁後繼函數”︁的源代码

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

== 概述 ==
后繼函数被用在定义自然数的[[皮亚诺公理]]，皮亚诺公理形式化了自然数的结构，当中后继函数是自然数上的一种原始运算，定义所有大於0的自然数和加法。例如，1被定义为 ''S''(0)，自然数的加法是由递归定义：
:<math>\begin{aligned}
&m+0&=m\\
&m+S(n)&=S(m+n)\\
\end{aligned}</math>
这可以用来计算任意两自然数的加法，例如<math>5+2=5+S(1)=S(5+1)=S(5+S(0))=S(S(5+0))=S(S(5))=S(6)=7</math>。

[[集合论]]中曾提出了集中自然数的构造，例如[[冯·诺依曼]]将0构造为空集<math>\{\}</math>，将''n''的后继集<math>S(n)</math>构造为集合<math>n\cup\{n\}</math>。这样，[[无穷公理]]就保证存在包含0且对S闭合的集合，最小的此种集合用<math>\mathbb{N}</math>表示，就是自然数。<ref>Halmos, Chapter 11</ref>
后续函数在[[超运算]]的[[格尔泽戈茨兹克层级]]中属于第0级，可以构建[[加法]]、[[乘法]]、[[幂]]、[[迭代冪次]]等。1986年，一项涉及超运算模式推广的研究调查了后继函数。<ref name=Ackermann>{{cite web|last=Rubtsov|first=C.A.|last2=Romerio|first2=G.F.|title=Ackermann's Function and New Arithmetical Operations|date=2004|url=http://www.rotarysaluzzo.it/Z_Vecchio_Sito/filePDF/Iperoperazioni%20(1).pdf|access-date=2024-02-07|archive-date=2024-02-03|archive-url=https://web.archive.org/web/20240203182320/http://www.rotarysaluzzo.it/Z_Vecchio_Sito/filePDF/Iperoperazioni%20(1).pdf|dead-url=no}}</ref>

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

== 另见 ==
* [[后继序数]]
* [[后继基数]]
* [[增值和减值操作符]]
* [[序列]]

== 参考文献 ==
{{reflist}}

* {{Cite book|title=Naive Set Theory|last=Paul R. Halmos|publisher=Nostrand|year=1968}}
[[Category:算术]]
[[Category:计算机逻辑]]
[[Category:數理邏輯]]