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 · 15 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 18 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 $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 $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 $N$ abstractly as a triple $(N, 0, σ)$ 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 $ω$ of von Neumann naturals (The natural numbers $N$ (von Neumann)), where $0 = \emptyset$ and $σ (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 $ω$ 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 $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 \leq n ⟺ \exists k (m + k = n)$ (Order on the natural numbers) is a linear order ( $\leq$ is a linear order on $N$ ) satisfying trichotomy (Trichotomy of the order on $N$ ), compatible with addition and multiplication (Order is compatible with addition, Order is compatible with multiplication) and discrete in that $σ (n)$ is the immediate successor of $n$ (Discreteness: $σ (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 $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 $N$ (FALSE: successor-closure alone forces a set to be all of $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, σ)$ consisting of a set $N$ , a distinguished element $0 \in N$ , and a successor function $σ : 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$ , $σ (n) \neq 0$ .
(P2) Successor is injective. For all $m, n \in N$ , if $σ (m) = σ (n)$ then $m = n$ .
(P3) Induction. For every subset $S \subseteq N$ (Subset $x \subseteq y$ , proper subset $x ⊊ y$ , and the separation notation ${z \in x : φ (z)}$ ), if $0 \in S$ and $σ (n) \in S$ whenever $n \in S$ , then $S = N$ .

The elements of $N$ are the natural numbers of the system. We abbreviate $1 : = σ (0)$ , $2 : = σ (1)$ , $3 : = σ (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 $σ$ , 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 $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 $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 = \emptyset$ .

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 \lor t = y))$ and The Axiom of Union: $\forall x \exists y \forall z (z \in y \leftrightarrow \exists s (s \in x \land z \in s))$ ). A set $I$ is inductive when

$\emptyset \in I and (x \in I ⟹ x^{+} \in I) 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 {anything}$ once closed off), so an inductive set is not yet a good definition of $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 $N$ (von Neumann)); minimality is what delivers the induction principle.

