Successor function

Successor functionMain

Community hub

Successor function

7 pages, 0 posts

0 subscribers

Recent from talks

Be the first to start a discussion here.

Recent from talks

Be the first to start a discussion here.

Contribute something

About hubMembersContent overviewUpdatesRules

Main reference articles

Successor function

View on Wikipedia

from Wikipedia

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. In this context, the extension of zeration is addition, which is defined as repeated succession.

Overview

[edit]

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 are defined.^[1] 1 is defined to be $S(0)$ , 2 is $S(1)$ , etc.; and addition on natural numbers is defined recursively by:

m+0=m

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

This can be used to compute the addition of any two natural numbers. For example:

5+2

=5+S(1)

=5+S(S(0))

=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 constructs the number 0 as the empty set and the successor of $n$ as the set $n\cup \{n\}$ . The axiom of infinity then guarantees the existence of a set that contains 0 and is closed with respect to $S$ . The smallest such set is denoted by $\mathbb {N}$ , and its members are called natural numbers.^[2]

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.^[3]

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

References

[edit]

^ Steffen, Bernhard; Rüthing, Oliver; Huth, Michael (2018). Mathematical Foundations of Advanced Informatics—Volume 1: Inductive Approaches. Springer. p. 121. doi:10.1007/978-3-319-68397-3. ISBN 978-3-319-68397-3.
^ Halmos, Chapter 11
^ Rubtsov, C.A.; Romerio, G.F. (2004). "Ackermann's Function and New Arithmetical Operations" (PDF).

Paul R. Halmos (1968). Naive Set Theory. Nostrand.

v t e Hyperoperations
Primary	Successor Addition Multiplication Exponentiation Tetration
Left inverse	Predecessor Subtraction Division Root extraction Super-root
Right inverse	Predecessor Subtraction Division Logarithm Super-logarithm
Related articles	Ackermann function Conway chained arrow notation Grzegorczyk hierarchy Knuth's up-arrow notation Steinhaus–Moser notation

This mathematical logic-related article is a stub. You can help Wikipedia by adding missing information.

Revisions and contributors Edit on Wikipedia Read on Wikipedia

View on Grokipedia

from Grokipedia

In mathematical logic and foundational mathematics, the successor function, typically denoted as

S

\mathrm{succ}

, is a fundamental unary function that maps each natural number

n

to its immediate successor

n+1

, serving as a core component in the axiomatic construction of the natural numbers.^[1] This function is introduced in the Peano axioms, which posit the existence of a constant 0 and the successor function

s

with properties including:

s

is a function from the natural numbers to themselves;

s(0) = 1

;

s

is injective (distinct numbers have distinct successors); no natural number has 0 as its successor; and the induction axiom ensures that properties holding for 0 and closed under succession apply to all natural numbers.^[2] These axioms formalize arithmetic operations like addition and multiplication via recursion on the successor, enabling the rigorous definition of the natural number system without circularity.^[2] Beyond Peano arithmetic, the successor function extends to ordinal numbers in set theory, where it plays a key role in constructing the von Neumann hierarchy of ordinals.^[3] In this framework, ordinals are defined as transitive sets well-ordered by the membership relation

\in

, with the empty set as 0, and the successor of an ordinal

\alpha

given by

S(\alpha) = \alpha \cup \{\alpha\}

, yielding finite ordinals such as

1 = \{0\}

2 = \{0, 1\}

, and so on.^[3] This set-theoretic definition aligns with the arithmetic successor while generalizing to transfinite ordinals, distinguishing successor ordinals (those of the form

S(\beta)

for some ordinal

\beta

) from limit ordinals (suprema of proper initial segments).^[4] The successor function thus underpins transfinite recursion theorems, allowing the definition of operations like addition and exponentiation on ordinals.^[4] The successor function's significance lies in its role as a primitive for building arithmetic structures, influencing computability theory through models like the primitive recursive functions, where it serves as a basic operation alongside zero and projection.^[5] In proof theory and model theory, properties of the successor ensure the well-foundedness of the natural numbers, preventing paradoxes and enabling Gödel's incompleteness theorems via arithmetization.^[2] Its abstract formulation also appears in category theory and type theory, where it models inductive types in dependent type systems like those in proof assistants such as Coq or Agda.^[1]

Definition and Basics

Formal Definition

The successor function, denoted

S(n)

\succ(n)

, is a function

\mathbb{N} \to \mathbb{N}

that maps each natural number

n

to its immediate successor

n+1

