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

For a set $A$, its definable power set consists of the subsets of $A$ definable by a first-order formula over $(A,\in )$ using finitely many parameters from $A$. The quantifiers range over $A$; this is generally much smaller than its full power set.

The constructible universe is defined by transfinite recursion:The last union denotes a definable proper class, not a set-sized union over a set of all ordinals. At a successor stage, only definitions over the previously constructed stage are permitted.

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 axiom of infinity fails. First prove $L_n=V_n$ for every finite ordinal $n$. The base stage is empty in both hierarchies. If $L_n=V_n$, that stage is a finite set. Every one of its subsets is definable over it with finitely many parameters, by a disjunction of equalities to the selected elements; the empty subset is defined by a false formula. HenceInduction and the limit-stage definitions givethe set of all hereditarily finite sets. Every member of this set is finite externally.

If this transitive structure satisfied the axiom of infinity, it would contain an inductive set $I$: zero belongs to $I$, and whenever $x\in I$, its successor $x\cup \{x\}$ belongs to $I$. These operations are the actual empty set and actual set successor, since they are absolute for this transitive structure and all relevant finite-rank sets lie in it. External induction would then place every finite ordinal in $I$, contradicting the finiteness of $I$.

Every individual finite ordinal does belong to $L_{\omega }$, but the set $\omega$ of all finite ordinals does not. The distinction between containing each finite ordinal and containing one inductive set is precisely the issue.

The cardinal sum is the cardinality of a disjoint union, and the cardinal product is the cardinality of the set of choice functions:Here the cardinals are represented by initial ordinals. Tagging by $\alpha$ makes the summands disjoint even when their underlying sets overlap. For an empty index set the sum is zero and the product is one, because there is exactly one empty function. If any factor in a nonempty product is zero, that product is empty.

This is König theorem for cardinal numbers. Let $D={⨆}_{\alpha <\beta }{\kappa }_{\alpha }$ and $P={\prod }_{\alpha <\beta }{\lambda }_{\alpha }$. For any proposed map $g:D\to P$, consider the values of the $\alpha$th coordinates on the $\alpha$th summand:This set has cardinality at most ${\kappa }_{\alpha }<{\lambda }_{\alpha }$. Choose $y_{\alpha }\in {\lambda }_{\alpha }\setminus E_{\alpha }$, using the axiom of choice, and assemble $y=(y_{\alpha })\in P$. For any $(\alpha ,\xi )\in D$, its image disagrees with $y$ at coordinate $\alpha$. Thus $y$ is outside the image of $g$, and no such $g$ is surjective.

Every ${\lambda }_{\alpha }$ is nonzero. The product is nonempty by choice; if $D$ is empty, strict inequality is immediate. Otherwise cardinal comparability principle in ZFC says that $|P|\le |D|$ would yield a surjection from $D$ onto the nonempty $P$, which the diagonal argument excludes. ThereforeThe diagonal coordinate is tied to the summand containing the argument; this is why a sum on the left pairs naturally with a product on the right.

The aleph numbers enumerate the infinite initial ordinals by transfinite recursion:Here ${\kappa }^{+}$ is the least cardinal strictly larger than $\kappa$. The Generalized continuum hypothesis isequivalently $2^{{\aleph }_{\alpha }}={\aleph }_{\alpha +1}$ for every ordinal $\alpha$ in ZFC.

Constant functions give the lower bound ${\aleph }_2\le {\aleph }_2^{{\aleph }_0}$. By the Generalized continuum hypothesis, ${\aleph }_2=2^{{\aleph }_1}$. The currying law for cardinal exponentiation and infinite cardinal arithmetic therefore giveHence $\boxed{{\aleph }_2^{{\aleph }_0}={\aleph }_2}$.

Put $\kappa ={\aleph }_{\omega }$. Apply König theorem for cardinal numbers to the sequences ${\aleph }_n<{\aleph }_{n+1}$:The sum is $\kappa$ because the countable union has cardinality at most $\kappa$ and its summands are cofinal in $\kappa$. Thus the power is strictly larger than $\kappa$, a fact that cannot be replaced by the regular-cardinal calculation of the preceding part.

For an upper bound, use $\kappa \le 2^{\kappa }$ and the currying law for cardinal exponentiation:where the last step is GCH at $\kappa$. There is no cardinal strictly between $\kappa$ and its successor, so

