Past exam of the mathematics course of the University of Cambridge / 2012 / iii / Paper 83 (Set Theory)

Here the power set notation gives $xEy⟺\mathcal{P}(x)\subseteq y$. Suppose a nonempty set $A$ has no $E$-minimal member. Form its intersection $b=\bigcap A$. This is a set: for any one $a_0\in A$, use the axiom schema of separation inside $a_0$ to define the elements common to all members of $A$. Selecting a single witness to nonemptiness is not an application of the axiom of choice.

For an arbitrary $y\in A$, lack of minimality supplies some $x\in A$ with $\mathcal{P}(x)\subseteq y$. Since $b\subseteq x$, every subset of $b$ is a subset of $x$, soThis conclusion holds for each $y\in A$, without choosing all the corresponding $x$ simultaneously. Intersecting over $y$ gives $\mathcal{P}(b)\subseteq b$.

For completeness, the contradiction in Cantor's theorem is completely explicit here. By the axiom schema of separation put $d=\{u\in b:u\notin u\}$. Then $d\in \mathcal{P}(b)\subseteq b$, and consequentlywhich is impossible. Thus no such $A$ exists:This power-set-predecessor relation proof uses neither a descending sequence nor a comparison of possibly non-well-orderable cardinalities. It proves well-foundedness directly from the minimal-member definition.

Order the collection $\mathrm{Ch}(P)$ of every chain in a partial order, including the empty chain, by inclusion. Suppose that $j:\mathrm{Ch}(P)\to P$ is an order-preserving function and an injection. Let $\theta =h(P)$ be the Hartogs ordinal: by Hartogs theorem, no injection from $\theta$ to $P$ exists.

Use transfinite recursion to define, for $\alpha <\theta$,We verify both that $j(C_{\alpha })$ is defined and that the values are strictly increasing. Assume inductively that the earlier values are strictly increasing. Then $C_{\alpha }$ is a chain in a partial order. For any $\beta <\alpha$, $C_{\beta }\subseteq C_{\alpha }$, so the fact that $j$ is order-preserving gives $p_{\beta }\le p_{\alpha }$. Furthermore $p_{\beta }\in C_{\alpha }$, whereas $p_{\beta }\notin C_{\beta }$ by distinctness of the earlier values. Thus $C_{\beta }\ne C_{\alpha }$, and injectivity gives $p_{\beta }\ne p_{\alpha }$. We have provedThe empty initial chain starts the induction, and the same argument applies at every limit ordinal.

If a globally defined recursion rule is desired, apply $j$ when the earlier range is a chain and otherwise use the fixed value $j(\varnothing )$. The induction shows that the fallback case never occurs. Thus no choices of new points are being made: the function $j$ uniquely determines every stage.

The resulting function $\alpha \mapsto p_{\alpha }$ is an injection from $\theta$ to $P$, contrary to its defining Hartogs ordinal property. Hence the chain-poset nonembedding lemma gives

We work in the ambient theory ZFC for this question. Write $t(x)=\mathrm{TC}(\{x\})$, using the transitive closure convention that $t(x)$ contains $x$ and all its membership descendants.

First construct a set containing exactly the intended objects. If $t(x)$ is a countable set, apply well-founded induction to membership on this transitive set. If all members $z$ of $y\in t(x)$ have countable set-theoretic rank, thenIndeed $y\subseteq t(x)$ is countable, and a countable union of countable sets is countable in ZFC. The induction therefore gives $\mathrm{rank}(x)<{\omega }_1$. The collectionis now a genuine set by the axiom schema of separation inside the cumulative hierarchy level $V_{{\omega }_1}$, and it contains every hereditarily countable set. It is a transitive set, since $y\in x$ implies $t(y)\subseteq t(x)$.

If $a$ is a countable subset of $C$, thenThe right side is countable, so $a\in C$. Thus $C$ has countable-subset closure. This proves existence of a set with the required closure before taking any intersection.

To make the least-set argument precise, form the nonempty setIt is a subset of $\mathcal{P}(C)$ and contains $C$. Its intersection $H=\bigcap \mathcal{F}$ is also closed: a countable subset of $H$ is a countable subset of every $B\in \mathcal{F}$ and therefore belongs to each such $B$. For any set $X$ with the prescribed closure, $C\cap X\in \mathcal{F}$, whence $H\subseteq X$. This is leastness among all such sets, not just among subsets of $C$.