, serving as the foundational operation for constructing the natural numbers from an initial element, typically 0 or 1.^[6] This mapping generates the entire sequence iteratively:

S([0](/page/0)) = 1

S(1) = 2

S(2) = 3

, and in general, any natural number

k

is obtained by applying

S

exactly

k

times to 0.^[6] Axiomatic characterization establishes

S

as injective, such that

S(m) = S(n)

implies

m = n

for all

m, n \in \mathbb{N}

, but not surjective, as 0 lies outside the image of

S

(no natural number has 0 as its successor).^[7] Additionally,

S

admits no fixed points, satisfying

S(n) \neq n

for every

n \in \mathbb{N}

, since equating a number to its successor would contradict the distinctness of natural numbers.^[7] In contrast to the predecessor function, which is partial and undefined at 0, the successor function is total, with its domain encompassing all natural numbers.^[7] The successor is introduced as a primitive in systems like the Peano axioms.^[8]

Examples in Arithmetic

The successor function, often denoted as

S(n)

, provides a foundational way to construct the natural numbers starting from 0, where each application advances to the next number. For instance,

S(0) = 1

S(3) = 4

, and

S(5) = 6

, demonstrating how repeated applications generate the sequence of positive integers: beginning with 0 and iteratively producing 1, 2, 3, and so on.^[9] This iterative process can be visualized in the following table, showing the input

n

and output

S(n)

for values from 0 to 10:

$n$	$S(n)$
0	1
1	2
2	3
3	4
4	5
5	6
6	7
7	8
8	9
9	10
10	11

The successor function's injectivity ensures that each application produces a distinct number, preventing cycles and maintaining a linear progression in the sequence.^[9] In arithmetic, the successor function underpins basic operations like addition, which can be defined recursively: for any natural numbers

m

and

n

m + 0 = m

and

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

. This recursive structure allows addition to build upon the successor, for example, computing

2 + 3

S(S(2 + 1)) = S(S(S(2))) = 5

.^[9] By generating an unending chain of distinct numbers from 0—where each step adds the "next" without bound—the successor function intuitively captures the infinite nature of the natural numbers, emphasizing their endless extensibility.^[10]

Role in Axiomatic Systems

Peano Axioms

The Peano axioms, formulated by Italian mathematician Giuseppe Peano in 1889, provide a foundational axiomatic system for the natural numbers, with the successor function serving as a primitive operation central to defining their structure.^[11] In Peano's original presentation in Arithmetices principia, nova methodo exposita, the axioms treat "1" as the initial natural number and the successor (denoted as

n'

) as a total function on the naturals, ensuring an infinite, linearly ordered chain without repetitions.^[11] The five axioms are:

1 is a natural number.
Every natural number $n$ has a natural number $n'$ as its successor.
1 is not the successor of any natural number.
If two natural numbers have the same successor, they are equal (injectivity of the successor).
If a set $X$ of natural numbers contains 1 and the successor of every element in $X$ , then $X$ contains all natural numbers (induction axiom schema).^[11]

A common modern variant, often used in first-order Peano arithmetic, replaces 1 with 0 as the base and denotes the successor as

S(n)

, while preserving the other properties: 0 is a natural number;

S

maps naturals to naturals;

S

is injective; 0 is not in the image of

S

; and the induction axiom states that any property holding for 0 and preserved under

S

holds for all naturals.^[12] This adjustment aligns with contemporary conventions but retains the successor's role in generating the number system recursively from the base.^[13] The successor function's primitive status in the Peano axioms enables the recursive definition of arithmetic operations, such as addition and multiplication, without presupposing them. Addition is defined as iterated application of the successor:

m + 0 = m

and

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

, effectively counting successors from

m

a number of times given by

n

.^[12] Multiplication builds on this as iterated addition:

m \cdot 0 = 0

and

m \cdot S(n) = m \cdot n + m

.^[12] These definitions, justified by the induction axiom, ensure that all basic arithmetic functions are derivable from the successor alone.^[13] Using the Peano axioms, several key theorems establish the successor's structural properties. First, 0 (or 1 in the original) has no predecessor, as it lies outside the image of the successor by axiom.^[12] Second, every nonzero natural number has a unique predecessor: for

S(k) \neq 0

, there exists a unique

m

such that

S(m) = k

, proved by induction on the injectivity and totality of

S

.^[12] Additionally, the axioms imply no cycles in the structure, as the induction axiom and injectivity ensure all iterates of the successor from the base are distinct: for any

n

n \neq S(n)

