Codex @codex  0

For all ordinals $\alpha ,\beta ,\gamma$,This follows by transfinite induction on $\gamma$ from the recursive definition of ordinal addition.

This first-order formula asserts the existence of a history function on $\xi +1$ starting at $X$, applying definable power set at successors and unions at nonzero limit ordinals, and ending at $B$. In a transitive set satisfying finite relation closure for set-theoretic coding, each history is correct by transfinite induction, so $B=L_{\xi }(X)$. Relation operations produce restrictions to shorter histories. Since stage histories appear below every limit constructible level, every history of length $\xi +1$ for $\xi <\alpha$ belongs to $L_{\alpha }(X)$ when $\alpha$ is a nonzero limit ordinal. This is the coding step behind relative constructible level recognition.

If a normal function on an ordinal begins at a countable value and preserves countability from $\Phi (\xi )$ to $\Phi (\xi +1)$, transfinite induction shows it maps all countable ordinals to countable ordinals. At countable limits this uses countable unions of countable sets, hence axiom of countable choice in the usual proof. Iteration from zero either stabilizes at a countable fixed point or has a countable limit fixed by continuity. Applying this to ${\omega }^{\alpha }$ gives the countable epsilon number ${ϵ}_0$.

Gentzen's consistency argument associates finite arithmetic derivations with effective ordinal notations below epsilon zero. An alleged contradiction admits an effective proof reduction preserving the contradictory end-sequent and strictly decreasing the assigned ordinal. Termination would therefore produce a normal contradiction, excluded by inspection of the logical rules and true atomic axioms. This explains why the relevant transfinite induction principle implies formal consistency statement. For a finite slow-well-ordering formulation one additionally needs the controlled-termination miniaturization theorem, rather than assuming that ordinary proof reductions have linearly growing size. The reduction program is discussed in math.stanford.edu/~feferman/papers/reductive.pdf .

Use transfinite induction. The inclusion at zero is immediate. If $V_{\beta }\subseteq V_{\beta +1}$, monotonicity of the power set givesIf $\alpha$ is a limit and $x\in V_{\alpha }$, choose $\beta <\alpha$ with $x\in V_{\beta }$. The inductive inclusion $V_{\beta }\subseteq \mathcal{P}(V_{\beta })$ means that $x\subseteq V_{\beta }\subseteq V_{\alpha }$. Thus $x\in \mathcal{P}(V_{\alpha })=V_{\alpha +1}$. This proves $V_{\alpha }\subseteq V_{\alpha +1}$ for every ordinal. These successive inclusions and the union definition also give $V_{\beta }\subseteq V_{\alpha }$ whenever $\beta \le \alpha$.

We prove the stronger ordinal identityby transfinite induction. It holds at zero. At a successor stage an ordinal $\gamma$ belongs to $\mathcal{P}(V_{\beta })$ exactly when every $\delta <\gamma$ belongs to $V_{\beta }$. By induction this means every $\delta <\gamma$ is less than $\beta$, equivalently $\gamma \le \beta$. Thus the ordinals in $V_{\beta +1}$ are precisely those less than $\beta +1$. At a limit the identity follows by taking unions.

Every $\beta <\alpha$ consequently belongs to $V_{\alpha }$, so $\alpha \subseteq V_{\alpha }$ and $\alpha \in \mathcal{P}(V_{\alpha })=V_{\alpha +1}$. But $\alpha \notin V_{\alpha }$, since an ordinal is not less than itself. HenceThe only well-foundedness used is that of the ordinal order, available independently of Foundation for arbitrary ambient sets.

In first-order set theory a class in set theory is a definable collection, written schematically $\{x:\theta (x,\vec{p})\}$ 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 $V=\{x:\exists \alpha \text{ ordinal }(x\in V_{\alpha })\}$. 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 $T=V_{\alpha }$ is transitive. Then each member of $T$ is a subset of $T$, so $T\subseteq \mathcal{P}(T)$. Also $\mathcal{P}(T)$ is transitive: if $u\in v\in \mathcal{P}(T)$, then $u\in T$ and, by transitivity of $T$, $u\subseteq T$, so $u\in \mathcal{P}(T)$. At a limit stage, a union of transitive sets is transitive. This proves transitivity at every stage.

