mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

, the successor function or successor operation sends a

natural number In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country"). Numbers used for counting are called ''Cardinal n ...

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 In computability theory, a primitive recursive function is roughly speaking a function that can be computed by a computer program whose loops are all "for" loops (that is, an upper bound of the number of iterations of every loop can be determined ...

. Successor operations are also known as zeration in the context of a zeroth

hyperoperation In mathematics, the hyperoperation sequence is an infinite sequence of arithmetic operations (called ''hyperoperations'' in this context) that starts with a unary operation (the successor function with ''n'' = 0). The sequence continues with ...

: H₀(''a'', ''b'') = 1 + ''b''. In this context, the extension of zeration is

addition Addition (usually signified by the Plus and minus signs#Plus sign, plus symbol ) is one of the four basic Operation (mathematics), operations of arithmetic, the other three being subtraction, multiplication and Division (mathematics), division. ...

, which is defined as repeated succession.

Overview

The successor function is part of the

formal language In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules. The alphabet of a formal language consists of symb ...

used to state the

Peano axioms In mathematical logic, the Peano axioms, also known as the Dedekind–Peano axioms or the Peano postulates, are axioms for the natural numbers presented by the 19th century Italian mathematician Giuseppe Peano. These axioms have been used nearly ...

, 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. Several constructions of the natural numbers within set theory have been proposed. For example,

John von Neumann John von Neumann (; hu, Neumann János Lajos, ; December 28, 1903 – February 8, 1957) was a Hungarian-American mathematician, physicist, computer scientist, engineer and polymath. He was regarded as having perhaps the widest cove ...

constructs the number 0 as the

empty set In mathematics, the empty set is the unique set having no elements; its size or cardinality (count of elements in a set) is zero. Some axiomatic set theories ensure that the empty set exists by including an axiom of empty set, while in other ...

, and the successor of ''n'', ''S''(''n''), as the set ''n'' ∪ . The

axiom of infinity In axiomatic set theory and the branches of mathematics and philosophy that use it, the axiom of infinity is one of the axioms of Zermelo–Fraenkel set theory. It guarantees the existence of at least one infinite set, namely a set containing the ...

then guarantees the existence of a set that contains 0 and is closed with respect to ''S''. The smallest such set is denoted by N, and its members are called natural numbers.Halmos, Chapter 11 The successor function is the level-0 foundation of the infinite

Grzegorczyk hierarchy The Grzegorczyk hierarchy (, ), named after the Polish logician Andrzej Grzegorczyk, is a hierarchy of functions used in computability theory. Every function in the Grzegorczyk hierarchy is a primitive recursive function, and every primitive recurs ...

s, used to build

multiplication Multiplication (often denoted by the cross symbol , by the mid-line dot operator , by juxtaposition, or, on computers, by an asterisk ) is one of the four elementary mathematical operations of arithmetic, with the other ones being additi ...

exponentiation Exponentiation is a mathematical operation, written as , involving two numbers, the '' base'' and the ''exponent'' or ''power'' , and pronounced as " (raised) to the (power of) ". When is a positive integer, exponentiation corresponds to re ...

tetration In mathematics, tetration (or hyper-4) is an operation based on iterated, or repeated, exponentiation. There is no standard notation for tetration, though \uparrow \uparrow and the left-exponent ''xb'' are common. Under the definition as rep ...

, etc. It was studied in 1986 in an investigation involving generalization of the pattern for hyperoperations. It is also one of the primitive functions used in the characterization of

computability Computability is the ability to solve a problem in an effective manner. It is a key topic of the field of computability theory within mathematical logic and the theory of computation within computer science. The computability of a problem is close ...

by recursive functions.

References

* Mathematical logic Arithmetic Logic in computer science {{mathlogic-stub

Overview

See also

References