, and by induction, no number equals a later successor.^[12] These results confirm the natural numbers form an infinite discrete chain under the successor.^[13]

Other Formal Systems

Second-order Peano arithmetic extends the first-order Peano axioms by incorporating second-order logic, which allows quantification over predicates and sets of natural numbers in addition to quantification over individual numbers. In this system, the successor function remains defined as in the first-order version, serving as a unary operation that maps each natural number to its immediate successor, ensuring the structure of the natural numbers is preserved. The key enhancement is the second-order induction axiom, which states that if a predicate holds for zero and is preserved under the successor operation for all natural numbers, then it holds for every natural number; this formulation enables the proof of stronger results, such as the categoricity of the natural numbers. Second-order Peano arithmetic captures the full semantics of the natural numbers and is complete for arithmetic truths. In Martin-Löf type theory, a constructive foundation for mathematics based on dependent types and intuitionistic logic, the natural numbers are defined as an inductive type with two constructors: zero, which introduces the base element, and successor, which recursively builds the next natural number from a previous one. The successor constructor, often denoted as

\mathsf{suc}

, takes a natural number

n

and produces

\mathsf{suc}(n)

, ensuring that every natural number except zero is the successor of exactly one other. This construction supports recursion and induction via dependent types, allowing definitions of functions like addition and multiplication through pattern matching on the structure of natural numbers; for instance, addition can be defined by recursing on the second argument using the successor to increment the first. Martin-Löf type theory's emphasis on constructive proofs means that the successor operation not only defines the type but also facilitates the explicit construction of inhabitants, aligning with its computational interpretation.^[14]^[15] Presburger arithmetic represents a decidable fragment of first-order arithmetic that includes the successor function and addition but excludes multiplication, focusing on the theory of natural numbers under these operations. Here, the successor function

S(x)

serves as the primitive from which addition is derived:

x + 0 = x

and

x + S(y) = S(x + y)

, enabling the expression of linear arithmetic statements. A seminal result is its decidability, established by Mojżesz Presburger in 1929 through quantifier elimination, and later connected to automata theory by J. Richard Büchi, who showed that the definable sets in Presburger arithmetic correspond to those recognizable by finite automata over strings representing numbers in unary, allowing algorithmic verification of any sentence in the theory. This contrasts with the undecidability of full Peano arithmetic, highlighting the successor's role in maintaining a well-behaved, computable structure without the complications introduced by multiplication.^[16]^[17] In Zermelo-Fraenkel set theory (ZF), the successor function is not a primitive but is integrated through set-theoretic operations on the constructed natural numbers, where zero is the empty set

\emptyset

, and the successor of a natural number

n

is defined as

n \cup \{n\}

. This construction leverages the axioms of union and pairing to ensure the natural numbers form an infinite, well-ordered set, with successor preserving the ordinal structure essential for inductive definitions. While ZF provides a foundational embedding for arithmetic, the successor's definition relies on the extensionality and infinity axioms rather than being axiomatized directly.^[18] Across these systems, the successor function consistently ensures well-foundedness and discreteness in the natural numbers, but their expressive power varies significantly: second-order Peano arithmetic achieves categorical uniqueness for the naturals, Martin-Löf type theory emphasizes constructive computability, Presburger arithmetic prioritizes decidability at the cost of limited operations, and ZF embeds successor within a broader set-theoretic universe. This diversity underscores the successor's foundational role in adapting to different logical strengths and applications.^[19]

Set-Theoretic Foundations

Von Neumann Construction

In set theory, the von Neumann construction defines ordinal numbers as transitive sets that are well-ordered by the membership relation, providing a concrete realization of the natural numbers using pure sets. This approach identifies the number zero with the empty set, denoted

0 = \emptyset

, the number one as the singleton containing zero,

1 = \{\emptyset\}

, and the number two as the set containing zero and one,

2 = \{\emptyset, \{\emptyset\}\}

. Subsequent numbers follow recursively, with each finite ordinal

n

comprising all preceding ordinals as its elements.^[20]^[21] The successor operation in this framework is defined as

S(n) = n \cup \{n\}

, which appends the ordinal itself to the collection of its predecessors, thereby extending the structure while preserving the well-ordering under membership. This operation ensures that each successor ordinal is strictly larger than its predecessor and maintains the transitive property, where every element of an element is also an element of the set. For instance, applying the successor to one yields

S(1) = \{\emptyset\} \cup \{\{\emptyset\}\} = \{\emptyset, \{\emptyset\}\} = 2