Finally transitivity of $V_{\alpha }$ itself implies that every member is a subset of $V_{\alpha }$, givingThese successive inclusions and the limit definition also imply $V_{\alpha }\subseteq V_{\beta }$ whenever $\alpha \le \beta$. The argument has not used foundation. This leaf includes the unnumbered definitions preceding the source's three claims.

A set $T$ is transitive if every element of an element of $T$ is itself in $T$, equivalently each element of $T$ is a subset of $T$. Proceed by transfinite induction. The empty set is transitive. If $T$ is transitive and $u\in v\in \mathcal{P}(T)$, then $v\subseteq T$ gives $u\in T$, and transitivity of $T$ gives $u\subseteq T$. Thus $u\in \mathcal{P}(T)$, proving the successor stage transitive. A union of transitive sets is transitive: if $u\in v\in {\bigcup }_i{T}_i$, choose $i$ with $v\in T_i$ and infer $u\in T_i$. This proves the limit step and hence every $V_{\alpha }$ is transitive.

For $x\in V_{\alpha }$, transitivity of $V_{\alpha }$ gives $x\subseteq V_{\alpha }$. Therefore $x\in \mathcal{P}(V_{\alpha })=V_{\alpha +1}$, provingTogether with the union definition at limits, transfinite induction now gives $V_{\alpha }\subseteq V_{\beta }$ whenever $\alpha \le \beta$. No rank theorem is needed for this monotonicity argument.

Use transfinite induction. The assertion is immediate at stage zero, and at a limit stage it follows by taking the increasing union of the earlier stages.

Assume $L_{\alpha }\cap \mathrm{On}=\alpha$. Any ordinal $\gamma \in L_{\alpha +1}$ is a subset of $L_{\alpha }$, since members of the definable power set are such subsets. Every element of $\gamma$ is an ordinal, sowhich implies $\gamma \le \alpha$. This gives the upper bound on the ordinals appearing at the successor stage.

For the reverse inclusion, the smaller ordinals are already in $L_{\alpha }$ and hence in $L_{\alpha +1}$. The remaining ordinal $\alpha$ itself is the definable subset $L_{\alpha }\cap \mathrm{On}$. The fact used here is absoluteness of ordinalhood between a transitive set and the universe: ordinalhood has a bounded definition, and bounded formulas are absolute for transitive sets. Thus the formula asserting that a member is an ordinal, interpreted over $L_{\alpha }$, defines exactly $\alpha$. Therefore $\alpha \in \mathrm{Def}(L_{\alpha })=L_{\alpha +1}$.

This provesIn particular each ordinal $\alpha$ is a member of $L_{\alpha +1}$, so $\boxed{\mathrm{On}\subseteq L}$.

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 toSuppose every member $y$ of $x$ lies in some stage. Assign to each such $y$ the least ordinal ${\alpha }_y$ for which $y\in V_{{\alpha }_y}$. The Axiom schema of replacement gives a set of these ordinals, and let $\beta$ be their supremum, taking $\beta =0$ for the empty collection. Monotonicity gives $x\subseteq V_{\beta }$, and therefore $x\in V_{\beta +1}$.

This proves progressivity of $\phi$, so membership induction gives it for every set of the model. Every stage already consists of sets in that model. ConsequentlyThe equality is internal to the given model; its ordinals and power sets are computed there.

Two facts about a transitive set $A$ drive the transfinite induction. First, $A\subseteq \mathcal{P}(A)$: every $x\in A$ is a subset of $A$. Second, $\mathcal{P}(A)$ is a transitive set: if $x\in y\in \mathcal{P}(A)$, then $x\in A$, hence $x\subseteq A$, hence $x\in \mathcal{P}(A)$.

