Alphabeta Math
TheoremStatement: AI-adaptedProof: AI-adaptedprecheck passverified 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 recursion

Statement

Let (W,<) be a well-order (Well-order and well-ordered set) and let G be a class function: a rule, given by a formula in the language of set theory, that assigns a set G(h) to every function h whose domain is a proper initial segment of W (Initial segment of a well-order). Then there is exactly one function F with domain W such that

F(a)=G(F↾W<a)for every a∈W.

Here F↾W<a is the restriction of F to the initial segment determined by a, so the value of F at a is prescribed in terms of all its earlier values at once.

Because G is a class function rather than a set, this is a theorem schema of ZF: one theorem for each formula defining G. It uses Replacement, and it uses no form of the Axiom of Choice.

Facts & Assumptions

Given: A well-order (W,<), a class function G as in the statement, and the axioms of ZF. Call a function h an attempt when dom(h) is an initial segment of W and h(b)=G(h↾W<b) for every b∈dom(h). The empty function is an attempt, with domain the initial segment ∅.

[A1]

G(h) is a well-determined set for every function h whose domain is a proper initial segment of W.

[A2]

The axioms of ZF are available, in particular Separation, Union and Replacement. No choice principle is assumed.

[L1]

Transfinite induction on (W,<): if W<a⊆S implies a∈S for every a∈W, then S=W (Transfinite induction).

[L2]

W<a={x∈W:x<a} and W≤a=W<a∪{a} are initial segments, an intersection of initial segments is an initial segment, and (W<a)<b=W<b for b<a (Initial segment of a well-order).

[L3]

The order of W is total and every nonempty subset of W has a least element (Well-order and well-ordered set).

Proof

technique · direct
1.1

Let h and k be attempts and put D=dom(h)∩dom(k); then D is an initial segment of W, being an intersection of two downward closed sets.

L2construct
2.1

Put S={a∈W:a∉D or h(a)=k(a)} and suppose W<a⊆S for some a∈D; since D is downward closed, W<a⊆D, so h and k agree at every x<a, that is h↾W<a=k↾W<a, and therefore h(a)=G(h↾W<a)=G(k↾W<a)=k(a), giving a∈S.

step 1.1A1L2
3.1

If instead a∉D then a∈S outright, so for every a∈W the implication "W<a⊆S implies a∈S" holds, and transfinite induction gives S=W: any two attempts agree on the intersection of their domains.

step 2.1L1
4.1

In particular, for each a∈W there is at most one attempt with domain W<a, and at most one attempt with domain W, since two of them would have that same set as the intersection of their domains.

step 3.1
5.1

Let T={a∈W:there is an attempt with domain W<a}, which is a set by Separation applied to W, and note that the attempt in question is unique when it exists.

step 4.1A2construct
6.1

Suppose W<a⊆T; for each b<a let hb be the unique attempt with domain W<b and put hb+=hb∪{(b,G(hb))}, a function with domain W≤b which is again an attempt, because it agrees with hb below b and hb+(b)=G(hb)=G(hb+↾W<b).

step 5.1step 4.1A1L2construct
7.1

The assignment b↦hb+ is given by a formula, so Replacement makes {hb+:b<a} a set; let u be the union of that set.

step 6.1A2construct
8.1

u is a function: any two of the hb+ are attempts and therefore agree on the intersection of their domains, so no argument receives two different values.

step 7.1step 3.1
8.2

dom(u) is the union of the sets W≤b for b<a, which equals W<a: each such W≤b is contained in W<a by transitivity of the order, and each x<a lies in W≤x.

step 7.1step 6.1L2L3
9.1

u is an attempt with domain W<a: for c<a we have u↾W<c=hc+↾W<c=hc and u(c)=hc+(c)=G(hc), so u(c)=G(u↾W<c).

step 8.1step 8.2step 6.1
10.1

Hence a∈T whenever W<a⊆T, so T=W by transfinite induction: for every a∈W there is a unique attempt ha with domain W<a.

step 9.1step 5.1step 4.1L1
11.1

Replacement applied to the formula a↦ha+=ha∪{(a,G(ha))} makes {ha+:a∈W} a set; let F 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 W≤a for a∈W, namely W itself.

step 10.1step 8.1step 8.2A2construct
12.1

F satisfies the recursion: for a∈W we get F↾W<a=ha and F(a)=ha+(a)=G(ha), so F(a)=G(F↾W<a), and in particular F is an attempt with domain W.

step 11.1step 9.1
13.1

Uniqueness: any function F′ with domain W satisfying F′(a)=G(F′↾W<a) for all a is by definition an attempt with domain W, hence equals F.

step 12.1step 4.1
14.1

There is therefore exactly one function F with domain W and F(a)=G(F↾W<a) for every a∈W.

step 12.1step 13.1∎

Remarks

Which axioms are spent. Separation produces T 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 ha 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 a 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. G has to be allowed to take values anywhere in the universe, since F(a) may be an arbitrary set, so G cannot be assumed to be a set of ordered pairs. That is why the result is a schema. When G happens to be an honest set function, defined on the set of all functions from proper initial segments of W into a fixed set A and taking values in A, the statement is an ordinary theorem of ZF and the same proof applies verbatim.

Relation to ordinary recursion. Taking W=N recovers the familiar recursion on the natural numbers, but not literally the published The recursion theorem: that theorem prescribes g(σ(n)) in terms of g(n) alone, whereas G here sees the whole earlier history F↾W<a. Course-of-values recursion on N is the special case of the present theorem, and it is what later pages use whenever a construction at stage n consults all earlier stages.

Depends on

Used by

…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