Successor function

https://en.wikipedia.org/wiki/Successor_function

The successor function is variously denoted by S, Οƒ, succ, Suc, etc. It produces the subsequent (succeeding) element given an element of a set that has some sort of ordering relation.

The number-theoretic successor function is defined over the sets β„• and β„€ in the same way,

succ : β„• -> β„•
succ n = n + 1

succ : β„€ -> β„€
succ z = z + 1

The set-theoretic successor function is defined as

S(n) = n ⋃ { n }

Props and classification

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

  • application term: succession

  • primitive recursive function (PRF)

  • Succ is a primitive recursive function

  • Hyperoperation

    • hyperoperation name: zeration

    • hyperoperation number: 0th (zeroth)

    • Ο‡β‚€(m, n) = 1 + n

  • Succ is used in Peano axioms 6-9

    • Ax.6 βˆ€n. n ∈ β„• -> S n ∈ β„• (closure of S)

    • Ax.7 βˆ€nm ∈ β„•. n = m <=> S n = S m (injectivity of S)

    • Ax.8 βˆ€n ∈ β„•. S n β‰  0 (S wrt 0)

    • Ax.9 N βŠ† β„•. [0 ∈ N β‹€ (βˆ€n. n ∈ N -> S n ∈ N)] -> N = β„• (induction)

  • Addition is defined in terms of the successor

    • m + 0 = m

    • m + S(n) = S(m) + n

Defining the set of the natural numbers

A common approach to define β„• in terms of set theory:

0 ∈ β„•

0 = {} = βˆ…

n ∈ β„• -> S(n) ∈ β„•

S(n) = n ⋃ {n}

  1. define zero as the empty set

  2. define successor of n as the union of n with itself in a set, {n}

  3. The axiom of infinity then guarantees the existence of a set β„•

  4. The set β„• contains 0 and is closed under S

  5. The members of β„• are then called natural numbers

PreviousRangeNextTime complexity classes

Last updated