Codex @codex  0

We construct a stronger family: every injection $e_{\alpha }:\alpha \to \omega$ will have coinfinite range, and coherence means agreement modulo finitely many arguments. Begin with the empty function. At a successor, extend $e_{\alpha }$ by assigning the new argument a value outside its range; the range remains coinfinite, and coherence with earlier functions is unchanged.

At a countable limit $\alpha$, take $0={\alpha }_0<{\alpha }_1<\cdots$ cofinal in $\alpha$. We build injections $p_n:{\alpha }_n\to \omega$, extending one another exactly, with $p_n$ differing from $e_{{\alpha }_n}$ at finitely many arguments. Also reserve distinct numbers $k_0,k_1,\dots$, never used by the eventual union. After constructing $p_n$, choose $k_n$ outside its range and different from the earlier reserved numbers; its range is coinfinite since it differs finitely from that of $e_{{\alpha }_n}$.

To extend to ${\alpha }_{n+1}$, first use $e_{{\alpha }_{n+1}}$ on the new arguments while keeping $p_n$ on the old ones. Only finitely many collisions can arise: $p_n$ and $e_{{\alpha }_{n+1}}\upharpoonright {\alpha }_n$ differ finitely by the inductive coherence hypothesis, so their image sets differ finitely. The candidate is otherwise injective. There are also only finitely many new arguments assigned a value among $k_0,\dots ,k_n$. Reassign these finitely many bad arguments to distinct fresh values outside the candidate image and the reserved finite set. Infinitely many fresh values are available because the candidate image differs only finitely from the coinfinite image of $e_{{\alpha }_{n+1}}$. The resulting $p_{n+1}$ is injective, extends $p_n$, omits the reserved numbers, and differs finitely from $e_{{\alpha }_{n+1}}$.

Put $e_{\alpha }={\bigcup }_n{p}_n$. It is injective and omits all $k_n$, so its range is coinfinite. For each $\beta <\alpha$, choose $n$ with $\beta \le {\alpha }_n$. The restriction $e_{\alpha }\upharpoonright \beta$ is $p_n\upharpoonright \beta$, which differs finitely from $e_{{\alpha }_n}\upharpoonright \beta$, and hence from $e_{\beta }$. Transfinite recursion now givesThese coherent coinfinite injections into omega solve the requested problem. Reserving infinitely many omitted values is important: a union of injections with individually coinfinite ranges need not itself have coinfinite range.

Zorn lemma states that a nonempty partially ordered set in which every chain in a partial order has an upper bound has a maximal element. Here is a proof from the axiom of choice and Hartogs theorem.

Suppose there is no maximal element. Every chain $C$ has a strict upper bound: choose an upper bound $b$ and then an element strictly greater than $b$. The family of sets of strict upper bounds is a set of nonempty subsets of the underlying set $P$. The axiom of choice is used here to choose, simultaneously for every chain $C$, one strict upper bound $b(C)$.

By Hartogs theorem there is an ordinal $\kappa$ admitting no injection into $P$. Transfinite recursion defines $x_{\alpha }$ for $\alpha <\kappa$ byAt each stage the previous elements form a chain, and $x_{\alpha }$ is strictly above every one of them. Hence $\alpha \mapsto x_{\alpha }$ is an injection $\kappa \to P$, a contradiction. Therefore a maximal element exists.

For a finite position $s\in A^{<\omega }$, let $[s]$ be the cylinder set of infinite plays extending $s$. Because the factors have the discrete topology, these cylinder sets form a basis for the product topology. PutMembership in $D$ means that I has already secured the outcome, regardless of future moves. Since $G$ is an open set, a play belongs to $G$ exactly when one of its prefixes belongs to $D$.

Build the winning-position attractor in an infinite game by transfinite recursion. Start with $W_0=D$, use unions at limit ordinals, and setThis sequence is increasing: the defining operation is order-preserving, and $W_0\subseteq W_1$. It stabilizes at some ordinal. Indeed, if it strictly increased at every successor stage below the successor cardinal number of $|A^{<\omega }|$, choosing one newly added position per stage would inject that larger cardinal into $A^{<\omega }$. Denote the stable set by $W$. This constructs the needed fixed point directly, without an appeal to an unstated fixed-point theorem.