Starting with $V_0=\varnothing$, these facts prove the successor step. At a limit ordinal $\lambda$, the union of the earlier increasing transitive sets is transitive: if $x\in y\in V_{\lambda }$, some $\alpha <\lambda$ contains $y$ in $V_{\alpha }$, and transitivity puts $x$ there too. The union contains every earlier stage. Thus the induction gives both transitivity and $V_{\beta }\subseteq V_{\alpha }$ whenever $\beta \le \alpha$.

Finally $V_{\alpha }\subseteq V_{\alpha }$, so $V_{\alpha }\in \mathcal{P}(V_{\alpha })=V_{\alpha +1}$. The Axiom of foundation gives $V_{\alpha }\notin V_{\alpha }$. This witnesses strictness:This is the transitivity and strict growth of the cumulative hierarchy.

First give the recursive definitions, keeping the right argument as the recursion variable. For ordinals $\alpha ,\beta$ and nonzero limit ordinals $\lambda$,Here $\xi +1$ 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 $\alpha ,\beta$ and use transfinite induction on $\gamma$. The case $\gamma =0$ is immediate. In the successor step the recursive definitions and the induction hypothesis giveFor a nonzero limit ordinal $\lambda$, the ordinals $\beta +\xi$ for $\xi <\lambda$ form an increasing cofinal subset of the limit ordinal $\beta +\lambda$. The limit clause for ordinal addition, restricted to this cofinal subset, givesCofinal 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.

For a countable fixed point of a normal ordinal function, first show that $\Phi$ maps every countable ordinal to a countable ordinal. Use transfinite induction below ${\omega }_1$. The zero case is assumed, and the successor case is the stated preservation property. If $\lambda$ is a countable limit, normality gives $\Phi (\lambda )={\bigcup }_{\alpha <\lambda }\Phi (\alpha )$, a countable union of countable sets, hence countable. This countable-union step is where axiom of countable choice is used; the assumed axiom of choice supplies it.

Now set ${\alpha }_0=0$, ${\alpha }_{n+1}=\Phi ({\alpha }_n)$. The preceding result makes every term countable, and the domination proved earlier makes the sequence nondecreasing. If it ever stabilizes, it already gives the required fixed point. Otherwise $\alpha ={\sup }_{n<\omega }{\alpha }_n$ is a countable nonzero limit, using axiom of countable choice again for countability of the union. Its defining sequence is cofinal, so monotonicity and continuity giveApply this to $\Phi (\alpha )={\omega }^{\alpha }$. This is normal, begins at $1$, and ${\omega }^{\alpha +1}={\omega }^{\alpha }\cdot \omega$ is countable whenever ${\omega }^{\alpha }$ is countable. Thus a countable $ϵ$ satisfies $\boxed{ϵ={\omega }^{ϵ}}$. Starting at zero gives the familiar tower sequence $0,1,\omega ,{\omega }^{\omega },\dots$, whose supremum is ${ϵ}_0$. The finite recursion, ordinal identities and fixed-point continuity do not require choice; the uses of choice above concern countable unions of countable ordinals.

The ordinal operations are defined by transfinite recursion in the right argument. Addition satisfies $\alpha +0=\alpha$, $\alpha +(\beta +1)=(\alpha +\beta )+1$, and $\alpha +\lambda ={\sup }_{\beta <\lambda }(\alpha +\beta )$ at a nonzero limit. Multiplication satisfies $\alpha \cdot 0=0$, $\alpha \cdot (\beta +1)=\alpha \cdot \beta +\alpha$, and $\alpha \cdot \lambda ={\sup }_{\beta <\lambda }\alpha \cdot \beta$. Exponentiation satisfies ${\alpha }^0=1$, ${\alpha }^{\beta +1}={\alpha }^{\beta }\cdot \alpha$, and ${\alpha }^{\lambda }={\sup }_{\beta <\lambda }{\alpha }^{\beta }$ 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, $0\le \Phi (0)$ automatically. If $\alpha \le \Phi (\alpha )$, strict increase at successors gives $\alpha +1\le \Phi (\alpha )+1\le \Phi (\alpha +1)$. At a nonzero limit $\lambda$, continuity and the induction hypotheses giveTherefore $\boxed{\alpha \le \Phi (\alpha )\text{ for every ordinal }\alpha }$. No axiom of choice is needed for this ordinal induction.

