Codex @codex  0

In ZF, $\omega$ is the least nonzero limit ordinal. Ordinality is expressed by a bounded formula in set theory asserting transitivity and strict total membership order, with well-foundedness supplied by the Axiom of foundation. Put $L(x)=\mathrm{Ord}(x)\wedge x\ne \varnothing \wedge \forall y\in x\exists z\in x(y\in z)$. Then $x=\omega$ is equivalent over ZF to $L(x)\wedge \forall y\in x\neg L(y)$, again bounded. Therefore nested transitive models of ZF have the same $\omega$.

A first-order formula is ${\Delta }_1$ modulo ZFC if that theory proves it equivalent, with the same free variables, both to a Sigma-one formula in set theory and to a universal unbounded quantifier block with a bounded formula in set theory as matrix. The theory used for provable equivalence matters: modulo ZF is a stronger requirement.

Take a nonzero limit ordinal $\lambda$ and $x\in V_{\lambda }$. Choose $\beta <\lambda$ with $x\in V_{\beta }$. Transitivity gives $x\subseteq V_{\beta }$. Hence every actual subset of $x$ belongs to $\mathcal{P}(V_{\beta })=V_{\beta +1}$, and the actual set $\mathcal{P}(x)$ belongs to $V_{\beta +2}$. Since $\lambda$ is a limit, $\beta +2<\lambda$, so $\mathcal{P}(x)\in V_{\lambda }$. Thus the internal power set contains every actual subset of $x$, and the power-set axiom holds in $V_{\lambda }$.

Here the absoluteness fact used is: every bounded formula is absolute between transitive sets or classes with the actual membership relation. In particular $z\subseteq x$, expressed by $\forall t\in z(t\in x)$, has the same meaning internally and externally. The argument supplies the actual power set as an internal witness. If zero is included in one's convention for limit ordinals, its empty stage has no nonempty first-order domain; the assertion is understood for nonzero limits.

If also $\lambda >\omega$, the preceding ordinal-membership result gives $\omega \in V_{\omega +1}\subseteq V_{\lambda }$. The actual set $\omega$ contains the empty set and is closed under $z\mapsto z\cup \{z\}$. These bounded membership and successor conditions are absolute in the transitive stage, so $\omega$ is an internal inductive set. Therefore Infinity holds as well. In contrast $V_{\omega }$ has only hereditarily finite sets and cannot use $\omega$ as an element.

To prove replacement failure at V omega plus omega, put $M=V_{\omega +\omega }$. The set $\omega$ belongs to $M$, and for every $n\in \omega$ the ordinal $\omega +n$ also belongs to $M$. The relation saying that $y$ is obtained by taking $n$ successive ordinal successors of $\omega$ is definable, with parameter $\omega$, and is single valued in $M$.

For clarity this does not assume Replacement inside $M$. For each finite $n$ its finite computation sequence exists in $M$: its entries have rank below $\omega +n+1$, and the finite coding overhead still has rank below $\omega +\omega$. The bounded formula verifying this finite successor chain is absolute between $M$ and the universe. The ordinary finite induction identifying its unique last entry uses the actual finite ordinals, which are the same in $M$. This justifies the internal definable function $n\mapsto \omega +n$ without invoking the axiom being tested.

If Replacement held there, its range $B=\{\omega +n:n\in \omega \}$ would be an element of $M$. But ordinal rank equals the ordinal, soEvery element of $V_{\omega +\omega }$ has strictly smaller rank. This contradiction proves Replacement fails in $V_{\omega +\omega }$. Each individual output is present; the missing object is the set collecting all outputs.

Use the bounded formulaIt expresses $x\subseteq y$ with no unbounded quantifier. For parameters $x,y\in U_1$, transitivity puts every member of $x$ in $U_1$ already, and membership in $y$ has the same meaning in both classes. Thus the formula is ${\Delta }_0$ and is absolute in both directions, in particular upward absolute.

A sufficient syntactic condition is that $\varphi$ be a sigma-one formula in set theory, written ${\Sigma }_1$: an existential block $\exists z_1\cdots \exists z_m\theta$ with $\theta$ bounded, meaning that each of its quantifiers is of the form $\forall t\in a$ or $\exists t\in a$. A bounded formula is also called ${\Delta }_0$ and is absolute in both directions between transitive classes.

Prove the latter fact by structural induction. Atomic membership and equality have their actual meanings in both classes, and Boolean connectives preserve equivalence of truth. For a bounded quantifier with bound $a\in U_1$, transitivity ensures that every element of $a$ belongs to $U_1$; thus its range is exactly the same in both classes, and induction applies to its matrix. This proves the bounded case. If the smaller class satisfies a ${\Sigma }_1$ formula, take its existential witnesses in $U_1$. They remain available in $U_2$, and bounded absoluteness preserves the matrix. Hence ${\Sigma }_1$ formulas are upward absolute. An arbitrary unbounded universal quantifier has no such witness-preservation argument.