For $\kappa ={\aleph }_{\omega }$, monotonicity of cardinal exponentiation givesThe middle equality uses the currying law for cardinal exponentiation, and the final one uses ${\aleph }_0\cdot \kappa =\kappa$. Hence ${\aleph }_0^{\kappa }=2^{\kappa }$, even before assuming GCH. Applying the Generalized continuum hypothesis yields

The membership induction theorem is the following schema, for every formula $\phi (x)$ with any fixed set parameters:Its hypothesis says the property is progressive under membership. In ZF it follows from the Axiom of foundation: if a counterexample $x$ exists, take the nonempty set of counterexamples in the transitive closure $\mathrm{TC}(\{x\})$, which contains $x$. A membership-minimal counterexample supplied by the Axiom of foundation has no counterexample among its elements, contradicting progressivity. The transitive closure ensures that all elements relevant to this argument remain in the set being considered.

Compose the two assumed isomorphisms to obtain a membership-preserving and membership-reflecting bijectionTransitivity of both targets implies, for every $a\in M_1$,For one inclusion use preservation of membership. For the other, if $c\in f(a)$, transitivity puts $c$ in $M_2$; surjectivity gives $c=f(b)$ for $b\in M_1$, and reflection gives $b\in a$.

Apply the membership induction theorem to the assertion that every $a\in M_1$ is fixed. If all members $b$ of $a$ are fixed, the displayed equation gives $f(a)=a$. Thus $f$ is the identity on $M_1$. Its range is $M_2$, so $M_1=M_2$, and the definition of $f$ givesThis proves uniqueness of the Mostowski collapse theorem. Existence of the two isomorphisms already supplies the membership structure needed in this argument.

Read epsilon as actual set membership restricted to $X$, the interpretation in which ambient ZF makes the relation well-founded. The structure's axiom of extensionality assumption meansBy well-founded recursion on membership, defineThe recursion theorem applies because the Axiom of foundation makes the restricted relation well-founded and each predecessor collection is a set. The Axiom schema of replacement gives the set $M=\pi [X]$.

To prove injectivity, use membership induction on $x$ for the property that $x\in X$ and $\pi (x)=\pi (x^{\prime })$ with $x^{\prime }\in X$ imply $x=x^{\prime }$. Suppose this property holds for every $y\in x\cap X$. Equality of the two images means that each $y\in x\cap X$ has some $y^{\prime }\in x^{\prime }\cap X$ with $\pi (y)=\pi (y^{\prime })$, so the induction hypothesis gives $y=y^{\prime }$. Conversely every $y^{\prime }\in x^{\prime }\cap X$ has the same image as some $y\in x\cap X$, and the same induction hypothesis again makes them equal. Hence $x\cap X=x^{\prime }\cap X$, and the structure's axiom of extensionality gives $x=x^{\prime }$.

The map is onto $M$ by definition. The recursion immediately preserves membership, and its injectivity makes membership reflection valid as well. Moreover if $z\in \pi (x)$ then $z=\pi (y)$ for a predecessor $y\in X$, so $z\in M$. Therefore $M$ is transitive and $\pi$ is the required membership isomorphism. This proves the existence direction of the Mostowski collapse theorem.

An arbitrary binary relation must also be well-founded. Axiom of extensionality alone is insufficient in that interpretation: the one-element relation with a self-loop is extensional, but any collapse onto a transitive set would produce a set containing itself, contrary to Axiom of foundation. The actual-membership interpretation above supplies precisely the hypothesis otherwise missing; no analogous claim is made for a general ill-founded relation.

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.

Assume a nonempty set $a$ has no membership-minimal element, so for every $x\in a$ there is $y\in x\cap a$. Consider the formula $\phi (x)\equiv x\notin a$.

It is progressive: if every element of $x$ is outside $a$ but $x\in a$, the assumed absence of a minimal element supplies $y\in x\cap a$, contradicting that hypothesis. The membership induction theorem therefore implies $x\notin a$ for every set $x$. This contradicts $a\ne \varnothing$.

Thus every nonempty set $a$ contains an element $x$ with $x\cap a=\varnothing$, exactly the Axiom of foundation:Only the induction schema and elementary set reasoning were needed; no prior use of Axiom of foundation occurs in the proof.