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.

Every countable structure in a countable first-order language has a Scott sentence whose countable models are precisely its isomorphic copies. In particular two countable structures with the same countable infinitary logic sentences are isomorphic. Countability of both structures is essential to the back-and-forth conclusion; the sentence need not exclude uncountable models.

Let $M$ be a nonempty countable structure in a countable first-order language. The countable infinitary logic $L_{{\omega }_1,\omega }$ permits countable logical conjunctions and logical disjunctions, but only finite strings of quantifiers and finitely many free variables in each formula. We construct a Scott formula ${\varphi }_{\bar{a}}^{\alpha }(\bar{x})$ for every finite tuple $\bar{a}$ from $M$ and every countable ordinal $\alpha$.

At stage zero, let ${\varphi }_{\bar{a}}^0$ be the conjunction of all atomic formulas true of $\bar{a}$ and the negations of all atomic formulas false of $\bar{a}$. Include atomic formulas involving arbitrary terms and constants, not just relation symbols applied directly to variables. There are only countably many such formulas. This complete atomic description ensures that matching tuples determine a partial isomorphism of structures.

At successors putAt a nonzero limit ordinal $\lambda <{\omega }_1$, put ${\varphi }_{\bar{a}}^{\lambda }={\bigwedge }_{\beta <\lambda }{\varphi }_{\bar{a}}^{\beta }$. All these are formulas of countable infinitary logic: each indexing set is countable, and the free variables are only the fixed finite tuple. Rename bound variables when necessary. Transfinite induction also shows $M\models {\varphi }_{\bar{a}}^{\alpha }(\bar{a})$.

For tuples of the same length within $M$, define $\bar{a}{\equiv }_{\alpha }\bar{b}$ by $M\models {\varphi }_{\bar{a}}^{\alpha }(\bar{b})$. Induction identifies this with the usual symmetric back-and-forth method equivalence: the tuples have the same atomic description at stage zero, and at a successor every one-element extension on either side has a matching extension at the previous stage. Thus these are decreasing equivalence relations, simultaneously for every finite tuple length.

There are only countably many pairs of finite tuples in $M$. A pair can cease to be equivalent at most once. The supremum of the first separation stages of all pairs that separate below ${\omega }_1$ is a countable ordinal. Choose a countable $\alpha$ at least that supremum. No pair can first separate at $\alpha +1$, soThis justifies stabilization without assuming that all tuples stabilize at one predetermined finite stage.

Now form the following Scott sentence, where the case $n=0$ has no displayed variables or quantifiers:It is a sentence of countable infinitary logic, because the family of all finite tuples is countable. The stabilization above and the truth of ${\varphi }_{\varnothing }^{\alpha }$ show $M\models {\sigma }_M$.

Suppose a countable structure $N$ satisfies ${\sigma }_M$. Start with the empty matching tuples, and maintain $N\models {\varphi }_{\bar{a}}^{\alpha }(\bar{b})$. The corresponding conjunct of ${\sigma }_M$ upgrades this to $N\models {\varphi }_{\bar{a}}^{\alpha +1}(\bar{b})$. The existential conjuncts extend the match by any specified element of $M$. The universal-disjunction conjunct extends it by any specified element of $N$. The atomic formula information makes a new element on one side match a new element on the other, and makes repeated elements agree with their earlier matches.

Enumerate both structures and alternate these two extension steps, including the least element not yet covered at each step. The union is a bijection preserving and reflecting every atomic formula, hence an isomorphism; for function symbols, eventually include both a tuple and the value of its function term to see explicitly that the function is preserved. For finite structures the same construction stops when both are covered. Conversely every isomorphic copy of $M$ satisfies ${\sigma }_M$, since isomorphisms preserve formulas of countable infinitary logic by induction on their construction. ThereforeIf countable $M,N$ have the same $L_{{\omega }_1,\omega }$ sentences, $N$ satisfies this Scott sentence of $M$ and is isomorphic to $M$. This proves Scott isomorphism theorem.

The rank characterization holds for a set relation, or a set-like class relation. For such a well-founded relation, use well-founded recursion to defineThe predecessor set is a set, so the supremum is an ordinal. For a set-like class relation, the closure of the predecessors of any one point under finitely many predecessor steps is a set; perform the ordinary set recursion there. Uniqueness makes these local definitions agree, producing a class rank function. The formula immediately gives $xRy\Rightarrow \rho (x)<\rho (y)$.

Conversely, suppose such an ordinal-valued function exists. For any nonempty subset, or nonempty subclass in the class formulation, take an element whose rank is least among the ranks occurring. It has no predecessor in that subset or subclass, because a predecessor would have smaller rank. This proves well-foundedness.

There is a qualification in the printed class formulation. If well-founded class relations are defined to include set-likeness, it is already implicit and the assertion is correct. Under the minimal-element definition alone, it must be supplied. Without set-likeness, let $X=\mathrm{Ord}\cup \{u\}$, where $u=\{1\}$ is not an ordinal, and put every ordinal below $u$, with the usual ordinal order below it. Every nonempty subclass has a minimal element, so the relation is well founded. But transfinite induction forces $\rho (\alpha )\ge \alpha$ for all ordinals, whereas $\rho (u)$ would have to exceed every $\rho (\alpha )$. No such ordinal exists. Thus the unrestricted class assertion is false; set-likeness is necessary for this standard rank proof.