Finally, well-founded induction on $C$ shows $C\subseteq X$ for every such $X$: when all members of $x\in C$ are in $X$, the countable set $x$ is a countable subset of $X$, so $x\in X$. Hence $H=C$, proving that the definition gives precisely

For the cardinal bound, code the entire countable membership ancestry. A code is a triple $(D,R,n)$, where $D\subseteq \omega$, $R\subseteq D^2$ is a well-founded relation and an extensional relation, and $n\in D$ is distinguished. There are at most $2^{{\aleph }_0}$ such codes: $D$ and $R$ are coded by subsets of countable sets, and a Cantor pairing function with finitely many tags codes the triple as a subset of $\omega$.

The well-founded recursiondefines its collapse, as in the Mostowski collapse theorem. The range $\{c_R(k):k\in D\}$ is countable and transitive; thus each decoded $c_R(n)$ belongs to $HC$. Conversely, for $x\in HC$, choose a bijection $e:D\to t(x)$ and the point $n$ with $e(n)=x$. Set $lRk$ exactly when $e(l)\in e(k)$. Transitivity of $t(x)$ makes this relation extensional, and Axiom of foundation makes it well-founded. The recursion then gives $c_R(k)=e(k)$, so this code decodes to $x$.

We have a surjection from a set of at most continuum many codes onto $HC$. Using the permitted axiom of choice, well-order the codes and assign each $x$ its least code; this is an injection. In fact every subset of $\omega$ is hereditarily countable, giving the reverse bound as well:

Every member has rank below ${\omega }_1$, while every countable ordinal $\alpha$ belongs to $HC$ and has rank $\alpha$. Consequently

The axioms hold except Power Set. axiom of extensionality and Axiom of foundation are inherited by this transitive structure. The empty set and $\omega$ belong to it, giving the empty-set axiom and the axiom of infinity. The axiom of pairing follows from countable-subset closure. For $a\in HC$, $\bigcup a$ is a countable subset of $HC$, giving the Axiom of union. Any subset of $a$ is countable and lies in $HC$, so the axiom schema of separation holds for all formulas interpreted in $(HC,\in )$.

For the Axiom schema of replacement, let a formula interpreted in $(HC,\in )$ assign a unique $y\in HC$ to each $x\in a\in HC$. Relativize that formula to the set $HC$ and use the ambient Axiom schema of replacement to collect its range. The range is countable and consists of members of $HC$, hence belongs to $HC$. The same argument, selecting one witness for each member of the countable domain, proves axiom schema of collection. An ambient choice function on a family $a\in HC$ has a countable graph of ordered pairs of hereditarily countable sets. Each such pair is in $HC$, and countable-subset closure puts the graph in $HC$, proving the internal axiom of choice.

However, all external subsets of $\omega$ are elements of $HC$. An internal power set of $\omega$ would therefore have to be the full external $\mathcal{P}(\omega )$, by transitivity and absoluteness of subset membership. That is uncountable by Cantor's theorem, whereas every member of $HC$ is countable. Thus the axioms satisfied by hereditarily countable sets areHere the asserted axiom list includes both Axiom schema of replacement and axiom schema of collection; no equivalence relying on Power Set is being silently invoked.

Put $\kappa =|X|$, an infinite cardinal number. The original PDF has the double exponent $2^{2^{|X|}}$; the single-exponent expression in the TeX aid is a transcription error.

We explicitly construct an independent family of subsets with $2^{\kappa }$ members on a set of size $\kappa$. LetFor each finite $s$ there are finitely many possibilities for $H$. The collection of finite subsets of an infinite cardinal has size $\kappa$, so $|D|\le \kappa$; the points $(\{\xi \},\varnothing )$ give the reverse bound. Thus $|D|=\kappa$.

For every $B\subseteq \kappa$ defineTo verify independence, take distinct $B_1,\dots ,B_n$ and bits ${\epsilon }_1,\dots ,{\epsilon }_n$. For each pair $i<j$, choose a point of $B_i△B_j$ and let $s$ contain all these finitely many points. The traces $B_i\cap s$ are pairwise distinct. SetThen $(s,H)\in A_{B_i}$ exactly for those $i$ with ${\epsilon }_i=1$. Every finite Boolean pattern is therefore realized. The cases $n=0,1$ work by the same definition, allowing $s=\varnothing$. In particular the sets $A_B$ are all distinct, so the finite-trace independent family construction gives exactly $2^{\kappa }$ independent members.

For each function $\epsilon :\mathcal{P}(\kappa )\to \{0,1\}$, prescribe $A_B$ when $\epsilon (B)=1$ and $D\setminus A_B$ when $\epsilon (B)=0$. Independence gives the finite intersection property. Their finite intersections generate a proper filter on a set: its members are the subsets of $D$ containing one of those intersections.

