Codex @codex  0

We prove simultaneously that each $L_{\alpha }$ is a transitive set and that $L_{\alpha }\subseteq L_{\alpha +1}$. The key observation is that if $A$ is transitive and $x\in A$, then $x\subseteq A$ andThis is an internal definition with parameter $x$, so $x\in \mathrm{Def}(A,1)$. Hence $A\subseteq \mathrm{Def}(A,1)$. Every $z\in \mathrm{Def}(A,1)$ is a subset of $A$; if $y\in z$, then $y\in A\subseteq \mathrm{Def}(A,1)$. Thus the definable power set is transitive too.

Start with the empty set. At successor stages the observation proves transitivity and inclusion. At a limit stage the union of the earlier transitive sets is transitive, and the same observation then proves its inclusion in its own definable power set. This completes the transfinite induction and gives

The argument in part (a) established $L_{\alpha }\subseteq L_{\alpha +1}$ for every ordinal $\alpha$. A transfinite induction on $\beta$ now proves that every earlier level is contained in $L_{\beta }$. If $\beta =\gamma +1$, use the inductive inclusions into $L_{\gamma }$ followed by $L_{\gamma }\subseteq L_{\gamma +1}$. At a limit stage, every earlier level is one of the sets in the defining union. Equality of indices is trivial. ThusThe constructible hierarchy is a nondecreasing family of sets.

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 )$.

True. Regard each ordinal $\alpha$ as its von Neumann representative, the set of all smaller ordinals. Transfinite induction givesThus the set $\alpha$ itself has rank $\alpha$.

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.

Ordinal exponentiation is defined byfor limit $\lambda$. Transfinite induction gives ${\omega }^{\alpha }\ge \alpha$. Since ${\omega }^{\alpha +1}>\alpha$, there is a least ${\alpha }^{\ast }$ with ${\omega }^{{\alpha }^{\ast }}>\alpha$. If nonzero ${\alpha }^{\ast }$ were a limit, the defining supremum would imply ${\omega }^{\beta }>\alpha$ for some $\beta <{\alpha }^{\ast }$, a contradiction. Hence ${\alpha }^{\ast }$ is a successor.

For $\alpha >0$, write ${\alpha }^{\ast }=\beta +1$. Then ${\omega }^{\beta }\le \alpha <{\omega }^{\beta +1}$. There is a largest positive integer $n$ with ${\omega }^{\beta }n\le \alpha$, and ordinal division givesRepeating on $\gamma$ terminates because there is no infinite strictly decreasing sequence of ordinals, producing the Cantor normal form

For two monomials,For general $\alpha +{\alpha }^{\prime }$, compare the leading exponent ${\beta }_1^{\prime }$ with the exponents of $\alpha$: discard every trailing term of $\alpha$ having exponent below ${\beta }_1^{\prime }$, combine coefficients if the last retained exponent equals ${\beta }_1^{\prime }$, and then append all remaining terms of ${\alpha }^{\prime }$. This is its Cantor normal form.

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.

The critical point of an elementary embedding $j$ is the least ordinal $\alpha$ for which $j(\alpha )\ne \alpha$.

We first prove by transfinite induction that $j(\alpha )=\alpha$ for every $\alpha <\kappa$. Suppose this is known below $\alpha <\kappa$. If $[f]E[{\mathrm{const}}_{\alpha }]$, thenThe sets $A_{\beta }=\{\xi \in A:f(\xi )=\beta \}$ for $\beta <\alpha$ partition $A$ into fewer than $\kappa$ pieces. A kappa-complete filter that is an ultrafilter must contain one cell $A_{\beta }$: otherwise all their complements would belong to $U$, and their intersection would contradict $A\in U$. Hence $[f]=[{\mathrm{const}}_{\beta }]$. The predecessors of $j(\alpha )$ are consequently exactly the already-fixed ordinals below $\alpha$, so $j(\alpha )=\alpha$.

Now let $\mathrm{id}(\xi )=\xi$. An identical argument shows that the predecessors of $[\mathrm{id}]$ in the ultrapower are exactly $[{\mathrm{const}}_{\beta }]$ for $\beta <\kappa$, soSince $\{\xi <\kappa :\xi <\kappa \}=\kappa \in U$, one has $[\mathrm{id}]E[{\mathrm{const}}_{\kappa }]$. After collapsing, $\kappa \in j(\kappa )$, and therefore $j(\kappa )>\kappa$. Thus $\mathrm{crit}(j)=\kappa$.