Here $0 : = \emptyset$ and the successor of $n$ is $σ (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 $ω$ that is inductive (Inductive set) and is a subset of every inductive set; it is unique. This $ω$ 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 $φ$ , $\forall \overset{ˉ}{p} \forall x \exists y \forall z (z \in y \leftrightarrow (z \in x \land φ (z, \overset{ˉ}{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 $\emptyset \in I$ and ( $x \in I \Rightarrow x^{+} \in I$ ).

Proof

technique · direct

1.1given

By the Axiom of Infinity fix an inductive set $I_{0}$ .

1.2givenconstruct

By Separation the collection $ω : = {x \in I_{0} : x \in J for every inductive set J}$ is a set.

2.1step 1.2

$ω$ is inductive: $\emptyset \in J$ for every inductive $J$ (so $\emptyset \in I_{0}$ and $\emptyset \in ω$ ), and if $x \in ω$ 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 ω$ .

2.2step 1.2

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

3.1step 2.1step 2.2∎

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

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

The natural numbers $N$ (von Neumann)

Definition

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

$N = ω : = ⋂ {I : I 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 $φ$ , $\forall \overset{ˉ}{p} \forall x \exists y \forall z (z \in y \leftrightarrow (z \in x \land φ (z, \overset{ˉ}{p})))$ , makes the intersection a set). On $N$ we take

$0 : = \emptyset, σ (n) : = n \cup {n},$

the distinguished element and the successor function. Thus $0 = \emptyset$ , $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 $ω \subseteq I$ for every inductive set $I$ . This minimality is exactly the induction principle (The principle of mathematical induction): a subset of $N$ that contains $0$ and is closed under $σ$ is itself inductive, hence contains $ω = N$ , hence equals $N$ .

With $0$ and $σ$ so defined, $(N, 0, σ)$ 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 N$ . If $0 \in S$ and $σ (n) \in S$ whenever $n \in S$ , then $S = N$ . Equivalently (property form): if a property $P$ satisfies $P (0)$ and ( $P (n) \Rightarrow P (σ (n))$ ) for all $n$ , then $P (n)$ holds for all $n \in N$ . This is the induction principle, the basis of proof by induction.

Facts & Assumptions

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

[L1]

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

Proof

technique · direct

1.1given

Suppose $S \subseteq N$ with $0 = \emptyset \in S$ and ( $x \in S \Rightarrow σ (x) = x \cup {x} \in S$ ).

2.1step 1.1

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

3.1L1step 2.1

$N = ω \subseteq S$ because $ω$ is a subset of every inductive set.

4.1step 3.1given

With $S \subseteq N$ by hypothesis, $S = N$ .

5.1step 4.1∎

The property form is the set case with $S = {n \in N : P (n)}$ : $P (0)$ and $P (n) \Rightarrow P (σ (n))$ give $0 \in S$ and $σ$ -closure, so $S = 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.

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 N$ : (a) $n$ is transitive, i.e. $x \in n \Rightarrow x \subseteq n$ ; and (b) $n \notin n$ .

Facts & Assumptions

Given: $N$ (The natural numbers $N$ (von Neumann)) with $0 = \emptyset$ , $σ (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 (σ (n))$ , then $P$ holds for all $n$ (The principle of mathematical induction).

Proof

technique · induction

1.1base

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

1.2ih

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

2.1step 1.2

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

2.2step 1.2

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

3.1step 2.1step 2.2discharge-induction∎

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

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 $(N, 0, σ) = (ω, \emptyset, \cdot^{+})$ satisfies the three Peano axioms (Peano system): (P1) $σ (n) \neq 0$ for all $n$ ; (P2) $σ$ is injective; (P3) induction. Hence a Peano system exists.

Facts & Assumptions

Given: $N = ω$ , $0 = \emptyset$ , $σ (n) = n \cup {n}$ (The natural numbers $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.1L1

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

1.2given

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

1.3L2given

(P2) Suppose $σ (m) = σ (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 $σ$ is injective.

2.1step 1.1step 1.2step 1.3∎

P1, P2, P3 all hold, so $(N, 0, σ)$ is a Peano system; in particular a Peano system exists.

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passverified 2026-09-23 (gpt-6-sol)Open item page →

The recursion theorem

Statement

Let $(N, 0, σ)$ be a Peano system (Peano system), in particular the natural numbers $N$ (The natural numbers $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 (σ (n)) = f (g (n))$ for all $n \in N$ .

Facts & Assumptions

Given: a Peano system $(N, 0, σ)$ , 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 $(σ (n), f (x)) \in R$ .

[L1]

Induction holds in every Peano system $N$ : any $S \subseteq N$ with $0 \in S$ that is closed under $σ$ equals $N$ (axiom P3 in Peano system).

[L2]

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

Proof

technique · direct

1.1givenconstruct

The set $N \times A$ is closed, so the collection of closed subsets of $N \times A$ is nonempty; let $g : = ⋂ {R : R \subseteq N \times A 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 $(σ (n), f (x)) \in R$ for each such $R$ , so $(σ (n), f (x)) \in g$ .

2.1L1step 1.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 $(σ (n), f (x)) \in g$ by closure, so $σ (n) \in D$ ; by induction $D = N$ , hence $g$ relates every $n$ to at least one $x$ .

2.2L2step 1.1

Suppose $(0, b) \in g$ with $b \neq a$ ; then $g ∖ {(0, b)}$ still contains $(0, a)$ and is closed, since any generated pair $(σ (m), f (z))$ has $σ (m) \neq 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$ .

3.1step 2.2

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

4.1L2step 3.1step 1.1

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

5.1L1step 2.1step 3.1step 4.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 (σ (n)) = f (g (n))$ for all $n$ .

6.1L1step 5.1∎

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

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 N$ there is a unique function $s_{m} : N \to N$ with $s_{m} (0) = m$ and $s_{m} (σ (n)) = σ (s_{m} (n))$ . Writing $m + n : = s_{m} (n)$ , addition $+ : N \times N \to N$ is a well-defined total binary operation satisfying $m + 0 = m$ and $m + σ (n) = σ (m + n)$ .

Facts & Assumptions

Given: the natural numbers $N$ with successor $σ$ .

[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 : N \to A$ with $g (0) = a$ and $g (σ (n)) = f (g (n))$ (The recursion theorem).

[L2]

$(N, 0, σ)$ is a Peano system (The von Neumann naturals form a Peano system).

Proof

technique · direct

1.1L1L2

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

2.1step 1.1

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

3.1step 1.1step 2.1∎

The recursion equations become $m + 0 = s_{m} (0) = m$ and $m + σ (n) = s_{m} (σ (n)) = σ (s_{m} (n)) = σ (m + n)$ , the defining clauses of addition.

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

Addition of natural numbers

Definition

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

$m + 0 = m, m + σ (n) = σ (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 + σ (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 + σ (n) = σ (m + n)$ with $n = 0$ gives $m + 1 = m + σ (0) = σ (m + 0) = σ (m)$ , so $σ (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 N$ there is a unique function $p_{m} : N \to N$ with $p_{m} (0) = 0$ and $p_{m} (σ (n)) = p_{m} (n) + m$ . Writing $m \cdot n : = p_{m} (n)$ , multiplication $\cdot : N \times N \to N$ is a well-defined total binary operation satisfying $m \cdot 0 = 0$ and $m \cdot σ (n) = m \cdot n + m$ .

Facts & Assumptions

Given: $N$ with successor $σ$ and addition $+$ (Addition of natural numbers).

[L1]

The recursion theorem (The recursion theorem).

[L2]

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

[L3]

$(N, 0, σ)$ is a Peano system (The von Neumann naturals form a Peano system).

Proof

technique · direct

1.1L2

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

2.1L1L3step 1.1

Since $(N, 0, σ)$ is a Peano system [L3], apply the recursion theorem with $A = N$ , $a = 0$ , $f = {a d d}_{m}$ : there is a unique $p_{m} : N \to N$ with $p_{m} (0) = 0$ and $p_{m} (σ (n)) = {a d d}_{m} (p_{m} (n)) = p_{m} (n) + m$ .

3.1step 2.1∎

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

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

Multiplication of natural numbers

Definition

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

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

We write $m n$ 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 σ (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 $(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 N$ , $n \neq σ (n)$ .

Facts & Assumptions

Given: $N$ with distinguished element $0$ and successor $σ$ .

[L1]

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

[L2]

The induction principle (The principle of mathematical induction).

Proof

technique · induction

1.1baseL1

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

1.2ih

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

2.1step 1.2L1

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

3.1step 1.1step 2.1discharge-induction∎

By induction [L2], $n \neq σ (n)$ for all $n \in N$ .

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 N$ with $n \neq 0$ , there exists $m \in N$ with $n = σ (m)$ . Equivalently, every natural number is either $0$ or a successor.

Facts & Assumptions

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

[L1]

The induction principle (The principle of mathematical induction).

Proof

technique · induction

1.1base

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

1.2ih

Inductive hypothesis: $n \in S$ .

2.1step 1.2

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

3.1step 1.1step 2.1discharge-induction∎

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

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 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 + σ (n) = σ (m + n)$ (Addition of natural numbers).

[L1]

Induction principle (The principle of mathematical induction).

Proof

technique · induction

1.1base

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

1.2ih

Inductive hypothesis: $0 + n = n$ .

2.1step 1.2given

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

3.1step 1.1step 2.1discharge-induction∎

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

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 N$ : $σ (m) + n = σ (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 + σ (k) = σ (m + k)$ (Addition of natural numbers).

[L1]

Induction principle (The principle of mathematical induction).

Proof

technique · induction

1.1base

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

1.2ih

Inductive hypothesis: $σ (m) + n = σ (m + n)$ .

2.1step 1.2given

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

3.1step 1.1step 2.1discharge-induction∎

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

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 N$ : $(a + b) + c = a + (b + c)$ .

Facts & Assumptions

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

[L1]

Induction principle (The principle of mathematical induction).

Proof

technique · induction

1.1base

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

1.2ih

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

2.1step 1.2

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

3.1step 1.1step 2.1discharge-induction∎

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

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 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: $σ (a) + k = σ (a + k)$ for all $a, k$ (Left successor law for addition).

[L3]

Induction principle (The principle of mathematical induction).

Proof

technique · induction

1.1baseL1

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

1.2ih

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

2.1step 1.2givenL2

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

3.1step 1.1step 2.1discharge-induction∎

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

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 N$ : if $m + k = n + k$ then $m = n$ .

Facts & Assumptions

Given: Addition (Addition of natural numbers).

[L1]

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

[L2]

Induction principle (The principle of mathematical induction).

Proof

technique · induction

1.1base

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

1.2ih

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

2.1step 1.2L1

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

3.1step 1.1step 2.1discharge-induction∎

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

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 N$ : $0 \cdot n = 0$ , $1 \cdot n = n$ , and $n \cdot 1 = n$ . Here $1 = σ (0)$ , and the clause $n \cdot 0 = 0$ is definitional.

Facts & Assumptions

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

[L1]

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

[L2]

The induction principle (The principle of mathematical induction).

Proof

technique · induction on $n$

1.1givenL1

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

1.2base

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

1.3ih

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

2.1step 1.3givenL1

Step: $0 \cdot σ (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 σ (n) = 1 \cdot n + 1 = n + 1 = σ (n)$ , where $n + 1 = n + σ (0) = σ (n + 0) = σ (n)$ by the addition recursion $m + σ (k) = σ (m + k)$ and $n + 0 = n$ .

3.1step 1.1step 2.1discharge-induction∎

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$ .

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 N$ : (left distributivity) $a \cdot (b + c) = a \cdot b + a \cdot c$ ; and (successor-left law) $σ (a) \cdot n = a \cdot n + n$ .

Facts & Assumptions

Given: multiplication $m \cdot 0 = 0$ , $m \cdot σ (n) = m \cdot n + m$ and addition $m + 0 = m$ , $m + σ (k) = σ (m + k)$ (Multiplication of natural numbers, Addition of natural numbers); in particular the addition recursion $a + σ (k) = σ (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.1base

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$ .

1.2ih

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

1.3L1given

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

2.1step 1.2L1

Step: $a \cdot (b + σ (c)) = a \cdot σ (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 σ (c)$ , using $b + σ (c) = σ (b + c)$ , the multiplication recursion, the hypothesis, associativity [L1], and $a \cdot σ (c) = a \cdot c + a$ .

3.1step 2.1step 1.3discharge-induction∎

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

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 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.1base

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.

1.2ih

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

2.1step 1.2L1

Step: $(a \cdot b) \cdot σ (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 σ (c))$ , using the multiplication recursion, the hypothesis, left distributivity [L1], and $b \cdot σ (c) = b \cdot c + b$ .

3.1step 1.1step 2.1discharge-induction∎

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

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 N$ : $m \cdot n = n \cdot m$ .

Facts & Assumptions

Given: multiplication (Multiplication of natural numbers).

[L1]

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

[L2]

The successor-left law $σ (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.1baseL1

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

1.2ih

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

2.1step 1.2L2

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

3.1step 1.1step 2.1discharge-induction∎

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

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 N$ : if $m \cdot n = 0$ then $m = 0$ or $n = 0$ . Equivalently, if $m \neq 0$ and $n \neq 0$ then $m \cdot n \neq 0$ .

Facts & Assumptions

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

[L1]

Every nonzero natural is a successor: if $x \neq 0$ then $x = σ (a)$ for some $a \in N$ (Every nonzero natural number is a successor).

[L2]

$σ (j) \neq 0$ for all $j \in N$ (Peano axiom P1) (The von Neumann naturals form a Peano system).

Proof

technique · contrapositive

1.1contrapositive-reduce

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

1.2assume-hyp

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

2.1L1step 1.2

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

3.1step 2.1given

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

4.1step 3.1L2discharge-contrapositive∎

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

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

Order on the natural numbers

Definition

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

$m \leq n ⟺ \exists k \in N (m + k = n),$

and the strict order by $m < n ⟺ (m \leq n and m \neq n)$ , using addition (Addition of natural numbers).

Remarks

Read $m \leq 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 $\leq$ is genuinely a linear order, reflexive, antisymmetric, transitive, and total, is proved in $\leq$ is a linear order on $N$ and Trichotomy of the order on $N$ ; compatibility with the arithmetic (Order is compatible with addition, Order is compatible with multiplication) and discreteness ( $m < n ⟺ σ (m) \leq n$ , Discreteness: $σ (n)$ is the immediate successor) follow.

In the von Neumann model this order coincides with membership and inclusion: $m \leq n ⟺ m \subseteq n$ and $m < n ⟺ m \in n$ , matching the picture of each natural number as the set ${0, 1, \dots, n - 1}$ of its predecessors (The natural numbers $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 passverified 2026-09-23 (gpt-6-sol)Open item page →

Trichotomy of the order on $N$

Statement

For all $m, n \in 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 $N$ , where $m \leq n$ means $\exists k (m + k = n)$ and $m < n$ means $m \leq n$ with $m \neq n$ (Order on the natural numbers), and addition with $m + 0 = m$ , $m + σ (n) = σ (m + n)$ (Addition of natural numbers).

[L1]

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

[L2]

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

[L3]

Addition is associative (Addition is associative).

[L4]

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

[L5]

$σ (x) \neq 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.1given

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

1.2givenL2L3L4L5L6L7

The two strict relations are incompatible: if $m < n$ and $m > n$ then $m + j = n$ and $n + i = m$ with $i, j \neq 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 = σ (a)$ [L4] gives, by the left successor law [L2], $j + i = σ (a) + i = σ (a + i) \neq 0$ [L5], a contradiction.

1.3givenL1L5L6L7

For any $x$ and nonzero $t$ , one has $x + t \neq x$ : otherwise commutativity [L7] and $0 + x = x$ [L1] give $t + x = 0 + x$ , so cancellation [L6] gives $t = 0$ . Thus $x < x + t$ by the order definition. In particular $n + σ (0) = σ (n)$ by the recursion, and $σ (0) \neq 0$ [L5], so $n < σ (n)$ .

1.4baseL1L4

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

1.5ih

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

2.1step 1.3step 1.5givenL2L4L5

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

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

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.

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

$\leq$ is a linear order on $N$

Statement

The relation $\leq$ on $N$ , where $m \leq n ⟺ \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 \leq n ⟺ \exists k (m + k = n)$ (Order on the natural numbers) and addition with $m + 0 = m$ , $m + σ (n) = σ (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 \neq 0$ then $j = σ (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 $N$ ).

[L5]

Addition is commutative (Addition is commutative).

[L6]

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

Proof

technique · direct

1.1given

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

1.2givenL1

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

1.3L1L3L6

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

1.4L4

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

2.1givenL1L2L5step 1.3

Antisymmetric: if $m \leq n$ and $n \leq 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$ .

3.1step 1.1step 1.2step 2.1step 1.4∎

Reflexivity, antisymmetry, transitivity, and totality all hold, so $\leq$ is a linear order on $N$ .

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 N$ : $m \leq n ⟺ m + k \leq n + k$ ; and $m < n ⟺ m + k < n + k$ (Order on the natural numbers).

Facts & Assumptions

Given: The order $m \leq n ⟺ \exists j (m + j = n)$ (Order on the natural numbers) and addition with $m + 0 = m$ , $m + σ (n) = σ (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.1givenL1

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

1.2givenL1L2

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

2.1step 1.1step 1.2L2∎

The strict forms follow: $m < n$ means $m \leq n$ and $m \neq n$ , while $m + k = n + k ⟺ m = n$ by cancellation, so $m < n ⟺ m + k < n + k$ .

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 N$ : if $m \leq n$ then $m \cdot k \leq n \cdot k$ ; and if in addition $k \neq 0$ and $m < n$ , then $m \cdot k < n \cdot k$ (Order on the natural numbers).

Facts & Assumptions

Given: The order $m \leq n ⟺ \exists d (m + d = n)$ , with $m < n$ meaning $m \leq n$ and $m \neq n$ (Order on the natural numbers); addition with $m + 0 = m$ (Addition of natural numbers); and multiplication with $m \cdot 0 = 0$ , $m \cdot σ (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 \neq 0$ and $k \neq 0 \Rightarrow d \cdot k \neq 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.1givenL1

If $m \leq 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 \leq n \cdot k$ .

2.1step 1.1givenL2L3L4∎

If moreover $m < n$ then $d \neq 0$ , for $d = 0$ would give $n = m + 0 = m$ , contradicting $m \neq n$ ; then with $k \neq 0$ we get $d \cdot k \neq 0$ by [L2], so $m \cdot k + d \cdot k = n \cdot k$ with $d \cdot k \neq 0$ ; and $m \cdot k \neq 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$ .

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

Discreteness: $σ (n)$ is the immediate successor

Statement

For all $m, n \in N$ : $m < n ⟺ σ (m) \leq n$ (Order on the natural numbers). Consequently there is no $k$ with $n < k < σ (n)$ : the successor $σ (n)$ is the immediate successor of $n$ .

Facts & Assumptions

Given: The order $m \leq n ⟺ \exists j (m + j = n)$ , with $m < n$ meaning $m \leq n$ and $m \neq n$ (Order on the natural numbers), and addition with $m + 0 = m$ , $m + σ (n) = σ (m + n)$ (Addition of natural numbers).

[L1]

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

[L2]

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

[L3]

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

[L4]

$σ (x) \neq 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.1givenL1L2

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

1.2givenL2L3L4L5

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

2.1step 1.1step 1.2∎

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

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 N$ with $k \neq 0$ : if $m \cdot k = n \cdot k$ then $m = n$ .

Facts & Assumptions

Given: multiplication defined by $m \cdot 0 = 0$ and $m \cdot σ (j) = m \cdot j + m$ ; the order $m \leq n ⟺ \exists j (m + j = n)$ , with $m < n$ meaning $m \leq n$ and $m \neq n$ .

[L1]

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

[L2]

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

Proof

technique · contradiction

1.1assume-contra

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

2.1step 1.1L1

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

3.1step 2.1L2

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

4.1step 1.1step 3.1discharge-contradiction∎

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

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 N$ has a least element: there is $ℓ \in S$ with $ℓ \leq s$ for all $s \in S$ .

Facts & Assumptions

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

[L1]

Induction principle: a subset of $N$ that contains $0$ and is closed under $σ$ equals $N$ (The principle of mathematical induction).

[L2]

$m < n ⟺ σ (m) \leq n$ ; consequently no $k$ satisfies $n < k < σ (n)$ (Discreteness: $σ (n)$ is the immediate successor).

[L3]

Exactly one of $s < n$ , $s = n$ , $n < s$ holds (Trichotomy of the order on $N$ ); and $n < s ⟺ σ (n) \leq s$ (Discreteness: $σ (n)$ is the immediate successor).

[L4]

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

[L5]

$σ (a) + i = σ (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.1assume-contra

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

1.2L2L4L5

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

2.1step 1.1L3L6given

First, $0 \in T$ : if $0 \in S$ then $0 \leq 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 \leq 0$ forces $m = 0$ , because $m \neq 0$ would give $0 < m$ (as $0 + m = m$ [L6] with $m \neq 0$ ) while $m \leq 0$ gives $m < 0$ , and [L3] admits at most one of these; so every $m \leq 0$ lies outside $S$ .

2.2step 1.1step 1.2L3

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

3.1step 2.1step 2.2L1discharge-contradiction∎

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

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 N$ , if $P (m)$ holds for all $m < n$ then $P (n)$ . Then $P (n)$ holds for all $n \in 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$ , $(P (m) for all m < n) \Rightarrow P (n)$ .

[L1]

Well-ordering: every nonempty subset of $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 $N$ ).

Proof

technique · contradiction

1.1assume-contra

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

2.1step 1.1L1L2

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

3.1step 2.1given

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

4.1step 2.1step 3.1discharge-contradiction∎

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

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, σ)$ and $(N^{'}, 0^{'}, σ^{'})$ be Peano systems (Peano system). There is a unique bijection $h : N \to N^{'}$ with $h (0) = 0^{'}$ and $h (σ (n)) = σ^{'} (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, σ)$ and $(N^{'}, 0^{'}, σ^{'})$ .

[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 (σ (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.1L1

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

1.2L1

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

2.1step 1.1step 1.2L2

The composite $h^{'} \circ h : N \to N$ satisfies $(h^{'} \circ h) (0) = h^{'} (0^{'}) = 0$ and $(h^{'} \circ h) (σ (n)) = h^{'} (σ^{'} (h (n))) = σ (h^{'} (h (n))) = σ ((h^{'} \circ h) (n))$ ; the identity ${i d}_{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 = {i d}_{N}$ .

2.2step 1.1step 1.2L2

Likewise $h \circ h^{'} = {i d}_{N^{'}}$ by the same argument carried out in $N^{'}$ .

3.1step 2.1step 2.2

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.

4.1step 1.1L1L2∎

Uniqueness: any $h_{1} : N \to N^{'}$ with $h_{1} (0) = 0^{'}$ and $h_{1} (σ (n)) = σ^{'} (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 $σ$ , hence is all of $N$ by induction [L2]).

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 = σ (0)$ and $2 = σ (1) = σ (σ (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 + σ (n) = σ (m + n)$ (Addition of natural numbers); numerals $1 = σ (0)$ , $2 = σ (1)$ (The natural numbers $N$ (von Neumann)).

Verification

technique · direct

1.1given

By definition $1 = σ (0)$ and $2 = σ (1) = σ (σ (0))$ .

1.2given

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

2.1step 1.1given

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

3.1step 2.1step 1.2∎

Hence $1 + 1 = σ (1 + 0) = σ (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 = σ (σ (0))$ and $4 = σ (σ (σ (σ (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 + σ (n) = σ (m + n)$ (Addition of natural numbers); $2 = σ (σ (0))$ , $4 = σ (σ (σ (σ (0))))$ (The natural numbers $N$ (von Neumann)).

Verification

technique · direct

1.1given

Write $2 = σ (σ (0))$ ; then $2 + 2 = 2 + σ (σ (0))$ .

1.2given

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

2.1step 1.1given

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

3.1step 2.1step 1.2∎

Hence $2 + 2 = σ (σ (2)) = σ (σ (σ (σ (0)))) = 4$ .

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, σ)$ satisfying (P1) $0$ is not a successor and (P2) $σ$ is injective automatically satisfies (P3) induction. The witness is $N = N ⊔ Z$ (a disjoint union of a copy of the naturals and a copy of the integers), with base point $0$ the zero of the $N$ -copy and $σ$ the usual successor $n \mapsto n + 1$ on each copy separately.

Facts & Assumptions

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

[L1]

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

[L2]

$N$ itself is the standard model (The natural numbers $N$ (von Neumann)).

Counterexample

technique · direct

1.1givenL1

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

1.2givenL1

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

1.3givenL1L2

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

2.1step 1.3

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

3.1step 1.1step 1.2step 1.3step 2.1∎

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

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 $σ$ follows from (P1) $0$ is not a successor together with (P3) induction. The witness is the three-element system $N = {0, 1, 2}$ with $σ (0) = 1$ , $σ (1) = 2$ , $σ (2) = 2$ .

Facts & Assumptions

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

[L1]

The Peano axioms (Peano system).

Counterexample

technique · direct

1.1givenL1

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

1.2givenL1

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

1.3givenL1

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

2.1step 1.1step 1.2step 1.3∎

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

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 $N$

Statement

False statement. If a set $S \subseteq N$ is nonempty and closed under the successor ( $n \in S \Rightarrow σ (n) \in S$ ), then $S = 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]

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

Refutation

technique · direct

1.1given

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

1.2L2

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

2.1step 1.1step 1.2

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

3.1step 2.1L1∎

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

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 NN (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 $N$ (von Neumann)

Trichotomy of the order on $N$

$\leq$ is a linear order on $N$

Discreteness: $σ (n)$ is the immediate successor

$1 + 1 = 2$ from the recursion

$2 + 2 = 4$ from the recursion