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

Here $Z{F}^{\ast }$ denotes ZF without foundation. Transfinite recursion on ordinals defines the cumulative hierarchy byThe associated class is $V=\{x:\exists \alpha \in \mathrm{Ord}(x\in V_{\alpha })\}$. Each level is a set, while $V$ is a definable class. Without Foundation it need not contain every ambient set; it consists of the sets built by this well-founded hierarchy.

Use transfinite induction. The inclusion at zero is immediate. If $V_{\beta }\subseteq V_{\beta +1}$, monotonicity of the power set givesIf $\alpha$ is a limit and $x\in V_{\alpha }$, choose $\beta <\alpha$ with $x\in V_{\beta }$. The inductive inclusion $V_{\beta }\subseteq \mathcal{P}(V_{\beta })$ means that $x\subseteq V_{\beta }\subseteq V_{\alpha }$. Thus $x\in \mathcal{P}(V_{\alpha })=V_{\alpha +1}$. This proves $V_{\alpha }\subseteq V_{\alpha +1}$ for every ordinal. These successive inclusions and the union definition also give $V_{\beta }\subseteq V_{\alpha }$ whenever $\beta \le \alpha$.

The preceding inclusion is exactly $V_{\alpha }\subseteq \mathcal{P}(V_{\alpha })$. Therefore every $x\in V_{\alpha }$ is a subset of $V_{\alpha }$. Equivalently,which says that $V_{\alpha }$ is a transitive set. This uses the power set definition and the proved inclusion, without any ambient use of Foundation.

We prove the stronger ordinal identityby transfinite induction. It holds at zero. At a successor stage an ordinal $\gamma$ belongs to $\mathcal{P}(V_{\beta })$ exactly when every $\delta <\gamma$ belongs to $V_{\beta }$. By induction this means every $\delta <\gamma$ is less than $\beta$, equivalently $\gamma \le \beta$. Thus the ordinals in $V_{\beta +1}$ are precisely those less than $\beta +1$. At a limit the identity follows by taking unions.

Every $\beta <\alpha$ consequently belongs to $V_{\alpha }$, so $\alpha \subseteq V_{\alpha }$ and $\alpha \in \mathcal{P}(V_{\alpha })=V_{\alpha +1}$. But $\alpha \notin V_{\alpha }$, since an ordinal is not less than itself. HenceThe only well-foundedness used is that of the ordinal order, available independently of Foundation for arbitrary ambient sets.

Every set is a subset of itself, so $V_{\alpha }\subseteq V_{\alpha }$. By the successor definition,Membership and inclusion are different statements here; this argument establishes membership of the whole level in its successor.

The class $V$ is transitive because all its levels are transitive. Let $a\in V$ be nonempty. There is a least ordinal $\alpha$ for which $a\cap V_{\alpha }\ne \varnothing$: existence follows by choosing an element of $a$, which lies in $V$, and then minimizing within some witnessing ordinal bound. The least ordinal is neither zero nor a limit, so write $\alpha =\beta +1$. Choose $x\in a\cap V_{\beta +1}$. Then $x\subseteq V_{\beta }$, while minimality gives $a\cap V_{\beta }=\varnothing$. Thus $a\cap x=\varnothing$. Also $x\in V$, proving Foundation inside $⟨V,\in ⟩$.

By the given hypothesis this same class satisfies every axiom of $Z{F}^{\ast }$, and hence it satisfies every axiom of $ZF$. Translate any finite formal $ZF$ proof by restricting each quantifier to the definable class $V$. Within $Z{F}^{\ast }$ the translated axioms have proofs, logical steps remain valid, and the translated contradiction is still a contradiction. Substituting those axiom proofs therefore converts the original derivation effectively into a finite derivation of contradiction from $Z{F}^{\ast }$. Equivalently,This is the syntactic relative-consistency construction; it does not assume that $V$ is a set or that it equals the whole ambient universe.

The transitive closure $\mathrm{TC}(a)$ is the least transitive set containing $a$ as a subset. Put $a_0=a$, $a_{n+1}=\bigcup a_n$ and defineRecursion and Replacement give the set of iterates, and Union gives its union. It contains $a=a_0$ as a subset. If $u\in v\in \mathrm{TC}(a)$, then $v\in a_n$ for some $n$, so $u\in a_{n+1}\subseteq \mathrm{TC}(a)$; hence it is transitive.

If $T$ is transitive with $a\subseteq T$, induction gives $a_n\subseteq T$ for every $n$, because $\bigcup T\subseteq T$. Therefore $\mathrm{TC}(a)\subseteq T$. This proves minimality and uniqueness. If the alternative convention asks for the least transitive set containing $a$ as an element, that set is $\mathrm{TC}(\{a\})$.

