Successor function

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

In mathematics, the successor function or successor operation is a primitive recursive function S such that S(n) = n+1 for each natural number n. For example, S(1) = 2 and S(2) = 3. 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.

Overview[edit]

The successor function is used in the Peano axioms which define the natural numbers. As such, it is not defined by addition, but rather is used to define all natural numbers beyond 0, as well as addition. 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 addition of any two natural numbers. For example, 5 + 2 = 5 + S(1) = S(5) + 1 = 6 + 1 = 6 + S(0) = S(6) + 0 = 7 + 0 = 7

Several ways have been proposed to construct the natural numbers using set theory, see set-theoretic definition of natural numbers. A common approach is to define the number 0 to be the empty set {}, and the successor S(x) to be x ∪ { x }. The axiom of infinity then guarantees the existence of a set ℕ that contains 0 and is closed with respect to S; members of ℕ are called natural numbers.[1]

The successor function is the level-0 foundation of the infinite hierarchy of hyperoperations (used to build addition, multiplication, exponentiation, tetration, etc.).

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

See also[edit]

References[edit]

  1. ^ Halmos, Chapter 11
  • Paul R. Halmos (1968). Naive Set Theory. Nostrand.