Editing Successor function (section)

==Overview==
The successor function is part of the [[formal language]] used to state the [[Peano axioms]], which formalise the structure of the natural numbers. In this formalisation, the successor function is a primitive operation on the natural numbers, in terms of which the standard natural numbers and addition are defined.<ref>{{cite book
 | last1 = Steffen | first1 = Bernhard
 | last2 = Rüthing | first2 = Oliver
 | last3 = Huth | first3 = Michael
 | year = 2018
 | title = Mathematical Foundations of Advanced Informatics&mdash;Volume 1: Inductive Approaches
 | url = https://books.google.com/books?id=CIBSDwAAQBAJ&pg=PA121
 | page = 121
 | publisher = Springer
 | doi = 10.1007/978-3-319-68397-3
 | isbn = 978-3-319-68397-3
}}</ref> For example, 1 is defined to be ''S''(0), and addition on natural numbers is defined recursively by:

:{|
|-
| ''m'' + 0 || = ''m'',
|-
| ''m'' + ''S''(''n'') || = ''S''(''m'' + ''n'').
|}

This can be used to compute the addition of any two natural numbers. For example, 5 + 2 = 5 + ''S''(1) = ''S''(5 + 1) = ''S''(5 + ''S''(0)) = ''S''(''S''(5 + 0)) = ''S''(''S''(5)) = ''S''(6) = 7.

Several [[set-theoretic definition of natural numbers|constructions of the natural numbers]] within set theory have been proposed. For example, [[John von Neumann]] constructs the number 0 as the [[empty set]] {}, and the successor of ''n'', ''S''(''n''), as the set ''n''&thinsp;∪&thinsp;{''n''}. The [[axiom of infinity]] then guarantees the existence of a set that contains 0 and is [[Closure (mathematics)#Closure operator|closed]] with respect to ''S''. The smallest such set is denoted by '''N''', and its members are called natural numbers.<ref>Halmos, Chapter 11</ref>

The successor function is the level-0 foundation of the infinite [[Grzegorczyk hierarchy]] of [[hyperoperation]]s, used to build [[addition]], [[multiplication]], [[exponentiation]], [[tetration]], etc. It was studied in 1986 in an investigation involving generalization of the pattern for hyperoperations.<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}}</ref>

It is also one of the primitive functions used in the characterization of [[computability]] by [[Computable function|recursive function]]s.