1. Overview
The natural numbers are often introduced axiomatically, through the Peano axioms. In this entry, we take a different perspective: we construct $\mathbb{N}$ inside ZF set theory as the smallest inductive set. This shifts induction from an external principle to an internal consequence of minimality.
We begin by defining inductive sets and showing that such sets exist. We then define $\mathbb{N}$ as the intersection of all inductive sets and establish its fundamental properties. Finally, we comment on categoricity and the appearance of nonstandard models.
2. Inductive Sets and Construction of $\mathbb{N}$
We work in ZF set theory.
Definition 2.1.
A set $I$ is inductive if
(1) $\varnothing \in I$,
(2) whenever $x \in I$, then $x \cup {x} \in I$.
Theorem 2.2 (Axiom of Infinity).
There exists an inductive set.
Definition 2.3.
The set of natural numbers $\mathbb{N}$ is defined as the intersection of all inductive sets.
Proposition 2.4.
$\mathbb{N}$ is inductive and contained in every inductive set.
Proof.
Since there exists at least one inductive set, the intersection defining $\mathbb{N}$ is well-defined.
Let $I$ be inductive. By definition of intersection, $\mathbb{N} \subseteq I$. Hence $\mathbb{N}$ is contained in every inductive set.
It remains to show that $\mathbb{N}$ is inductive. Because every inductive set contains $\varnothing$, it follows that $\varnothing \in \mathbb{N}$.
If $x \in \mathbb{N}$, then $x$ belongs to every inductive set. Since inductive sets are closed under the successor operation \(x \mapsto x \cup \{x\},\) it follows that $x \cup {x}$ belongs to every inductive set.
Hence $x \cup {x} \in \mathbb{N}$.
Therefore $\mathbb{N}$ is inductive. $\square$
3. Minimality and Induction
Theorem 3.1 (Minimality ⇒ Induction).
If $A \subseteq \mathbb{N}$ contains $0$ and is closed under successor, then $A = \mathbb{N}$.
Proof.
Such $A$ is inductive. Since $\mathbb{N}$ is the smallest inductive set, $\mathbb{N} \subseteq A$. $\square$
Theorem 3.2 (Induction ⇒ Minimality).
If $\mathbb{N}$ satisfies induction, then it is contained in every inductive set.
Proof.
Let $I$ be inductive and set
\(A = \mathbb{N} \cap I.\)
Then $A$ contains $0$ and is successor-closed.
By induction $A = \mathbb{N}$. $\square$
Remark 3.3.
\[\text{Minimal inductive set} \Longleftrightarrow \text{Induction}.\]4. The Peano Structure
The natural numbers form a structure $(\mathbb{N}, 0, S)$ characterized by the Peano axioms:
-
$0 \in \mathbb{N}$.
-
$0$ is not the successor of any element of $\mathbb{N}$.
-
The successor function $S : \mathbb{N} \to \mathbb{N}$ is injective; that is, \(S(m) = S(n) \Rightarrow m = n.\)
-
$\mathbb{N}$ is closed under successor: \(n \in \mathbb{N} \Rightarrow S(n) \in \mathbb{N}.\)
-
(Induction Axiom) If $A \subseteq \mathbb{N}$ satisfies \(0 \in A, \quad n \in A \Rightarrow S(n) \in A,\) then $A = \mathbb{N}$.
Under the von Neumann realization \(0 = \varnothing, \qquad S(n) = n \cup \{n\},\) these axioms are satisfied, and the natural numbers arise as the smallest inductive set.
5. Equivalent Foundational Principles
Theorem 5.1.
The following are equivalent on $\mathbb{N}$:
-
Induction
-
Well-ordering of $\mathbb{N}$
-
Minimal counterexample principle
(i.e., if a property $P(n)$ does not hold for all $n \in \mathbb{N}$, then the set of counterexamples ${n \in \mathbb{N} \mid P(n)\text{ fails}}$ has a least element.) -
$\mathbb{N}$ is the smallest inductive set
Definition 5.2.
A binary relation $<$ on a set $X$ is said to be well-founded if there is no infinite strictly decreasing sequence
\(x_0 > x_1 > x_2 > \cdots .\)
Equivalently, every nonempty subset of $X$ has a minimal element.
On the natural numbers with their usual order, well-foundedness is equivalent to the well-ordering principle and hence to induction.
6. Consequences of Induction Not Equivalent to Induction
Several familiar principles of finite mathematics follow from the principle of mathematical induction, yet are strictly weaker and do not imply induction itself. We record representative examples.
(1) Multiplication Principle. If a procedure consists of $n$ successive stages with $m_1, m_2, \ldots, m_n$ possible choices at each stage, then the total number of outcomes is \(m_1 m_2 \cdots m_n.\) This principle is proved by induction on the number of stages. It concerns only finite combinatorial structure and does not express well-foundedness or minimality of $\mathbb{N}$; hence it is strictly weaker than induction.
(2) Pigeonhole Principle. If more than $n$ objects are distributed among $n$ boxes, then at least one box contains more than one object. The general finite form follows by induction on the number of boxes: if the statement holds for $n$ boxes, then distributing more than $n+1$ objects among $n+1$ boxes either places more than $n$ objects into the first $n$ boxes (to which the induction hypothesis applies) or forces at least two objects into the remaining box. However, the pigeonhole principle addresses only finite counting configurations. It does not ensure the existence of least elements in arbitrary subsets of $\mathbb{N}$ and therefore does not imply the well-ordering principle. Consequently, it is weaker than induction.
(3) Finite Iteration Principle. The validity of constructions carried out in finitely many successive steps—for example finite sums, finite products, or recursively defined finite sequences—is justified by induction. Nevertheless, the legitimacy of finite iteration does not by itself guarantee minimality or well-foundedness, and therefore does not imply induction.
Logical perspective. Induction expresses the well-founded successor structure of $\mathbb{N}$. The principles above are finite consequences of that structure, but they do not capture its foundational content. In particular, none of them entails the well-ordering principle or the minimal counterexample method.
7. Categoricity of Second-Order Peano Arithmetic
Second-order Peano arithmetic is the theory of a structure $(\mathbb{N}, 0, S)$ satisfying the Peano axioms, where the induction axiom is interpreted in second-order logic, i.e., it ranges over all subsets of $\mathbb{N}$. In contrast, in first-order logic induction applies only to those subsets that are definable by a formula in the language of arithmetic. For example, the set of even numbers ${n \in \mathbb{N} \mid \exists k\ (n = 2k)}$ is definable, whereas an arbitrary subset of $\mathbb{N}$ need not be.
Theorem 7.1 (Categoricity).
Any two models $(\mathbb{N}, 0, S)$ and $(\mathbb{N}’, 0’, S’)$ of the second-order Peano axioms are isomorphic.
Sketch of proof.
Define a function
\(f : \mathbb{N} \to \mathbb{N}'\)
recursively by
\(f(0) = 0', \qquad f(S(n)) = S'(f(n)).\)
This definition is valid by the recursion principle in $\mathbb{N}$. The map $f$ satisfies the commutative relation \(f \circ S = S' \circ f.\)
Injectivity.
We prove by induction on $m$ that for all $n \in \mathbb{N}$,
\(f(m) = f(n) \Rightarrow m = n.\)
Base case: Let $m = 0$. If $f(0) = f(n)$, then $0’ = f(n)$. If $n \neq 0$, then $n = S(k)$ for some $k$, and hence \(f(n) = f(S(k)) = S'(f(k)),\) which is a successor in $\mathbb{N}’$. But $0’$ is not a successor by the Peano axioms. Thus $n = 0$.
Inductive step: Assume the statement holds for $m$. Suppose $f(S(m)) = f(n)$. If $n = 0$, then \(f(S(m)) = S'(f(m))\) is a successor in $\mathbb{N}’$, contradicting that $0’$ is not a successor. Hence $n = S(k)$ for some $k$. Then \(S'(f(m)) = f(S(m)) = f(S(k)) = S'(f(k)).\)
By injectivity of $S’$, we obtain $f(m) = f(k)$. By the induction hypothesis, $m = k$, hence $S(m) = S(k) = n$.
Surjectivity.
Let $A \subseteq \mathbb{N}’$ be the image of $f$. Since $f(0) = 0’$, we have $0’ \in A$. If $x \in A$, say $x = f(n)$, then
\(S'(x) = S'(f(n)) = f(S(n)) \in A.\)
Hence $A$ is inductive in $\mathbb{N}’$. By the second-order induction axiom in $\mathbb{N}’$, $A = \mathbb{N}’$, so $f$ is surjective.
Structure preservation.
By definition $f(0) = 0’$ and $f(S(n)) = S’(f(n))$, so $f$ preserves the distinguished element and successor operation. Therefore $f$ is an isomorphism. $\square$
8. Nonstandard Models of First-Order Arithmetic
The categoricity above depends essentially on the second-order form of induction. In first-order logic, Peano arithmetic admits nonstandard models and is therefore not categorical.
A nonstandard model is a structure $(M, 0, S)$ satisfying all Peano axioms but containing elements not obtainable from $0$ by finitely many applications of the successor operation. Such elements behave like “infinite integers”: they are larger than every standard natural number, yet still have predecessors and successors within the model.
These additional elements form infinite ascending and descending chains inside $M$, but the first-order induction axiom cannot exclude them. Hence first-order Peano arithmetic does not uniquely characterize the standard natural numbers up to isomorphism: in addition to the usual model $\mathbb{N}$, there exist nonstandard models not isomorphic to it.
Theorem 8.1.
First-order Peano arithmetic has nonstandard models.
Remark 8.2.
The existence of nonstandard models follows from general results of model theory, in particular the Compactness and Löwenheim–Skolem theorems. Informally, by adjoining a new element intended to be larger than every standard natural number and applying compactness, one obtains a model of the Peano axioms containing such an element, yielding a nonstandard extension of $\mathbb{N}$.
Remark 8.3 (Internal vs. External Well-Foundedness).
The equivalence of induction and the minimal-element principle is provable within first-order Peano arithmetic itself and therefore holds inside every model of PA, including nonstandard models. In particular, every definable nonempty subset of such a model has a least element.
However, from the external set-theoretic viewpoint a nonstandard model is not well-founded. If $a$ is a nonstandard element, then externally one can form an infinite descending sequence \(a > a - 1 > a - 2 > a - 3 > \cdots .\)
This does not contradict induction inside the model, because the set of all predecessors of $a$ is not definable by a single first-order formula in the language of arithmetic. Thus the internal minimal-element principle does not guarantee external well-foundedness.
Nonstandard models contain elements larger than every standard natural number; such elements arise via compactness arguments and behave externally like numbers beyond the standard sequence of naturals.
Remark 8.4.
For further discussion of nonstandard models of arithmetic, see Kaye, Models of Peano Arithmetic, or standard texts on model theory such as Enderton or Marker.
9. Recursion and Initiality
A Peano structure is a triple $(A, a_0, F)$ consisting of a set $A$, a distinguished element $a_0 \in A$, and a function $F : A \to A$.
Theorem 9.1 (Recursion Theorem).
Let $A$ be a set, $a_0 \in A$, and $F : A \to A$. There exists a unique function $f : \mathbb{N} \to A$ such that
\(f(0) = a_0, \qquad f(S(n)) = F(f(n)).\)
This theorem expresses the validity of definitions by recursion on $\mathbb{N}$.
Initiality.
The natural numbers $(\mathbb{N}, 0, S)$ are initial among all Peano structures: for every Peano structure $(A, a_0, F)$ there exists a unique function $f : \mathbb{N} \to A$ satisfying
\(f(0) = a_0, \qquad f(S(n)) = F(f(n)).\)
Relation between Recursion and Initiality.
The recursion theorem is precisely the statement of initiality: the unique function $f$ is the unique morphism from $(\mathbb{N}, 0, S)$ to $(A, a_0, F)$. Conversely, initiality guarantees the existence and uniqueness of recursively defined functions.
Foundational significance.
Initiality explains why induction, recursion, and minimality are manifestations of the same structural fact: the natural numbers form the smallest successor-generated system. Recursive definitions, proofs by induction, and well-founded arguments all arise from this initial structure.
10. Historical Note
Richard Dedekind (1888) introduced the notion of a simply infinite system and characterized the natural numbers as the smallest successor-closed set, thereby formulating arithmetic in terms of structural minimality.
Giuseppe Peano (1889) gave an explicit axiomatization of arithmetic using a distinguished element $0$, a successor function, and the induction axiom.
Mario Pieri later observed that the induction axiom may be replaced by an equivalent minimal-element (well-ordering) principle. This reformulation shifted emphasis from inductive closure to order-theoretic well-foundedness, without altering the resulting theory.
Together, these contributions clarified that minimality, induction, and well-ordering are structurally equivalent foundations of arithmetic.
Appendix A — Pieri Equivalence
Theorem A.1.
On $\mathbb{N}$: Well-ordering $\Longleftrightarrow$ Induction.
Well-ordering ⇒ Induction.
Assume $A \subseteq \mathbb{N}$ inductive but not all of $\mathbb{N}$. Let $m$ be least element of complement. $m \neq 0$ since $0 \in A$. So $m = q + 1$ and $q \in A$. Hence $q + 1 = m \in A$, contradiction. $\square$
Induction ⇒ Well-ordering.
Assume nonempty $B \subseteq \mathbb{N}$ has no least element. Let $S$ be the complement of $B$. $0 \in S$ since $B$ has no least element. $S$ must contain some element greater than $0$; otherwise $1$ would be the least element of $T$. Let $n \in S$, $n > 0$, for some $n$. If $k < n$ and $k \in T$, then there exists $k_1 < k$ and $k_1 \in T$ since $T$ has no least element. For the same reason the string of numbers $\cdots < k_1 < k$ is in $T$. Since $n$ is finite, this string ends in $1$ which is not in $T$. Further, since $n \in S$, $n + 1 \in S$; otherwise $n + 1$ would be the least element of $T$. Thus $S$ is an inductive subset of $\mathbb{N}$. Hence $S = \mathbb{N}$ and $T = \varnothing$; a contradiction. $\square$
Appendix B — Equivalent Forms of Induction
Theorem B.1 (Equivalent Forms of Induction).
On $\mathbb{N}$, the following principles are equivalent:
-
Principle of Mathematical Induction (PMI)
-
Principle of Strong (Complete) Induction
-
Well-Ordering Principle: every nonempty subset of $\mathbb{N}$ has a least element
-
Minimal Counterexample Principle
-
No Infinite Descent: there is no infinite strictly decreasing sequence in $\mathbb{N}$
-
$\mathbb{N}$ is the smallest inductive set
-
Recursion Principle: definitions by induction are valid and unique
Sketch of equivalence:
PMI ⇒ Strong Induction.
Assume $P(0)$ holds and $P(k)$ holds for all $k < n$ implies $P(n)$. Using ordinary induction, one shows $P(n)$ holds for all $n$.
Strong Induction ⇒ PMI.
Assume the principle of strong induction: if $P(0)$ holds and
\(P(0) \wedge P(1) \wedge \cdots \wedge P(n-1) \Rightarrow P(n)\)
for all $n \ge 1$, then $P(n)$ holds for all $n \in \mathbb{N}$. To derive ordinary induction, assume $P(0)$ holds and $P(n) \Rightarrow P(n+1)$ for all $n$. We claim that for each $n \ge 1$,
\(P(0) \wedge P(1) \wedge \cdots \wedge P(n-1) \Rightarrow P(n).\)
Indeed, from the conjunction we obtain $P(n-1)$, hence $P(n)$ by the step hypothesis. Therefore the strong induction hypothesis applies, and we conclude $P(n)$ holds for all $n$.
Well-Ordering ⇒ Minimal Counterexample.
If a statement fails, the set of counterexamples is nonempty and therefore has a least element.
Minimal Counterexample ⇒ PMI.
If $P(0)$ holds and $P(n) \Rightarrow P(n+1)$, any counterexample would yield a smaller one, contradiction.
Well-Ordering ⇒ No Infinite Descent.
An infinite strictly decreasing sequence would produce a nonempty subset with no least element.
No Infinite Descent ⇒ Well-Ordering.
If a set had no least element, one could construct an infinite strictly decreasing sequence.
PMI ⇐⇒ Minimal Inductive Set.
A subset containing $0$ and closed under successor must equal $\mathbb{N}$.
PMI ⇐⇒ Recursion.
Existence and uniqueness of recursively defined functions depend on inductive closure.
$\square$
Remark B.2 (Finite vs Infinite Cartesian Products).
The statement that a finite Cartesian product of nonempty sets is nonempty follows from induction: given $A_1, \ldots, A_n \neq \varnothing$, one constructs an element of $A_1 \times \cdots \times A_n$ recursively. For example, begin by choosing $a_1 \in A_1$. If $(a_1, \ldots, a_k)$ has been constructed in $A_1 \times \cdots \times A_k$ and $A_{k+1} \neq \varnothing$, choose $a_{k+1} \in A_{k+1}$. Induction on $k$ yields an element $(a_1, \ldots, a_n)$ of the full product.
However, for an arbitrary family $(A_i)$ $(i\in I)$ of nonempty sets, the statement \(\prod_{i \in I} A_i \neq \varnothing\) is equivalent to the Axiom of Choice. Indeed, an element of the product is precisely a function $f : I \to \bigsqcup_{i \in I} A_i$ such that $f(i) \in A_i$ for each $i \in I$, that is, a choice function. Thus finite product nonemptiness is a consequence of induction, whereas infinite product nonemptiness belongs to set-theoretic choice and is logically independent of induction.
Remark B.3 (Fermat’s Method of Infinite Descent).
The classical method of infinite descent is another formulation of well-foundedness of $\mathbb{N}$. It asserts that no infinite strictly decreasing sequence of natural numbers exists. This principle is equivalent to induction and underlies many classical number-theoretic arguments.
Remark B.4 (Structural Insight).
All equivalent forms above express one structural property: the natural numbers form a well-founded successor structure. Induction, minimal counterexample, well-ordering, and recursion are different manifestations of this single foundational fact.
References
• R. Dedekind, Was sind und was sollen die Zahlen?, 1888.
• G. Peano, Arithmetices principia, nova methodo exposita, 1889.
• M. Pieri, “Sur la géométrie envisagée comme un système purement logique,” 1908.
• T. Jech, Set Theory, Springer, 2003.
• H.-D. Ebbinghaus, J. Flum, W. Thomas, Mathematical Logic, 2nd ed., Springer, 1994.
• R. Kaye, Models of Peano Arithmetic, Oxford University Press, 1991.
• H. Enderton, A Mathematical Introduction to Logic, 2nd ed., Academic Press, 2001.
Cite as:
ProofZoom Entry-0001 — Natural Numbers as the Smallest Inductive Structure, ProofZoom (2026)