Absoluteness of constructible levels Created 2026-10-05 Updated 2026-10-06
For a transitive model of ZFC and , the internally computed constructible hierarchy agrees with the ambient level: . Satisfaction for a fixed set structure is computed from the same finite formulas and the same domain in both universes. Transfinite recursion then proves agreement at successors and limits. If , it follows that .
Non-Ramsey set from transfinite selection Created 2026-10-05 Updated 2026-10-06
Using the axiom of choice, enumerate all infinite subsets of the positive integers in order type . By transfinite recursion, choose two previously unused infinite subsets of each . This is possible because each has cardinality and fewer choices have been made at stage . The set is not a Ramsey set of infinite subsets, since every meets both it and its complement.
Open determinacy Created 2026-10-06 Updated 2026-10-14
An infinite game of perfect information with an open set of winning plays for I in the product topology on a discrete move set has a winning strategy in an infinite game for one player. Construct a winning-position attractor in an infinite game by transfinite recursion; ranks give I a terminating descent strategy inside it, and its complement gives II a strategy avoiding every winning prefix. The move set need not be countable, in the usual set theory with axiom of choice.
Ordinal Created 2026-09-24 Updated 2026-11-05
An ordinal records the order type of a well-order. In the von Neumann representation, it is a transitive set well-ordered by membership. The first examples are , , , and .
Every well-order is isomorphic to exactly one ordinal. Ordinal order distinguishes arrangements with the same cardinality: and are both countably infinite, but only the latter has a greatest element. Transfinite induction and transfinite recursion extend finite reasoning through these order types. Their ordinal addition generally fails commutativity because it records concatenation order.
Ordinal arithmetic 2026-10-14
Ordinal arithmetic defines addition, multiplication and exponentiation of ordinals through order types or transfinite recursion. The usual operations need not be commutative. Natural sum and natural product instead combine Cantor normal forms and are commutative; the Hessenberg natural sum is the natural addition operation.
Here denotes ZF without foundation. Transfinite recursion on ordinals defines the cumulative hierarchy by
The associated class is . Each level is a set, while is a definable class. Without Foundation it need not contain every ambient set; it consists of the sets built by this well-founded hierarchy.
In first-order set theory a class in set theory is a definable collection, written schematically using a logical formula and set parameters. A class term is an abbreviation for such a defining condition; it does not add a new kind of object to the quantifiers of ZF. A class in set theory is proper if it is not the collection of elements of any set.
Define the cumulative hierarchy by transfinite recursion:
and let . Without foundation this denotes the well-founded part produced by the hierarchy; it must not simply be assumed to contain every ambient set. Transfinite recursion on ordinals and the relevant set constructions remain available in ZF without foundation.
Prove transitivity by transfinite induction. The empty stage is transitive. Suppose is transitive. Then each member of is a subset of , so . Also is transitive: if , then and, by transitivity of , , so . At a limit stage, a union of transitive sets is transitive. This proves transitivity at every stage.
Finally transitivity of itself implies that every member is a subset of , giving
These successive inclusions and the limit definition also imply whenever . The argument has not used foundation. This leaf includes the unnumbered definitions preceding the source's three claims.
For a set , let consist of the subsets of definable over the structure by a first-order formula with finitely many parameters from . It is a set contained in : satisfaction for a set structure and the set of logical formula codes give a uniform set construction of these definable subsets. If is transitive, every is one such subset, defined over by , so .
Define the constructible hierarchy by transfinite recursion:
Gödel's constructible universe is the definable class in set theory
At successor stages only subsets definable over the previous stage are admitted, in contrast to the full power-set construction of the cumulative hierarchy. The stages are transitive and increasing, as permitted in the question, and their union contains every ordinal. Finite parameters are essential in the definition of .
The cumulative hierarchy is defined by transfinite recursion on the ordinals:
The recursion theorem of ZF supplies each set stage. The whole universe is , a proper-class union. Equivalently, exactly when the rank of is less than , where .
For a set , its definable power set consists of the subsets of definable by a first-order formula over using finitely many parameters from . The quantifiers range over ; this is generally much smaller than its full power set.
The constructible universe is defined by transfinite recursion:
The last union denotes a definable proper class, not a set-sized union over a set of all ordinals. At a successor stage, only definitions over the previously constructed stage are permitted.
The aleph numbers enumerate the infinite initial ordinals by transfinite recursion:
Here is the least cardinal strictly larger than . The Generalized continuum hypothesis is
equivalently for every ordinal in ZFC.
The cumulative hierarchy is defined by transfinite recursion:
This recursion on ordinals is available without assuming the Axiom of foundation for all sets. The stages are increasing and transitive, by transfinite induction using their definitions.
Work internally in the specified model of ZF without the Axiom of foundation, and assume the membership induction theorem. Apply it to
Suppose every member of lies in some stage. Assign to each such the least ordinal for which . The Axiom schema of replacement gives a set of these ordinals, and let be their supremum, taking for the empty collection. Monotonicity gives , and therefore .
This proves progressivity of , so membership induction gives it for every set of the model. Every stage already consists of sets in that model. Consequently
The equality is internal to the given model; its ordinals and power sets are computed there.
The cumulative hierarchy is the transfinite recursion
Here is the power set. The class consists of all sets in ZF, by the Axiom of foundation and Axiom schema of replacement.
Use the convention that the transitive closure is the least transitive set containing as a subset. In ZF, transfinite recursion and Axiom schema of replacement construct
Then . If , some has , whence . Thus is transitive. If another transitive set contains , induction gives for every , and hence . This proves existence and uniqueness of the transitive closure.
Let be the bounded definition of omega above. The displayed construction can be expressed as
Here the brackets abbreviate a bounded formula in set theory: use the permitted bounded function and union predicates, bound the values of by , and bound each successor index by . Ordered-pair graph access is bounded; says every value in occurs at an index in . Any auxiliary sets used for the graph coding may be put in the initial existential block. Thus this is a Sigma-one formula in set theory defining .
Denote this formula by . Existence and uniqueness give the ZF equivalence
The right side is again , after combining existential blocks. Consequently is a Delta-one formula modulo ZF, so Delta-one absoluteness applies. Therefore transitive closure is Delta-one definable and is ZF-absolute. If closure is instead required to contain as an element, apply exactly this construction to ; the absoluteness conclusion is unchanged.
First give the recursive definitions, keeping the right argument as the recursion variable. For ordinals and nonzero limit ordinals ,
Here is the successor ordinal, and the supremum of a set of ordinals is its union. These are ordinal arithmetic, defined by transfinite recursion, and differ from cardinal sum and ordinal multiplication.
Associativity of ordinal addition is true. Fix and use transfinite induction on . The case is immediate. In the successor step the recursive definitions and the induction hypothesis give
For a nonzero limit ordinal , the ordinals for form an increasing cofinal subset of the limit ordinal . The limit clause for ordinal addition, restricted to this cofinal subset, gives
Cofinal restriction is valid because ordinal addition by a fixed ordinal on the left is increasing and continuous in its right argument, directly from its recursive definition. This completes the induction.
The ordinal operations are defined by transfinite recursion in the right argument. Addition satisfies , , and at a nonzero limit. Multiplication satisfies , , and . Exponentiation satisfies , , and at nonzero limits. These are ordinal operations, not commutative cardinal arithmetic.
For a normal function on an ordinal, prove domination by transfinite induction. At zero, automatically. If , strict increase at successors gives . At a nonzero limit , continuity and the induction hypotheses give
Therefore . No axiom of choice is needed for this ordinal induction.
Ordinal arithmetic describes the order types of well-ordered constructions. Its operations are defined by transfinite recursion, continuous in their right argument at limits. For addition,
For multiplication,
and, for , exponentiation is defined by
The usual conventions give and for . Ordinal addition concatenates orders, while ordinal multiplication takes a succession of copies of the left factor indexed by the right factor.
Ordinal addition and ordinal multiplication are associative but generally not commutative; exponentiation is not an associative operation. For example,
The distributive identity is ; the reversed distributive law fails, since but . For positive bases, follows from the recursive definitions. These are order-type identities, not an extension of commutative integer arithmetic.
Every nonzero ordinal has a unique Cantor normal form
Comparisons are lexicographic in the exponent/coefficient list. Adding a later ordinal can erase smaller final terms of the earlier one, explaining noncommutativity. Hessenberg natural sum instead aligns equal exponents and adds their coefficients, producing a commutative operation. Finite recursive expressions formed from zero, sums and powers of describe exactly the ordinals below epsilon zero, the least positive solution of . With and ,
To use these ordinals computationally, fix effective fundamental sequences of limit ordinals. Write a nonzero limit below as , where this is its last Cantor term with one copy separated off. If , set
If is a nonzero limit, set . These sequences increase to their limit; for instance and . At the endpoint choose . The shift by one is a convention; changing it changes exact finite values, so it must be specified.
The fast-growing hierarchy now combines iteration at successors with diagonalization at limits:
The superscript denotes repeated function composition, not exponentiation. Thus
The next level iterates an exponential-growth function times, yielding tower-like growth; further finite levels iterate the corresponding higher growth. Each fixed finite level is primitive recursive, and every unary primitive recursive function is eventually dominated by a sufficiently high finite level. The first limit diagonalizes over all of them: has Ackermannian growth and is not primitive recursive. Further limits give diagonals over already transfinite stretches of the hierarchy.
Transfinite induction proves totality for every fixed ordinal index in the chosen well-founded notation system: limit evaluation passes to a smaller index, while successor evaluation performs finitely many calls at the preceding index. For the standard fundamental sequences, implies for all sufficiently large . This eventual dominance in a fast-growing hierarchy is not pointwise monotonicity in the ordinal index. For example,
even though .
The hierarchy also measures proof-theoretic strength. Every fixed with is provably total in Peano arithmetic, and every number-theoretic function provably total there is eventually majorized by some such level. The endpoint is a total recursive function in the usual mathematical metatheory but its totality is not provable in consistent PA. The classification is established in epub.ub.uni-muenchen.de/3843/1/3843.pdf . The distinction is between separately proving each fixed lower level and proving one uniform diagonal statement covering all lower levels; a theory cannot interchange those quantifiers without additional strength.
A related example is Goodstein's theorem. Changing the base in a hereditary base representation can increase the natural number dramatically, but replacing that base by gives an ordinal rank of a Goodstein term below . Subtracting one strictly decreases this rank, so an infinite nonterminating process would give an impossible ordinal descent. This illustrates the central connection: ordinal descent proves termination while fast-growing hierarchies measure how long finite terminating processes can last. The size of intermediate natural numbers need not resemble the simplicity of their ordinal termination measure.
In the game , where , the players alternately choose natural numbers and produce a sequence . Player I wins exactly when . A strategy in an infinite game assigns a move to every finite position where its player is to move; it is winning if every play following it is won by that player. A game is determined if one player has a winning strategy. Both cannot have winning strategies, since their joint play would have to be won by both. The axiom of determinacy asserts
Without assuming AD, one can prove determinacy for finite games by backward induction, and for games with open or closed payoffs by the following argument. Give its product topology of discrete move coordinates. If is open, let be the finite positions whose entire cylinder of extensions lies in . Form a winning-position attractor in an infinite game by transfinite recursion: add an I-position if some child has already been added, and add an II-position if all its children have already been added. Take unions at limits. The process stabilizes because there are only set-many positions and each genuine successor change adds a new one.
An added nonterminal position receives its least entry ordinal. At an I-position in the stable attractor, choose a child of smaller rank; at an II-position every child has smaller rank. Thus every play following I's rank-decreasing strategy must reach : an infinite strictly descending sequence of ordinals cannot exist. The resulting play is in , so I wins from any position in the attractor.
Outside the attractor, every child of an I-position remains outside, and an II-position has some child outside. Otherwise the ranks of all its children would have a set-sized supremum and the parent would have been added at a later stage. II chooses such a child and keeps the play outside forever. If its outcome were in the open set , some finite prefix would have its entire cylinder in , contrary to this avoidance. Therefore II wins from outside. With natural-number moves the least suitable child may be chosen at each position, so no choice axiom is needed for these strategies. This proves open determinacy. For a closed payoff, apply the same argument to its open complement with the players' winning roles interchanged. Clopen payoffs are included in both results.
Now assume AC and construct an undetermined game. The set of strategies for either player has cardinality , since a strategy is a function on a countably infinite set of positions. Each fixed strategy is compatible with plays: the other player's sequence of freely chosen moves determines distinct full plays. Use choice to enumerate I's strategies as and II's as , and well-order the space of plays.
Recursively choose following and following , with all selected plays distinct. At stage fewer than plays have been used, while each compatible-play set has size , so fresh choices exist; take the least ones in the fixed well-order. This does not require regularity of , since for every below its initial ordinal.
Put . Every I-strategy has the losing compatible play , and every II-strategy has the losing compatible play . Therefore neither player has a winning strategy. This choice diagonalization of an undetermined game proves
The elementary determinacy proofs above concern specified definable payoff classes; the diagonal construction explains why extending them to every arbitrary subset of the play space is incompatible with choice.
Interpret the assertion in the usual well-founded, class-theoretic version of Zermelo set theory, including foundation, class comprehension and separation with class parameters. Classes are not extra sets. The axiom of limitation of size, in the form used here, says that every proper class is in bijection with the universe .
First derive replacement. Let a functional class relation map a set onto its image class . If were proper, the limitation axiom would give a bijection . Its composite with the original map would be a surjection . Class-parameter separation forms
Surjectivity gives with , whence iff , a contradiction. Thus is a set, proving each instance of replacement. The argument also gives class replacement when the functional class is a parameter.
The class of ordinals is proper: were it a set, its union and successor would be ordinals larger than every ordinal in it. Limitation gives a bijection . Ordering by the ordinal indices of gives a global well-order; each nonempty set has a member with least index. Choosing that member defines global choice.
Conversely assume replacement and global choice. Ordinary choice well-orders each rank segment, and global choice selects such a well-order uniformly, since the collection of well-orders of each fixed rank segment is a nonempty set. Order all sets first by their rank of a set and then by the selected order within that rank. The resulting global order is set-like: the predecessors of any element are contained in a rank segment and form a set. Restrict it to a proper class . By transfinite recursion, enumerate in this order. It cannot be exhausted at a set ordinal, since replacement would then make a set. Every member appears, because its predecessors form a set, whose well-order has an ordinal order type. Hence has order type . The same applies to , and composing the two enumerations gives a bijection . Thus limitation of size is equivalent to replacement plus global choice in this class-theoretic setting.
The axiom of determinacy, , says that every infinite game of perfect information in which two players alternately choose natural numbers and Player I wins according to a specified payoff is a determined infinite game. A strategy specifies a move at every finite position where its player moves; it is winning if every compatible infinite play is won by that player.
Finite games are determined by backward induction. For infinite games, open determinacy has a direct proof. Let consist of the finite positions whose extension cylinder sets lie in the open payoff . Build the winning-position attractor in an infinite game by transfinite recursion: start with , add an I-position if some successor has already entered, add a II-position if every successor has already entered, and take unions at limit stages. The process stabilizes because there are only countably many finite positions.
At a position in the attractor but outside , I can choose a successor with strictly smaller entry rank, and every move of II has smaller entry rank. There is no infinite descending sequence of ordinals, so I forces entry into and wins. Outside the attractor, every I-move stays outside it, while II can choose a successor outside it; that strategy avoids forever. Since is open, a play belongs to exactly when some prefix belongs to . Thus II wins from outside the attractor. This proves determination for open payoffs; swapping the players proves it for closed payoffs too. The stronger Borel determinacy theorem gives determination for every Borel set payoff, whereas asserts this for arbitrary payoffs.
To contradict from choice, enumerate both players' strategies as and , where . There are strategies because the set of finite positions is countable; there are also plays following any fixed strategy because the other player's moves are arbitrary. At stage of the choice diagonalization of an undetermined game, choose a fresh play following and then a different fresh play following , avoiding all earlier reservations. This is possible because fewer than plays have been reserved at every ; regularity of is not required.
Set . Every loses on , and every loses on . Thus neither player has a winning strategy, and AD and AC are inconsistent together.