Past exam of the mathematics course of the University of Cambridge / 2012 / iii / Paper 83 / 1

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