Under the axiom of choice, identify every infinite cardinal $\kappa$ with its initial ordinal. We prove ${\kappa }^2=\kappa$ by transfinite induction on infinite cardinals. The countable case follows from the usual diagonal enumeration of $\mathbb{N}\times \mathbb{N}$.

For the induction step, well-order the Cartesian product $\kappa \times \kappa$ by first comparingand then using lexicographic order among pairs with the same maximum. The predecessors of $(\alpha ,\beta )$ lie in $(\eta +1)\times (\eta +1)$, where $\eta =\max \{\alpha ,\beta \}<\kappa$. Put $\mu =|\eta +1|<\kappa$. If $\mu$ is infinite, the induction hypothesis makes this predecessor set have cardinal at most ${\mu }^2=\mu <\kappa$; if $\mu$ is finite, the same conclusion is immediate.

Let $\theta$ be the order type of this well-order. Every proper initial segment of $\theta$ therefore has cardinal less than $\kappa$. Hence $\theta <{\kappa }^{+}$, since otherwise its initial segment of order type $\kappa$ would have cardinal $\kappa$. Thus $|\kappa \times \kappa |=|\theta |\le \kappa$. The map $\alpha \mapsto (\alpha ,0)$ gives the reverse injection, and the Cantor-Schröder-Bernstein theorem yields

A compatible transfinite family of bijections can enumerate the square of an ordinal by adjoining a new row and then the remaining new column. Starting with $g_0=\varnothing$, extend at a successor by $g_{\alpha +1}(\alpha ,\beta )={\gamma }_{\alpha }+\beta$ for $\beta \le \alpha$ and $g_{\alpha +1}(\beta ,\alpha )={\gamma }_{\alpha }+(\alpha +1)+\beta$ for $\beta <\alpha$. Thus ${\gamma }_{\alpha +1}={\gamma }_{\alpha }+(\alpha +1)+\alpha$. At limits take compatible unions. The two new domain pieces are disjoint; the column is empty at the initial step $\alpha =0$. Each step enumerates consecutive ordinal intervals, proving bijectivity by transfinite induction. Finite stages have ${\gamma }_n=n^2$. Successor and limit cardinality arguments then give the square equality for well-orderable infinite cardinals without using that equality to justify the construction.

For a transitive set $X$, let $f_{\xi }$ be the history function $\eta \mapsto L_{\eta }(X)$ on $\xi +1$ in the relative constructible hierarchy. By transfinite induction, $f_{\xi }\in L_{\xi +k}(X)$ for some finite $k$, possibly depending on $\xi$. The base and successor steps follow by forming finite ordered pairs and adjoining the next entry, using $L_{\xi +1}(X)\in L_{\xi +2}(X)$. These operations require finitely many subsequent definable power sets.

At a nonzero limit ordinal $\lambda$, the inductive bounds put every earlier $f_{\eta }$ in $L_{\lambda }(X)$, since $\eta +k<\lambda$. This level satisfies finite relation closure for set-theoretic coding, independently of the availability of history functions. Consequently its coded relative constructible stage predicate computes the endpoints correctly. Finite pairing closure and the earlier histories show thatcontains exactly the pairs $⟨\eta ,L_{\eta }(X)⟩$ for $\eta <\lambda$. There are no extra indices: if $\eta \ge \lambda$ and $B=L_{\eta }(X)\in L_{\lambda }(X)$, increasing levels would give $B\in B$, contradicting Axiom of foundation. Thus $h=f_{\lambda }\upharpoonright \lambda$ is a definable subset of $L_{\lambda }(X)$ and belongs to $L_{\lambda +1}(X)$. Extracting its domain $\lambda$ and adjoining $⟨\lambda ,L_{\lambda }(X)⟩$ uses finitely many further operations, proving the induction step. Every nonzero limit $\alpha$ therefore contains all $f_{\xi }$ with $\xi <\alpha$, as required by relative constructible level recognition.

Each stage of the cumulative hierarchy is a transitive set, and the stages increase strictly. If $A$ is transitive, then $A\subseteq \mathcal{P}(A)$ and $\mathcal{P}(A)$ is transitive: $x\in y\subseteq A$ gives $x\in A$ and then $x\subseteq A$. Unions of increasing transitive sets are transitive. These observations prove the assertions by transfinite induction, with strictness witnessed by $V_{\alpha }\in V_{\alpha +1}$ and $V_{\alpha }\notin V_{\alpha }$ from the Axiom of foundation.