Past exam of the analytic topology and axiomatic set theory course of the University of Oxford / 2009 / B

The cumulative hierarchy is defined by transfinite recursion on the ordinals:The recursion theorem of ZF supplies each set stage. The whole universe is $V={\bigcup }_{\alpha \in \mathrm{Ord}}{V}_{\alpha }$, a proper-class union. Equivalently, $x\in V_{\alpha }$ exactly when the rank of $x$ is less than $\alpha$, where $\mathrm{rank}(x)=\sup \{\mathrm{rank}(z)+1:z\in x\}$.

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.

Induct on $\alpha$. For every $\beta <\alpha$, the induction hypothesis says $\beta \in V_{\beta +1}$, and monotonicity gives $V_{\beta +1}\subseteq V_{\alpha }$. Thus every element of the ordinal $\alpha$ lies in $V_{\alpha }$, so $\alpha \subseteq V_{\alpha }$. Taking its power set givesFor $\alpha =0$ the inclusion is vacuous and $\varnothing \in \mathcal{P}(\varnothing )$ supplies the base case. This argument uses ordinal membership as strict order and the previously proved hierarchy monotonicity.

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.

König's theorem for cardinal numbers states that, for a set-indexed family with ${\kappa }_i<{\lambda }_i$ at every index,Here the sum is the cardinality of a disjoint union and the product is the cardinality of a Cartesian product. Work in ZFC. Choose disjoint sets $A_i$ of sizes ${\kappa }_i$ and sets $B_i$ of sizes ${\lambda }_i$. For any function $f:{⨆}_i{A}_i\to {\prod }_i{B}_i$, its $i$th coordinate values on $A_i$ form a subset of $B_i$ of cardinality at most ${\kappa }_i$. Choose $b_i\in B_i$ outside that subset, using choice. Then $b=(b_i{)}_i$ cannot equal $f(a)$ for any $a$: if $a\in A_j$, its $j$th coordinate was specifically excluded. Thus there is no surjection from the disjoint union onto the product.

Cardinal comparability under choice now implies the displayed strict inequality. Empty index set gives $0<1$ directly; empty individual $A_i$ cause no difficulty, since the corresponding coordinate excludes an empty image. This is the cardinal diagonal theorem, rather than the finitely branching tree result also bearing König's name.

The generalized continuum hypothesis isEquivalently, for every ordinal $\alpha$, $2^{{\aleph }_{\alpha }}={\aleph }_{\alpha +1}$. Here $2^{\kappa }$ is the cardinality of the power set of a set of cardinality $\kappa$, and ${\kappa }^{+}$ is the least strictly larger cardinal. The hypothesis says that no intermediate cardinal lies between an infinite set and its power set.

For GCH arithmetic at aleph omega, let $\kappa ={\aleph }_{\omega }$. Use monotonicity of cardinal exponentiation, the law $(a^b{)}^c=a^{bc}$, and $\kappa \cdot \kappa =\kappa$ for infinite cardinals in ZFC. Since $2\le \kappa \le 2^{\kappa }$,Thus ${\kappa }^{\kappa }=2^{\kappa }$, and the generalized continuum hypothesis yieldsThe lower bound embeds binary-valued functions into $\kappa$-valued ones; the upper bound codes each value by a subset and combines the resulting pairs of indices. In particular the equality before applying the hypothesis is a ZFC equality.

Write again $\kappa ={\aleph }_{\omega }$. The countable cardinal sum ${\sum }_{n<\omega }{\aleph }_n$ equals $\kappa$: it is at least their supremum, and at most ${\aleph }_0\cdot \kappa =\kappa$. König's theorem givesThe latter product injects into $P={\prod }_{n<\omega }{\aleph }_n$ by fixing coordinate zero and putting its $n$th coordinate in coordinate $n+1$. Conversely $P$ injects into the set of all functions $\omega \to \kappa$. ThereforeNo cardinal lies strictly between $\kappa$ and its successor, soThe strict lower bound is essential: replacing the product by the supremum of its factors would incorrectly give ${\aleph }_{\omega }$.

The product from the preceding part injects into ${\kappa }^{{\aleph }_0}$, where $\kappa ={\aleph }_{\omega }$, because each coordinate value is an ordinal below $\kappa$. Combining its strict König lower bound with the exponentiation upper bound givesHenceOnly the instance $2^{{\aleph }_{\omega }}={\aleph }_{\omega +1}$ of the generalized continuum hypothesis was needed in these three computations, though the question assumes the full hypothesis. No assumption that countable exponentiation leaves this singular cardinal unchanged is valid: König's theorem rules that out.

Let $U_1\subseteq U_2$ be transitive classes, both interpreted with actual membership. A formula $\varphi (\bar{x})$ is upward absolute from $U_1$ to $U_2$ if for every tuple of parameters $\bar{a}$ from $U_1$,For proper classes this means the usual relativization of the fixed formula's quantifiers. Full absoluteness requires the implication in both directions. The qualification on parameters matters: the smaller class must contain every object named in the comparison.

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.

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.

Equality with the union is expressed byThe first conjunct says that every member of $x$ lies in some member of $y$; the second gives the reverse inclusion. Every quantifier is bounded by a parameter or by an element of a previously bounded parameter. Therefore bounded absoluteness applies, proving full absoluteness and hence upward absoluteness of $x=\bigcup y$. This only compares the relation for existing parameters; it does not require either class to contain the union of every one of its sets.

A bounded expression for the successor relation isThe first two clauses put $y$ and all its elements into $x$, while the last forbids any additional member of $x$. Extensionality identifies this exactly with $x=y\cup \{y\}$. Since the formula is ${\Delta }_0$, it is absolute in both directions between the transitive classes and therefore upward absolute. This bounded description also justifies the successor computations used earlier in the rank-stage Replacement counterexample.

To prove that power-set equality is not upward absolute, use the standard constructible universe theorem: $L$ is a transitive inner model of ZF containing every ordinal, and set rank is absolute between $L$ and $V$. Since $V\ne L$, some rank stage contains a nonconstructible set. Let $\alpha$ be the least ordinal with $V_{\alpha }⊈L$. It is not zero; it cannot be a limit, since a union of earlier stages contained in $L$ is still contained in $L$. Thus $\alpha =\beta +1$ and $V_{\beta }\subseteq L$.

We need not merely this inclusion, but that $y=V_{\beta }$ itself belongs to $L$. Inside $L$, ZF constructs its own rank stage $(V_{\beta }{)}^L$, which is a set of $L$. By transitivity and rank absoluteness,Consequently $y\in L$. Let $x=(\mathcal{P}(y){)}^L$, the power set computed in $L$. Then $x\in L$ and $L\models x=\mathcal{P}(y)$.

By minimality there is $z\in V_{\beta +1}\setminus L$. Externally $z\subseteq V_{\beta }=y$, but $z\notin x$, because every member of the set $x\in L$ is in the transitive class $L$. Hence $V/\models x=\mathcal{P}(y)$. Taking $U_1=L$ and $U_2=V$ proves power-set equality is not upward absolute, even between transitive models of ZF.

There is no contradiction with absoluteness of $z\subseteq y$: that bounded relation agrees whenever both parameters are present in the smaller class. Power-set equality quantifies over all subsets, including a new $z$ absent from the smaller class. The step proving $V_{\beta }\in L$ is essential; inclusion in a class alone would not imply membership in it.