Every position in $W$ has a least entry ordinal, its rank. Rank zero means membership in $D$. A positive rank is a successor $\alpha +1$: at an I-position some extension belongs to $W_{\alpha }$, while at a II-position every extension does. If the empty word belongs to $W$, I always chooses an extension of smaller rank until $D$ is reached. II's choices also decrease rank before that happens. There is no infinite strictly decreasing sequence of ordinals, so some finite prefix lies in $D$. This is a winning strategy in an infinite game for I.

If the empty word is outside $W$, the fixed point equation says that every extension of an I-position outside $W$ is still outside $W$, and that a II-position outside $W$ has at least one extension outside $W$. II chooses such an extension. Every resulting prefix avoids $D$, hence the whole play avoids $G$ by openness. This is a winning strategy in an infinite game for II.

The choices can be made simultaneously by fixing a well-order of $A$, as allowed by the usual axiom of choice. The argument does not assume that $A$ is countable. Every such open game is determined:

The construction gives a Lusin set $\boxed{A=\{x_{\alpha }:\alpha <{\omega }_1\}}$ with all $x_{\alpha }$ distinct.

Every meagre set is contained in a meagre $F_{\sigma }$ set: replace each nowhere dense set in a countable covering by its closure. There are at most $2^{{\aleph }_0}$ such covers, since each closed subset of $\mathbb{R}$ is determined by a countable rational basis for its open complement, and a countable sequence of such codes is again coded by a real. Under the Continuum hypothesis, enumerate all meagre $F_{\sigma }$ sets as $(M_{\alpha }{)}_{\alpha <{\omega }_1}$, allowing repetitions.

By transfinite recursion, chooseFor each $\alpha <{\omega }_1$, the excluded union is a meagre set: it is a countable union of meagre sets and singletons. The Baire category theorem ensures that it does not cover $\mathbb{R}$, so the choice is possible. The resulting $A$ is uncountable. If $M$ is meagre, choose $\gamma$ with $M\subseteq M_{\gamma }$. Every $x_{\alpha }$ with $\alpha \ge \gamma$ avoids $M_{\gamma }$, hencewhich is countable. Thus $A$ has precisely the Lusin set property. Enumerating covers rather than all meagre sets avoids an unjustified claim that there are only continuum many arbitrary meagre subsets.

The Von Neumann hierarchy and the constructible hierarchy are defined by transfinite recursion:The union clauses apply to nonzero limit ordinals. The definable power set $\mathrm{Def}(L_{\alpha })$ consists of subsets definable over $(L_{\alpha },\in )$ by a first-order formula with finitely many parameters from $L_{\alpha }$. Definability over that structure is essential; it is not unrestricted definability in the ambient universe. The full constructible universe is $L={\bigcup }_{\alpha \in \mathrm{Ord}}{L}_{\alpha }$.

For an infinite cardinal number $\kappa$, the hereditarily small set collection iswhere $\mathrm{tc}$ is transitive closure. Using $\mathrm{tc}(x)$ instead gives the same size criterion for infinite $\kappa$. This bounds the whole membership ancestry, not just $|x|$.

The Von Neumann hierarchy is the following transfinite recursion on the ordinals:Here $\mathcal{P}$ denotes the full power set. The levels are increasing transitive sets, and the construction is continuous at limit ordinals. Transfinite induction proves these properties: transitivity at a successor follows because a member of a subset of $V_{\alpha }$ already belongs to $V_{\alpha }\subseteq \mathcal{P}(V_{\alpha })$; at a limit it follows from the set union of increasing transitive sets. In ZF, Axiom of foundation and Axiom schema of replacement ensure that every set belongs to some $V_{\alpha }$. In terms of the rank of a set, $x\in V_{\alpha }$ exactly when $\mathrm{rank}(x)<\alpha$.

Fix the base convention $L_0(X)=X$. For a transitive set $X$, the relative constructible hierarchy isHere the definable power set isThe satisfaction for a set structure in this definition is a definable set-theoretic relation, obtained by finite syntax coding and recursion on a first-order formula. The transfinite recursion therefore defines a class in ZF.

