Skip to the passage panel
WikiLean · Articles Articles Brain Contribute About

Preliminary: these links have not yet had an independent audit.

Transfinite induction

19 passages11 formalized4 partial4 not formalized

Statement only

More ways to filter
Library
ATLAS related only
Passages
About this page

This page

  • Wikipedia revision 1355154855, pinned: the text here is that revision, not today's article.
  • WikiProject Mathematics: C-class, High importance
  • Annotated article on WikiLean.
  • 19 passages checked, 34 Lean locations (and 6 related declarations).

Central statements: 9 of the 19 passages state the article's subject or a named result or definition; the other 10 are supporting (examples, setup). Of these 9: 6 formalized, 3 partial.

What the colours mean

  • Formalized a Lean declaration states it, proved, or a Lean definition defines it
  • Statement only Lean states it, but the proof is not finished
  • Partial Lean states part of it, or a more general or special form
  • Not formalized searched every library and not found

Libraries searched

Searched 48 Lean libraries, pinned 2026-10-17, 3 left out (library set u1).

How these links were made

  • Accuracy, from an audit of a sample of 224 items (blind, not independent): Strong links (exact, close or broad match) on supporting passages that have exactly the right relation: 92% (95% interval 49–99%), from 36 drawn of 1029, weighted by relation and library, an effective sample of 5.1; Links in a counting relation (exact, close, broad, narrow match or part) on supporting passages that have exactly the right relation: 73% (95% interval 40–92%), from 48 drawn of 1740, weighted by relation and library, an effective sample of 8.1; Central and subject passages whose formalization status is right: 86% (95% interval 73–94%), from 44 drawn of 1905, weighted by recorded status, an effective sample of 42; 'Not formalized' on supporting passages that is right (no declaration in the 48 libraries states it): 60% (95% interval 25–87%), from 12 drawn of 1236, weighted by article, an effective sample of 6.1.
  • Audit run tierA-batch1-audit, run by jack, 2 Nov 2026, 21:10 – 3 Nov 2026, 02:10 UTC: judged by Claude Opus 5.5 (claude-opus-5-5).
  • Record set tierA-b1b (cf-locate-recordset/2, statuses by status rule 3), exported 1 Nov 2026 by formal-companion at commit d85385a.
  • Seal sha256 23710337d053e8212378a9e580805628bcdfda61a6fc431e65f24a4a16c9e602.
  • Inventory run inv-tierA-b1r, run by jack, 30 Oct 2026, 07:23–20:00 UTC: worker Claude Opus 5 (claude-opus-5), reviewer Claude Opus 5 (claude-opus-5). It listed the formal passages, each with its kind and prominence, that the locate run then searched.
  • Locate run loc-tierA-b1b, run by jack, 31 Oct 2026, 04:59 – 1 Nov 2026, 03:06 UTC: worker Claude Opus 5 (claude-opus-5), reviewer Claude Opus 5 (claude-opus-5).
  • Challenge run chal-tierA-b1, run by jack, 1 Nov 2026, 03:19–14:25 UTC: worker Claude Opus 5 (claude-opus-5), reviewer Claude Opus 5 (claude-opus-5). In this article it re-checked every Lean location on a central or subject passage (22 locations); on supporting passages, a seeded sample (seed 0; drawn at 0.5 for strong matches, 0.2 for weaker links and 0.25 for absences): 9 of 12 locations and 0 of 3 absences. In all, 31 of 34 Lean locations (91%) and 0 of 3 absences (0%) were re-checked.
  • Passage text: 19 of 19 passages shown in full, each the slice of the pinned revision's text that its record's span sha256 hashes, checked when the store was built.
  • Lean code: each declaration's type, from the declaration corpus of universe u1 (built 18 Oct 2026, sha256 a364fd6aede5), at the commit its card links.

How the text is shown