. The construction originates from John von Neumann's 1923 work on transfinite numbers, where he formalized ordinals as sets of preceding ordinals to axiomatize set theory rigorously.^[22] This hierarchy of finite von Neumann ordinals establishes a bijection with the natural numbers as defined by the Peano axioms, interpreting the abstract successor function concretely within Zermelo-Fraenkel set theory (ZF) and thereby proving the existence of the natural numbers as sets. The mapping sends each Peano natural number to its corresponding von Neumann ordinal, with the successor corresponding directly to the set-theoretic operation, satisfying properties like injectivity and the absence of cycles.^[21]^[20] A distinctive feature of the von Neumann construction is its seamless extension to transfinite ordinals, where successor ordinals continue to be formed via

S(\alpha) = \alpha \cup \{\alpha\}

for any ordinal

\alpha

, though the present discussion restricts attention to the finite case relevant to the natural numbers' successor function.

Properties in Set Theory

In set theory, particularly within Zermelo-Fraenkel (ZF) set theory, the successor function on the natural numbers, constructed as von Neumann ordinals, exhibits well-foundedness as a core property. Successor chains under this construction form well-ordered sets with respect to the membership relation

\in

, ensuring that every non-empty subset has a least element and precluding infinite descending sequences. This well-foundedness is formalized and guaranteed by the axiom of foundation (regularity) in ZF, which states that every non-empty set contains an element disjoint from all others in the set, thereby preventing cycles or infinite regressions in the membership hierarchy.^[23] Set-theoretic induction on these successor-constructed natural numbers mirrors the principle of mathematical induction from Peano arithmetic, adapted to the transitive closure and rank functions inherent in the ordinal structure. Specifically, for a property

P

holding on the empty set (0) and preserved under the successor operation

S(n) = n \cup \{n\}

P

extends to all natural numbers via the well-ordering of

\omega

, the least infinite ordinal. This is established through transfinite induction over ordinals, where the successor step assumes

P(\alpha)

implies

P(\alpha^+)

, and the process leverages the rank function

\mathrm{rank}(x) = \sup\{\mathrm{rank}(y) + 1 \mid y \in x\}

to ensure completeness up to

\omega

.^[24]^[25] The successor function preserves finite cardinality in this construction, with

|S(n)| = |n| + 1

for each finite ordinal

n

, as each application adjoins a distinct new element without redundancy due to the transitive and well-ordered nature of the sets. This bijection between the ordinal

n

and sets of cardinality

n

underscores the identification of finite cardinals with natural numbers in set theory.^[24] The successor operation defines the strict linear order on

[\omega](/page/Omega)

, the order type of the natural numbers, where

S(n) < S(m)

if and only if

n < m

, with the order realized via

\in

. This induces the order topology on

[\omega](/page/Omega)

as a discrete space, consisting of isolated points, and positions

[\omega](/page/Omega)

as the smallest infinite ordinal in the class of all ordinals.^[25]^[26] Up to isomorphism, the well-ordered set generated by the successor axioms in set theory is unique, corresponding precisely to the von Neumann construction of

\omega

; any well-ordered set satisfying the successor properties (starting from an empty initial element and iteratively adjoining successors) is order-isomorphic to exactly one ordinal. This uniqueness follows from the fact that ordinals are rigid: no two distinct ordinals are order-isomorphic.^[25]^[26]

Applications and Extensions

In Computability Theory

In computability theory, the successor function serves as a foundational primitive operation for defining classes of computable functions on the natural numbers. It is one of the initial functions in the definition of primitive recursive functions, alongside the zero function

Z(x) = 0

and projection functions

P_i^n(x_1, \dots, x_n) = x_i

, which select the

i

-th argument.^[27] These base functions are closed under composition and primitive recursion, where a function

f

is defined by

f(0, \vec{y}) = g(\vec{y})

f(0,y

)=g(y

) and $f(S(x), \vec{y}) = h(x, f(x, \vec{y}), \vec{y})$

)=h(x,f(x,y

),y

), with $S(x) = x + 1$ denoting the successor. This schema enables the construction of arithmetic operations such as addition (via iterated successor) and multiplication (via recursion on addition), forming the class of primitive recursive functions, which are total computable functions with bounded growth.^[27]^[27] The successor function also plays a central role in the Grzegorczyk hierarchy, a refinement of the primitive recursive functions organized by growth rates. The hierarchy begins with the base functions—zero, successor, and projections—and builds levels $\mathcal{E}^n$ through limited recursion schemes, where $\mathcal{E}^0$ is the class generated from the zero function, successor, and projections under composition and bounded recursion, and higher levels incorporate functions like addition ( $\mathcal{E}^1$ ) and multiplication ( $\mathcal{E}^2$ ).^[28] All primitive recursive functions appear in some level of this hierarchy, with the successor providing the iterative step for hyperoperations at each stage.^[27] Extending beyond primitive recursion, the μ-recursive functions (also known as general recursive functions) incorporate the successor, zero, and projections as initial functions, closed under composition and now also under the μ-operator of unbounded minimization: $\mu y [T(\vec{x}, y) = 0]$

