imported>Jochen Burghardt at 19:03, 20 October 2025

2025-10-20T19:03:23Z

← Previous revision	Revision as of 19:03, 20 October 2025
(No difference)

imported>Dedhert.Jr: supply source for the successor function?

2024-03-27T13:27:23Z

supply source for the successor function?

New page

{{short description|Elementary operation on a natural number}}
{{other uses|Successor (disambiguation)}}

In [[mathematics]], the '''successor function''' or '''successor operation''' sends a [[natural number]] to the next one. The successor function is denoted by ''S'', so ''S''(''n'') = ''n'' +{{space|hair}}1. For example, ''S''(1) = 2 and ''S''(2) = 3. The successor function is one of the basic components used to build a [[primitive recursive function]].

Successor operations are also known as '''zeration''' in the context of a zeroth [[hyperoperation]]: H<sub>0</sub>(''a'', ''b'') = 1 + ''b''. In this context, the extension of zeration is [[addition]], which is defined as repeated succession.

==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—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'' ∪ {''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.

==See also==
*[[Successor ordinal]]
*[[Successor cardinal]]
*[[Increment and decrement operators]]
*[[Sequence]]

==References==
{{reflist}}
*{{cite book| author=Paul R. Halmos| title=Naive Set Theory| year=1968| publisher=Nostrand}}

{{Hyperoperations}}
[[Category:Mathematical logic]]
[[Category:Arithmetic]]
[[Category:Logic in computer science]]

{{mathlogic-stub}}

Successor function - Revision history

imported>Jochen Burghardt at 19:03, 20 October 2025

imported>Dedhert.Jr: supply source for the successor function?