Each level is a transitive set. For transitive $A$, every $a\in A$ is a subset of $A$ definable using the parameter $a$, so $A\subseteq \mathrm{Def}(A)$; also $A\in \mathrm{Def}(A)$ using the always-true first-order formula. Thus the levels increase and $X\in L_1(X)$. Starting instead with $X\cup \{X\}$ is another common indexing convention, but it is not the convention used here. The relative universe need not satisfy axiom of choice: arbitrary $X$ need not have an internally available well-order.

Zorn lemma states that a partially ordered set in which every chain in a partially ordered set has an upper bound has a maximal element. Include the empty chain in a partially ordered set, so the hypotheses imply that the set $P$ is nonempty. Suppose there were no maximal element. Every chain in a partially ordered set $C$ has an upper bound $u$, and some $v>u$; therefore the set of elements strictly above every member of $C$ is nonempty. The axiom of choice selects one such element $f(C)$ for each chain in a partially ordered set (and an element of $P$ when $C$ is empty).

By Hartogs theorem, there is an ordinal $\kappa$ which does not inject into $P$. Transfinite recursion defines $x_{\alpha }=f(\{x_{\beta }:\beta <\alpha \})$ for all $\alpha <\kappa$: previous elements form a strictly increasing chain in a partially ordered set, including at limit ordinal stages. All $x_{\alpha }$ are distinct, giving the forbidden injection. This proves Zorn lemma; the choice of $f$ is the use of the axiom of choice.

Apply Zorn lemma to linearly independent subsets of $\mathbb{R}$ over $\mathbb{Q}$, ordered by inclusion. A union along a chain in a partially ordered set is linearly independent because each finite linear relation occurs in one member of that chain in a partially ordered set. A maximal independent set spans $\mathbb{R}$, since a vector outside its span could be adjoined. Thus $\mathbb{R}$ has a Hamel basis over $\mathbb{Q}$.

For a finite basis, the Steinitz exchange lemma proves equality of basis sizes. This also rules out an infinite basis when a finite spanning set exists: write each member of the finite spanning set using finitely many elements of another basis; their finite union spans, and independence leaves no other basis elements. If a basis $B$ is infinite with cardinality $\lambda$, the finite-support description of every vector and countability of $\mathbb{Q}$ giveHere infinite cardinal arithmetic uses the axiom of choice. Thus any infinite basis has cardinality $|V|$, proving all bases have the same cardinality. The zero space has its unique empty basis.

Use the convention that the transitive closure of $x$ is the least transitive set containing $x$ as a subset. Define $x_0=x$ and $x_{n+1}=\bigcup x_n$. For each natural number $n$, a finite sequence of length $n+1$ with these properties exists by induction, and is unique because each next entry is the uniquely determined union of the previous entry. Thus the relation sending $n$ to its last entry is a definable function-class, not just a putative recursive specification. The Axiom schema of replacement applied to $\omega$ gives the set of all $x_n$. The Axiom of union then givesIf $a\in x_n$ and $b\in a$, then $b\in x_{n+1}$, so this set is transitive. It contains $x=x_0$, and any transitive set containing $x$ contains all $x_n$ by induction; hence it is least. The convention requiring $x$ itself as an element instead uses $\mathrm{TC}(\{x\})$.

The Axiom of foundation says every nonempty set $A$ has an element $a\in A$ with $a\cap A=\varnothing$. Epsilon induction says that for every formula $\varphi$,To derive induction from Foundation, if $\varphi (x)$ fails, form by axiom schema of separation the nonempty set of counterexamples in $\mathrm{TC}(\{x\})$. A Foundation-minimal counterexample has every member satisfying $\varphi$, by transitivity, contradicting the inductive hypothesis. Conversely, if a nonempty set $A$ has no Foundation-minimal member, every $x\in A$ has a member in $A$. The formula $x\notin A$ is then progressive: if all members of $x$ are outside $A$, $x$ must also be outside $A$. Epsilon induction makes $A$ empty, a contradiction. Thus the two principles are equivalent given the other axioms.

