Successor function

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 +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: H0(a, b) = 1 + b. In this context, the extension of zeration is addition, which is defined as repeated succession.

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 is defined. For example, 1 is defined to be S(0), and addition on natural numbers is defined recursively by:

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.

The successor function is the level-0 foundation of the infinite Grzegorczyk hierarchy of hyperoperations, used to build addition, multiplication, exponentiation, tetration, etc. It was studied in 1986 in an investigation involving generalization of the pattern for hyperoperations.[2]

It is also one of the primitive functions used in the characterization of computability by recursive functions.