Each passage is shown in full, as revision 1355154855 states it (checked against its record's span hash when the store was built). Where a passage is only part of a sentence, it is highlighted and the rest of the sentence is shown in grey around it, from the same copy of the revision; a list item also shows the sentence that introduces it. Formulas are drawn from their TeX; hover one to see it.

Each card's Lean code is its declaration's type as Lean prints it, from the declaration corpus of library set u1 at the card's commit, laid out as a header: binders before the colon, then the hypotheses as arrows (the corpus keeps no hypothesis names) and the conclusion, in Mathlib's notation (𝓝, π, R[X], Type*). It is not the source text; Source opens that.

Select a highlighted passage to see where Lean formalizes it.

Representation of the ordinal numbers up to ω ω {\displaystyle \omega ^{\omega }} . Each turn of the spiral represents one power of ω {\displaystyle \omega } . Transfinite induction requires proving a base case (used for 0), a successor case (used for those ordinals which have a predecessor), and a limit case (used for nonzero ordinals which do not have a predecessor).

Transfinite induction is an extension of mathematical induction to ordinal numbers. Its correctness is a theorem of ZF, and relies on the fact that the ordinal numbers are well-ordered, and thus a statement that is not universally true for all ordinals must have a minimal counterexample. In fact, this principle is also true for arbitrary well-ordered sets, but since any well-ordered set can be indexed by ordinals in an order-preserving way, it suffices to establish the principle for ordinals.[1]

Overview

The principle of transfinite induction is as follows:

Let P ( α ) {\displaystyle P(\alpha )} be a property defined for all ordinals α {\displaystyle \alpha } . Suppose that whenever P ( β ) {\displaystyle P(\beta )} is true for all ⁠ β < α {\displaystyle \beta <\alpha } ⁠, then P ( α ) {\displaystyle P(\alpha )} is also true.[2] Then P {\displaystyle P} is true for all ordinals.

This principle can be easily proved by considering the contrapositive form:

If ⁠ P {\displaystyle P} ⁠ is not true for all ordinals, then there exists an ordinal ⁠ α {\displaystyle \alpha } ⁠ such that ⁠ P ( β ) {\displaystyle P(\beta )} ⁠ is true for all ⁠ β < α {\displaystyle \beta <\alpha } ⁠, but ⁠ P ( α ) {\displaystyle P(\alpha )} ⁠ is false.

Such an ⁠ α {\displaystyle \alpha } ⁠ is just a minimal counterexample, the existence of which is guaranteed by the fact the class of ordinal numbers is well-ordered.

Induction by cases

A proof by transfinite induction is often broken down into three cases:

  • Zero case: Prove that P ( 0 ) {\displaystyle P(0)} is true.
  • Successor case: Prove that for any successor ordinal α + 1 {\displaystyle \alpha +1} , P ( α + 1 ) {\displaystyle P(\alpha +1)} follows from P ( α ) {\displaystyle P(\alpha )} (and, if necessary, P ( β ) {\displaystyle P(\beta )} for all β < α {\displaystyle \beta <\alpha } ).
  • Limit case: Prove that for any limit ordinal λ {\displaystyle \lambda } , if P ( β ) {\displaystyle P(\beta )} holds for all β < λ {\displaystyle \beta <\lambda } , then P ( λ ) {\displaystyle P(\lambda )} .

All three cases are identical except for the type of ordinal considered. They do not formally need to be considered separately, but in practice the proofs are typically so different as to require separate presentations. Zero is sometimes considered a limit ordinal and then may sometimes be treated in proofs in the same case as limit ordinals.

Transfinite recursion

Transfinite recursion is similar to transfinite induction; however, instead of proving that something holds for all ordinal numbers, we construct a sequence of objects, one for each ordinal.

As an example, a basis for a (possibly infinite-dimensional) vector space can be created by starting with the empty set and for each ordinal α > 0 choosing a vector that is not in the span of the vectors { v β ∣ β < α } {\displaystyle \{v_{\beta }\mid \beta <\alpha \}} . This process stops when no vector can be chosen.

More formally, we can state the Transfinite Recursion Theorem as follows:

Transfinite Recursion Theorem (version 1). Given a class function[3] G: V → V (where V is the class of all sets), there exists a unique transfinite sequence F: Ord → V (where Ord is the class of all ordinals) such that

F ( α ) = G ( F ↾ α ) {\displaystyle F(\alpha )=G(F\upharpoonright \alpha )} for all ordinals α, where ↾ {\displaystyle \upharpoonright } denotes the restriction of F's domain to ordinals < α.

As in the case of induction, we may treat different types of ordinals separately: another formulation of transfinite recursion is the following:

Transfinite Recursion Theorem (version 2). Given a set g1, and class functions G2, G3, there exists a unique function F: Ord → V such that

  • F(0) = g1,
  • F(α + 1) = G2(F(α)), for all α ∈ Ord,
  • F ( λ ) = G 3 ( F ↾ λ ) {\displaystyle F(\lambda )=G_{3}(F\upharpoonright \lambda )} , for all limit λ ≠ 0.

Note that we require the domains of G2, G3 to be broad enough to make the above properties meaningful. The uniqueness of the sequence satisfying these properties can be proved using transfinite induction.

More generally, one can define objects by transfinite recursion on any well-founded relation R. (R need not even be a set; it can be a proper class, provided it is a set-like relation; i.e. for any x, the collection of all y such that yRx is a set.)

Relationship to the axiom of choice

Proofs or constructions using induction and recursion often use the axiom of choice to produce a well-ordered relation that can be treated by transfinite induction. However, if the relation in question is already well-ordered, one can often use transfinite induction without invoking the axiom of choice.[4] For example, many results about Borel sets are proved by transfinite induction on the ordinal rank of the set; these ranks are already well-ordered, so the axiom of choice is not needed to well-order them.

The following construction of the Vitali set shows one way that the axiom of choice can be used in a proof by transfinite induction:

First, well-order the real numbers (this is where the axiom of choice enters via the well-ordering theorem), giving a sequence ⟨ r α ∣ α < β ⟩ {\displaystyle \langle r_{\alpha }\mid \alpha <\beta \rangle } , where β is an ordinal with the cardinality of the continuum. Let v0 equal r0. Then let v1 equal rα1, where α1 is least such that rα1 − v0 is not a rational number. Continue; at each step use the least real from the r sequence that does not have a rational difference with any element thus far constructed in the v sequence. Continue until all the reals in the r sequence are exhausted. The final v sequence will enumerate the Vitali set.

The above argument uses the axiom of choice in an essential way at the very beginning, in order to well-order the reals. After that step, the axiom of choice is not used again.

Other uses of the axiom of choice are more subtle. For example, a construction by transfinite recursion frequently will not specify a unique value for Aα+1, given the sequence up to α, but will specify only a condition that Aα+1 must satisfy, and argue that there is at least one set satisfying this condition. If it is not possible to define a unique example of such a set at each stage, then it may be necessary to invoke (some form of) the axiom of choice to select one such at each step. For inductions and recursions of countable length, the weaker axiom of dependent choice is sufficient. Because there are models of Zermelo–Fraenkel set theory of interest to set theorists that satisfy the axiom of dependent choice but not the full axiom of choice, the knowledge that a particular proof only requires dependent choice can be useful.

See also

Notes

  1. ^ J. Schlöder, Ordinal Arithmetic. Accessed 2022-03-24.
  2. ^ It is not necessary here to assume separately that P ( 0 ) {\displaystyle P(0)} is true. As there is no β {\displaystyle \beta } less than 0, it is vacuously true that for all β < 0 {\displaystyle \beta <0} , P ( β ) {\displaystyle P(\beta )} is true.
  3. ^ A class function is a rule (specifically, a logical formula) assigning each element in the lefthand class to an element in the righthand class. It is not a function because its domain and codomain are not sets.
  4. ^ In fact, the domain of the relation does not even need to be a set. It can be a proper class, provided that the relation R is set-like: for any x, the collection of all y such that y R x must be a set.

References

  • Suppes, Patrick (1972), "Section 7.1", Axiomatic set theory, Dover Publications, ISBN 0-486-61630-4