TheoremStatement: AI-adaptedProof: 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.

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

Strong (complete) induction

Statement

Facts & Assumptions

Proof

Depends on

Dependency tree · 2 levels

Sources