The recursive definition of ordinal addition is $\alpha +0=\alpha$, $\alpha +(\beta +1)=(\alpha +\beta )+1$, and $\alpha +\lambda ={\sup }_{\beta <\lambda }(\alpha +\beta )$ for a nonzero limit ordinal $\lambda$. The synthetic definition is the order type of the ordered disjoint union of a copy of $\alpha$ followed by a copy of $\beta$.

For the synthetic operation, adding the empty order does nothing, adding a successor appends one final point, and concatenation with a limit order is the increasing union of the initial concatenations with all its proper initial segments. Their order types have supremum ${\sup }_{\beta <\lambda }(\alpha +\beta )$. Thus the synthetic operation satisfies the recursive equations. Transfinite induction gives uniqueness of the recursively defined operation, proving equivalence.

The recursive definitions of ordinal multiplication and ordinal exponentiation areThe last equation in each line is for nonzero limit $\lambda$. In particular the convention $0^0=1$ belongs to this recursive definition.

For every countable ordinal $\beta$, ${\omega }^{\beta }$ is countable: successor stages use a countable product, and countable limit stages a countable union. Hence ${\omega }^{{\omega }_1}={\sup }_{\beta <{\omega }_1}{\omega }^{\beta }\le {\omega }_1$. Conversely ${\omega }^{\beta }\ge \beta$ by transfinite induction, so these values are cofinal in ${\omega }_1$. Therefore ${\omega }^{{\omega }_1}={\omega }_1$.

It is not the least fixed point. Set $a_0=1$, $a_{n+1}={\omega }^{a_n}$ and define epsilon zero as ${\epsilon }_0={\sup }_n{a}_n$. This is countable, and continuity of ordinal exponentiation at limits gives ${\omega }^{{\epsilon }_0}={\sup }_n{\omega }^{a_n}={\epsilon }_0$. Any fixed point of $\alpha \mapsto {\omega }^{\alpha }$ dominates every $a_n$ by induction, hence dominates ${\epsilon }_0$. Thus the least fixed point is ${\epsilon }_0<{\omega }_1$.

Yes. A cardinal fixed point of the singular cardinal enumeration is obtained by countable iteration. Start with ${\kappa }_0={\aleph }_0$ and putThe singular cardinal enumeration is strictly increasing and satisfies ${\sigma }_{\alpha }\ge \alpha$ for every ordinal $\alpha$; the latter follows by transfinite induction for any strictly increasing ordinal-valued enumeration. If equality occurs at some ${\kappa }_n$, that cardinal number is already a witness. Otherwise the sequence is strictly increasing. Put $\kappa ={\sup }_{n<\omega }{\kappa }_n$. This is an uncountable singular cardinal of cofinality $\omega$.

For every $\alpha <\kappa$, some $n$ has $\alpha <{\kappa }_n$, and thereforeAlso ${\sup }_n{\sigma }_{{\kappa }_n}=\kappa$, so ${\sup }_{\alpha <\kappa }{\sigma }_{\alpha }=\kappa$. At a limit ordinal index, if the supremum of all preceding enumerated cardinals is itself singular, it is exactly the next member: every smaller singular cardinal already has a preceding index. ThusThis argument uses continuity only at a singular supremum; the enumeration need not be continuous at a weakly inaccessible cardinal.

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

Use relative constructible level recognition. The finite coding conditions matter here: merely writing “every set is relatively constructible” inside an arbitrary transitive set does not ensure that its computations are correct.

Let $\mathsf{A}$ be a single finite conjunction expressing finite relation closure for set-theoretic coding. Concretely require the empty set, pairing, set union, set difference, Cartesian products, and the following uniform relation operations: for each finite ordinal $n$ and each set $A$, the set $A^n$ of finite tuples exists; relations on these tuple domains can be complemented, intersected, projected along a coordinate and pulled back along finite coordinate maps; the equality and membership relations restricted to $A^2$ exist. These are finitely many first-order closure assertions with $n$ quantified, not an axiom schema. Each operation is specified by its usual elementwise membership equivalence. Transitivity makes the operations correct externally. Finite tuple domains are also correct: every individual finite tuple is already present by pairing and union.

These conditions make satisfaction for a set structure absolute. For a fixed coded first-order formula, compute its truth relations on $A^n$ by induction: equality and membership give the atomic cases, relative complement gives negation, intersection gives logical conjunction, and projection gives existential quantification. All required truth tables exist by $\mathsf{A}$ and agree with the actual ones. Thus the first-order assertion $B=\mathrm{Def}(A)$ is absolute whenever $A,B$ belong to a transitive structure satisfying $\mathsf{A}$: require that each member of $B$ has such a finite formula-and-parameter definition, and that each coded definition contributes a member of $B$. Codes are finite objects; no truth predicate for the ambient universe is being used.

