Transfinite recursion theorem
≈ 7 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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.
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
Text derived from https://en.wikipedia.org/w/index.php?oldid=1360285624 under CC BY-SA 4.0; modifications have been made.