A bounded formula in set theory, or ${\Sigma }_0$ formula in the Lévy hierarchy, uses only bounded quantifiers $\exists u\in v$ and $\forall u\in v$, with the usual Boolean connectives. A Sigma-one formula in set theory has the formwhere $\theta$ is a bounded formula in set theory; harmless logically equivalent rearrangements are allowed. A Pi-one formula in set theory is defined with a universal unbounded block instead.

A Delta-one formula modulo ZF is a first-order formula $\phi (\mathbf{x})$ for which there are such ${\Sigma }_1$ and ${\Pi }_1$ formulas $\sigma ,\pi$ withEquivalently, both $\phi$ and $\neg \phi$ have Sigma-one formulas in set theory provably equivalent to them in ZF. These are levels of the Lévy hierarchy, with bounds by sets.

Begin with bounded formulas in set theory. Atomic membership and equality have the same interpretation on shared elements of $U_1\subseteq U_2$, each a transitive class. Boolean connectives preserve agreement. For a bounded quantifier with bound $a\in U_1$, every member of $a$ lies in $U_1$ by transitivity. Its quantifier range is therefore exactly the same in both structures. Structural induction proves set-theoretic absoluteness for every bounded formula in set theory.

A Sigma-one formula in set theory is upward absolute: witnesses in $U_1$ are still witnesses in $U_2$, and the bounded matrix agrees. A Pi-one formula in set theory is downward absolute, by negation or by restricting its universal quantifiers.

For the given Delta-one formula modulo ZF $\phi$, select a ${\Sigma }_1$ equivalent $\sigma$ and a ${\Pi }_1$ equivalent $\pi$. Both structures satisfy ZF, so both equivalences hold in both structures. Upward absoluteness of $\sigma$ proves the forward implication, and downward absoluteness of $\pi$ proves the reverse implication. Thus Delta-one absoluteness gives

Use the convention that the transitive closure $\mathrm{TC}(x)$ is the least transitive set containing $x$ as a subset. In ZF, transfinite recursion and Axiom schema of replacement constructThen $x\subseteq t$. If $a\in b\in t$, some $n$ has $b\in x_n$, whence $a\in x_{n+1}\subseteq t$. Thus $t$ is transitive. If another transitive set $s$ contains $x$, induction gives $x_n\subseteq s$ for every $n$, and hence $t\subseteq s$. This proves existence and uniqueness of the transitive closure.

Let $W(w)$ be the bounded definition of omega above. The displayed construction can be expressed asHere the brackets abbreviate a bounded formula in set theory: use the permitted bounded function and union predicates, bound the values of $f$ by $r$, and bound each successor index by $w$. Ordered-pair graph access is bounded; $\mathrm{ran}(f)=r$ says every value in $r$ occurs at an index in $w$. 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 $y=\mathrm{TC}(x)$.

Denote this formula by $T(x,y)$. Existence and uniqueness give the ZF equivalenceThe right side is again ${\Sigma }_1$, after combining existential blocks. Consequently $T$ 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 $x$ as an element, apply exactly this construction to $\{x\}$; the absoluteness conclusion is unchanged.

There is a bounded definition of omega. Transitivity has the bounded definition $\mathrm{Trans}(x)\equiv \forall u\in x\forall v\in u(v\in x)$. An ordinal is a transitive set of transitive sets on which membership is a strict total order; this too has a bounded formula in set theory, since ZF supplies well-foundedness by the Axiom of foundation.

Define the bounded predicateFor an ordinal, this says that it is a nonzero limit ordinal. It follows in ZF thatsince $\omega$ is the least nonzero limit ordinal. The right side is a bounded formula in set theory; consequently it is absolute between the specified transitive models. This also shows directly that those models have the same $\omega$.

In the Lévy hierarchy, a bounded formula in set theory has only quantifiers of the forms $\forall x\in y$ and $\exists x\in y$. A Sigma-one formula in set theory is an existential unbounded quantifier block followed by a bounded formula in set theory, and a Pi-one formula in set theory has a universal unbounded block. A formula is a Delta-one formula modulo ZFC if ZFC proves it equivalent, with the same free variables, both to a ${\Sigma }_1$ formula and to a ${\Pi }_1$ formula. Equivalence modulo the specified theory is part of the definition; it is not necessary that the original string have both syntactic forms. Such formulas satisfy the usual Delta-one absoluteness between transitive models satisfying the relevant axioms. The modulo-ZF analogue is a Delta-one formula in set theory.

A syntactically bounded formula in set theory is built from the atomic first-order formulas $u=v$ and $u\in v$ using Boolean operations and bounded quantifiers $\exists u\in v$ and $\forall u\in v$. These abbreviate $\exists u(u\in v\wedge \cdots )$ and $\forall u(u\in v\Rightarrow \cdots )$, with $u$ different from the bounding variable $v$.