Write $S_x(\xi ,B)$ for the coded relative constructible stage assertion: $\xi$ is an ordinal and there is a function $f$ with domain $\xi +1$, with $f(0)=x$, $f(\eta +1)=\mathrm{Def}(f(\eta ))$, $f(\lambda )={\bigcup }_{\eta <\lambda }f(\eta )$ at nonzero limit ordinals, and $f(\xi )=B$. Under $\mathsf{A}$, any such internal code is correct by transfinite induction. Restrictions of a code to shorter domains exist by the relation operations. Define the one-free-variable first-order formulaAll displayed abbreviations expand into first-order formulas of the membership language.

Suppose $M$ is transitive, $X\in M$, and $M\models \Phi (X)$. Let $I$ be the externally defined set of indices of stage codes in $M$. It contains $0$, is downward closed by restricting codes, and has no largest member by the last conjunct. Thus $I$ is a nonzero limit ordinal $\alpha$. Correctness of stage codes gives $L_{\xi }(X)\in M$ for $\xi <\alpha$, hence $L_{\xi }(X)\subseteq M$ by transitivity. Conversely the exhaustion conjunct puts every $y\in M$ in some such level. Therefore

For the converse, every $L_{\alpha }(X)$ with nonzero limit $\alpha$ satisfies $\mathsf{A}$: each listed operation on parameters from one level is definable at finitely many later levels, still below $\alpha$. Moreover stage histories appear below every limit constructible level. Here is the essential limit step of that lemma. If the histories $f_{\eta }$ for $\eta <\lambda$ are available in $L_{\lambda }(X)$, the correct predicate $S_X$ defines their graph of endpoints as a subset of $L_{\lambda }(X)$. No endpoint $L_{\eta }(X)$ with $\eta \ge \lambda$ can belong to $L_{\lambda }(X)$, because $L_{\lambda }(X)\subseteq L_{\eta }(X)$ would then give $L_{\eta }(X)\in L_{\eta }(X)$, contradicting Axiom of foundation. The defined graph therefore has domain exactly $\lambda$. Adjoining its final pair $(\lambda ,L_{\lambda }(X))$ takes finitely many more stages. Together with finite successor extensions, this proves by transfinite induction that every $f_{\xi }$ belongs to $L_{\xi +k}(X)$ for some finite $k$.

Thus all histories for $\xi <\alpha$ belong to $L_{\alpha }(X)$. Exhaustion follows from continuity, and $\xi +1<\alpha$ supplies a larger represented stage. Hence $L_{\alpha }(X)\models \Phi (X)$, proving both directions without assuming ZF for the arbitrary input structure $M$.

A suitable relative condensation lemma fixes the base pointwise. Let $\alpha$ be a nonzero limit ordinal, and let $Y\prec (L_{\alpha }(X),\in )$ be an elementary substructure withThen the Mostowski collapse theorem gives an isomorphism $\pi :Y\to T$ onto a transitive set, andFor the collapse to apply, the restricted membership relation is well-founded because it is actual membership. It is extensional: if two members of $Y$ differ, an element distinguishing them in $L_{\alpha }(X)$ can be chosen in $Y$ by elementary substructure structure. Since $X$ is transitive and all its members are in $Y$, transfinite induction on their rank of a set shows that $\pi$ fixes every member of $X$, and then $\pi (X)=X$.

By the preceding relative constructible level recognition, $L_{\alpha }(X)\models \Phi (X)$. Elementary substructure agreement transfers this to $Y$, and the collapse isomorphism transfers it to $T$. Thus $T\models \Phi (X)$ and $T=L_{\beta }(X)$ for a nonzero limit ordinal $\beta$.

For the bound, let $\rho =X\cap \mathrm{Ord}$. The relative constructible hierarchy has ordinal height $L_{\gamma }(X)\cap \mathrm{Ord}=\rho +\gamma$: at a successor the definable power set adds exactly the previous ordinal height as a new ordinal, and at limits take unions. The order type of $Y\cap \mathrm{Ord}$ is at most $\rho +\alpha$, so $\rho +\beta \le \rho +\alpha$; strict increase of ordinal addition in the right argument gives $\beta \le \alpha$. The requirement $X\subseteq Y$ is essential to this version: merely having $X\in Y$ need not make the collapse fix the base.

True. The valid distributive law for ordinal multiplication isThe synthetic definition of ordinal multiplication takes a sequence of copies of the left factor, indexed by the right factor. A sequence indexed first by $\beta$ and then by $\gamma$ is exactly the concatenation of the two corresponding sequences. Taking order types gives the identity. Equivalently, use transfinite induction on $\gamma$, with the successor rule and the supremum rule at limit ordinals.

For ordinals, the inductive definition of ordinal addition isThe synthetic definition takes a well-order of type $\alpha$, followed by a disjoint well-order of type $\beta$, with every point of the first preceding the second. They agree by transfinite induction on $\beta$: the empty second order does nothing; adding its last point takes the successor; at a limit ordinal, the concatenated order is the union of its initial concatenations, whose types have the displayed supremum.