Natural Numbers and Induction - Core Definitions

The natural numbers form the most fundamental infinite set in mathematics. In set theory, we construct them from first principles using the von Neumann ordinals, providing a rigorous foundation for arithmetic and mathematical induction.

DefinitionVon Neumann Natural Numbers

Using the von Neumann construction, each natural number is defined as the set of all smaller natural numbers:

\begin{align*} 0 &= \emptyset \\ 1 &= \{0\} = \{\emptyset\} \\ 2 &= \{0, 1\} = \{\emptyset, \{\emptyset\}\} \\ 3 &= \{0, 1, 2\} \\ n+1 &= n \cup \{n\} = \{0, 1, \ldots, n\} \end{align*}

This construction ensures that $m \in n$ if and only if $m < n$ as natural numbers, unifying membership with the ordering relation.

This elegant encoding makes each natural number $n$ simultaneously represent both the number itself and the set $\{0, 1, \ldots, n-1\}$ . Consequently, $n$ has exactly $n$ elements: $|n| = n$ .

DefinitionSuccessor Operation

The successor of a set $x$ is defined as:

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

For natural numbers, this operation corresponds to adding one: $S(n) = n + 1$ . The successor operation is:

Injective: $S(m) = S(n) \Rightarrow m = n$
Non-surjective on $\omega$ : There is no $n \in \omega$ with $S(n) = 0$
Preserves transitivity: If $x$ is transitive, so is $S(x)$

ExampleFirst Few Natural Numbers

Explicitly writing out the first natural numbers as sets:

\begin{align*} 0 &= \emptyset \\ 1 &= \{\emptyset\} \\ 2 &= \{\emptyset, \{\emptyset\}\} \\ 3 &= \{\emptyset, \{\emptyset\}, \{\emptyset, \{\emptyset\}\}\} \\ 4 &= \{0, 1, 2, 3\} \end{align*}

Notice that $0 \in 1 \in 2 \in 3 \in 4$ , and more generally, the membership relation $\in$ on natural numbers corresponds exactly to the less-than relation $<$ .

DefinitionThe Set omega

The set of all natural numbers, denoted $\omega$ or $\mathbb{N}$ , is the smallest inductive set:

\omega = \{0, 1, 2, 3, \ldots\} = \bigcap \{I : I \text{ is inductive}\}

where a set $I$ is inductive if $\emptyset \in I$ and $x \in I \Rightarrow S(x) \in I$ .

Key properties of $\omega$ :

Transitive: $n \in \omega \land m \in n \Rightarrow m \in \omega$
Well-ordered: Every non-empty subset has a least element
Infinite: $\omega$ is not equinumerous with any of its elements
Limit ordinal: $\omega \neq S(\alpha)$ for any $\alpha$

The set $\omega$ provides the foundation for all arithmetic. We can define addition, multiplication, and exponentiation on $\omega$ using recursion, and prove their familiar properties using induction.

TheoremPeano Axioms in ZFC

The von Neumann natural numbers satisfy the Peano axioms:

$0 \in \omega$ (zero is a natural number)
$n \in \omega \Rightarrow S(n) \in \omega$ (closure under successor)
$\forall n \in \omega(S(n) \neq 0)$ (zero is not a successor)
$S$ is injective on $\omega$
Induction: If $P(0)$ and $\forall n(P(n) \Rightarrow P(S(n)))$ , then $\forall n \in \omega(P(n))$

These axioms characterize the natural numbers uniquely up to isomorphism.

Remark

In Peano's original formulation, natural numbers were taken as primitive objects with successor as a primitive operation. In ZFC, we construct them as specific sets, deriving the Peano axioms as theorems. This demonstrates the power of set theory as a foundation: even the most basic mathematical objects can be built from pure set existence.

DefinitionArithmetic Operations

We define arithmetic operations on $\omega$ by recursion:

Addition: For $m, n \in \omega$ ,

\begin{align*} m + 0 &= m \\ m + S(n) &= S(m + n) \end{align*}

Multiplication: For $m, n \in \omega$ ,

\begin{align*} m \cdot 0 &= 0 \\ m \cdot S(n) &= m \cdot n + m \end{align*}

Exponentiation: For $m, n \in \omega$ ,

\begin{align*} m^0 &= 1 \\ m^{S(n)} &= m^n \cdot m \end{align*}

These recursive definitions, validated by the principle of recursion on $\omega$ , give rise to all familiar arithmetic properties: associativity, commutativity, distributivity, and so forth. Each property can be rigorously proved using mathematical induction.

ExampleProof by Induction: Commutativity of Addition

To prove $m + n = n + m$ for all $m, n \in \omega$ , we use induction on $n$ (for fixed $m$ ):

Base case: $m + 0 = m = 0 + m$ (requires proving $0 + m = m$ by induction on $m$ )

Inductive step: Assume $m + n = n + m$ . Then:

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

using the inductive hypothesis and properties of successor addition.

The construction of natural numbers in ZFC demonstrates how even the most elementary mathematics rests on the foundation of set theory. From the empty set and the axiom of infinity, we build $\omega$ and derive all arithmetic, providing a completely rigorous basis for mathematics.