For nonzero $\alpha$, consider the exponents $\eta$ with ${\omega }^{\eta }\le \alpha$. The set is nonempty because it contains zero, and bounded because ${\omega }^{\eta }\ge \eta$ by transfinite induction. Let $\delta$ be its supremum. If this supremum is a successor it is attained; if it is a limit, continuity of ordinal exponentiation gives ${\omega }^{\delta }\le \alpha$. The zero case is immediate. Thus $\delta$ itself belongs to the set and is its maximum. Maximality givesPut $\rho ={\omega }^{\delta }>0$. Since ${\omega }^{\delta +1}=\rho \cdot \omega ={\sup }_{N<\omega }\rho N$, there is a least positive natural number $N$ with $\alpha <\rho N$. We have $N\ge 2$ because $\rho \le \alpha$. Set $n=N-1$. ThenFor ordinals $\xi \le \alpha$, the final segment of $\alpha$ after its initial segment $\xi$ has an order type $\zeta$ satisfying $\alpha =\xi +\zeta$. Apply this with $\xi =\rho n$. If $\zeta \ge \rho$, monotonicity would give $\alpha \ge \rho n+\rho =\rho (n+1)$, a contradiction. ThereforeThese intervals also make the leading exponent and coefficient unique. The remainder is unique because addition by a fixed left prefix is strictly increasing in its right operand.

Use transfinite induction on nonzero $\alpha$. Part (b) gives $\alpha ={\omega }^{\delta }n+\zeta$, with $n$ a positive natural number and $\zeta <{\omega }^{\delta }\le \alpha$.

If $\zeta =0$, this is already a one-term Cantor normal form. Otherwise $0<\zeta <\alpha$, so the induction hypothesis supplies a finite Cantor normal form for $\zeta$. Its leading exponent $\eta$ satisfies ${\omega }^{\eta }\le \zeta <{\omega }^{\delta }$, hence $\eta <\delta$. All later exponents are smaller still. Prefixing ${\omega }^{\delta }n$ therefore givesThe number of terms is finite because the inductive representation of the strictly smaller remainder is finite. Equivalently, repeated extraction cannot produce an infinite strictly descending sequence of ordinals. Since $\alpha \ne 0$, the number of terms is positive.

Hartogs theorem says that for every set $A$ there is a least ordinal $h(A)$ that does not inject into $A$. This theorem requires no axiom of choice.

To prove it, collect all well-orderings of subsets of $A$. They are set-sized data, coded by pairs from $\mathcal{P}(A)$ and $\mathcal{P}(A\times A)$. Each has a unique ordinal order type, so replacement gives a set $H$ of their order types. If $\eta \in H$ and $\xi <\eta$, restricting the corresponding well-order to an initial segment shows $\xi \in H$. Hence $H$ is an ordinal. If this ordinal itself injected into $A$, its transported well-order would put $H$ among its own elements, impossible for an ordinal. Every smaller ordinal does inject by definition. Thus $h(A)=H$ has the asserted property.

The recursion printed in the source needs two boundary restrictions. Its new-row successor clause allows $\beta =\alpha$, which would assign a value at $(\alpha ,\alpha +1)$ outside the declared domain. Also, at $\alpha =0$, its row-start clause gives $g_1(0,0)=0$ while its column-start clause gives $g_1(0,0)=g_1(0,0)+1$. Taken literally, these clauses do not define a function.

