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 recursion
Statement
Let be a well-order (Well-order and well-ordered set) and let be a class function: a rule, given by a formula in the language of set theory, that assigns a set to every function whose domain is a proper initial segment of (Initial segment of a well-order). Then there is exactly one function with domain such that
Here is the restriction of to the initial segment determined by , so the value of at is prescribed in terms of all its earlier values at once.
Because is a class function rather than a set, this is a theorem schema of ZF: one theorem for each formula defining . It uses Replacement, and it uses no form of the Axiom of Choice.
Facts & Assumptions
Given: A well-order , a class function as in the statement, and the axioms of ZF. Call a function an attempt when is an initial segment of and for every . The empty function is an attempt, with domain the initial segment .
is a well-determined set for every function whose domain is a proper initial segment of .
The axioms of ZF are available, in particular Separation, Union and Replacement. No choice principle is assumed.
Transfinite induction on : if implies for every , then (Transfinite induction).
and are initial segments, an intersection of initial segments is an initial segment, and for (Initial segment of a well-order).
The order of is total and every nonempty subset of has a least element (Well-order and well-ordered set).
Proof
Let and be attempts and put ; then is an initial segment of , being an intersection of two downward closed sets.
Put and suppose for some ; since is downward closed, , so and agree at every , that is , and therefore , giving .
If instead then outright, so for every the implication " implies " holds, and transfinite induction gives : any two attempts agree on the intersection of their domains.
In particular, for each there is at most one attempt with domain , and at most one attempt with domain , since two of them would have that same set as the intersection of their domains.
Let , which is a set by Separation applied to , and note that the attempt in question is unique when it exists.
Suppose ; for each let be the unique attempt with domain and put , a function with domain which is again an attempt, because it agrees with below and .
The assignment is given by a formula, so Replacement makes a set; let be the union of that set.
is a function: any two of the are attempts and therefore agree on the intersection of their domains, so no argument receives two different values.
is the union of the sets for , which equals : each such is contained in by transitivity of the order, and each lies in .
is an attempt with domain : for we have and , so .
Hence whenever , so by transfinite induction: for every there is a unique attempt with domain .
Replacement applied to the formula makes a set; let be its union, which by the arguments of steps 8.1 and 8.2 is a function whose domain is the union of the sets for , namely itself.
satisfies the recursion: for we get and , so , and in particular is an attempt with domain .
Uniqueness: any function with domain satisfying for all is by definition an attempt with domain , hence equals .
There is therefore exactly one function with domain and for every .
Remarks
Which axioms are spent. Separation produces in step 5.1; Replacement produces the sets of attempts in steps 7.1 and 11.1; Union assembles them. Replacement is genuinely needed and cannot be traded away: the attempts are not subsets of any single set given in advance, so Separation alone cannot collect them. This is the standard reason transfinite recursion is unavailable in Zermelo set theory without Replacement.
No choice is used, and the reason is uniqueness. At every stage the object to be used is the unique attempt with a given domain, singled out by step 4.1, never one of many candidates. A construction phrased as "at stage pick some element not yet used" is a different theorem and does cost a choice principle; the difference is exactly the content of FALSE: transfinite induction and recursion need the Axiom of Choice.
Class function, not a set function. has to be allowed to take values anywhere in the universe, since may be an arbitrary set, so cannot be assumed to be a set of ordered pairs. That is why the result is a schema. When happens to be an honest set function, defined on the set of all functions from proper initial segments of into a fixed set and taking values in , the statement is an ordinary theorem of ZF and the same proof applies verbatim.
Relation to ordinary recursion. Taking recovers the familiar recursion on the natural numbers, but not literally the published The recursion theorem: that theorem prescribes in terms of alone, whereas here sees the whole earlier history . Course-of-values recursion on is the special case of the present theorem, and it is what later pages use whenever a construction at stage consults all earlier stages.
Depends on
Used by
- Generics over countable transitive models in ZF Corollary
- Automorphisms acting on forcing names Definition
- Finite beth iteration above an infinite cardinal Definition
- Finite-support forcing iterations Definition
- Forcing names and their rank Definition
- Rapid filters and the Raisonnier family Definition
- The constructible hierarchy and constructible rank Definition
- The countable Borel hierarchy and its limit convention Definition
- The cumulative hierarchy Definition
- ZFA universes, atoms, pure sets, and the kernel Definition
- A scale used in the Dowker subspace Example
- Sealing a named maximal antichain Example
- FALSE: transfinite induction and recursion need the Axiom of Choice False statement
- A connected CW pair has a model without low relative cells Lemma
- A long chain with club continuity below aleph omega Lemma
- A supported Boolean algebra has an ideal maximal in its supported-definability class Lemma
- A tight strongly unbounded coloring gives finite-target AD guessing Lemma
- Balogh combinatorial map Lemma
- Balogh countable restriction enumeration Lemma
- Bounding projections produce an exact upper bound with large coordinate cofinalities Lemma
- Canonical finite-sequence coding from a supplied well-order Lemma
- Canonical L-hulls are elementary and small Lemma
- CH gives a Luzin set, and classical Luzin sets give the cylinder property Lemma
- Club continuity produces strongly increasing subsequences Lemma
- Club guessing at the double successor of an uncountable regular cardinal Lemma
- Cofinality and size of the scale subspace Lemma
- Directed progressive products have club continuous chains Lemma
- Disjoint box refinements in the ambient Rudin space Lemma
- Elementary hull transfer for bounded cofinality strata Lemma
- Finite predecessor closures are sets Lemma
- Finite-stage L histories and weak limit-level absoluteness Lemma
- For every ordinal α there is a least ordinal β admitting a map β → α with cofinal range, and that map may always be taken strictly increasing Lemma
- Generalized delta systems for small supports Lemma
- Maximal antichains well-order linearly ordered sets Lemma
- Multiple choice produces maximal antichains Lemma
- Nested intervals form a Suslin tree Lemma
- Nice refinements exist and are regular but not Lindelof Lemma
- Normal trees have faithful sequence representations Lemma
- Normalizing a scale at existing least upper bounds Lemma
- Pattern closure yields an end-homogeneous sequence Lemma
…and 44 more results.
Dependency tree · two levels
7 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.
Sources
- Transfinite induction (Wikipedia) (standard reference, not scraped)
- Axiom schema of replacement (Wikipedia) (standard reference, not scraped)
- T. Jech, Set Theory, 3rd millennium ed., Ch. 2 (Ordinal numbers) (standard reference, not scraped)
- A. Marks, Set Theory (standard reference, not scraped)
- J. T. Moore, MATH 6870: Set Theory (standard reference, not scraped)