Past exam of the axiomatic set theory course of the University of Oxford / 2011 (C1.2b, DMAC 2B61, DMPC 2B61)

The cumulative hierarchy is the transfinite recursionHere $\mathcal{P}$ is the power set. The class $V={\bigcup }_{\alpha \in \mathrm{Ord}}{V}_{\alpha }$ consists of all sets in ZF, by the Axiom of foundation and Axiom schema of replacement.

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.

Fix $x\in V_{\delta }$. Since $\delta$ is a limit ordinal, choose $\beta <\delta$ with $x\in V_{\beta }$. Transitivity gives $x\subseteq V_{\beta }$. Every subset $u\subseteq x$ therefore belongs to $V_{\beta +1}=\mathcal{P}(V_{\beta })$, and consequentlyThe last inclusion uses $\beta +2<\delta$, since a finite number of successor steps remains below a limit ordinal. In particular every subset of $x$ is also an element of the transitive set $V_{\delta }$.

Take $y=\mathcal{P}(x)$. For any $u\in V_{\delta }$, transitivity ensures that the internal statement $u\subseteq x$ agrees with the external one. HenceSuch a $y\in V_{\delta }$ exists for every $x\in V_{\delta }$, so $(V_{\delta },\in )$ satisfies the Axiom of power set. This power-set axiom at limit ranks actually holds for every nonzero limit ordinal; the stated restriction $\delta >\omega$ is sufficient.

Every finite ordinal belongs to $V_{\omega }$, so $\omega \subseteq V_{\omega }$ and $\omega \in \mathcal{P}(V_{\omega })=V_{\omega +1}$. However, $\omega \notin V_{\omega }$, whose elements are the hereditarily finite sets.

Suppose $y\in V_{\omega +1}$ were an internal power set of $\omega$. Internally $\omega \subseteq \omega$, and $\omega$ is an available element of the structure. Thus the Axiom of power set would require $\omega \in y$. But $y\in \mathcal{P}(V_{\omega })$ means $y\subseteq V_{\omega }$, which would put $\omega \in V_{\omega }$, a contradiction. ThereforeThis proves power-set failure at the first rank above V omega by an internal obstruction, including the subset $\omega$ itself.

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

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

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.

Use the usual cardinal arithmetic with the axiom of choice. The König theorem for cardinal numbers states that for any index set $I$ and cardinal numbers ${\kappa }_i<{\lambda }_i$,Represent the cardinal numbers as initial ordinals. Let $A=\{(i,\alpha ):i\in I,\alpha <{\kappa }_i\}$ and $B={\prod }_{i\in I}{\lambda }_i$. There is an injection $A\to B$: send $(i,\alpha )$ to the function whose $i$th coordinate is $\alpha +1$ and whose other coordinates are zero. The unique nonzero coordinate identifies $i$, and its value identifies $\alpha$. All values are allowed because $\alpha +1\le {\kappa }_i<{\lambda }_i$.

For any proposed surjection $F:A\to B$, its $i$th row has at most ${\kappa }_i$ elements, soChoose $b_i$ to be the least omitted ordinal. The function $b=(b_i{)}_{i\in I}$ belongs to $B$ and differs from $F(i,\alpha )$ at coordinate $i$, for every $(i,\alpha )\in A$. Thus $F$ is not surjective. Cardinal comparison now gives the strict inequality. If $I=\varnothing$, the conclusion is $0<1$, also valid.

For an infinite cardinal number $\kappa$, its cofinality isviewing $\kappa$ as an initial ordinal. Equivalently it is the smallest cardinal number which is the domain size of a cofinal map into $\kappa$.

Put $\lambda =2^{\kappa }$ and $\mu =\mathrm{cf}(\lambda )$. Suppose $\mu \le \kappa$, and choose cofinal ordinals ${\alpha }_i<\lambda$ for $i<\mu$. Put $a_i=|{\alpha }_i|<\lambda$. Their union is $\lambda$, so infinite cardinal arithmetic givesApply the König theorem for cardinal numbers to $a_i<a_i^{+}$. Each successor cardinal $a_i^{+}$ is at most $\lambda$, whenceHere the last equalities use the currying law for cardinal exponentiation and square of an infinite cardinal. This contradiction proves the cofinality of a power-set cardinal bound

Put $\mu =\mathrm{cf}(\kappa )$ and choose cofinal ordinals ${\alpha }_i<\kappa$, $i<\mu$. With $a_i=|{\alpha }_i|$, the same union comparison and infinite cardinal arithmetic give ${\sum }_{i<\mu }{a}_i=\kappa$. Since $a_i<\kappa$, their successor cardinals satisfy $a_i^{+}\le \kappa$. The König theorem for cardinal numbers therefore givesThis König bound for the Gimel function applies to regular and singular cardinals alike; choosing cofinal ordinals also covers successor cardinal numbers.

Take the Beth numberCantor's theorem makes this sequence strictly increasing. It is a countable cofinal sequence in $\kappa$, while no finite set is cofinal in the limit ordinal $\kappa$. Hence $\mathrm{cf}(\kappa )={\aleph }_0$. ConsequentlyThus Beth omega is a singular strong limit above the continuum. No Continuum hypothesis is needed for the example.