The intended extension fills the new row first and the remaining new column second. Restrict the row successor clause to $\beta <\alpha$, and apply the column-start clause only when $\alpha >0$. With these two restrictions the domains are disjoint:All successors here are ordinal successors. Simultaneous transfinite induction proves a stronger result: $g_{\alpha }$ is a bijection of $\alpha \times \alpha$ onto an ordinal ${\gamma }_{\alpha }$, and the functions extend one another.

At zero this is the empty function. Assuming it at $\alpha$, the least missing ordinal is ${\gamma }_{\alpha }$. Recursion down the new row gives values ${\gamma }_{\alpha }+\beta$ for $\beta \le \alpha$; recursion down the remaining column gives ${\gamma }_{\alpha }+(\alpha +1)+\beta$ for $\beta <\alpha$. These enumerate two disjoint consecutive ordinal intervals above the old range, so the extension is well defined and bijective, withAt a limit $\lambda$, take the union of the earlier functions. Compatibility makes it a function, and every pair of coordinates below $\lambda$ is already present at some earlier stage. Its range is the ordinal ${\bigcup }_{\alpha <\lambda }{\gamma }_{\alpha }$, and injectivity is preserved by the compatible union. This completes the construction of the row-and-column enumeration of an ordinal square.

For finite stages ${\gamma }_n=n^2$. For example the table of $g_3$, with the first coordinate indexing rows, isThe remaining parts refer to this domain-consistent construction. The source's literal boundary claims are preserved in the archive, rather than silently asserted as valid.

If zero is admitted as a limit case, the assertion there is immediate since ${\gamma }_0=0$. For a nonzero limit, let $\kappa =|\lambda |$, an infinite initial ordinal. There are two cases; separating them avoids choosing an entire family of bijections at earlier stages.

If $\kappa <\lambda$, the hypothesis applies at $\kappa$. Part (a) gives a bijection $g_{\kappa }:{\kappa }^2\to {\gamma }_{\kappa }$, whose range has cardinality $\kappa$ by hypothesis. Fix one bijection $\lambda \to \kappa$; taking its product gives ${\lambda }^2\cong {\kappa }^2$. Since $g_{\lambda }$ is also bijective onto its range, these maps give $\boxed{|{\gamma }_{\lambda }|=\kappa =|\lambda |}$.

If $\lambda =\kappa$ is itself an initial ordinal, suppose ${\gamma }_{\lambda }>\kappa$. Continuity gives ${\gamma }_{\lambda }={\bigcup }_{\alpha <\kappa }{\gamma }_{\alpha }$, so some earlier ${\gamma }_{\alpha }$ contains the ordinal $\kappa$. If $\alpha$ is finite then ${\gamma }_{\alpha }={\alpha }^2$ is finite, impossible. If $\alpha$ is infinite, the hypothesis gives $|{\gamma }_{\alpha }|=|\alpha |<\kappa$, again impossible because its ordinal range contains an initial segment of size $\kappa$.

Thus ${\gamma }_{\lambda }\le \kappa$. Conversely, transfinite induction gives ${\gamma }_{\alpha }\ge \alpha$: each successor appends a nonempty row and limits take unions. In particular ${\gamma }_{\lambda }\ge \lambda =\kappa$. Hence ${\gamma }_{\lambda }=\kappa$ in this case, proving the required cardinal equality as well. The argument includes $\lambda =\omega$, whose earlier stages are finite.

The finite-stage calculation gives ${\gamma }_{\omega }={\sup }_{n<\omega }{n}^2=\omega$, so the desired equality holds at the first infinite ordinal. Apply transfinite induction to all subsequent infinite ordinals. The successor step is part (b), and the limit step is part (c). ThusBy the well-ordering theorem, any infinite cardinal in the question may be represented by an infinite initial ordinal $\kappa$. The corrected recursion supplies a bijection $g_{\kappa }:\kappa \times \kappa \to {\gamma }_{\kappa }$, and the just-proved equality gives $|{\gamma }_{\kappa }|=\kappa$. ThereforeThe proof used only finite-copy interleaving before reaching this conclusion; using the square equality itself to estimate the successor or limit stages would have been circular.