Session-authored (Fable 5 assisted)

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced — the exact statement appears in a cited source; only wording and notation differ.
AI-adapted — a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated — a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

✓ 33 results · all verified · 17 also independently AI-judged

Every result on this page is machine-checked by a proof checker and read in full and owner-audited; the judge is an additional, independent cross-model AI review of the proofs. The 16 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.

Construction of the Natural Numbers

1 · Prerequisites

2 · Summary

Objective. This page builds the natural numbers $\mathbb{N}$ from the ground and proves the facts that every later construction silently assumes. It is the prerequisite that sits beneath the two constructions of $\mathbb{R}$ , the Cauchy-sequence construction and the Dedekind-cut construction: both begin "the natural numbers, with their arithmetic and order, are the assumed starting point", and this page discharges exactly that assumption. The headline is the principle of mathematical induction (The principle of mathematical induction), the proof technique used everywhere in mathematics, obtained here from its set-theoretic source.

Two starting points, reconciled. There are two standard ways to say what the natural numbers are, and we use both. The Peano axioms (Peano system) describe $\mathbb{N}$ abstractly as a triple $(N, 0, \sigma)$ with a zero, a successor, and an induction axiom. ZFC set theory instead builds a concrete model: the Axiom of Infinity yields an inductive set (Inductive set), and the smallest one (The natural numbers exist: a smallest inductive set) is the set $\omega$ of von Neumann naturals (The natural numbers $\mathbb{N}$ (von Neumann)), where $0 = \varnothing$ and $\sigma(n) = n \cup \{n\}$ , so each number is the set of its predecessors. The bridge between the two views is The von Neumann naturals form a Peano system: the von Neumann model satisfies the Peano axioms, so a Peano system provably exists. Everything after the bridge is proved from the Peano axioms alone, so it holds in any model.

Induction, and definition by recursion. Minimality of $\omega$ is exactly the induction principle: a set of naturals that contains $0$ and is closed under the successor is everything (The principle of mathematical induction). Its indispensable companion is the recursion theorem (The recursion theorem), which licenses defining a function on $\mathbb{N}$ by specifying its value at $0$ and at each successor. Without it the recursive definitions of addition and multiplication would be unjustified; with it they are genuine total functions (Addition is a well-defined total operation, Multiplication is a well-defined total operation).

Arithmetic, proved. Addition (Addition of natural numbers) and multiplication (Multiplication of natural numbers) are defined by recursion, and their laws are then theorems, each proved by induction: addition is associative, commutative, and cancellative (Addition is associative, Addition is commutative, Addition is cancellative); multiplication distributes over addition and is associative and commutative (Distributivity and the successor law for multiplication, Multiplication is associative, Multiplication is commutative); and there are no zero divisors (The natural numbers have no zero divisors). The archetype of the method is the one-line unfolding $1 + 1 = 2$ ( $1+1=2$ from the recursion), with $2 + 2 = 4$ ( $2+2=4$ from the recursion) right behind it.

Order and its consequences. The order $m \le n \iff \exists k\ (m + k = n)$ (Order on the natural numbers) is a linear order ( $\le$ is a linear order on $\mathbb{N}$ ) satisfying trichotomy (Trichotomy of the order on $\mathbb{N}$ ), compatible with addition and multiplication (Order is compatible with addition, Order is compatible with multiplication) and discrete in that $\sigma(n)$ is the immediate successor of $n$ (Discreteness: $\sigma(n)$ is the immediate successor). Its deepest consequence is the well-ordering principle (The well-ordering principle): every nonempty set of naturals has a least element. From it comes strong induction (Strong (complete) induction), so ordinary induction, well-ordering and strong induction are available interchangeably in what follows.

Uniqueness. Finally, the natural numbers are pinned down: any two Peano systems are isomorphic by a unique isomorphism (Categoricity: the natural numbers are unique up to unique isomorphism), proved from the recursion theorem exactly as the uniqueness of $\mathbb{R}$ is proved one level up. So the set-theoretic encoding chosen at the start is immaterial, and it is legitimate to speak of the natural numbers.

Why the axioms are sharp. The optional items show that the induction axiom and the injectivity of the successor cannot be dropped. Dropping induction leaves room for extra elements a proof by induction would never reach (The induction axiom is independent of the other Peano axioms); dropping injectivity of the successor allows a finite model in which distinct numbers collapse (Injectivity of the successor is independent of the other Peano axioms); and induction genuinely needs its base case, since successor-closure alone does not force a set to be all of $\mathbb{N}$ (FALSE: successor-closure alone forces a set to be all of $\mathbb{N}$ ).

3 · Logical flowchart

4 · Definitions, theorems and proofs

DefinitionDefinition: Literature-sourcedProof: Not applicableaudited 2026-07-25Open item page →

Peano system

Definition

A Peano system is a triple $(N, 0, \sigma)$ consisting of a set $N$ , a distinguished element $0 \in N$ , and a successor function $\sigma : N \to N$ (A function is a relation $f$ with $(a,b) \in f$ and $(a,c) \in f$ implying $b = c$ ; $f : A \to B$ , the value $f(a)$ , domain and codomain), satisfying the three Peano axioms:

(P1) Zero is not a successor. For every $n \in N$ , $\sigma(n) \neq 0$ .
(P2) Successor is injective. For all $m, n \in N$ , if $\sigma(m) = \sigma(n)$ then $m = n$ .
(P3) Induction. For every subset $S \subseteq N$ (Subset $x \subseteq y$ , proper subset $x \subsetneq y$ , and the separation notation $\{\, z \in x : \varphi(z) \,\}$ ), if $0 \in S$ and $\sigma(n) \in S$ whenever $n \in S$ , then $S = N$ .

The elements of $N$ are the natural numbers of the system. We abbreviate $1 := \sigma(0)$ , $2 := \sigma(1)$ , $3 := \sigma(2)$ , and so on.

Remarks

Axiom (P3), the induction axiom, is the load-bearing one: it says $N$ has no proper subset that contains $0$ and is closed under $\sigma$ , so every element is reached from $0$ by finitely many successors. It is what makes definition by recursion and proof by induction legitimate (The principle of mathematical induction, The recursion theorem).

This is a structural definition: it does not say what the natural numbers are, only which laws they obey. Two questions are therefore separate and both require proof: that a Peano system exists (a model built inside set theory, The von Neumann naturals form a Peano system, from the von Neumann naturals The natural numbers $\mathbb{N}$ (von Neumann)), and that it is unique up to a unique isomorphism (Categoricity: the natural numbers are unique up to unique isomorphism). Together these justify speaking of the natural numbers $\mathbb{N}$ .

We use the modern $0$ -based convention ( $0 \in N$ ). Peano's original postulates started from $1$ ; the choice is immaterial, and starting at $0$ matches the set-theoretic construction, where $0 = \varnothing$ .

DefinitionDefinition: Literature-sourcedProof: Not applicableaudited 2026-07-25Open item page →

Inductive set

Definition

Working in ZFC, for a set $x$ write $x^{+} := x \cup \{x\}$ for its successor (a set, by the axioms of Pairing and Union, The Axiom of Pairing: $\forall x\,\forall y\,\exists z\,\forall t\,(t \in z \leftrightarrow (t = x \vee t = y))$ and The Axiom of Union: $\forall x\,\exists y\,\forall z\,(z \in y \leftrightarrow \exists s\,(s \in x \wedge z \in s))$ ). A set $I$ is inductive when

$\varnothing \in I \quad\text{and}\quad \bigl(x \in I \implies x^{+} \in I\bigr)\ \text{for every } x.$

That is, $I$ contains the empty set and is closed under the successor operation.

Remarks

The Axiom of Infinity (The Axiom of Infinity: there is a set containing a set with no elements and closed under $y \mapsto y \cup \{y\}$ ) is precisely the assertion that an inductive set exists. Inductive sets can be large and are far from unique (if $I$ is inductive so is $I \cup \{\text{anything}\}$ once closed off), so an inductive set is not yet a good definition of $\mathbb{N}$ . The natural numbers are carved out as the smallest inductive set, the intersection of all of them (The natural numbers exist: a smallest inductive set, The natural numbers $\mathbb{N}$ (von Neumann)); minimality is what delivers the induction principle.

Here $0 := \varnothing$ and the successor of $n$ is $\sigma(n) := n^{+} = n \cup \{n\}$ , so $1 = \{0\}$ , $2 = \{0,1\}$ , $3 = \{0,1,2\}$ : each natural number is the set of all smaller natural numbers.

LemmaStatement: AI-adaptedProof: AI-adaptedprecheck passjudge pass (openai/gpt-5.4)audited 2026-07-25Open item page →

The natural numbers exist: a smallest inductive set

Statement

There is a set $\omega$ that is inductive (Inductive set) and is a subset of every inductive set; it is unique. This $\omega$ is the set of natural numbers.

Facts & Assumptions

Given: ZFC; in particular the Axiom of Infinity (The Axiom of Infinity: there is a set containing a set with no elements and closed under $y \mapsto y \cup \{y\}$ ): there exists an inductive set; the Axiom Schema of Separation (The Axiom Schema of Separation: for each formula $\varphi$ , $\forall \bar p\,\forall x\,\exists y\,\forall z\,(z \in y \leftrightarrow (z \in x \wedge \varphi(z,\bar p)))$ ); and Extensionality (The Axiom of Extensionality: $\forall x\,\forall y\,(\forall z\,(z \in x \leftrightarrow z \in y) \to x = y)$ ). Write $x^{+} := x \cup \{x\}$ . Recall that $I$ inductive means $\varnothing \in I$ and ( $x \in I \Rightarrow x^{+} \in I$ ).

Proof

technique · direct

1.1

By the Axiom of Infinity fix an inductive set $I_0$ .

given

1.2

By Separation the collection $\omega := \{x \in I_0 : x \in J \text{ for every inductive set } J\}$ is a set.

givenconstruct

2.1

$\omega$ is inductive: $\varnothing \in J$ for every inductive $J$ (so $\varnothing \in I_0$ and $\varnothing \in \omega$ ), and if $x \in \omega$ then $x \in J$ for every inductive $J$ , hence $x^{+} \in J$ for every inductive $J$ , and $x^{+} \in I_0$ since $x \in I_0$ and $I_0$ is inductive, so $x^{+} \in \omega$ .

step 1.2

2.2

$\omega \subseteq J$ for every inductive $J$ : any $x \in \omega$ satisfies $x \in J$ by definition.

step 1.2

3.1