,y)=0], the least $y$ such that predicate $T$ holds. This addition yields Turing-complete computation, encompassing all partial computable functions, as the successor enables encoding of natural numbers and recursive definitions.^[27]^[27] A key example highlighting the limits of primitive recursion is the Ackermann function, which generalizes hyperoperations using nested recursion on the successor. Defined as $A(m, n)$ with cases building from successor ( $A(0, n) = S(n)$ ) to iterated operations like addition, multiplication, exponentiation, and beyond, it grows faster than any primitive recursive function, demonstrating that μ-recursion strictly contains primitive recursion.^[29]^[27] Under the Church-Turing thesis, the successor function underpins the equivalence of computational models, serving as a basic operation for encoding natural numbers in both λ-calculus (via Church numerals, where successor applies a function one more time) and Turing machines (via tape increments). These encodings allow simulation of arithmetic and recursion, supporting the thesis that λ-definable or Turing-computable functions capture all effective computations.^[30]^[30] Properties of the successor function, such as its injectivity ( $S(x) = S(y)$ implies $x = y$ ), are decidable because the function is primitive recursive and total, admitting a Turing machine that halts and verifies such relations on all inputs; this contrasts with undecidable problems like the halting problem for general recursive functions.^[27]^[31]

In Computer Science

In functional programming languages, the successor function is often implemented as a higher-order function that increments a value by one, facilitating pure and composable operations without side effects. For instance, in Haskell, the Prelude module defines succ :: Enum a => a -> a, which returns the successor of its argument for enumerable types, such as integers where succ n = n + 1; this is commonly used in list generation, like [succ x | x <- [0..9]] to produce [1,2,3,...,10]. Immutable data structures in functional programming leverage the successor concept to represent counters as chains of linked lists or trees, ensuring persistence where each increment creates a new version without modifying the original. In such representations, zero is encoded as an empty list (nil), and the successor of a number

n

is a cons cell pairing a unit value with the list for

n

, allowing efficient sharing of structure across versions; this approach is foundational in languages like Haskell for building persistent counters that support concurrent access. For arbitrary-precision arithmetic, libraries implement the successor operation to handle large integers beyond fixed-size types, managing overflow through carry propagation across limbs. In the GNU Multiple Precision Arithmetic Library (GMP), incrementing a multi-precision integer mpz_t by one uses mpz_add_ui(rop, op, 1UL), which adds the unsigned long integer 1 to the operand and stores the result, efficiently propagating carries if the most significant limb overflows.^[32] Church numerals provide a lambda-encoded representation of natural numbers in untyped lambda calculus, where the successor function enables numerical computation without primitive integers. The successor

S

is defined as

\lambda n. \lambda f. \lambda x. n f (f x)

, which applies the function

f

one additional time to

x

when composed with a numeral

n

, thus incrementing the count; this encoding, introduced by Alonzo Church, underpins arithmetic in pure functional settings like Lisp dialects or theoretical machines. To mitigate stack overflow in recursive applications of successor, such as building deep chains for large counters, functional languages employ tail-recursive implementations that accumulate results iteratively. For example, a tail-recursive increment function in Scheme or Haskell uses an accumulator parameter, transforming linear recursion into constant-space execution via compiler optimizations like tail-call elimination, preserving efficiency for primitive recursive computations.

Historical Development

Early Concepts