To extend this to an ultrafilter, order its proper filter extensions by inclusion. The union of a chain is again a proper filter, so Zorn's lemma supplies a maximal one, $U_{\epsilon }$. If neither a subset $Y$ nor its complement belonged to this filter, adjoining $Y$ would still generate a proper filter: otherwise some existing member would be disjoint from $Y$ and force its complement into the filter already. Maximality therefore gives the ultrafilter dichotomy. Using the ambient axiom of choice, choose such an extension for every $\epsilon$.

Distinct functions differ at some $B$. Their ultrafilters respectively contain $A_B$ and its complement, and cannot be equal. There are $2^{2^{\kappa }}$ such functions. Transporting the ultrafilters along a bijection $D\to X$ proves the lower bound. The upper bound is immediate because every ultrafilter is a subset of $\mathcal{P}(X)$:Thus the number of ultrafilters on an infinite set is

The maximum is $2^{{\aleph }_1}$. We construct that many aleph-one-like linear orders, whose proper initial segments are countable, and prove that they are nonisomorphic. As usual the rational-type requirement concerns nonempty proper initial segments; the empty segment occurs in every order.

Let $D$ be the club set of nonzero limit ordinals below ${\omega }_1$. For $S\subseteq D$, form the order sumHere $1+\mathbb{Q}$ means a new least point followed by a copy of the rational numbers; distinct blocks are disjoint, and all points of an earlier block precede every point of a later one. Every block is countable, dense and has no greatest point. Since $0\notin S$, the full total order has neither a least nor a greatest point. It has size ${\aleph }_1$.

The sum is dense: within a block use density, and for points in different blocks choose a larger point in the earlier block. If $I$ is a proper initial segment and $y\notin I$ lies in block $\alpha$, then $I$ is contained in the union of the blocks through $\alpha$. There are only countably many such blocks, each countable. Thus $I$ is countable, rather than an uncountable interval in an aleph-one-dense order.

Every nonempty $I$ is dense and has no least point. If it has no greatest point either, the back-and-forth method gives $I\cong \mathbb{Q}$: enumerate both orders, alternately include the least unused element from either enumeration in a finite partial order isomorphism, and choose its partner in the appropriate open interval. Density and absence of endpoints always supply a new partner. The union is a bijective order isomorphism. If $I$ has a greatest point, remove it, apply the same argument, and reattach it. Hence every nonempty proper initial segment is isomorphic to $\mathbb{Q}$ or $\mathbb{Q}+1$.

The stationary information is recorded at the limit cuts. WriteThis is a continuous increasing kappa-filtration by countable initial segments. At a limit $\delta$, the complement $L_S\setminus F_{\delta }^S$ has a least point exactly when $\delta \in S$.

Suppose $f:L_S\to L_T$ is an order isomorphism. Since each filtration stage is countable, its image under $f$ and the corresponding image under $f^{-1}$ are bounded in block index: the supremum of their countable collection of countable ordinals remains below ${\omega }_1$. Choose $g(\alpha )<{\omega }_1$ so thatThe setis a club set. To see unboundedness, start above any given ordinal and recursively choose ${\gamma }_{n+1}>{\gamma }_n$ larger than every $g(\alpha )$ for $\alpha \le {\gamma }_n$. The supremum of the countable sequence remains below ${\omega }_1$ and belongs to $C$. Closure follows because below a limit of members of $C$, each fixed $\alpha$ lies below one of those members.

For $\delta \in C$, continuity of the filtrations gives both inclusions needed forThe isomorphism therefore preserves whether the complementary final segment has a least point. ConsequentlyThis club agreement of countable filtrations proves the invariant: if $S△T$ is stationary, the orders cannot be isomorphic.

We also construct enough pairwise different stationary encodings. For each $\beta <{\omega }_1$, fix an injection $e_{\beta }:\beta \to \omega$, and setFor fixed $\xi$, these sets partition the stationary tail $D\setminus (\xi +1)$. At least one $A_{\xi ,n}$ is stationary: otherwise choose a club avoiding each one and intersect the countably many clubs to obtain a club avoiding the entire tail. The countable-intersection fact follows directly: above any starting point choose an increasing sequence, visiting each club infinitely often; its countable supremum belongs to every club by closure. For each $\xi$ let $n(\xi )$ be the least such $n$. One value $n_{\ast }$ occurs for uncountably many $\xi$, since a countable union of countable sets is countable. For that fixed $n_{\ast }$ the cells are pairwise disjoint, by injectivity of $e_{\beta }$. Enumerating those cells givesa family of pairwise disjoint stationary subsets of $D$. This is the explicit Ulam matrix on omega-one proof of disjoint stationary subsets of omega-one.