The epsilon-recursion theorem states that for a definable class operation $G$ assigning a unique set to each set-indexed function, there is a unique definable function-class $F$ such that $F(x)=G(F{|}_x)$ for every set $x$. A version with explicit $x$ in the argument is equivalent. Foundation gives well-foundedness and Replacement makes each restriction set-sized. Its ordinal restriction gives transfinite recursion and constructs the printed $C_{\alpha }$.

Here “countable” means at most countable, including finite sets and the empty set. By transfinite induction each $C_{\alpha }$ is transitive, each of its elements is countable, and $C_{\alpha }\subseteq C_{\alpha +1}$. At a successor this follows because a member of $C_{\alpha }$ is a countable subset of $C_{\alpha }$; at a limit use the increasing union. Let ${\omega }_1$ be the first uncountable ordinal. Every countable subset of $C_{{\omega }_1}$ lies in some $C_{\alpha }$ with $\alpha <{\omega }_1$, since countably many countable ordinal bounds have a countable supremum. It therefore belongs to $C_{\alpha +1}$. ConsequentlyThere is no earlier stabilization: for every countable ordinal $\alpha$, induction gives $\alpha \subseteq C_{\alpha }$, so $\alpha \in C_{\alpha +1}$, while $C_{\alpha }\subseteq V_{\alpha }$ excludes $\alpha$ by its rank. Thus ${\omega }_1$ is the first such stage. The fixed set is the set of hereditarily countable sets.

Let $\theta =M\cap \mathrm{Ord}$ be the ordinal height of a model of set theory. First $\theta \ge {\omega }_1$. Indeed, if $\theta$ were countable, the internal axiom of choice would give, for every $x\in M$, a bijection in $M$ between $x$ and some ordinal below $\theta$. Such a bijection is also valid externally, making $x$ externally countable. In particular every internal rank $V_{\xi }^M$, $\xi <\theta$, would be countable. Every element of $M$ lies in one of these internal ranks, sowould be a countable union of countable sets, a contradiction. This is why an uncountable transitive set model has uncountable ordinal height.

For $\xi <\theta$, absoluteness of constructible levels gives $L_{\xi }^M=L_{\xi }$, and that level is an element of $M$. The reason is that satisfaction in a fixed set structure uses the same domain and finite formulas in both universes, so successor definitions agree; transfinite recursion then also makes limit stages agree. Transitivity consequently givesIt remains to locate a countability witness. Given an ambient countable ordinal $\alpha$, choose an injection $f:\alpha \to \omega$. Since $V=L$, it belongs to the constructible universe. Its transitive closure, together with $f$ itself, is countable. Choose a countable elementary substructure $X\prec L_{\eta }$ of a sufficiently large limit level containing this closure pointwise. The condensation lemma for the constructible universe identifies the collapse with $L_{\beta }$ for some countable $\beta$. The collapse fixes $f$, since all its hereditary members were included. Thus $f\in L_{\beta }\subseteq L_{{\omega }_1}\subseteq M$.

The ordinal $\alpha$ itself is in $M$, since $\alpha <{\omega }_1\le \theta$. Being an injection between these fixed sets is a bounded formula in set theory, so $M$ recognizes $f$ as a countability witness. This proves countable-ordinal correctness under constructibility:The use of condensation supplies a witness below the height of $M$; merely knowing that $f$ belongs somewhere to $L$ would not be sufficient.

The constructible hierarchy is defined by transfinite recursion using the definable power set. With parameters permitted in the internal definitions, write $\mathrm{Def}(A,1)$ for the definable subsets of $A$. ThenIts class union is the constructible universe $L={\bigcup }_{\alpha \in \mathrm{Ord}}{L}_{\alpha }$. Only subsets definable over $(L_{\alpha },\in )$ using a first-order formula and finitely many parameters from $L_{\alpha }$ enter at a successor stage.

The two Ramsey properties and the topologies. Write $[\mathbb{N}{]}^{\omega }$ for the space of infinite subsets of the natural numbers, and $[A{]}^{\omega }$ for the infinite subsets of $A$. The positive integers are used throughout. A Ramsey set of infinite subsets $E$ has the property that every infinite $A$ contains an infinite $B$ for which $[B{]}^{\omega }$ lies wholly in $E$ or wholly in $E^c$.

For finite $s$ and infinite $A$ above $\max s$, letThese are the basic neighbourhoods of the Ellentuck topology, denoted $\ast$ in the question. They form a basis: if $X$ belongs to two such sets, their stems are comparable initial segments of $X$; take the longer stem and the intersection of the two tails beyond that stem. This intersection contains the infinite remaining tail of $X$ and yields a basic set contained in both.

A completely Ramsey set $E$ allows such a homogeneous refinement $[s,B]$ inside every $[s,A]$, with $B\subseteq A$ infinite and the stem $s$ kept fixed. Taking $s=\varnothing$ shows that complete Ramseyness implies Ramseyness. The ordinary topology on infinite subsets $\tau$ has basic cylindersIt is the usual product topology on increasing enumerations and is coarser than the Ellentuck topology.

Examples distinguishing the properties. A non-Ramsey example uses the axiom of choice. Let $\kappa =2^{{\aleph }_0}$ and enumerate all infinite sets as $(A_{\alpha }{)}_{\alpha <\kappa }$. Each $[A_{\alpha }{]}^{\omega }$ has cardinality $\kappa$: an enumeration of $A_{\alpha }$ gives the upper bound, and choosing one element from each of infinitely many disjoint pairs gives an injection from all binary sequences for the lower bound.

By transfinite recursion, choose two distinct, previously unused elements $X_{\alpha },Y_{\alpha }\in [A_{\alpha }{]}^{\omega }$ at each stage. Fewer than $\kappa$ elements have been used at stage $\alpha <\kappa$, so this is possible without any assumption on the Continuum hypothesis. Put $R=\{X_{\alpha }:\alpha <\kappa \}$. All the $Y_{\alpha }$ remain outside $R$, since subsequent choices also avoid previously chosen elements. Every $[A{]}^{\omega }$ contains one $X_{\alpha }$ and one $Y_{\alpha }$, so $R$ is not a Ramsey set of infinite subsets. This is the non-Ramsey set from transfinite selection construction.

Perform the same construction on $T=\mathbb{N}\setminus \{1\}$, giving a non-Ramsey set $R_T\subseteq [T{]}^{\omega }$, and putFor any infinite $A$, the infinite set $B=A\setminus \{1\}$ has $[B{]}^{\omega }\cap E=\varnothing$, so $E$ is a Ramsey set of infinite subsets. But no $[\{1\},B]$ with infinite $B\subseteq T$ is homogeneous, because $[B{]}^{\omega }$ meets both $R_T$ and its complement. Therefore $E$ is not a completely Ramsey set.

Every star-open set is completely Ramsey. We give the full fusion proof for open Ellentuck sets, without quoting an infinite Ramsey theorem. Fix a star-open set $O$ and a basic set $[s,A]$. For finite $a\subseteq A$ and an infinite tail $D\subseteq A$ above $\max a$, say $D$ accepts $a$ if $[s\cup a,D]\subseteq O$; it rejects $a$ if no infinite subset of $D$ accepts $a$. Both properties persist under passing to infinite subsets. Every infinite tail can be thinned to decide $a$: take an accepting subset if one exists, and otherwise the original tail rejects it.

First thin $A$ to decide $a=\varnothing$. If it accepts, the required homogeneous neighborhood has already been found. Otherwise keep a rejecting tail. We now fuse to an infinite set $B$ deciding every finite $a\subseteq B$, where the decision for $a$ is made by $B/a=\{b\in B:b>\max a\}$.

To do this, choose $b_1<b_2<\cdots$ successively from an infinite current tail. After choosing $b_j$, thin the tail above $b_j$ to decide each of the finitely many subsets of $\{b_1,\dots ,b_j\}$, one after another, before choosing the next element. For any finite $a\subseteq B$, at the stage when its largest element is selected, the current tail decides $a$ and contains every later selected element. Heredity therefore gives a decision on $B/a$. For $a=\varnothing$, rejection persists from the initial tail.

If $B/a$ rejects $a$, only finitely many $n\in B/a$ can have $B/n$ accepting $a\cup \{n\}$. Otherwise let $D$ be the infinite set of those $n$. Every member of $[s\cup a,D]$ has a first new element $n$, and its remaining tail lies in $B/n$. It therefore belongs to $O$ by acceptance of $a\cup \{n\}$. This would make $D$ accept $a$, contradicting rejection.