The origins of the successor function trace back to prehistoric and ancient practices of counting, where iterative marking represented the basic operation of advancing from one unit to the next. Tally marks, one of the earliest known numerical notations dating to approximately 42,000 years ago, functioned as a unary system in which each additional stroke implicitly applied a successor to build cumulative quantities, as evidenced by incisions on bones like the Lebombo bone from South Africa. In ancient Greek mathematics, Euclid's Elements (c. 300 BCE) implicitly incorporated this successor concept through its common notions, such as the principle that equals added to equals yield equals, which underpins the successive extension of line segments and the counting of units in geometric constructions. Similarly, in Indian mathematics, Aryabhata's Aryabhatiya (499 CE) employed iterative counting in computational methods, such as sequentially extracting square roots by dividing and subtracting across place values or generating sine differences by successive adjustments from prior terms.^[33]^[34]^[35] During the medieval period, the successor operation gained practical prominence in European arithmetic through the adoption of more efficient numeral systems. Leonardo Fibonacci's Liber Abaci (1202) introduced the Hindu-Arabic decimal system to the West, emphasizing sequential numbering for commercial calculations, where numbers were generated successively to handle problems in accounting, interest computation, and inventory—effectively formalizing the iterative "next" step in everyday arithmetic beyond Roman numerals' limitations. This work highlighted the successor's role in building longer sequences efficiently, as seen in examples of multiplying and adding by advancing digit places step-by-step.^[36] In the 17th century, Gottfried Wilhelm Leibniz extended these ideas toward a more abstract framework in his Characteristica universalis, a proposed universal symbolic language for thought that incorporated basic arithmetic operations to enable mechanical reasoning and discovery across sciences. By the late 19th century, Richard Dedekind advanced this toward rigor in Was sind und was sollen die Zahlen? (1888), where he defined the natural numbers as a simply infinite system generated by chains of successors: starting from a base element (like 1), each number's chain includes itself and all its iterated successors under a mapping φ, ensuring every natural number is reachable by finite succession without cycles. Dedekind's approach formalized the intuition that natural numbers form an unending sequence built by repeated "next" applications.^[37]^[38] This evolution reflects a broader transition from concrete tally marks—simple incisions representing one-to-one correspondences—to abstract formal iteration, where the successor emerged as a foundational primitive for defining infinite structures. Early methods like notches on sticks or pebbles in containers evolved into symbolic systems that abstracted the "add one" process, culminating in axiomatic treatments like the Peano axioms that explicitly posited the successor as irreducible.^[39]

Modern Formalizations

In the late 19th century, Gottlob Frege advanced a logicist program to derive arithmetic from pure logic, defining the successor function as part of the construction of natural numbers through equinumerosity and logical operations, thereby grounding numerical succession in conceptual content rather than intuition.^[40] This approach, outlined in his 1884 work Die Grundlagen der Arithmetik, emphasized the successor as a relation derived from the extension of concepts, influencing subsequent formal systems by prioritizing logical reduction over axiomatic primitives.^[41] Building on such foundations, Giuseppe Peano introduced the first rigorous axiomatic system for arithmetic in 1889, positing the successor function as a primitive operation that generates the natural numbers from zero, with axioms ensuring injectivity, no cycles, and induction.^[42] Published in Arithmetices principia, nova methodo exposita, this formulation treated the successor as an undefined term, providing a symbolic and deductive framework that profoundly shaped later developments, including the logical reconstructions by Bertrand Russell and Alfred North Whitehead in Principia Mathematica.^[43] In the 1920s, David Hilbert's formalist program sought to establish the consistency of arithmetic through finitary methods, incorporating the successor function within axiomatized systems like Peano arithmetic to verify provability without infinite assumptions.^[44] Hilbert's approach, articulated in lectures and collaborations such as with Wilhelm Ackermann, viewed the successor as a basic recursive operation amenable to metamathematical analysis, aiming to secure mathematics against paradoxes by proving relative consistency.^[45] Kurt Gödel's 1931 incompleteness theorems demonstrated fundamental limits to such formalizations, showing that in any consistent extension of Peano arithmetic—which relies on the successor for defining the naturals—there exist undecidable statements, including the consistency of the system itself. These results, from Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I, revealed that successor-based axiomatizations like Peano's cannot fully capture arithmetic's truths within their own formal bounds, impacting Hilbert's program by proving its core consistency proof unattainable.^[46] Post-World War II developments in constructive mathematics, notably Errett Bishop's 1967 Foundations of Constructive Analysis, reframed the successor function to emphasize computability and effective definability, requiring explicit algorithms for its application in building natural numbers and avoiding non-constructive existence proofs.^[47] This approach, rooted in intuitionistic logic, treated successors as operations yielding verifiable outputs, aligning arithmetic with computational feasibility and influencing modern type theory and program verification.^[48]

Info Pages

Talk Pages

Special Pages

Successor function

Recent from talks

Recent from talks

Contribute something

Contribute something

Media Pages

Timelines

Articles

Notes collections

Notes

Notes

Days in Chronicle

Successor function

Overview

See also

References