For $A\subseteq {\omega }_1$ put $S(A)={\bigcup }_{\eta \in A}{S}_{\eta }$. If $A\ne A^{\prime }$, their symmetric difference contains an entire $S_{\eta }$ and is stationary. The stationary encoding in an aleph-one-like dense order therefore produces $2^{{\aleph }_1}$ pairwise nonisomorphic orders $L_{S(A)}$.

Finally, on a fixed carrier of size ${\aleph }_1$, every total order is a subset of its Cartesian square. That square has size ${\aleph }_1$, so there are at most $2^{{\aleph }_1}$ possible relations. Thus

An Aronszajn tree is a set-theoretic tree of height ${\omega }_1$, with countable levels and no uncountable chain in a partial order, equivalently no cofinal branch. The strict predecessors of a node are well-ordered, and its height is their order type. Such trees exist in ZFC, as the following rationally labelled Aronszajn tree construction shows.

We build countable nonempty levels $T_{\alpha }$ for all $\alpha <{\omega }_1$. A node $t\in T_{\alpha }$ is a strictly increasing function $t:\alpha \to \mathbb{Q}\cap (0,1)$, and the tree order is proper initial-segment extension. Every restriction $t\upharpoonright \beta$ must lie in $T_{\beta }$. Give nonempty $t$ the rational labeland give the empty root label $0$. We require labels to increase strictly along the tree. We also maintain the bounded rational extension property:Keeping room below every rational cap is what makes the limit step possible.

Start with $T_0=\{\varnothing \}$. At a successor stage, for every $s\in T_{\alpha }$ and every rational $r$ with $\ell (s)<r<1$, includein $T_{\alpha +1}$. Its label is $r$, strictly larger than its predecessor's. This level is countable. To extend an earlier node below a prescribed cap $q$, first extend to $T_{\alpha }$ below $q$ by the inductive property, if necessary, then choose a new rational label between that label and $q$. Thus the extension property is preserved.

Now let $\lambda <{\omega }_1$ be a nonzero limit. The whole tree below $\lambda$ is countable. For each pair $(s,q)$ with $s\in T_{\beta }$, $\beta <\lambda$, and $\ell (s)<q<1$, construct one node at height $\lambda$ extending $s$ below $q$. There are only countably many such pairs.

Choose a rational $r$ with $\ell (s)<r<q$ and an increasing sequenceSet $s_0=s$. Given $s_n\in T_{{\alpha }_n}$ with $\ell (s_n)<r$, setThis is rational and satisfies $\max \{\ell (s_n),r-1/(n+1)\}<r_n<r$. The successor rule supplies $u_n=s_n^{⌢}{r}_n$ at height ${\alpha }_n+1$. If ${\alpha }_{n+1}={\alpha }_n+1$, take $s_{n+1}=u_n$; otherwise use the already established extension property below $\lambda$ to extend $u_n$ to $s_{n+1}\in T_{{\alpha }_{n+1}}$ with label below $r$.

The union $t={\bigcup }_n{s}_n$ has domain $\lambda$ and extends $s$. It is strictly increasing, and every shorter restriction is already in its prescribed level. All its values are below $r$, while it contains the values $r_n>r-1/(n+1)$. HenceEvery predecessor's label is below the label of some $s_n$, and hence below $r$. Thus strict increase of labels survives at the limit. Include one such $t$ for each pair $(s,q)$ in $T_{\lambda }$, discarding duplicates. This gives a countable level and preserves every bounded extension requirement. In particular applying it to the root makes the level nonempty. The choices here are permitted by the ambient axiom of choice; transfinite recursion through the set ${\omega }_1$ completes the construction.

Put $T={\bigcup }_{\alpha <{\omega }_1}{T}_{\alpha }$. A node of domain $\alpha$ has exactly the restrictions of domains $\beta <\alpha$ as predecessors, so its height is $\alpha$. Therefore $T$ has height ${\omega }_1$ and countable levels. Since $\ell :T\to \mathbb{Q}$ is strictly increasing on comparable nodes, an uncountable chain would inject into the countable set $\mathbb{Q}$, which is impossible. Each label fiber is a tree antichain, so the tree is even a special Aronszajn tree: