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

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.

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.

The principle of mathematical induction

Statement

Facts & Assumptions

Proof

Depends on

Dependency tree · 2 levels

Sources