Past exam of the mathematics course of the University of Cambridge / 2015 / iii / Paper 24 / 1

A strict partial order is a well-founded relation when every nonempty subset $Y\subseteq P$ has a minimal member:In ZFC this is equivalent to the absence of an infinite descending sequence $p_0{>}_P{p}_1{>}_P\cdots$. A descending sequence violates the minimal-member property; conversely, repeatedly choosing a predecessor from a subset with no minimal member constructs such a sequence using the axiom of choice.

For a Sierpiński decomposition of the plane, $A,B$ partition ${\mathbb{R}}^2$, and one has countable vertical sections while the other has countable horizontal sections. With the orientation fixed as follows,for every real $x,y$. Interchanging the coordinate directions and the names $A,B$ gives the equivalent convention. Here “countable” includes finite sets.

The relation of eventual domination isA dominating family $C\subseteq {\omega }^{\omega }$ satisfiesIt must dominate every function, and the exceptional finite initial interval may depend on both functions.

Use the order completeness of $\mathbb{R}$ to defineThe set in this supremum is nonempty and bounded above: choose $d_0,d_1\in D$ with $d_0<x<d_1$, using that $D$ is an order-dense subset. For $x\in D$, all its displayed values lie below $\phi (x)$. If $y<\phi (x)$, choose $e\in D$ with $y<e<\phi (x)$; then $d={\phi }^{-1}(e)<x$. Thus the supremum equals $\phi (x)$.

The extension is strictly increasing. If $x<y$, choose $d,e\in D$ with $x<d<e<y$; thenApply the same construction to ${\phi }^{-1}$, obtaining $\psi$. For $d<x$, choose $e\in D$ with $d<e<x$; this gives $\phi (d)<\tilde{\phi }(x)$. For $d>x$, a point of $D$ between $x$ and $d$ similarly gives $\phi (d)>\tilde{\phi }(x)$. HenceTaking inverse images and a supremum shows $\psi (\tilde{\phi }(x))=x$. The symmetric argument gives $\tilde{\phi }(\psi (y))=y$, so the extension is an order automorphism.

For uniqueness, any increasing extension $h$ has the same strict lower cut in $D$ at its value $h(x)$. Two distinct real numbers have different cuts in an order-dense subset, so $h(x)=\tilde{\phi }(x)$. The extension exists and is unique.

If two order automorphisms agree on $\mathbb{Q}$, their values at any real $x$ are the same supremum of the common values at rational points below $x$. This is the uniqueness argument for extension of an order automorphism from a dense subset; it does not require either automorphism to carry $\mathbb{Q}$ onto itself.

Their restrictions belong to ${\mathbb{R}}^{\mathbb{Q}}$, whose cardinality isThis gives the upper bound. The translations $x\mapsto x+r$, one for each real $r$, are distinct order automorphisms, giving the lower bound. Consequently

Write $\mathfrak{c}=2^{{\aleph }_0}$ and enumerate all nonidentity order automorphisms of the real line as $⟨h_{\alpha }:\alpha <\mathfrak{c}⟩$. We construct sets of points to include and exclude, starting with $I_0=\mathbb{Q}$ and $E_0=\varnothing$.

At stage $\alpha$, each of $I_{\alpha },E_{\alpha }$ has cardinality less than $\mathfrak{c}$. Since $h_{\alpha }$ is a nonidentity increasing bijection, its moved points contain a nonempty open interval. Indeed if $h_{\alpha }(u)>u$, points between $u$ and $h_{\alpha }(u)$ are moved; the other direction is similar. There are therefore $\mathfrak{c}$ moved points. Choose one, $x_{\alpha }$, outsideThen put $x_{\alpha }$ into $I$ and $h_{\alpha }(x_{\alpha })$ into $E$. They are different, and the included and excluded sets remain disjoint. Take unions at limit stages. This recursion works even when $\mathfrak{c}$ is singular: before stage $\alpha$, only countably many initial points and at most $|\alpha |$ chosen pairs have been used.

Let $X=\mathbb{Q}\cup \{x_{\alpha }:\alpha <\mathfrak{c}\}$. It is an order-dense subset of cardinality $\mathfrak{c}$. Any nonidentity order automorphism of $X$ extends uniquely to some $h_{\alpha }$ of $\mathbb{R}$, but its value at $x_{\alpha }\in X$ is the excluded point $h_{\alpha }(x_{\alpha })\notin X$, a contradiction. Thus the resulting rigid dense subset of the real line satisfies

On $[\kappa {]}^{\omega }$, declare $A\sim B$ when their symmetric difference is finite. Use the well-ordering theorem to choose one representative $R_{[A]}$ from each equivalence class, and color byRemoving one point from a countably infinite set does not change its equivalence class and reverses this parity. For any $H\subseteq \kappa$ of order type $\omega$ and $x\in H$, both $H$ and $H\setminus \{x\}$ belong to $[H{]}^{\omega }$ and receive different colors. There is no homogeneous $H$ of order type $\omega$. This proves the negative infinite-arity partition relationThe slashed arrow in the PDF is essential.