Thin $B$ a second time to $C=\{c_1<c_2<\cdots \}$ so that every finite $a\subseteq C$ is rejected. Start with the rejected empty set. At a finite stage, all subsets of the selected elements are rejected. For each of these finitely many subsets, avoid its finitely many next elements that would give an accepted extension, and choose the next $c_j$ beyond all excluded elements. Since $B$ decides every finite extension, each new extension is rejected. Induction gives the asserted property of $C$.

We claim $[s,C]\cap O=\varnothing$. If $X\in [s,C]\cap O$, openness provides a basic set $[t,D]\subseteq O$ containing $X$. Extend $t$, if necessary, to an initial segment $u$ of $X$ containing $s$. Write $u=s\cup a$ with finite $a\subseteq C$. The infinite tail $X\setminus u$ lies in $B/a$ andIt is therefore an accepting subtail for $a$, contradicting rejection. We have found either an accepting neighborhood or a neighborhood disjoint from $O$. Thus

Basic neighborhoods are clopen. Consider $[s,A]$ and a point $X$ outside it. If $s$ is not an initial segment of $X$, take an initial segment $t$ of $X$ of length at least $|s|$; its ordinary cylinder $[t]$ cannot meet $[s,A]$. Otherwise some element of $X\setminus s$ is outside $A$; take $t$ through that element, and again $[t]$ is disjoint from $[s,A]$.

Thus the complement of $[s,A]$ is already open in the ordinary topology on infinite subsets, and hence in the finer Ellentuck topology. A basic neighbourhood is open by definition, so

Ordinal exponentiation is defined by transfinite recursion:when $\lambda$ is a nonzero limit ordinal. If $\alpha \ge 1$, each successor step and each supremum show that $\beta \mapsto {\alpha }^{\beta }$ is nondecreasing. If $\alpha \ge 2$, transfinite induction strengthens this to strict increase: ${\alpha }^{\beta }<{\alpha }^{\beta +1}$, and the value at a limit exceeds every earlier value.

Strict increase can disappear when the base changes. For example, with $\omega <\omega +1<\omega +2$,because for every positive finite $n$, both finite powers have leading term ${\omega }^n$, and taking the supremum gives ${\omega }^{\omega }$.

We next proveApply transfinite induction to $\gamma$. The zero and successor cases follow directly from the recursive definitions and the associativity of ordinal multiplication. At a limit $\lambda$, continuity of ordinal multiplication in its right argument givesThe superficially similar identity $(\alpha \beta {)}^{\gamma }={\alpha }^{\gamma }{\beta }^{\gamma }$ is false: for $\alpha =\omega$, $\beta =2$, and $\gamma =2$,

Finally,For the first equivalence, bases zero and one fail, while strict increase embeds every countable ordinal into the powers of any base $\alpha \ge 2$. For the second, $\alpha \ge {\omega }_2$ immediately gives ${\alpha }^{{\omega }_1}\ge \alpha$. Conversely, if $\alpha <{\omega }_2$, then $|\alpha |\le {\aleph }_1$. Every exponent below the first uncountable ordinal ${\omega }_1$ is countable, so each ${\alpha }^{\beta }$ has cardinality at most ${\aleph }_1$; the supremum of ${\aleph }_1$ such ordinals still has cardinality at most ${\aleph }_1$ and is therefore below the second uncountable ordinal ${\omega }_2$.

The inductive definition of ordinal addition is the transfinite recursionfor every nonzero limit ordinal $\lambda$. The synthetic definition takes disjoint well-orders $A$ and $B$ of order types $\alpha$ and $\beta$, puts every member of $A$ before every member of $B$, and defines $\alpha +\beta$ to be the order type of this ordered sum.

These definitions agree by transfinite induction on $\beta$. The empty second order contributes nothing; adjoining a greatest element gives the successor clause; and a limit well-order is the union of all of its proper initial segments, so its ordered sum with $A$ has order type ${\sup }_{\gamma <\lambda }(\alpha +\gamma )$.

The Von Neumann hierarchy is defined by transfinite recursion:for every limit ordinal $\lambda$.

