{
  "id": "enwiki-001360285624",
  "slug": "transfinite-recursion-theorem",
  "title": "Transfinite recursion theorem",
  "qid": "",
  "lead": "In mathematics, the transfinite recursion theorem says a function can be defined using a recursion over a well-ordered set; for example, \\mathbb{N} but also over general well-ordered sets. Since each well-ordered set is isomorphic to an ordinal, the theorem is also often stated in terms of ordinals.",
  "body": "In mathematics, the transfinite recursion theorem says a function can be defined using a recursion over a well-ordered set; for example, \\mathbb{N} but also over general well-ordered sets. Since each well-ordered set is isomorphic to an ordinal, the theorem is also often stated in terms of ordinals. Transfinite recursion is an instance of transfinite induction and the latter works over a well-ordered set (in fact, the feasibility of such an induction is equivalent to well-ordered-ness). In particular, the theorem can be stated for well-ordered sets. If A is a partially ordered set, we write A^a = \\{ b \\in A \\mid b The transfinite recursion theorem is also commonly stated for ordinals. One simple version is: let a set X and a class function G with values in X defined on the class of all functions be given. Then, for each ordinal \\alpha , there exists a unique function f : \\alpha \\to X such that, for every ordinal \\beta ; that is, \\beta \\in \\alpha or \\beta \\subsetneq \\alpha , f(\\beta) = G(f|_{\\beta}) . Since an ordinal is a well-ordered set, the above version follows from the well-ordered version (as \\beta = \\alpha^{\\beta} ). Although it is common to ask G to be defined for all functions, this is just a convenient way of stating the theorem. In practice, one usually only defines G(f) for functions f : \\alpha \\to X , \\alpha all ordinals, and then extends G for all other functions arbitrary. When A = \\mathbb{N} , the proof here appears in N. Jacobson's Basic Algebra I and exactly the same proof goes through for an arbitrary well-ordered set. The proof itself is taken from Halmos. We say a subset E \\subset A \\times X is closed (with respect to G ) if for each function f : A^a \\to X, \\, a \\in A whose graph is contained in E , we have (a, G(f)) is in E . For example, A \\times X is closed. Let F be the intersection of all closed subsets of A \\times X (with respect to G ), which is again closed. We shall prove F is a graph of a function A \\to X ; that is, the fiber p^{-1}(a) for the projection p : F \\subset A \\times X \\to A has exactly one element for each a in A . For this, we shall use strong induction over A . That is, assuming \\# p^{-1}(b) = 1 for every b , we show \\# p^{-1}(a) = 1 . By inductive hypothesis, we have the function f : A^a \\to X, \\, b \\mapsto \\text{unique element in }p^{-1}(b) . Note the graph of it lies in F . Since F is closed, (a, G(f)) is in F . Thus, \\# p^{-1}(a) \\ge 1 . To show it is the equality, suppose otherwise. That means there is some pair (a, y) \\ne (a, G(f)) in F . We claim the set E := F - \\{ (a, y) \\} is closed. Thus, let g : A^b \\to X be a function whose graph lies in E . If b = a , then we have f = g by inductive hypothesis; indeed, since their graphs lie in F , \\{ f(c), g(c) \\} \\subset p^{-1}(c) for each c . Thus, (b, G(g)) \\in E since y \\neq G(f) = G(g) and F is closed. If b \\ne a , then again (b, G(g)) is in E as F is closed. This proves the claim and then E \\subsetneq F is a contradiction to the smallest-ness of F . Finally, the uniqueness holds by a similar but easier induction. \\square Let the above V be given a well-ordering by the well-ordering theorem. Suppose we are given a sequence of vectors x_{\\gamma} indexed by an ordinal \\beta . That is, we are given a function f : \\beta \\to V such that f(\\gamma) = x_{\\gamma} for each \\gamma \\in \\beta (or \\gamma ). Then let G(f) = the least element in the complement V - \\operatorname{span}(\\operatorname{im}(f)) if V \\ne \\operatorname{span}(\\operatorname{im}(f)) and G(f) = 0 otherwise. Note, since f is arbitrary, the image of f is not necessarily linearly independent; all we have is that G(f) is linearly independent from the nonzero vectors in \\operatorname{im}(f) . The transfinite recursion theorem then says: given an ordinal \\alpha , there exists a unique f : \\alpha \\to V that satisfies the recursion condition; i.e., f(\\beta) = G(f|_{\\beta}) is linearly independent from \\operatorname{im}(f|_{\\beta}) for \\beta . In particular, the nonzero vectors in the image of f are linearly independent. Finally, if we take \\alpha = \\kappa to be some large ordinal; e.g., take \\kappa to have cardinality strictly larger than that of V , then, for the reason of cardinality, B := \\operatorname{im}(f : \\kappa \\to V) - \\{ 0 \\} is a basis of V . (Note, unlike a construction by Zorn's lemma, this basis is uniquely determined by a choice of a well-ordering on V .) b(C) = c(\\{ \\text{strict upper bounds of }C \\}). We now recursively construct a sequence over ordinals. For each function f : \\beta \\to X , let G(f) = b(\\operatorname{im}(f)) if \\operatorname{im}(f) is a chain and otherwise G(f) = some arbitrary element in X ; e.g., b(\\emptyset) . By the transfinite recursion theorem, we find a function f : \\alpha \\to X such that f(\\beta) = G(f|_{\\beta}) for \\beta ; in particular, it is injective. But this is a contradiction since there is an ordinal whose cardinality is strictly larger than that of X (see Hartogs number). If one is not sure about the existence of a large ordinal, there is also an argument that avoids ordinals altogether (still using transfinite recursion). See e.g., . \\square where X^b = \\{ c \\mid c . We shall extend these isomorphisms to an isomorphism X^a \\simeq \\alpha for some ordinal \\alpha . If a = s(b) is a successor; i.e., the least element among strict upper bounds of b , then we let f|_{X^b} = g_b and f(a) = \\alpha_b . Then f : X^a \\overset{\\sim}\\to s(\\alpha_b) := \\alpha_b \\cup \\{ \\alpha_b \\}, where the union on the right exists by the axiom of union. If a = \\sup(X^a) , then, thinking g_b as sets of ordered pairs, let f = \\bigcup_{b The union on the right is a set by the axiom of replacement and the axiom of union; indeed, the former guarantees the collection \\{ g_b \\mid b is a set. Let \\alpha be the image of f , which is clearly an ordinal, and f : X^a \\overset{\\sim}\\to \\alpha . Finally, we check the uniqueness. By transfinite induction, we see isomorphisms between ordinals are the identities. Then given f : X \\overset{\\sim}\\to \\alpha, g : X \\overset{\\sim}\\to \\beta , we have g \\circ f^{-1} : \\alpha \\overset{\\sim}\\to \\beta is the identity and so f = g . \\square The same argument can be used to prove the transfinite recursion theorem when the target X is a class. The proof is by strong induction over ordinals (the same proof works for well-ordered sets but we use ordinals for simplicity). Thus, assume the theorem is true for every \\beta . By inductive hypothesis, for each \\beta , we have a unique function g_{\\beta} : \\beta \\to X satisfying the recursion condition. Let h_{\\beta} : \\beta \\to X be given by \\gamma \\mapsto G(g_{\\beta}|_{\\gamma}) . In the limit case; i.e., \\alpha is a limit ordinal, identifying functions with their graphs, consider the union \\bigcup_{\\beta The formation of a union is justified by the axiom of union but for the above union to be a set, we need the collection \\{ h_{\\beta} \\mid \\beta to be a set; in other words, the image of the map \\beta \\mapsto h_{\\beta} to be a set and that is ensured by the axiom of replacement. Finally, this union is the graph of a function f : \\alpha \\to X that satisfies the required recursion condition. The successor case is handled similarly. \\square",
  "categories": [
    "10639732",
    "23603337",
    "26220375",
    "28607427"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1360285624",
  "content_hash": "",
  "created_at": null,
  "updated_at": 1781953903.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "enwiki-001360285624",
    "type": "webpage",
    "title": "Transfinite recursion theorem",
    "author": [
      {
        "family": "Anticloud FZ LLE",
        "literal": "Anticloud FZ LLE"
      }
    ],
    "container-title": "encyclopegia.org",
    "publisher": "Anticloud FZ LLE",
    "publisher-place": "Dubai, United Arab Emirates",
    "URL": "https://encyclopegia.org/a/transfinite-recursion-theorem",
    "issued": {
      "date-parts": [
        [
          2026,
          11,
          21
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          21
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:enwiki-001360285624",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1360285624",
    "note": "Immutable snapshot enwiki-001360285624"
  }
}