Uniqueness: if $\omega'$ is also inductive and contained in every inductive set, then $\omega \subseteq \omega'$ (as $\omega'$ is inductive) and $\omega' \subseteq \omega$ (as $\omega$ is inductive), so $\omega = \omega'$ by Extensionality.

step 2.1step 2.2∎

DefinitionDefinition: Literature-sourcedProof: Not applicableaudited 2026-07-25Open item page →

The natural numbers $\mathbb{N}$ (von Neumann)

Definition

The set of natural numbers is the smallest inductive set (Inductive set),

$\mathbb{N} = \omega := \bigcap\,\{\, I : I \text{ is inductive} \,\},$

which exists and is itself inductive by The natural numbers exist: a smallest inductive set (the Axiom of Infinity, The Axiom of Infinity: there is a set containing a set with no elements and closed under $y \mapsto y \cup \{y\}$ , supplies one inductive set to intersect within, and Separation, The Axiom Schema of Separation: for each formula $\varphi$ , $\forall \bar p\,\forall x\,\exists y\,\forall z\,(z \in y \leftrightarrow (z \in x \wedge \varphi(z,\bar p)))$ , makes the intersection a set). On $\mathbb{N}$ we take

$0 := \varnothing, \qquad \sigma(n) := n \cup \{n\},$

the distinguished element and the successor function. Thus $0 = \varnothing$ , $1 = \{0\}$ , $2 = \{0, 1\}$ , $3 = \{0, 1, 2\}$ , and in general $n = \{0, 1, \dots, n-1\}$ is the set of its predecessors.

Remarks

"Smallest" means $\omega \subseteq I$ for every inductive set $I$ . This minimality is exactly the induction principle (The principle of mathematical induction): a subset of $\mathbb{N}$ that contains $0$ and is closed under $\sigma$ is itself inductive, hence contains $\omega = \mathbb{N}$ , hence equals $\mathbb{N}$ .

With $0$ and $\sigma$ so defined, $(\mathbb{N}, 0, \sigma)$ satisfies the Peano axioms (Peano system, proved in The von Neumann naturals form a Peano system), so it is a model of the abstract natural numbers. By categoricity (Categoricity: the natural numbers are unique up to unique isomorphism) any other model is uniquely isomorphic to it, so the particular set-theoretic encoding chosen here is immaterial to every arithmetic and order property that follows: those are developed from the Peano axioms, not from the sets themselves.

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passverified 2026-08-02 (claude-opus-5)Open item page →

The principle of mathematical induction

Statement

Let $S \subseteq \mathbb{N}$ . If $0 \in S$ and $\sigma(n) \in S$ whenever $n \in S$ , then $S = \mathbb{N}$ . Equivalently (property form): if a property $P$ satisfies $P(0)$ and ( $P(n) \Rightarrow P(\sigma(n))$ ) for all $n$ , then $P(n)$ holds for all $n \in \mathbb{N}$ . This is the induction principle, the basis of proof by induction.

Facts & Assumptions

Given: $\mathbb{N} = \omega$ is the smallest inductive set (Inductive set, The natural numbers $\mathbb{N}$ (von Neumann), The natural numbers exist: a smallest inductive set); $0 = \varnothing$ , $\sigma(n) = n \cup \{n\}$ .

[L1]

$\omega$ is contained in every inductive set (The natural numbers exist: a smallest inductive set).

Proof

technique · direct

1.1

Suppose $S \subseteq \mathbb{N}$ with $0 = \varnothing \in S$ and ( $x \in S \Rightarrow \sigma(x) = x \cup \{x\} \in S$ ).

given

2.1

Then $S$ contains $\varnothing$ and is closed under $x \mapsto x \cup \{x\}$ , so $S$ is an inductive set.

step 1.1

3.1

$\mathbb{N} = \omega \subseteq S$ because $\omega$ is a subset of every inductive set.

L1step 2.1

4.1

With $S \subseteq \mathbb{N}$ by hypothesis, $S = \mathbb{N}$ .

step 3.1given

5.1

The property form is the set case with $S = \{n \in \mathbb{N} : P(n)\}$ : $P(0)$ and $P(n) \Rightarrow P(\sigma(n))$ give $0 \in S$ and $\sigma$ -closure, so $S = \mathbb{N}$ , i.e. $P$ holds for all $n$ ; conversely the set form is the property form applied to $P(n) :\equiv n \in S$ , so the two are equivalent.

step 4.1∎

LemmaStatement: AI-adaptedProof: AI-generatedprecheck passverified 2026-08-02 (claude-opus-5)Open item page →

Every natural number is a transitive set and is not a member of itself

Statement

For every $n \in \mathbb{N}$ : (a) $n$ is transitive, i.e. $x \in n \Rightarrow x \subseteq n$ ; and (b) $n \notin n$ .

Facts & Assumptions

Given: $\mathbb{N}$ (The natural numbers $\mathbb{N}$ (von Neumann)) with $0 = \varnothing$ , $\sigma(n) = n \cup \{n\}$ ; the induction principle (The principle of mathematical induction). Let $P(n)$ be the conjunction " $n$ is transitive and $n \notin n$ ".

[L1]

Induction: if $P(0)$ and $P(n) \Rightarrow P(\sigma(n))$ , then $P$ holds for all $n$ (The principle of mathematical induction).

Proof

technique · induction

1.1

Base $P(0)$ : $0 = \varnothing$ has no members, so it is vacuously transitive and $\varnothing \notin \varnothing$ .

base

1.2

Inductive hypothesis: $P(n)$ holds, i.e. $n$ is transitive and $n \notin n$ .

2.1

$\sigma(n) = n \cup \{n\}$ is transitive: take $x \in \sigma(n)$ ; if $x \in n$ then $x \subseteq n \subseteq \sigma(n)$ by the inductive hypothesis transitivity; if $x = n$ then $x = n \subseteq \sigma(n)$ since $n \subseteq n \cup \{n\}$ ; either way $x \subseteq \sigma(n)$ .

step 1.2

2.2

$\sigma(n) \notin \sigma(n)$ : suppose $\sigma(n) \in \sigma(n) = n \cup \{n\}$ , so $\sigma(n) \in n$ or $\sigma(n) = n$ ; if $\sigma(n) = n$ then $n \in n$ (as $n \in \{n\} \subseteq \sigma(n) = n$ ), contradicting the inductive hypothesis $n \notin n$ ; if $\sigma(n) \in n$ then $\sigma(n) \subseteq n$ by transitivity of $n$ , and since $n \in n \cup \{n\} = \sigma(n) \subseteq n$ we get $n \in n$ , again contradicting $n \notin n$ ; hence $\sigma(n) \notin \sigma(n)$ .

step 1.2

3.1

Hence $P(\sigma(n))$ holds; by induction [L1], $P(n)$ for all $n \in \mathbb{N}$ : every natural number is transitive and satisfies $n \notin n$ .

step 2.1step 2.2discharge-induction∎

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (openai/gpt-5.4)audited 2026-07-25Open item page →

The von Neumann naturals form a Peano system

Statement

The triple $(\mathbb{N}, 0, \sigma) = (\omega, \varnothing, {\cdot}^{+})$ satisfies the three Peano axioms (Peano system): (P1) $\sigma(n) \neq 0$ for all $n$ ; (P2) $\sigma$ is injective; (P3) induction. Hence a Peano system exists.

Facts & Assumptions

Given: $\mathbb{N} = \omega$ , $0 = \varnothing$ , $\sigma(n) = n \cup \{n\}$ (The natural numbers $\mathbb{N}$ (von Neumann)).

[L1]

Induction principle (The principle of mathematical induction).

[L2]

Every natural number is transitive and satisfies $n \notin n$ (Every natural number is a transitive set and is not a member of itself).

Proof

technique · direct

1.1

(P3) The induction axiom holds: it is exactly the induction principle.

1.2

(P1) For every $n$ , $\sigma(n) = n \cup \{n\}$ contains $n$ , so $\sigma(n)$ is nonempty and $\sigma(n) \neq \varnothing = 0$ .

given

1.3

(P2) Suppose $\sigma(m) = \sigma(n)$ , i.e. $m \cup \{m\} = n \cup \{n\}$ ; then $m \in n \cup \{n\}$ so $m \in n$ or $m = n$ , and symmetrically $n \in m$ or $n = m$ ; if $m \neq n$ then $m \in n$ and $n \in m$ , whence by transitivity [L2] $m \in n$ gives $m \subseteq n$ , and $n \in m \subseteq n$ gives $n \in n$ , contradicting $n \notin n$ [L2]; therefore $m = n$ and $\sigma$ is injective.

L2given

2.1

P1, P2, P3 all hold, so $(\mathbb{N}, 0, \sigma)$ is a Peano system; in particular a Peano system exists.

step 1.1step 1.2step 1.3∎

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (openai/gpt-5.4)audited 2026-07-25Open item page →

The recursion theorem

Statement

Let $(N,0,\sigma)$ be a Peano system (Peano system), in particular the natural numbers $\mathbb{N}$ (The natural numbers $\mathbb{N}$ (von Neumann)). For any set $A$ , any element $a \in A$ , and any function $f : A \to A$ , there is a unique function $g : N \to A$ such that $g(0) = a$ and $g(\sigma(n)) = f(g(n))$ for all $n \in N$ .

Facts & Assumptions

Given: a Peano system $(N,0,\sigma)$ , a set $A$ , an element $a \in A$ , and a function $f : A \to A$ . Call a set $R \subseteq N \times A$ closed when $(0,a) \in R$ and, for all $n \in N$ and $x \in A$ , $(n,x) \in R$ implies $(\sigma(n),f(x)) \in R$ .

[L1]

Induction holds in $N$ : any $S \subseteq N$ with $0 \in S$ that is closed under $\sigma$ equals $N$ (axiom P3, The principle of mathematical induction).

[L2]

In a Peano system $\sigma(n) \ne 0$ (P1) and $\sigma$ is injective (P2) (Peano system).

Proof

technique · direct

1.1

The set $N \times A$ is closed, so the collection of closed subsets of $N \times A$ is nonempty; let $g := \bigcap \{ R : R \subseteq N \times A \text{ closed} \}$ , which is itself closed, since if every closed $R$ contains $(0,a)$ then so does $g$ , and if $(n,x) \in g$ then $(n,x) \in R$ for each closed $R$ , whence $(\sigma(n),f(x)) \in R$ for each such $R$ , so $(\sigma(n),f(x)) \in g$ .

givenconstruct

2.1

Let $D = \{ n \in N : \exists x \in A,\ (n,x) \in g \}$ ; then $0 \in D$ since $(0,a) \in g$ , and if $n \in D$ with $(n,x) \in g$ then $(\sigma(n),f(x)) \in g$ by closure, so $\sigma(n) \in D$ ; by induction $D = N$ , hence $g$ relates every $n$ to at least one $x$ .

L1step 1.1

2.2

Suppose $(0,b) \in g$ with $b \ne a$ ; then $g \setminus \{(0,b)\}$ still contains $(0,a)$ and is closed, since any generated pair $(\sigma(m),f(z))$ has $\sigma(m) \ne 0$ by P1 and so is never equal to $(0,b)$ ; this contradicts the minimality of $g$ , so $a$ is the unique second coordinate paired with $0$ .

L2step 1.1

3.1

Let $U = \{ n \in N : \text{there is exactly one } x \text{ with } (n,x) \in g \}$ ; then $0 \in U$ by step 2.2.

step 2.2

4.1

Assume $n \in U$ with unique value $x$ , so $(n,x) \in g$ and $(\sigma(n),f(x)) \in g$ by closure; if $(\sigma(n),c) \in g$ with $c \ne f(x)$ , then $g \setminus \{(\sigma(n),c)\}$ contains $(0,a)$ because $\sigma(n) \ne 0$ , and is closed, because a generated pair $(\sigma(m),f(z))$ with $(m,z) \in g \setminus \{(\sigma(n),c)\}$ can equal $(\sigma(n),c)$ only if $\sigma(m) = \sigma(n)$ and $f(z) = c$ , but $\sigma(m) = \sigma(n)$ forces $m = n$ by injectivity, then $z = x$ by uniqueness at $n$ , giving $f(z) = f(x) \ne c$ , a contradiction; hence $g \setminus \{(\sigma(n),c)\}$ is closed and smaller than $g$ , contradicting minimality, so $f(x)$ is the unique value at $\sigma(n)$ and $\sigma(n) \in U$ .

L2step 3.1step 1.1

5.1

By induction $U = N$ , so together with the totality from step 2.1 the relation $g$ is a function $g : N \to A$ ; it satisfies $g(0) = a$ , and closure with uniqueness gives $g(\sigma(n)) = f(g(n))$ for all $n$ .

L1step 2.1step 3.1step 4.1

6.1

If $h : N \to A$ also satisfies $h(0) = a$ and $h(\sigma(n)) = f(h(n))$ , then the set $\{ n : g(n) = h(n) \}$ contains $0$ and is closed under $\sigma$ , since $g(n) = h(n)$ implies $g(\sigma(n)) = f(g(n)) = f(h(n)) = h(\sigma(n))$ , so by induction it equals $N$ , that is $h = g$ .

L1step 5.1∎

CorollaryStatement: AI-adaptedProof: AI-adaptedprecheck passverified 2026-08-02 (claude-opus-5)Open item page →

Addition is a well-defined total operation

Statement

For each $m \in \mathbb{N}$ there is a unique function $s_m : \mathbb{N} \to \mathbb{N}$ with $s_m(0) = m$ and $s_m(\sigma(n)) = \sigma(s_m(n))$ . Writing $m + n := s_m(n)$ , addition $+ : \mathbb{N} \times \mathbb{N} \to \mathbb{N}$ is a well-defined total binary operation satisfying $m + 0 = m$ and $m + \sigma(n) = \sigma(m + n)$ .

Facts & Assumptions

Given: the natural numbers $\mathbb{N}$ with successor $\sigma$ .

[L1]

The recursion theorem: for a set $A$ , an element $a \in A$ , and a function $f : A \to A$ there is a unique $g : \mathbb{N} \to A$ with $g(0) = a$ and $g(\sigma(n)) = f(g(n))$ (The recursion theorem).

[L2]

$(\mathbb{N}, 0, \sigma)$ is a Peano system (The von Neumann naturals form a Peano system).

Proof

technique · direct

1.1

Fix $m \in \mathbb{N}$ ; since $(\mathbb{N}, 0, \sigma)$ is a Peano system [L2], apply the recursion theorem with $A = \mathbb{N}$ , $a = m$ , and $f = \sigma$ : there is a unique function $s_m : \mathbb{N} \to \mathbb{N}$ with $s_m(0) = m$ and $s_m(\sigma(n)) = \sigma(s_m(n))$ .

L1L2

2.1

Define $m + n := s_m(n)$ ; since $s_m$ is a total function on $\mathbb{N}$ for every $m \in \mathbb{N}$ , the assignment $(m,n) \mapsto m + n$ is a well-defined function $\mathbb{N} \times \mathbb{N} \to \mathbb{N}$ .

step 1.1

3.1

The recursion equations become $m + 0 = s_m(0) = m$ and $m + \sigma(n) = s_m(\sigma(n)) = \sigma(s_m(n)) = \sigma(m + n)$ , the defining clauses of addition.

step 1.1step 2.1∎

DefinitionDefinition: Literature-sourcedProof: Not applicableaudited 2026-07-25Open item page →

Addition of natural numbers

Definition

Addition $+ : \mathbb{N} \times \mathbb{N} \to \mathbb{N}$ is defined by recursion on the second argument: for each fixed $m \in \mathbb{N}$ ,

$m + 0 = m, \qquad m + \sigma(n) = \sigma(m + n).$

Remarks

This is a definition by recursion, and it requires justification: it does not directly say what $m + n$ is, but pins down $m + 0$ and reduces $m + \sigma(n)$ to $m + n$ . The recursion theorem (The recursion theorem) guarantees that for each $m$ there is exactly one function $n \mapsto m + n$ obeying these two equations, so $+$ is a well-defined total binary operation (Addition is a well-defined total operation).

Taking $m = n = 0$ gives $0 + 0 = 0$ . The equation $m + \sigma(n) = \sigma(m+n)$ with $n = 0$ gives $m + 1 = m + \sigma(0) = \sigma(m + 0) = \sigma(m)$ , so $\sigma(m) = m + 1$ : the successor is "add one", recovering the familiar reading of the Peano successor. The basic laws (commutativity, associativity, cancellation, and the left identity $0 + n = n$ ) are not built in and must be proved by induction (Left identity for addition, Addition is commutative, Addition is associative, Addition is cancellative).

CorollaryStatement: AI-adaptedProof: AI-adaptedprecheck passverified 2026-08-02 (claude-opus-5)Open item page →

Multiplication is a well-defined total operation

Statement

For each $m \in \mathbb{N}$ there is a unique function $p_m : \mathbb{N} \to \mathbb{N}$ with $p_m(0) = 0$ and $p_m(\sigma(n)) = p_m(n) + m$ . Writing $m \cdot n := p_m(n)$ , multiplication $\cdot : \mathbb{N} \times \mathbb{N} \to \mathbb{N}$ is a well-defined total binary operation satisfying $m \cdot 0 = 0$ and $m \cdot \sigma(n) = m \cdot n + m$ .

Facts & Assumptions

Given: $\mathbb{N}$ with successor $\sigma$ and addition $+$ (Addition of natural numbers).

[L1]

The recursion theorem (The recursion theorem).

[L2]

For fixed $m$ , the map $\mathrm{add}_m : x \mapsto x + m$ is a function $\mathbb{N} \to \mathbb{N}$ (Addition of natural numbers).

[L3]

$(\mathbb{N}, 0, \sigma)$ is a Peano system (The von Neumann naturals form a Peano system).

Proof

technique · direct

1.1

Fix $m \in \mathbb{N}$ ; the map $\mathrm{add}_m : \mathbb{N} \to \mathbb{N}$ , $\mathrm{add}_m(x) = x + m$ , is a well-defined function.

2.1

Since $(\mathbb{N}, 0, \sigma)$ is a Peano system [L3], apply the recursion theorem with $A = \mathbb{N}$ , $a = 0$ , $f = \mathrm{add}_m$ : there is a unique $p_m : \mathbb{N} \to \mathbb{N}$ with $p_m(0) = 0$ and $p_m(\sigma(n)) = \mathrm{add}_m(p_m(n)) = p_m(n) + m$ .

L1L3step 1.1

3.1

Define $m \cdot n := p_m(n)$ ; as $p_m$ is total for each $m \in \mathbb{N}$ , the assignment $(m,n) \mapsto m \cdot n$ is a well-defined function $\mathbb{N} \times \mathbb{N} \to \mathbb{N}$ with $m \cdot 0 = 0$ and $m \cdot \sigma(n) = m \cdot n + m$ .

step 2.1∎

DefinitionDefinition: Literature-sourcedProof: Not applicableaudited 2026-07-25Open item page →

Multiplication of natural numbers

Definition

Multiplication $\cdot : \mathbb{N} \times \mathbb{N} \to \mathbb{N}$ is defined by recursion on the second argument, using addition (Addition of natural numbers): for each fixed $m \in \mathbb{N}$ ,

$m \cdot 0 = 0, \qquad m \cdot \sigma(n) = m \cdot n + m.$

We write $mn$ for $m \cdot n$ when no confusion arises.

Remarks

As with addition, this is a recursion and is legitimate by the recursion theorem (The recursion theorem): for each $m$ the map $n \mapsto m \cdot n$ is the unique function with $m \cdot 0 = 0$ and $m \cdot \sigma(n) = m \cdot n + m$ , so $\cdot$ is a well-defined total operation (Multiplication is a well-defined total operation).

The base clause $m \cdot 0 = 0$ builds in absorption on the right; that $0 \cdot n = 0$ on the left, and $1 \cdot n = n = n \cdot 1$ , are proved by induction (Zero and one under multiplication). Multiplication distributes over addition (Distributivity and the successor law for multiplication) and is associative and commutative (Multiplication is associative, Multiplication is commutative); with The natural numbers have no zero divisors and Cancellation for multiplication by a nonzero factor this makes $(\mathbb{N}, +, \cdot)$ a commutative semiring in which cancellation holds.

LemmaStatement: Literature-sourcedProof: AI-adaptedprecheck passverified 2026-08-02 (claude-opus-5)Open item page →

No natural number equals its own successor

Statement

For every $n \in \mathbb{N}$ , $n \neq \sigma(n)$ .

Facts & Assumptions

Given: $\mathbb{N}$ with distinguished element $0$ and successor $\sigma$ .

[L1]

$\sigma(n) \neq 0$ for all $n$ (P1) and $\sigma$ is injective (P2) (The von Neumann naturals form a Peano system).

[L2]

The induction principle (The principle of mathematical induction).

Proof

technique · induction

1.1

Base case $n = 0$ : $\sigma(0) \neq 0$ by P1, so $0 \neq \sigma(0)$ .

baseL1

1.2

Inductive hypothesis: $n \neq \sigma(n)$ .

2.1

If $\sigma(n) = \sigma(\sigma(n))$ then injectivity of $\sigma$ gives $n = \sigma(n)$ , contradicting the hypothesis; hence $\sigma(n) \neq \sigma(\sigma(n))$ .

step 1.2L1

3.1

By induction [L2], $n \neq \sigma(n)$ for all $n \in \mathbb{N}$ .

step 1.1step 2.1discharge-induction∎

LemmaStatement: Literature-sourcedProof: AI-adaptedprecheck passverified 2026-08-02 (claude-opus-5)Open item page →

Every nonzero natural number is a successor

Statement

For every $n \in \mathbb{N}$ with $n \neq 0$ , there exists $m \in \mathbb{N}$ with $n = \sigma(m)$ . Equivalently, every natural number is either $0$ or a successor.

Facts & Assumptions

Given: $\mathbb{N}$ with distinguished element $0$ and successor $\sigma$ . Let $S = \{n \in \mathbb{N} : n = 0 \text{ or } \exists m \in \mathbb{N}\ (n = \sigma(m))\}$ .

[L1]

The induction principle (The principle of mathematical induction).

Proof

technique · induction

1.1

Base case: $0 \in S$ since $0 = 0$ .

base

1.2

Inductive hypothesis: $n \in S$ .

2.1

$\sigma(n)$ is the successor of $n$ , so $\sigma(n) \in S$ (it satisfies $\exists m,\ \sigma(n) = \sigma(m)$ with $m = n$ ).

step 1.2

3.1

By induction [L1], $S = \mathbb{N}$ , so every $n \in \mathbb{N}$ is $0$ or a successor; if $n \neq 0$ then $n = \sigma(m)$ for some $m$ .

step 1.1step 2.1discharge-induction∎

LemmaStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (openai/gpt-5.4)audited 2026-07-25Open item page →

Left identity for addition

Statement

For all $n \in \mathbb{N}$ : $0 + n = n$ . The right identity $n + 0 = n$ is definitional, so together with this law $0$ is a two-sided identity for addition.

Facts & Assumptions

Given: Addition with $m + 0 = m$ and $m + \sigma(n) = \sigma(m + n)$ (Addition of natural numbers).

[L1]

Induction principle (The principle of mathematical induction).

Proof

technique · induction

1.1

Base $n = 0$ : $0 + 0 = 0$ by the clause $m + 0 = m$ at $m = 0$ .

base

1.2

Inductive hypothesis: $0 + n = n$ .

2.1

Step: $0 + \sigma(n) = \sigma(0 + n) = \sigma(n)$ , using $m + \sigma(n) = \sigma(m + n)$ at $m = 0$ , then the hypothesis.

step 1.2given

3.1

By induction [L1], $0 + n = n$ for all $n \in \mathbb{N}$ .

step 1.1step 2.1discharge-induction∎

LemmaStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (openai/gpt-5.4)audited 2026-07-25Open item page →

Left successor law for addition

Statement

For all $m, n \in \mathbb{N}$ : $\sigma(m) + n = \sigma(m + n)$ . (The recursion defines addition on the second argument; this is the matching law for adding on the first.)

Facts & Assumptions

Given: Addition with $m + 0 = m$ and $m + \sigma(k) = \sigma(m + k)$ (Addition of natural numbers).

[L1]

Induction principle (The principle of mathematical induction).

Proof

technique · induction

1.1

Base $n = 0$ : $\sigma(m) + 0 = \sigma(m)$ by $x + 0 = x$ , and $\sigma(m + 0) = \sigma(m)$ by $m + 0 = m$ , so $\sigma(m) + 0 = \sigma(m + 0)$ .

base

1.2

Inductive hypothesis: $\sigma(m) + n = \sigma(m + n)$ .

2.1

Step: $\sigma(m) + \sigma(n) = \sigma(\sigma(m) + n) = \sigma(\sigma(m + n)) = \sigma(m + \sigma(n))$ , applying $x + \sigma(k) = \sigma(x + k)$ at the outer sum, then the hypothesis, then $m + \sigma(n) = \sigma(m + n)$ backward inside $\sigma$ .

step 1.2given

3.1

By induction [L1], $\sigma(m) + n = \sigma(m + n)$ for all $n$ , and since $m$ was arbitrary, for all $m, n \in \mathbb{N}$ .

step 1.1step 2.1discharge-induction∎

LemmaStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (openai/gpt-5.4)audited 2026-07-25Open item page →

Addition is associative

Statement

For all $a, b, c \in \mathbb{N}$ : $(a + b) + c = a + (b + c)$ .

Facts & Assumptions

Given: Addition with $m + 0 = m$ and $m + \sigma(n) = \sigma(m + n)$ (Addition of natural numbers).

[L1]

Induction principle (The principle of mathematical induction).

Proof

technique · induction

1.1

Base $c = 0$ : $(a + b) + 0 = a + b$ and $a + (b + 0) = a + b$ , so they are equal.

base

1.2

Inductive hypothesis: $(a + b) + c = a + (b + c)$ .

2.1

Step: $(a + b) + \sigma(c) = \sigma((a + b) + c) = \sigma(a + (b + c)) = a + \sigma(b + c) = a + (b + \sigma(c))$ , using $m + \sigma(n) = \sigma(m + n)$ twice and the hypothesis.

step 1.2

3.1

By induction [L1], $(a + b) + c = a + (b + c)$ for all $c$ , hence for all $a, b, c \in \mathbb{N}$ .

step 1.1step 2.1discharge-induction∎

LemmaStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (openai/gpt-5.4)audited 2026-07-25Open item page →

Addition is commutative

Statement

For all $m, n \in \mathbb{N}$ : $m + n = n + m$ .

Facts & Assumptions

Given: Addition (Addition of natural numbers).

[L1]

$0 + k = k$ for all $k$ (Left identity for addition).

[L2]

Left successor law: $\sigma(a) + k = \sigma(a + k)$ for all $a, k$ (Left successor law for addition).

[L3]

Induction principle (The principle of mathematical induction).

Proof

technique · induction

1.1

Base $n = 0$ : $m + 0 = m$ and $0 + m = m$ by [L1], so $m + 0 = 0 + m$ .

baseL1

1.2

Inductive hypothesis: $m + n = n + m$ .

2.1

Step: $m + \sigma(n) = \sigma(m + n) = \sigma(n + m)$ by the recursion and the hypothesis; and the left successor law [L2] gives $\sigma(n) + m = \sigma(n + m)$ , so $m + \sigma(n) = \sigma(n + m) = \sigma(n) + m$ .

step 1.2givenL2

3.1

By induction [L3], $m + n = n + m$ for all $n$ , hence for all $m, n \in \mathbb{N}$ .

step 1.1step 2.1discharge-induction∎

LemmaStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (openai/gpt-5.4)audited 2026-07-25Open item page →

Addition is cancellative

Statement

For all $m, n, k \in \mathbb{N}$ : if $m + k = n + k$ then $m = n$ .

Facts & Assumptions

Given: Addition (Addition of natural numbers).

[L1]

$\sigma$ is injective (P2) (The von Neumann naturals form a Peano system).

[L2]

Induction principle (The principle of mathematical induction).

Proof

technique · induction

1.1

Base $k = 0$ : if $m + 0 = n + 0$ then $m = n$ , since $m + 0 = m$ and $n + 0 = n$ .

base

1.2

Inductive hypothesis: for all $m, n$ , $m + k = n + k \Rightarrow m = n$ .

2.1

Step: suppose $m + \sigma(k) = n + \sigma(k)$ ; then $\sigma(m + k) = \sigma(n + k)$ by $m + \sigma(j) = \sigma(m + j)$ , so $m + k = n + k$ by injectivity [L1], hence $m = n$ by the hypothesis.

step 1.2L1

3.1

By induction [L2], cancellation holds for all $k$ , hence for all $m, n, k \in \mathbb{N}$ .

step 1.1step 2.1discharge-induction∎

LemmaStatement: AI-adaptedProof: AI-adaptedprecheck passjudge pass (openai/gpt-5.4)audited 2026-07-25Open item page →

Zero and one under multiplication

Statement

For all $n \in \mathbb{N}$ : $0 \cdot n = 0$ , $1 \cdot n = n$ , and $n \cdot 1 = n$ . Here $1 = \sigma(0)$ , and the clause $n \cdot 0 = 0$ is definitional.

Facts & Assumptions

Given: multiplication $m \cdot 0 = 0$ and $m \cdot \sigma(n) = m \cdot n + m$ (Multiplication of natural numbers), and addition with $m + 0 = m$ and $m + \sigma(k) = \sigma(m + k)$ (Addition of natural numbers).

[L1]

$0 + k = k$ for all $k \in \mathbb{N}$ (Left identity for addition).

[L2]

The induction principle (The principle of mathematical induction).

Proof

technique · induction on $n$

1.1

Right unit $n \cdot 1 = n$ : $n \cdot 1 = n \cdot \sigma(0) = n \cdot 0 + n = 0 + n = n$ , using the multiplication recursion then [L1].

givenL1

1.2

Base of the left inductions: $0 \cdot 0 = 0$ and $1 \cdot 0 = 0$ by the clause $m \cdot 0 = 0$ .

base

1.3

Inductive hypothesis: $0 \cdot n = 0$ and $1 \cdot n = n$ .

2.1

Step: $0 \cdot \sigma(n) = 0 \cdot n + 0 = 0 + 0 = 0$ , using the hypothesis $0 \cdot n = 0$ and $0 + 0 = 0$ (the instance $k = 0$ of [L1]); and $1 \cdot \sigma(n) = 1 \cdot n + 1 = n + 1 = \sigma(n)$ , where $n + 1 = n + \sigma(0) = \sigma(n + 0) = \sigma(n)$ by the addition recursion $m + \sigma(k) = \sigma(m + k)$ and $n + 0 = n$ .

step 1.3givenL1

3.1

By induction [L2], $0 \cdot n = 0$ and $1 \cdot n = n$ for all $n$ ; together with step 1.1, $n \cdot 1 = n$ for all $n$ .

step 1.1step 2.1discharge-induction∎

LemmaStatement: AI-adaptedProof: AI-adaptedprecheck passjudge pass (openai/gpt-5.4)audited 2026-07-25Open item page →

Distributivity and the successor law for multiplication

Statement

For all $a, b, c, n \in \mathbb{N}$ : (left distributivity) $a \cdot (b + c) = a \cdot b + a \cdot c$ ; and (successor-left law) $\sigma(a) \cdot n = a \cdot n + n$ .

Facts & Assumptions

Given: multiplication $m \cdot 0 = 0$ , $m \cdot \sigma(n) = m \cdot n + m$ and addition $m + 0 = m$ , $m + \sigma(k) = \sigma(m + k)$ (Multiplication of natural numbers, Addition of natural numbers); in particular the addition recursion $a + \sigma(k) = \sigma(a + k)$ is available.

[L1]

Addition is associative (Addition is associative) and commutative (Addition is commutative).

[L2]

The induction principle (The principle of mathematical induction).

Proof

technique · induction on $c$ for distributivity, with a second induction on $n$ for the successor law

1.1

Base $c = 0$ : $a \cdot (b + 0) = a \cdot b = a \cdot b + 0 = a \cdot b + a \cdot 0$ , using $b + 0 = b$ and $a \cdot 0 = 0$ .

base

1.2

Inductive hypothesis: $a \cdot (b + c) = a \cdot b + a \cdot c$ .

1.3

Successor-left law $\sigma(a) \cdot n = a \cdot n + n$ , by a second induction on $n$ : base $n = 0$ gives $\sigma(a) \cdot 0 = 0 = a \cdot 0 + 0$ ; assuming $\sigma(a) \cdot n = a \cdot n + n$ , the step gives $\sigma(a) \cdot \sigma(n) = \sigma(a) \cdot n + \sigma(a) = (a \cdot n + n) + \sigma(a) = a \cdot n + (n + \sigma(a)) = a \cdot n + \sigma(n + a) = a \cdot n + \sigma(a + n) = a \cdot n + (a + \sigma(n)) = (a \cdot n + a) + \sigma(n) = a \cdot \sigma(n) + \sigma(n)$ , using associativity and commutativity [L1] and $a + \sigma(k) = \sigma(a + k)$ .

L1given

2.1

Step: $a \cdot (b + \sigma(c)) = a \cdot \sigma(b + c) = a \cdot (b + c) + a = (a \cdot b + a \cdot c) + a = a \cdot b + (a \cdot c + a) = a \cdot b + a \cdot \sigma(c)$ , using $b + \sigma(c) = \sigma(b + c)$ , the multiplication recursion, the hypothesis, associativity [L1], and $a \cdot \sigma(c) = a \cdot c + a$ .

step 1.2L1

3.1

By induction [L2], $a \cdot (b + c) = a \cdot b + a \cdot c$ for all $c$ (hence all $a, b, c$ ) and $\sigma(a) \cdot n = a \cdot n + n$ for all $a, n$ .

step 2.1step 1.3discharge-induction∎

LemmaStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (openai/gpt-5.4)audited 2026-07-25Open item page →

Multiplication is associative

Statement

For all $a, b, c \in \mathbb{N}$ : $(a \cdot b) \cdot c = a \cdot (b \cdot c)$ .

Facts & Assumptions

Given: multiplication and addition (Multiplication of natural numbers, Addition of natural numbers).

[L1]

Left distributivity $a \cdot (b + c) = a \cdot b + a \cdot c$ (Distributivity and the successor law for multiplication).

[L2]

The induction principle (The principle of mathematical induction).

Proof

technique · induction on $c$, with $a, b$ fixed

1.1

Base $c = 0$ : $(a \cdot b) \cdot 0 = 0$ and $a \cdot (b \cdot 0) = a \cdot 0 = 0$ , so the two sides are equal.

base

1.2

Inductive hypothesis: $(a \cdot b) \cdot c = a \cdot (b \cdot c)$ .

2.1

Step: $(a \cdot b) \cdot \sigma(c) = (a \cdot b) \cdot c + a \cdot b = a \cdot (b \cdot c) + a \cdot b = a \cdot (b \cdot c + b) = a \cdot (b \cdot \sigma(c))$ , using the multiplication recursion, the hypothesis, left distributivity [L1], and $b \cdot \sigma(c) = b \cdot c + b$ .

step 1.2L1

3.1

By induction [L2], $(a \cdot b) \cdot c = a \cdot (b \cdot c)$ for all $c$ , hence for all $a, b, c \in \mathbb{N}$ .

step 1.1step 2.1discharge-induction∎

LemmaStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (openai/gpt-5.4)audited 2026-07-25Open item page →

Multiplication is commutative

Statement

For all $m, n \in \mathbb{N}$ : $m \cdot n = n \cdot m$ .

Facts & Assumptions

Given: multiplication (Multiplication of natural numbers).

[L1]

$0 \cdot k = 0$ for all $k \in \mathbb{N}$ (Zero and one under multiplication).

[L2]

The successor-left law $\sigma(n) \cdot m = n \cdot m + m$ (Distributivity and the successor law for multiplication).

[L3]

The induction principle (The principle of mathematical induction).

Proof

technique · induction on $n$, with $m$ fixed

1.1

Base $n = 0$ : $m \cdot 0 = 0$ and $0 \cdot m = 0$ by [L1], so $m \cdot 0 = 0 \cdot m$ .

baseL1

1.2

Inductive hypothesis: $m \cdot n = n \cdot m$ .

2.1

Step: $m \cdot \sigma(n) = m \cdot n + m = n \cdot m + m = \sigma(n) \cdot m$ , using the multiplication recursion, the hypothesis, then the successor-left law [L2].

step 1.2L2

3.1

By induction [L3], $m \cdot n = n \cdot m$ for all $n$ , hence for all $m, n \in \mathbb{N}$ .

step 1.1step 2.1discharge-induction∎

LemmaStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (openai/gpt-5.4)audited 2026-07-25Open item page →

The natural numbers have no zero divisors

Statement

For all $m,n\in\mathbb{N}$ : if $m\cdot n=0$ then $m=0$ or $n=0$ . Equivalently, if $m\ne 0$ and $n\ne 0$ then $m\cdot n\ne 0$ .

Facts & Assumptions

Given: multiplication defined by $m\cdot 0=0$ and $m\cdot\sigma(k)=m\cdot k+m$ ; addition defined by $m+0=m$ and $m+\sigma(k)=\sigma(m+k)$ .

[L1]

Every nonzero natural is a successor: if $x\ne 0$ then $x=\sigma(a)$ for some $a\in\mathbb{N}$ (Every nonzero natural number is a successor).

[L2]

$\sigma(j)\ne 0$ for all $j\in\mathbb{N}$ (Peano axiom P1) (The von Neumann naturals form a Peano system).

Proof

technique · contrapositive

1.1

It suffices to prove the contrapositive: if $m\ne 0$ and $n\ne 0$ then $m\cdot n\ne 0$ .

contrapositive-reduce

1.2

Assume $m\ne 0$ and $n\ne 0$ .

assume-hyp

2.1

By [L1] write $m=\sigma(a)$ and $n=\sigma(b)$ for some $a,b\in\mathbb{N}$ .

L1step 1.2

3.1

Then $m\cdot n=m\cdot\sigma(b)=m\cdot b+m=m\cdot b+\sigma(a)=\sigma(m\cdot b+a)$ , using the multiplication recursion, $m=\sigma(a)$ , and $c+\sigma(a)=\sigma(c+a)$ .

step 2.1given

4.1

By [L2], $\sigma(m\cdot b+a)\ne 0$ , so $m\cdot n\ne 0$ ; this proves the contrapositive, hence if $m\cdot n=0$ then $m=0$ or $n=0$ .

step 3.1L2discharge-contrapositive∎

DefinitionDefinition: Literature-sourcedProof: Not applicableverified 2026-08-02 (claude-opus-5)Open item page →

Order on the natural numbers

Definition

For $m, n \in \mathbb{N}$ , define the order by

$m \le n \iff \exists k \in \mathbb{N}\ (m + k = n),$

and the strict order by $m < n \iff (m \le n \text{ and } m \neq n)$ , using addition (Addition of natural numbers).

Remarks

Read $m \le n$ as " $n$ is $m$ plus something": the gap $k$ with $m + k = n$ is unique when it exists (by commutativity and cancellation, Addition is commutative, Addition is cancellative) and is written $n - m$ once subtraction is available. That $\le$ is genuinely a linear order, reflexive, antisymmetric, transitive, and total, is proved in $\le$ is a linear order on $\mathbb{N}$ and Trichotomy of the order on $\mathbb{N}$ ; compatibility with the arithmetic (Order is compatible with addition, Order is compatible with multiplication) and discreteness ( $m < n \iff \sigma(m) \le n$ , Discreteness: $\sigma(n)$ is the immediate successor) follow.

In the von Neumann model this order coincides with membership and inclusion: $m \le n \iff m \subseteq n$ and $m < n \iff m \in n$ , matching the picture of each natural number as the set $\{0, 1, \dots, n-1\}$ of its predecessors (The natural numbers $\mathbb{N}$ (von Neumann)). That coincidence is not proved here; it is derived from the additive definition above on a later page. The least-element property of every nonempty subset, the well-ordering principle (The well-ordering principle), is the deepest consequence.

LemmaStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (openai/gpt-5.4)audited 2026-07-25Open item page →

Trichotomy of the order on $\mathbb{N}$

Statement

For all $m, n \in \mathbb{N}$ exactly one of $m < n$ , $m = n$ , $m > n$ holds. In particular the order (Order on the natural numbers) is total.

Facts & Assumptions

Given: The order on $\mathbb{N}$ , where $m \le n$ means $\exists k\ (m + k = n)$ and $m < n$ means $m \le n$ with $m \ne n$ (Order on the natural numbers), and addition with $m + 0 = m$ , $m + \sigma(n) = \sigma(m + n)$ (Addition of natural numbers).

[L1]

$0 + k = k$ (Left identity for addition).

[L2]

Left successor law: $\sigma(a) + k = \sigma(a + k)$ (Left successor law for addition).

[L3]

Addition is associative (Addition is associative).

[L4]

Every nonzero natural is a successor: $n \ne 0 \Rightarrow n = \sigma(a)$ for some $a$ (Every nonzero natural number is a successor).

[L5]

$\sigma(x) \ne 0$ for every $x$ (axiom P1 of The von Neumann naturals form a Peano system).

[L6]

Cancellation: $x + k = y + k \Rightarrow x = y$ (Addition is cancellative).

[L7]

Addition is commutative (Addition is commutative).

Proof

technique · induction

1.1

At most one of the three holds where equality is involved: $m < n$ forces $m \ne n$ and $m > n$ forces $n \ne m$ , so $m = n$ is incompatible with either strict relation.

given

1.2

The two strict relations are incompatible: if $m < n$ and $m > n$ then $m + j = n$ and $n + i = m$ with $i, j \ne 0$ , so $m + (j + i) = (m + j) + i = n + i = m = m + 0$ ; by commutativity [L7], $(j + i) + m = 0 + m$ , so $j + i = 0$ by cancellation [L6]; yet $j = \sigma(a)$ [L4] gives, by the left successor law [L2], $j + i = \sigma(a) + i = \sigma(a + i) \ne 0$ [L5], a contradiction.

givenL2L3L4L5L6L7

1.3

For every $n$ one has $n < \sigma(n)$ , since $n + \sigma(0) = \sigma(n + 0) = \sigma(n)$ by the recursion, with $\sigma(0) \ne 0$ [L5].

givenL5

1.4

Base case $n = 0$ : for arbitrary $m$ , either $m = 0$ , giving $m = n$ , or $m \ne 0$ so $0 + m = m$ [L1] with $m \ne 0$ gives $0 < m$ , that is $n < m$ ; so at least one of $m < n$ , $m = n$ , $m > n$ holds.

baseL1L4

1.5

Inductive hypothesis: fix $n$ and assume that for every $m$ at least one of $m < n$ , $m = n$ , $m > n$ holds.

2.1

Successor step: for arbitrary $m$ , apply the hypothesis; if $m < n$ then $n = m + k$ with $k \ne 0$ , and the recursion gives $m + \sigma(k) = \sigma(m + k) = \sigma(n)$ , so $\sigma(n) = m + \sigma(k)$ with $\sigma(k) \ne 0$ [L5], giving $m < \sigma(n)$ ; if $m = n$ then $m + \sigma(0) = \sigma(m + 0) = \sigma(m) = \sigma(n)$ , so $\sigma(n) = m + \sigma(0)$ with $\sigma(0) \ne 0$ , giving $m < \sigma(n)$ ; if $m > n$ then $m = n + i$ with $i \ne 0$ , so $i = \sigma(a)$ [L4], and the recursion gives $n + \sigma(a) = \sigma(n + a)$ while the left successor law [L2] gives $\sigma(n) + a = \sigma(n + a)$ , so $m = n + \sigma(a) = \sigma(n + a) = \sigma(n) + a$ , whence $a = 0$ gives $m = \sigma(n)$ and $a \ne 0$ gives $\sigma(n) < m$ ; in every case at least one of $m < \sigma(n)$ , $m = \sigma(n)$ , $m > \sigma(n)$ holds.

step 1.5givenL2L4L5

3.1

By the induction principle with base 1.4, hypothesis 1.5, and step 2.1, comparability holds for all $m, n$ , and with the incompatibilities 1.1 and 1.2 exactly one of $m < n$ , $m = n$ , $m > n$ holds, so the order is total.

step 1.1step 1.2step 1.4step 2.1discharge-induction∎

TheoremStatement: AI-adaptedProof: AI-adaptedprecheck passverified 2026-08-02 (claude-opus-5)Open item page →

$\le$ is a linear order on $\mathbb{N}$

Statement

The relation $\le$ on $\mathbb{N}$ , where $m \le n \iff \exists k\ (m + k = n)$ (Order on the natural numbers), is a linear (total) order: reflexive, antisymmetric, transitive, and total.

Facts & Assumptions

Given: The order $m \le n \iff \exists k\ (m + k = n)$ (Order on the natural numbers) and addition with $m + 0 = m$ , $m + \sigma(n) = \sigma(m + n)$ (Addition of natural numbers).

[L1]

$0 + k = k$ and addition is associative (Left identity for addition, Addition is associative).

[L2]

Cancellation: $m + k = n + k \Rightarrow m = n$ (Addition is cancellative).

[L3]

Every nonzero natural is a successor: if $j \ne 0$ then $j = \sigma(i)$ for some $i$ (Every nonzero natural number is a successor).

[L4]

Trichotomy: exactly one of $m < n$ , $m = n$ , $m > n$ holds (Trichotomy of the order on $\mathbb{N}$ ).

[L5]

Addition is commutative (Addition is commutative).

[L6]

$\sigma(x) \ne 0$ for every $x$ (Peano axiom P1) (The von Neumann naturals form a Peano system).

Proof

technique · direct

1.1

Reflexive: $m + 0 = m$ , so $m \le m$ .

given

1.2

Transitive: if $m \le n$ and $n \le p$ , say $m + k = n$ and $n + j = p$ , then $m + (k + j) = (m + k) + j = n + j = p$ , so $m \le p$ .

givenL1

1.3

A sum is zero only if both summands are: if $k + j = 0$ with $j \ne 0$ then $j = \sigma(i)$ and $k + j = k + \sigma(i) = \sigma(k + i) \ne 0$ [L6], a contradiction, so $k = j = 0$ .

L1L3L6

1.4

Total: by trichotomy one of $m < n$ , $m = n$ , $m > n$ holds, and each of these gives $m \le n$ or $n \le m$ .

2.1

Antisymmetric: if $m \le n$ and $n \le m$ , say $m + k = n$ and $n + j = m$ , then $m + (k + j) = (m + k) + j = n + j = m = m + 0$ ; commuting both sides [L5] gives $(k + j) + m = 0 + m$ , and cancelling the common right summand $m$ [L2] gives $k + j = 0$ , hence $k = j = 0$ by step 1.3 and $m = n$ .

givenL1L2L5step 1.3

3.1

Reflexivity, antisymmetry, transitivity, and totality all hold, so $\le$ is a linear order on $\mathbb{N}$ .

step 1.1step 1.2step 2.1step 1.4∎

LemmaStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (openai/gpt-5.4)audited 2026-07-25Open item page →

Order is compatible with addition

Statement

For all $m, n, k \in \mathbb{N}$ : $m \le n \iff m + k \le n + k$ ; and $m < n \iff m + k < n + k$ (Order on the natural numbers).

Facts & Assumptions

Given: The order $m \le n \iff \exists j\ (m + j = n)$ (Order on the natural numbers) and addition with $m + 0 = m$ , $m + \sigma(n) = \sigma(m + n)$ (Addition of natural numbers).

[L1]

Addition is associative and commutative (Addition is associative, Addition is commutative).

[L2]

Cancellation: $m + k = n + k \Rightarrow m = n$ (Addition is cancellative).

Proof

technique · direct

1.1

Forward: if $m \le n$ , say $m + j = n$ , then $(m + k) + j = (m + j) + k = n + k$ , so $m + k \le n + k$ .

givenL1

1.2

Backward: if $m + k \le n + k$ , say $(m + k) + j = n + k$ , then $(m + j) + k = n + k$ , so $m + j = n$ by cancellation, giving $m \le n$ .

givenL1L2

2.1

The strict forms follow: $m < n$ means $m \le n$ and $m \ne n$ , while $m + k = n + k \iff m = n$ by cancellation, so $m < n \iff m + k < n + k$ .

step 1.1step 1.2L2∎

LemmaStatement: Literature-sourcedProof: AI-adaptedprecheck passverified 2026-08-02 (claude-opus-5)Open item page →

Order is compatible with multiplication

Statement

For all $m, n, k \in \mathbb{N}$ : if $m \le n$ then $m \cdot k \le n \cdot k$ ; and if in addition $k \ne 0$ and $m < n$ , then $m \cdot k < n \cdot k$ (Order on the natural numbers).

Facts & Assumptions

Given: The order $m \le n \iff \exists d\ (m + d = n)$ , with $m < n$ meaning $m \le n$ and $m \ne n$ (Order on the natural numbers); addition with $m + 0 = m$ (Addition of natural numbers); and multiplication with $m \cdot 0 = 0$ , $m \cdot \sigma(n) = m \cdot n + m$ (Multiplication of natural numbers).

[L1]

Right distributivity $(m + d) \cdot k = m \cdot k + d \cdot k$ , from left distributivity and commutativity (Distributivity and the successor law for multiplication, Multiplication is commutative).

[L2]

No zero divisors: $d \ne 0$ and $k \ne 0 \Rightarrow d \cdot k \ne 0$ (The natural numbers have no zero divisors).

[L3]

Cancellation for addition: $x + k = y + k \Rightarrow x = y$ (Addition is cancellative).

[L4]

Addition is commutative: $x + y = y + x$ (Addition is commutative).

Proof

technique · direct

1.1

If $m \le n$ , write $m + d = n$ ; then $n \cdot k = (m + d) \cdot k = m \cdot k + d \cdot k$ by right distributivity, so $m \cdot k \le n \cdot k$ .

givenL1

2.1

If moreover $m < n$ then $d \ne 0$ , for $d = 0$ would give $n = m + 0 = m$ , contradicting $m \ne n$ ; then with $k \ne 0$ we get $d \cdot k \ne 0$ by [L2], so $m \cdot k + d \cdot k = n \cdot k$ with $d \cdot k \ne 0$ ; and $m \cdot k \ne n \cdot k$ , since equality would give $m \cdot k + d \cdot k = m \cdot k + 0$ , hence $d \cdot k + m \cdot k = 0 + m \cdot k$ by [L4] and $d \cdot k = 0$ by [L3], a contradiction; therefore $m \cdot k < n \cdot k$ .

step 1.1givenL2L3L4∎

LemmaStatement: AI-adaptedProof: AI-adaptedprecheck passverified 2026-08-02 (claude-opus-5)Open item page →

Discreteness: $\sigma(n)$ is the immediate successor

Statement

For all $m, n \in \mathbb{N}$ : $m < n \iff \sigma(m) \le n$ (Order on the natural numbers). Consequently there is no $k$ with $n < k < \sigma(n)$ : the successor $\sigma(n)$ is the immediate successor of $n$ .

Facts & Assumptions

Given: The order $m \le n \iff \exists j\ (m + j = n)$ , with $m < n$ meaning $m \le n$ and $m \ne n$ (Order on the natural numbers), and addition with $m + 0 = m$ , $m + \sigma(n) = \sigma(m + n)$ (Addition of natural numbers).

[L1]

Every nonzero natural is a successor: $j \ne 0 \Rightarrow j = \sigma(i)$ (Every nonzero natural number is a successor).

[L2]

$\sigma(m) + i = \sigma(m + i)$ (the left successor law, Left successor law for addition) and $m + \sigma(i) = \sigma(m + i)$ (the addition recursion).

[L3]

Cancellation: $x + k = y + k \Rightarrow x = y$ (Addition is cancellative).

[L4]

$\sigma(x) \ne 0$ for every $x$ (Peano axiom P1) (The von Neumann naturals form a Peano system).

[L5]

Addition is commutative: $x + y = y + x$ (Addition is commutative).

Proof

technique · direct

1.1

Forward: if $m < n$ then $m \le n$ and $m \ne n$ , so $m + j = n$ for some $j$ , with $j \ne 0$ since $j = 0$ would give $m = n$ ; then $j = \sigma(i)$ [L1] and $n = m + \sigma(i) = \sigma(m + i) = \sigma(m) + i$ [L2], hence $\sigma(m) \le n$ .

givenL1L2

1.2

Backward: if $\sigma(m) \le n$ then $\sigma(m) + i = n$ , so $n = \sigma(m) + i = \sigma(m + i) = m + \sigma(i)$ [L2], hence $m \le n$ ; and $m \ne n$ , since $m = n$ would give $m + \sigma(i) = m = m + 0$ , so $\sigma(i) + m = 0 + m$ by [L5] and $\sigma(i) = 0$ by [L3], contradicting [L4]; therefore $m < n$ .

givenL2L3L4L5

2.1

No $k$ satisfies $n < k < \sigma(n)$ : if $n < k$ then $\sigma(n) \le k$ by the equivalence, so $k \ge \sigma(n)$ , contradicting $k < \sigma(n)$ ; thus $\sigma(n)$ is the immediate successor.

step 1.1step 1.2∎

LemmaStatement: Literature-sourcedProof: AI-adaptedprecheck passverified 2026-08-02 (claude-opus-5)Open item page →

Cancellation for multiplication by a nonzero factor

Statement

For all $m,n,k\in\mathbb{N}$ with $k\ne 0$ : if $m\cdot k=n\cdot k$ then $m=n$ .

Facts & Assumptions

Given: multiplication defined by $m\cdot 0=0$ and $m\cdot\sigma(j)=m\cdot j+m$ ; the order $m\le n\iff\exists j\ (m+j=n)$ , with $m<n$ meaning $m\le n$ and $m\ne n$ .

[L1]

Trichotomy: for all $m,n\in\mathbb{N}$ exactly one of $m<n$ , $m=n$ , $m>n$ holds (Trichotomy of the order on $\mathbb{N}$ ).

[L2]

Strict monotonicity: if $k\ne 0$ and $m<n$ then $m\cdot k<n\cdot k$ (Order is compatible with multiplication).

Proof

technique · contradiction

1.1

Suppose $m\cdot k=n\cdot k$ with $k\ne 0$ but $m\ne n$ .

assume-contra

2.1

By trichotomy [L1], $m\ne n$ forces $m<n$ or $n<m$ .

step 1.1L1

3.1

If $m<n$ then $m\cdot k<n\cdot k$ by [L2] (since $k\ne 0$ ); if $n<m$ then $n\cdot k<m\cdot k$ by [L2]; either way $m\cdot k\ne n\cdot k$ .

step 2.1L2

4.1

This contradicts $m\cdot k=n\cdot k$ , so the assumption $m\ne n$ is impossible and $m=n$ .

step 1.1step 3.1discharge-contradiction∎

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passverified 2026-08-02 (claude-opus-5)Open item page →

The well-ordering principle

Statement

Every nonempty subset $S \subseteq \mathbb{N}$ has a least element: there is $\ell \in S$ with $\ell \le s$ for all $s \in S$ .

Facts & Assumptions

Given: A nonempty subset $S \subseteq \mathbb{N}$ . Define $T = \{\, n \in \mathbb{N} : \text{every } m \text{ with } m \le n \text{ satisfies } m \notin S \,\}$ (informally, no element of $S$ is $\le n$ ).

[L1]

Induction principle: a subset of $\mathbb{N}$ that contains $0$ and is closed under $\sigma$ equals $\mathbb{N}$ (The principle of mathematical induction).

[L2]

$m < n \iff \sigma(m) \le n$ ; consequently no $k$ satisfies $n < k < \sigma(n)$ (Discreteness: $\sigma(n)$ is the immediate successor).

[L3]

Exactly one of $s < n$ , $s = n$ , $n < s$ holds (Trichotomy of the order on $\mathbb{N}$ ); and $n < s \iff \sigma(n) \le s$ (Discreteness: $\sigma(n)$ is the immediate successor).

[L4]

$\sigma$ is injective (Peano axiom P2) (The von Neumann naturals form a Peano system).

[L5]

$\sigma(a) + i = \sigma(a + i)$ for all $a, i$ (the left successor law, Left successor law for addition).

[L6]

$0 + k = k$ for all $k$ (Left identity for addition).

Proof

technique · contradiction

1.1

Suppose $S$ is nonempty but has no least element.

assume-contra

1.2

If $m < \sigma(n)$ then $m \le n$ : by [L2] applied to $m$ and $\sigma(n)$ we get $\sigma(m) \le \sigma(n)$ , say $\sigma(m) + i = \sigma(n)$ ; then $\sigma(m + i) = \sigma(m) + i = \sigma(n)$ [L5], so $m + i = n$ by injectivity [L4], hence $m \le n$ .

L2L4L5

2.1

First, $0 \in T$ : if $0 \in S$ then $0 \le s$ for all $s \in S$ , since $0 + s = s$ [L6], making $0$ a least element, contrary to the assumption; hence $0 \notin S$ ; moreover $m \le 0$ forces $m = 0$ , because $m \ne 0$ would give $0 < m$ (as $0 + m = m$ [L6] with $m \ne 0$ ) while $m \le 0$ gives $m < 0$ , and [L3] admits at most one of these; so every $m \le 0$ lies outside $S$ .

step 1.1L3L6given

2.2

Next, $T$ is closed under $\sigma$ : assume $n \in T$ ; if $\sigma(n) \in S$ then no $s \in S$ satisfies $s < \sigma(n)$ (else $s \le n$ by step 1.2, so $s \notin S$ because $n \in T$ , a contradiction), hence $\sigma(n) \le s$ for all $s \in S$ by [L3], making $\sigma(n)$ a least element, contrary to the assumption; therefore $\sigma(n) \notin S$ , and any $m$ with $m \le \sigma(n)$ satisfies $m = \sigma(n)$ or $m \ne \sigma(n)$ ; in the second case $m \le \sigma(n)$ together with $m \ne \sigma(n)$ gives $m < \sigma(n)$ by the definition of the strict order, hence $m \le n$ by step 1.2 and $m \notin S$ because $n \in T$ , while in the first case $m = \sigma(n) \notin S$ ; so every $m \le \sigma(n)$ lies outside $S$ , giving $\sigma(n) \in T$ .

step 1.1step 1.2L3

3.1

By the induction principle [L1], from $0 \in T$ and closure under $\sigma$ , $T = \mathbb{N}$ ; then for every $n$ , taking $m = n \le n$ shows $n \notin S$ , so $S = \varnothing$ , contradicting nonemptiness; therefore $S$ has a least element.

step 2.1step 2.2L1discharge-contradiction∎

TheoremStatement: AI-adaptedProof: AI-adaptedprecheck passverified 2026-08-02 (claude-opus-5)Open item page →

Strong (complete) induction

Statement

Let $P$ be a property of naturals such that for every $n \in \mathbb{N}$ , if $P(m)$ holds for all $m < n$ then $P(n)$ . Then $P(n)$ holds for all $n \in \mathbb{N}$ . (At $n = 0$ the hypothesis is vacuous, so $P(0)$ is forced.)

Facts & Assumptions

Given: A property $P$ satisfying the strong-induction hypothesis $H$ : for every $n$ , $\big(P(m) \text{ for all } m < n\big) \Rightarrow P(n)$ .

[L1]

Well-ordering: every nonempty subset of $\mathbb{N}$ has a least element (The well-ordering principle).

[L2]

Exactly one of $x < y$ , $x = y$ , $y < x$ holds (Trichotomy of the order on $\mathbb{N}$ ).

Proof

technique · contradiction

1.1

Suppose $P$ fails somewhere; let $S = \{\, n \in \mathbb{N} : P(n) \text{ is false} \,\}$ , a nonempty subset of $\mathbb{N}$ .

assume-contra

2.1

By well-ordering [L1], $S$ has a least element $\ell$ , so $\ell \le s$ for every $s \in S$ ; hence every $m < \ell$ lies outside $S$ , since $m \in S$ would give $\ell \le m$ , which [L2] does not allow alongside $m < \ell$ ; that is, $P(m)$ holds for all $m < \ell$ .

step 1.1L1L2

3.1

By the hypothesis $H$ applied at $\ell$ , $P(\ell)$ holds, so $\ell \notin S$ .

step 2.1given

4.1

But $\ell \in S$ by construction, a contradiction; hence $S$ is empty and $P(n)$ holds for all $n \in \mathbb{N}$ .

step 2.1step 3.1discharge-contradiction∎

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passverified 2026-08-02 (claude-opus-5)Open item page →

Categoricity: the natural numbers are unique up to unique isomorphism

Statement

Let $(N, 0, \sigma)$ and $(N', 0', \sigma')$ be Peano systems (Peano system). There is a unique bijection $h : N \to N'$ with $h(0) = 0'$ and $h(\sigma(n)) = \sigma'(h(n))$ for all $n \in N$ , an isomorphism of Peano systems. Thus the natural numbers are determined up to a unique isomorphism.

Facts & Assumptions

Given: Two Peano systems $(N, 0, \sigma)$ and $(N', 0', \sigma')$ .

[L1]

Recursion theorem, valid in any Peano system since its proof uses only the axioms P1 to P3: for a set $A$ , an element $a \in A$ , and $f : A \to A$ , there is a unique $g : N \to A$ with $g(0) = a$ and $g(\sigma(n)) = f(g(n))$ (The recursion theorem).

[L2]

Induction holds in each system (axiom P3): a subset containing the base point and closed under the successor is the whole system (Peano system).

Proof

technique · direct

1.1

Apply the recursion theorem [L1] in $(N, 0, \sigma)$ with $A = N'$ , $a = 0'$ , $f = \sigma'$ : there is a unique $h : N \to N'$ with $h(0) = 0'$ and $h(\sigma(n)) = \sigma'(h(n))$ .

1.2

Symmetrically, apply [L1] in $(N', 0', \sigma')$ with $A = N$ , $a = 0$ , $f = \sigma$ : there is a unique $h' : N' \to N$ with $h'(0') = 0$ and $h'(\sigma'(n')) = \sigma(h'(n'))$ .

2.1

The composite $h' \circ h : N \to N$ satisfies $(h' \circ h)(0) = h'(0') = 0$ and $(h' \circ h)(\sigma(n)) = h'(\sigma'(h(n))) = \sigma(h'(h(n))) = \sigma((h' \circ h)(n))$ ; the identity $\mathrm{id}_N$ satisfies the same two equations, so by induction [L2] the set $\{\, n : (h' \circ h)(n) = n \,\}$ is all of $N$ , i.e. $h' \circ h = \mathrm{id}_N$ .

step 1.1step 1.2L2

2.2

Likewise $h \circ h' = \mathrm{id}_{N'}$ by the same argument carried out in $N'$ .

step 1.1step 1.2L2

3.1

Hence $h$ is a bijection with inverse $h'$ , and it preserves the base point and the successor, so it is an isomorphism of Peano systems.

step 2.1step 2.2

4.1

Uniqueness: any $h_1 : N \to N'$ with $h_1(0) = 0'$ and $h_1(\sigma(n)) = \sigma'(h_1(n))$ satisfies the recursion clauses defining $h$ in step 1.1, so $h_1 = h$ by the uniqueness in [L1] (equivalently $\{\, n : h_1(n) = h(n) \,\}$ contains $0$ and is closed under $\sigma$ , hence is all of $N$ by induction [L2]).

step 1.1L1L2∎

5 · Examples, counterexamples and false statements

ExampleConstruction: AI-adaptedVerification: AI-adaptedprecheck passjudge pass (openai/gpt-5.4)audited 2026-07-25Open item page →

$1+1=2$ from the recursion

Example

With $1 = \sigma(0)$ and $2 = \sigma(1) = \sigma(\sigma(0))$ , the recursive definition of addition gives $1 + 1 = 2$ . This is the archetypal proof by unfolding a recursive definition.

Facts & Assumptions

Given: addition $m + 0 = m$ , $m + \sigma(n) = \sigma(m + n)$ (Addition of natural numbers); numerals $1 = \sigma(0)$ , $2 = \sigma(1)$ (The natural numbers $\mathbb{N}$ (von Neumann)).

Verification

technique · direct

1.1

By definition $1 = \sigma(0)$ and $2 = \sigma(1) = \sigma(\sigma(0))$ .

given

1.2

$1 + 0 = 1$ , by $m + 0 = m$ with $m = 1$ .

given

2.1

$1 + 1 = 1 + \sigma(0) = \sigma(1 + 0)$ , by $m + \sigma(n) = \sigma(m + n)$ with $m = 1$ , $n = 0$ .

step 1.1given

3.1

Hence $1 + 1 = \sigma(1 + 0) = \sigma(1) = 2$ .

step 2.1step 1.2∎

ExampleConstruction: AI-adaptedVerification: AI-adaptedprecheck passjudge pass (openai/gpt-5.4)audited 2026-07-25Open item page →

$2+2=4$ from the recursion

Example

With $2 = \sigma(\sigma(0))$ and $4 = \sigma(\sigma(\sigma(\sigma(0))))$ , the recursion gives $2 + 2 = 4$ , by unfolding the successor twice down to $2 + 0 = 2$ .

Facts & Assumptions

Given: addition $m + 0 = m$ , $m + \sigma(n) = \sigma(m + n)$ (Addition of natural numbers); $2 = \sigma(\sigma(0))$ , $4 = \sigma(\sigma(\sigma(\sigma(0))))$ (The natural numbers $\mathbb{N}$ (von Neumann)).

Verification

technique · direct

1.1

Write $2 = \sigma(\sigma(0))$ ; then $2 + 2 = 2 + \sigma(\sigma(0))$ .

given

1.2

$2 + 0 = 2$ , by $m + 0 = m$ .

given

2.1

$2 + \sigma(\sigma(0)) = \sigma(2 + \sigma(0)) = \sigma(\sigma(2 + 0))$ , applying $m + \sigma(n) = \sigma(m + n)$ twice.

step 1.1given

3.1

Hence $2 + 2 = \sigma(\sigma(2)) = \sigma(\sigma(\sigma(\sigma(0)))) = 4$ .

step 2.1step 1.2∎

CounterexampleConstruction: AI-adaptedVerification: AI-adaptedprecheck passverified 2026-08-02 (claude-opus-5)Open item page →

The induction axiom is independent of the other Peano axioms

Statement refuted

Refuted claim: any triple $(N, 0, \sigma)$ satisfying (P1) $0$ is not a successor and (P2) $\sigma$ is injective automatically satisfies (P3) induction. The witness is $N = \mathbb{N} \sqcup \mathbb{Z}$ (a disjoint union of a copy of the naturals and a copy of the integers), with base point $0$ the zero of the $\mathbb{N}$ -copy and $\sigma$ the usual successor $n \mapsto n + 1$ on each copy separately.

Facts & Assumptions

Given: $N = \mathbb{N} \sqcup \mathbb{Z}$ with $\sigma$ acting as successor within each copy; $0 =$ the $\mathbb{N}$ -copy's zero. Write $N_{\mathbb{N}}, N_{\mathbb{Z}}$ for the two copies.

[L1]

The Peano axioms P1, P2, P3 (Peano system).

[L2]

$\mathbb{N}$ itself is the standard model (The natural numbers $\mathbb{N}$ (von Neumann)).

Counterexample

technique · direct

1.1

P1 holds: $\sigma$ is the successor within each copy; $0$ is the $\mathbb{N}$ -copy zero, which is not the successor of any element (nothing in $N_{\mathbb{N}}$ maps to it, and $\sigma$ maps $N_{\mathbb{Z}}$ into $N_{\mathbb{Z}}$ ), so $\sigma(x) \neq 0$ for all $x$ .

givenL1

1.2

P2 holds: $\sigma$ is injective on $N_{\mathbb{N}}$ and on $N_{\mathbb{Z}}$ separately, and $\sigma$ maps each copy into itself, so $\sigma$ is injective on $N$ .

givenL1

1.3

P3 fails: let $S = N_{\mathbb{N}}$ , the $\mathbb{N}$ -copy; then $0 \in S$ and $\sigma$ maps $S$ into $S$ ( $\sigma(N_{\mathbb{N}}) \subseteq N_{\mathbb{N}}$ ), so $S$ contains $0$ and is closed under $\sigma$ ; the $\mathbb{N}$ -copy is the standard model [L2].

givenL1L2

2.1

But $S = N_{\mathbb{N}} \neq N$ , since the $\mathbb{Z}$ -copy $N_{\mathbb{Z}}$ is disjoint from $S$ and nonempty.

step 1.3

3.1

Thus $(N, 0, \sigma)$ satisfies P1 and P2 but not P3, refuting the claim: induction is independent of P1 and P2 and cannot be dropped.

step 1.1step 1.2step 1.3step 2.1∎

CounterexampleConstruction: AI-adaptedVerification: AI-adaptedprecheck passverified 2026-08-02 (claude-opus-5)Open item page →

Injectivity of the successor is independent of the other Peano axioms

Statement refuted

Refuted claim: (P2) injectivity of $\sigma$ follows from (P1) $0$ is not a successor together with (P3) induction. The witness is the three-element system $N = \{0, 1, 2\}$ with $\sigma(0) = 1$ , $\sigma(1) = 2$ , $\sigma(2) = 2$ .

Facts & Assumptions

Given: $N = \{0, 1, 2\}$ , base point $0$ , $\sigma(0) = 1$ , $\sigma(1) = 2$ , $\sigma(2) = 2$ .

[L1]

The Peano axioms (Peano system).

Counterexample

technique · direct

1.1

P1 holds: the values of $\sigma$ are $\sigma(0) = 1$ , $\sigma(1) = 2$ , $\sigma(2) = 2$ , none of which is $0$ , so $\sigma(x) \neq 0$ for all $x$ .

givenL1

1.2

P3 holds: if $S \subseteq N$ with $0 \in S$ and $S$ closed under $\sigma$ , then $0 \in S$ forces $1 = \sigma(0) \in S$ , then $2 = \sigma(1) \in S$ , so $S = \{0, 1, 2\} = N$ ; thus induction holds.

givenL1

1.3

P2 fails: $\sigma(1) = 2 = \sigma(2)$ but $1 \neq 2$ , so $\sigma$ is not injective.

givenL1

2.1

So $(N, 0, \sigma)$ satisfies P1 and P3 but not P2, refuting the claim; note the failure permits the pathology $\sigma(2) = 2$ (a number that is its own successor) and a finite model in which distinct numerals collapse.

step 1.1step 1.2step 1.3∎

False statementConstruction: AI-adaptedVerification: AI-adaptedprecheck passverified 2026-08-02 (claude-opus-5)Open item page →

FALSE: successor-closure alone forces a set to be all of $\mathbb{N}$

Statement

False statement. If a set $S \subseteq \mathbb{N}$ is nonempty and closed under the successor ( $n \in S \Rightarrow \sigma(n) \in S$ ), then $S = \mathbb{N}$ . (That is, the induction principle would hold without its base case $0 \in S$ .)

Facts & Assumptions

Given: the claim above.

[L1]

The induction principle requires $0 \in S$ (The principle of mathematical induction).

[L2]

$\sigma(n) \neq 0$ for all $n$ (P1) (The von Neumann naturals form a Peano system).

Refutation

technique · direct

1.1

Take $S = \mathbb{N} \setminus \{0\} = \{n \in \mathbb{N} : n \neq 0\}$ , the set of nonzero naturals; it is nonempty (for instance $1 = \sigma(0) \in S$ ).

given

1.2

$S$ is closed under $\sigma$ : for any $n$ , $\sigma(n) \neq 0$ by P1 [L2], so $\sigma(n) \in S$ .

2.1

But $0 \notin S$ , so $S \neq \mathbb{N}$ ; the nonempty successor-closed set $S$ is not all of $\mathbb{N}$ , refuting the claim.

step 1.1step 1.2

3.1

The base case $0 \in S$ is therefore indispensable in the induction principle [L1]; successor-closure and nonemptiness do not suffice.

step 2.1L1∎

Sources

Standard references

Recommended treatments; not extraction sources.

Construction of the Natural Numbers

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

Peano system

Definition

Remarks

Inductive set

Definition

Remarks

The natural numbers exist: a smallest inductive set

Statement

Facts & Assumptions

Proof

The natural numbers N\mathbb{N}N (von Neumann)

Definition

Remarks

The principle of mathematical induction

Statement

Facts & Assumptions

Proof

Every natural number is a transitive set and is not a member of itself

Statement

Facts & Assumptions

Proof

The von Neumann naturals form a Peano system

Statement

Facts & Assumptions

Proof

The recursion theorem

Statement

Facts & Assumptions

Proof

Addition is a well-defined total operation

Statement

Facts & Assumptions

Proof

Addition of natural numbers

Definition

Remarks

Multiplication is a well-defined total operation

Statement

Facts & Assumptions

Proof

Multiplication of natural numbers

Definition

Remarks

No natural number equals its own successor

Statement

Facts & Assumptions

Proof

Every nonzero natural number is a successor

Statement

Facts & Assumptions

Proof

Left identity for addition

Statement

Facts & Assumptions

Proof

Left successor law for addition

Statement

Facts & Assumptions

Proof

Addition is associative

Statement

Facts & Assumptions

Proof

Addition is commutative

Statement

Facts & Assumptions

Proof

Addition is cancellative

Statement

Facts & Assumptions

Proof

Zero and one under multiplication

Statement

Facts & Assumptions

Proof

The natural numbers $\mathbb{N}$ (von Neumann)

Trichotomy of the order on $\mathbb{N}$

$\le$ is a linear order on $\mathbb{N}$

Discreteness: $\sigma(n)$ is the immediate successor

$1+1=2$ from the recursion

$2+2=4$ from the recursion