TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (z-ai/glm-5.2)verified 2026-07-26 (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.

Transfinite induction

Statement

Let $(W, <)$ be a well-order (Well-order and well-ordered set) and let $S \subseteq W$ satisfy the following: for every $a \in W$ , if $W_{< a} \subseteq S$ then $a \in S$ (Initial segment of a well-order). Then $S = W$ .

In property form: if a property $P$ of elements of $W$ satisfies "whenever $P (x)$ holds for every $x < a$ , it holds at $a$ ", then $P (a)$ holds for every $a \in W$ .

This is a theorem of ZF. No form of the Axiom of Choice is used. Choice is perfectly available at this point in the library, since Zorn's lemma is proved from it on the previous page; the claim made here is about this proof, which never invokes it.

Facts & Assumptions

Given: A well-order $(W, <)$ and a subset $S \subseteq W$ with the stated closure property. No base case is assumed separately: the hypothesis applied to the least element of $W$ , where the initial segment below it is empty, supplies it.

[A1]

For every $a \in W$ : if $W_{< a} \subseteq S$ then $a \in S$ .

[L1]

Every nonempty subset of $W$ has a least element, and the order is total (Well-order and well-ordered set).

[L2]

$W_{< a} = {x \in W : x < a}$ (Initial segment of a well-order).

Proof

technique · contradiction

1.1assume-contra

Suppose, for contradiction, that $S \neq W$ .

2.1step 1.1

Since $S \subseteq W$ , the set $C = W ∖ S$ is then nonempty.

3.1step 2.1L1choose

Let $a = \min C$ , the least element of $C$ in the order of $W$ , which exists because $C$ is a nonempty subset of $W$ .

4.1step 3.1L2

Every $x \in W$ with $x < a$ satisfies $x \notin C$ , by minimality of $a$ , hence $x \in S$ ; that is, $W_{< a} \subseteq S$ .

5.1step 4.1A1

The hypothesis on $S$ therefore applies at $a$ and gives $a \in S$ .

6.1step 5.1step 3.1discharge-contradiction∎

But $a \in C = W ∖ S$ gives $a \notin S$ , which is impossible; hence $W ∖ S$ is empty and $S = W$ .

Remarks

Where the well-ordering is used. Only once, to produce the least element of $W ∖ S$ . Nothing else about $W$ enters the argument, so the same proof establishes the statement for an arbitrary well-founded relation once that notion is available.

No separate base case. Applying the hypothesis at $a = \min W$ , when $W$ is nonempty, forces $\min W \in S$ , because the initial segment below $\min W$ is empty and is therefore contained in $S$ vacuously. This is why transfinite induction is stated with a single clause where ordinary induction has two, and it is also why the statement holds vacuously for $W = \emptyset$ .

Successors and limits. The scheme that looks stronger, with one clause for the least element, one for successors and one for limits, is the specialisation of this theorem to a well-order in which those three kinds of element are distinguished. Nothing is gained by assuming it separately, and the three-clause form is what gets used once ordinals are available.

Least counterexample. The dual reading is often the useful one: if $S \neq W$ then the hypothesis must fail somewhere, so there is a least $a$ with $a \notin S$ and every $x < a$ in $S$ . Steps 2.1 to 5.1 are precisely the construction of that least counterexample.

Transfinite induction

Statement

Facts & Assumptions

Proof

Remarks

Depends on

Dependency tree · 2 levels

Sources