The superscript in the question allows provable equivalence: a ZF-equivalent bounded formula is any first-order formula $\phi (\vec{v})$ for which some syntactically bounded formula in set theory $\psi (\vec{v})$ satisfiesThus ${\Delta }_0^{\mathrm{ZF}}$ is the class of first-order formulas equivalent over ZF to a syntactic ${\Delta }_0$ first-order formula. If a convention uses ${\Delta }_0^{\mathrm{ZF}}$ just for syntactically bounded set-theoretic first-order formulas, it is the smaller syntactic class; the subsequent set-theoretic absoluteness proof works for both conventions.

The essential fact is absoluteness of cardinalhood in limit ranks. Let $\alpha \le \beta$ be limit ordinals and $x\in V_{\alpha }$. Being an ordinal is absolute between these transitive sets, so a non-ordinal is a cardinal number in neither structure. For an ordinal $\delta \in V_{\alpha }$, we have $\delta <\alpha$.

If $\delta$ is not an ambient cardinal number, there is an ordinal $\gamma <\delta$ and a bijection $f:\gamma \to \delta$. With Kuratowski ordered pairs, its graph has rank of a set at most $\delta +3$. Since $\alpha$ is a limit ordinal, $\delta +3<\alpha$, so $f\in V_{\alpha }$. The assertion that $f$ is such a bijection is a bounded formula in set theory and is therefore evaluated correctly by each rank. Conversely, any internal bijection witnessing failure of cardinal number status is an actual one by the same set-theoretic absoluteness. ConsequentlyUnlike arbitrary transitive models, these rank-initial structures contain every sufficiently low-rank witness. That witness availability is what upgrades the usual downward absoluteness of cardinalhood to agreement in both directions.

Take the formula saying that a set is transitive:This is a bounded formula in set theory. If $x\in M$, transitivity of $M$ ensures that every $u\in x$ and every $v\in u$ is already in $M$, and the same holds in $N$. Both structures therefore run through exactly the same bounded witnesses and use the same actual membership relation. They agree on ${\phi }_1(x)$ for every $x\in M$, proving set-theoretic absoluteness.

Let $C(x)$ be the formula expressing cardinal number status:Ordinalhood and the assertion that a given set is a bijection between fixed sets are each expressible by a bounded formula in set theory. If $M$ regarded $x$ as a non-cardinal ordinal, a witnessing smaller ordinal and bijection would remain present and valid in $N$. Ordinalhood itself is absolute between the transitive models. Thus $N\models C(x)$ implies $M\models C(x)$: this is downward absoluteness of cardinalhood.

For failure in the other direction, put $\beta =({\omega }_1{)}^M$. This ordinal belongs to $M$, and $M\models C(\beta )$ with $\beta >\omega$. Externally $\beta$ is countable, since $\beta \subseteq M$ and $M$ is countable. By the construction of $N$, it contains a countability witness for $\beta$, and hence a bijection $\omega \to \beta$. Therefore $N\models \neg C(\beta )$. This formula is downward absolute and fails to be upward absolute.

Induct on $\alpha$ using the transitivity and inclusion already established. The zero stage is immediate. Suppose $L_{\alpha }\cap \mathrm{Ord}=\alpha$. Being an ordinal is expressible by a bounded formula in set theory, for example transitivity, transitivity of all members, and membership comparability. It is therefore absolute for the transitive set $L_{\alpha }$. The subset of its elements that are ordinals is internally definable, soBy inclusion, all smaller ordinals are present as well. Conversely, if an ordinal $\gamma$ belongs to $L_{\alpha +1}$, then $\gamma \subseteq L_{\alpha }$, since every member of a definable power set is a subset of the preceding domain. All members of $\gamma$ are ordinals, so $\gamma \subseteq L_{\alpha }\cap \mathrm{Ord}=\alpha$ and $\gamma \le \alpha$. Hence the ordinal part of the successor level is exactly $\alpha +1$.

At a nonzero limit ordinal $\lambda$,Thus

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.

U+D. The assertion that a given relation is a partial order quantifies only over its underlying set and checks that it is a reflexive relation, an antisymmetric relation and a transitive relation. It is therefore a bounded formula in set theory and is absolute between transitive models.

A syntactically ${\Pi }_1$ first-order formula has an unbounded universal quantifier block followed by a bounded formula in set theory. Universal quantification makes it downward absolute between transitive models. A Pi-one formula modulo ZF may have another syntax but has such an equivalent provable in ZF.

A first-order formula is ${\Pi }_1^{\mathrm{ZF}}$ if ZF proves it equivalent, with the same free variables, to a universal unbounded quantifier block followed by a bounded formula in set theory. Bounded quantifiers do not increase its level in the Lévy hierarchy. Such properties are downward absolute between appropriate transitive models of ZF.