In
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 ...
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: H
0(''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
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 sym ...
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.
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 c ...
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 othe ...
, and the successor of ''n'', ''S''(''n''), as the set ''n'' ∪ . The
axiom of infinity then guarantees the existence of a set that contains 0 and is
closed
Closed may refer to:
Mathematics
* Closure (mathematics), a set, along with operations, for which applying those operations on members always results in a member of the set
* Closed set, a set which contains all its limit points
* Closed interval, ...
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 of
hyperoperations, used to build
addition,
multiplication
Multiplication (often denoted by the Multiplication sign, cross symbol , by the mid-line #Notation and terminology, dot operator , by juxtaposition, or, on computers, by an asterisk ) is one of the four Elementary arithmetic, elementary Op ...
,
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 ...
,
tetration, 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 clo ...
by
recursive functions.
See also
*
Successor ordinal
*
Successor cardinal
*
Increment and decrement operators
Increment and decrement operators are unary operators that ''add'' or ''subtract'' one, to or from their operand, respectively.
They are commonly implemented in imperative programming languages. C-like languages feature two versions (pre- an ...
*
Sequence
In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is called ...
References
*
Mathematical logic
Arithmetic
Logic in computer science
{{mathlogic-stub