The membership induction principle is the schemaallowing fixed parameters in $\phi$.

Suppose the progressiveness hypothesis holds but $\neg \phi (a)$. The transitive set $T=\mathrm{TC}(\{a\})$ contains $a$. Separation gives the nonempty set $B=\{x\in T:\neg \phi (x)\}$. By Foundation choose $b\in B$ with $b\cap B=\varnothing$. Every $y\in b$ belongs to $T$ because it is a transitive set and cannot belong to $B$, so every such $y$ satisfies $\phi$. Progressiveness now gives $\phi (b)$, a contradiction. Thus the principle holds. The transitive closure is needed to turn a possibly proper class of counterexamples into a set to which Foundation applies.

An $\in$-isomorphism is a bijection $f:X\to Y$ such that $x\in x^{\prime }$ if and only if $f(x)\in f(x^{\prime })$ for all $x,x^{\prime }\in X$. When $Y$ is transitive, surjectivity gives the stronger recursive descriptionIndeed every member of $f(x)$ belongs to $Y$ because it is a transitive set and so has a preimage in $X$; the isomorphism property identifies exactly which preimages occur.

If $f,g$ are two such maps, possibly to different transitive sets, form $B=\{x\in X:f(x)\ne g(x)\}$. If $B$ were nonempty, Foundation would give $x\in B$ with $x\cap B=\varnothing$. All predecessors $u\in x\cap X$ then satisfy $f(u)=g(u)$, and the recursive descriptions force $f(x)=g(x)$, a contradiction. Therefore the map and its transitive range are unique.

The necessary and sufficient condition is that $⟨X,\in ⟩$ be well-founded and extensional as a relation on $X$. Well-foundedness says every nonempty $A\subseteq X$ has a member with no $\in$-predecessor in $A$. The extensional relation condition says distinct elements $x,x^{\prime }\in X$ have distinct predecessor sets $x\cap X$, $x^{\prime }\cap X$. Sufficiency is the Mostowski collapse theorem.

For necessity, an isomorphism transfers well-foundedness from its transitive range, where Foundation applies. For extensionality, if $x\cap X=x^{\prime }\cap X$, the recursive descriptions give $f(x)=f(x^{\prime })$, and injectivity gives $x=x^{\prime }$. Notice that ambient axiom of extensionality alone does not establish this internal predecessor condition; for example $X=\{\{0\},\{2\}\}$ can have distinct elements with no predecessors in $X$.

A cardinal number is an initial ordinal: an ordinal not in bijection with any smaller ordinal. In $ZFC$ every set has the cardinality of a unique such ordinal.

For an infinite cardinal $\kappa$, its cofinality is the least cardinality of an unbounded subset of the ordinal $\kappa$. Equivalently,A subset is unbounded when no ordinal below $\kappa$ bounds all its elements. A cofinal sequence can be taken increasing, and $\mathrm{cf}(\kappa )$ is an infinite regular cardinal.

König theorem for cardinal numbers says that for families of cardinals ${\kappa }_i<{\lambda }_i$ indexed by a set $I$,The sum is the cardinality of the disjoint union of sets $A_i$ of sizes ${\kappa }_i$, and the product is the cardinality of ${\prod }_i{B}_i$ for sets of sizes ${\lambda }_i$.

Consider any function $F:{⨆}_i{A}_i\to {\prod }_i{B}_i$. For each $i$, the set of $i$th coordinates of images of points from the $i$th block has cardinality at most ${\kappa }_i<{\lambda }_i$. Choose $b_i\in B_i$ outside it. Then $b=(b_i{)}_i$ is not the image of any point: a point from block $i$ has the wrong $i$th coordinate. Thus there is no surjection from the sum set onto the product set. Cardinal comparability in $ZFC$ makes the inequality strict in the indicated direction. For the empty index set the statement is $0<1$, also true. This is the diagonal argument underlying the inequality.

First derive the standard consequence of König theorem for cardinal numbers that every infinite cardinal $\rho$ satisfiesLet $\theta =\mathrm{cf}(\rho )$ and take cofinal ordinals ${\alpha }_i<\rho$, $i<\theta$. Put ${\rho }_i=\max (1,|{\alpha }_i|)<\rho$. Their sum is $\rho$: it is at least the size of the union of the cofinal ordinals and at most $\rho \cdot \theta =\rho$. Choose the next larger cardinal ${\rho }_i^{+}\le \rho$. König theorem for cardinal numbers givesThis also covers $\rho ={\aleph }_0$, using finite cardinals and their next larger finite cardinals.

