後繼函數

數學中，後繼函數 或 後繼運算是使${\displaystyle S(n)=n+1}$的原始遞歸函數S，其中n為自然數。例如， S(1)=2， S(2)=3。後繼函數也稱為zeration，因為它是第零個超運算：${\displaystyle H_{0}(a,\ b)=1+b}$。zeration的推廣是加法，加法可看做反覆進行一定次數的後繼運算。

概述

後繼函數被用在定義自然數的皮亞諾公理，皮亞諾公理形式化了自然數的結構，當中後繼函數是自然數上的一種原始運算，定義所有大於0的自然數和加法。例如，1被定義為 S(0)，自然數的加法是由遞歸定義：

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

這可以用來計算任意兩自然數的加法，例如${\displaystyle 5+2=5+S(1)=S(5+1)=S(5+S(0))=S(S(5+0))=S(S(5))=S(6)=7}$。

集合論中曾提出了集中自然數的構造，例如馮·諾依曼將0構造為空集${\displaystyle \{\}}$，將n的後繼集${\displaystyle S(n)}$構造為集合${\displaystyle n\cup \{n\}}$。這樣，無窮公理就保證存在包含0且對S閉合的集合，最小的此種集合用${\displaystyle \mathbb {N} }$表示，就是自然數。^[1] 後續函數在超運算的格爾澤戈茨茲克層級中屬於第0級，可以構建加法、乘法、冪、迭代冪次等。1986年，一項涉及超運算模式推廣的研究調查了後繼函數。^[2]

後繼函數是用於描述遞歸函數可計算性的初等函數之一。

另見

• 後繼序數
• 後繼基數
• 增值和減值操作符
• 序列

參考文獻

1. Halmos, Chapter 11
2. Rubtsov, C.A.; Romerio, G.F. Ackermann's Function and New Arithmetical Operations (PDF). 2004 [2024-02-07]. （原始內容存檔 (PDF)於2024-02-03）.

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