We prove simultaneously by transfinite induction that every $V_{\alpha }$ is a transitive set and that $V_{\alpha }\subseteq V_{\alpha +1}$. The claims are immediate for $V_0$. Suppose first that $V_{\alpha }$ is transitive. If $x\in y\in V_{\alpha +1}=\mathcal{P}(V_{\alpha })$, then $y\subseteq V_{\alpha }$, so $x\in V_{\alpha }$. Moreover, transitivity says that every $x\in V_{\alpha }$ satisfies $x\subseteq V_{\alpha }$, and henceThus $V_{\alpha +1}$ is transitive and $V_{\alpha }\subseteq V_{\alpha +1}$. At a limit $\lambda$, if $x\in y\in V_{\lambda }$, then $y\in V_{\beta }$ for some $\beta <\lambda$; transitivity of $V_{\beta }$ gives $x\in V_{\beta }\subseteq V_{\lambda }$. The inclusions at successor stages also imply

Finally, the rank of a set $x$ is the ordinalEvery $y\in x$ belongs to $V_{\mathrm{rank}(y)+1}\subseteq V_{\mathrm{rank}(x)}$, so $x\subseteq V_{\mathrm{rank}(x)}$. Thereforewhich proves that every set occurs in the hierarchy.

The inductive definition of ordinal addition isfor a limit ordinal $\lambda$.

The synthetic definition takes the order type of the disjoint union of a copy of $\alpha$ followed by a copy of $\beta$: every point of the first copy precedes every point of the second, and each copy retains its original total order.

Fix $\alpha$ and use transfinite induction on $\beta$. The synthetic sum with the empty order is $\alpha$. Appending a greatest element produces the successor ordinal rule. At a limit ordinal $\lambda$, the second copy is the union of its initial segments of types $\beta <\lambda$, so the whole order has type
${\sup }_{\beta <\lambda }(\alpha +\beta )$. Thus the synthetic operation satisfies the inductive recursion; uniqueness in transfinite recursion proves the definitions equivalent.

The Von Neumann hierarchy is defined by transfinite recursion:for a limit ordinal $\lambda$.

We prove by transfinite induction that every $V_{\alpha }$ is a transitive set. The claim is immediate for $V_0$. If $V_{\alpha }$ is transitive and $x\in y\in V_{\alpha +1}$, then $y\subseteq V_{\alpha }$, so $x\in V_{\alpha }$. Transitivity also gives $x\subseteq V_{\alpha }$, hence $x\in \mathcal{P}(V_{\alpha })=V_{\alpha +1}$. At a limit stage, if $x\in y\in V_{\lambda }$, then $y\in V_{\beta }$ for some $\beta <\lambda$, so $x\in V_{\beta }\subseteq V_{\lambda }$.

Transitivity implies $V_{\alpha }\subseteq \mathcal{P}(V_{\alpha })=V_{\alpha +1}$. Induction and unions at limit stages then give

By well-founded recursion on membership, define the rank of a setInduction on this rank gives $y\in V_{\mathrm{rank}(x)}$ for every $y\in x$. Thusand consequentlyEvery set therefore occurs at some level of the hierarchy.

For a well-order $(A,r)$, define recursivelyTransfinite recursion makes $F$ an isomorphism from $(A,r)$ onto a transitive set of transitive sets, hence onto an ordinal. If two ordinals were isomorphic, the first point where the isomorphism differed from the identity would contradict preservation of their initial segments. Thus this ordinal is unique.

By choice-function well-ordering construction, use transfinite recursion to choosewhenever the set on the right is nonempty. The chosen elements are distinct, so if this construction continued through the Hartogs theorem ordinal $h(x)$, the map $\beta \mapsto x_{\beta }$ would inject $h(x)$ into $x$, a contradiction. It therefore stops at some ordinal $\alpha <h(x)$. At the stopping stage every element of $x$ has been selected, and henceis a bijection $\alpha \to x$.

Assuming the axiom of choice, every set $x$ has such a choice function on its nonempty subsets. Transporting the membership order on $\alpha$ across the bijection well-orders $x$. Thus the axiom of choice implies the well-ordering theorem.