Suppose $\lambda ={\kappa }^{\mu }$ with both $\kappa ,\mu$ infinite. Infinite cardinal multiplication givesIf $\mathrm{cf}(\lambda )\le \mu$, monotonicity of exponentiation would contradict the preceding strict inequality for $\rho =\lambda$. Thus $\mathrm{cf}(\lambda )>\mu \ge {\aleph }_0$. This direction does not require GCH.

Conversely assume GCH and $\mathrm{cf}(\lambda )>{\aleph }_0$. Every function $\omega \to \lambda$ has bounded range. For each infinite cardinal $\nu <\lambda$, GCH givesFinite bounded ranges are also covered by the bound ${\aleph }_0^{{\aleph }_0}\le {\aleph }_1\le \lambda$. Counting functions according to an ordinal bound on their range now gives ${\lambda }^{{\aleph }_0}\le \lambda \cdot \lambda =\lambda$. Constant functions give the reverse inequality. Thereforewhich is the required representation with $\kappa =\lambda$, $\mu ={\aleph }_0$. This proves both directions.

For a set $A$, its definable power set isOnly finitely many parameters occur in each definition. Satisfaction for the set structure is definable, so this specifies a uniformly definable class function assigning a set to every set $A$, with $\mathrm{Def}(A)\subseteq \mathcal{P}(A)$. Every subset definable over the structure with its parameters occurs. The full set $A$ itself occurs by the formula $x=x$. If $A$ is transitive, then $A\subseteq \mathrm{Def}(A)$, since any $p\in A$ is defined as a subset of $A$ by $x\in p$. In that case $\mathrm{Def}(A)$ is transitive as well: a member of one of its elements lies in $A$, hence in $\mathrm{Def}(A)$.

The constructible hierarchy and universe areThe displayed properties prove by induction that levels are transitive and increasing, so $L$ is transitive. It contains every ordinal: inductively $L_{\alpha }\cap \mathrm{Ord}=\alpha$, and the subset of $L_{\alpha }$ consisting of ordinals is definable there, giving $\alpha \in L_{\alpha +1}$. Ordinalhood is absolute here because the levels are transitive. Both the level function and membership in $L$ are definable in $ZF$. This is Gödel's constructible universe, which can contain fewer subsets than the full universe.

For each $x\in a$, let ${\beta }_x$ be the least ordinal with $x\in L_{{\beta }_x}$. It exists because $a\subseteq L$, and it is uniquely definable. Replacement therefore gives the set $\{{\beta }_x:x\in a\}$. Choose an ordinal $\alpha$ at least their supremum. Increasingness of the hierarchy givesIf $a$ is empty, $\alpha =0$ works. No assumption that $a$ itself belongs to $L$ is used; it is enough that its elements do.

Fix $a\in L$. In the ambient universe, Separation forms the setIt is a set of constructible sets, so the previous part gives an ordinal bound on all its members. Increase the bound to a level $L_{\beta }$ also containing $a$. Transitivity ensures $a\subseteq L_{\beta }$. ThenThe inclusion test is absolute for the transitive level $L_{\beta }$, since all members of $x$ and $a$ lie there. The right side is consequently a subset definable over $L_{\beta }$ with parameter $a$, soFor $x\in L$, transitivity of the constructible universe makes internal and ambient subsethood of $a$ agree. Hence $L$ satisfies that $S$ consists exactly of all its subsets of $a$. This is the Power set Axiom in $⟨L,\in ⟩$. It is not the assertion that every ambient subset of $a$ belongs to $L$.

Use the constructible universe theorem that $L$ satisfies $ZFC$ and GCH. In particular, internally it has a bijectionThis bijection belongs to $L$ and is also an actual bijection in the ambient universe, because its domain, range and graph are transitive-model sets with the same membership relation.

We must compare the ordinals rather than assume cardinality is absolute. Every ordinal below ${\omega }_1^L$ is countable in $L$, and its witnessing enumeration belongs to the ambient universe too. Thus every such ordinal is countable externally, proving ${\omega }_1^L\le {\omega }_1$. Consequently the ambient cardinality of the constructible reals is at most ${\aleph }_1$.

If every subset of $\omega$ were constructible, the displayed bijection would enumerate the full ambient power set using at most ${\aleph }_1$ points. This contradicts the assumption $2^{{\aleph }_0}={\aleph }_2$. ThereforeThe argument permits ${\omega }_1^L$ to be strictly smaller than the ambient ${\omega }_1$, exactly the cardinal-absoluteness issue highlighted in the source.