Past exam of the mathematics course of the University of Cambridge / 2007 / iii / Paper 26 / 2

Order the collection $\mathrm{Ch}(P)$ of all chains in a partial order, including the empty chain, by inclusion. Suppose that $f:\mathrm{Ch}(P)\to P$ were an order-preserving injection. The chain-poset nonembedding lemma follows by a transfinite recursion of length the Hartogs ordinal $h(P)$:Inductively, the previously constructed points form a strictly increasing chain. If $\beta <\alpha$, then $C_{\beta }⊊C_{\alpha }$, since $p_{\beta }$ belongs to the latter but not the former. Monotonicity gives $p_{\beta }\le p_{\alpha }$, and injectivity makes this inequality strict. Thus the recursion continues at every $\alpha <h(P)$ and gives an injection $h(P)\to P$, contradicting the defining property of the Hartogs ordinal. Therefore $\boxed{\mathrm{Ch}(P)\text{ has no order-preserving embedding into }P.}$ The empty chain is part of the convention: excluding it would make a one-point poset a counterexample.

Suppose a nonempty set $S$ had no minimal member for the intersection-power-set predecessor relation. Put $b=\bigcap S$, which is a set by separation. For every $y\in S$ there is an $x\in S$ with $\mathcal{P}(x\cap y)\subseteq y$. Since $b\subseteq x\cap y$, this gives $\mathcal{P}(b)\subseteq y$. Intersecting over every $y\in S$ yields $\mathcal{P}(b)\subseteq b$.

Now form the diagonal subset $d=\{u\in b:u\notin u\}$. It belongs to $\mathcal{P}(b)$, hence to $b$, so its defining condition implies $d\in d⟺d\notin d$, a contradiction. Thus $\boxed{R\text{ is well-founded}.}$ This is a Cantor diagonal argument; it uses neither the Axiom of foundation nor the axiom of choice. In particular, no selection of an infinite descending sequence is needed.