3
$\begingroup$

I was just browsing through the Puzzle section on Noam Elkies website. The puzzle can be found here.

The solution to the puzzle proves that any well-ordered subset of $\mathbb{R}$ is countable. In the solution, Elkies defines $s(x)$ to be the immediately following element of $x$ for any $x\in S$ for a well ordered subset $S\subset \mathbb{R}$.

I want to understand the added note at the bottom. It says to consider any interval $(x,s(x))$. I take it he means to view this interval as an subset of $\mathbb{R}$, for it is empty in $S$? Then I know there always exists a rational between any two reals since $\mathbb{Q}$ is dense in $\mathbb{R}$, so one could map $(x,s(x))$ to some $r(x)\in (x,s(x))$, which would show $S$ is in bijection with a subset of $\mathbb{Q}$, and hence countable.

What I don't get is why this mapping doesn't require choice. For any interval $(x,s(x))$, how could we distinquish some $r(x)$ to pick? Are we possibly talking about taking the least rational in $(x,s(x))$ for any $x$? Would that be a way to distinguish which rational to choose?

  • 0
    BTW there are several questions on this site about this problem. For example http://math.stackexchange.com/questions/408300/countable-ordinals-are-embeddable-in-the-rationals-bbb-q-proofs-and-their, http://math.stackexchange.com/questions/496488/universality-of-mathbb-q, http://math.stackexchange.com/questions/44559/formal-proof-for-a-subset-of-the-real-numbers-well-ordered-with-the-normal-orde, http://math.stackexchange.com/questions/37151/showing-any-countable-dense-linear-ordering-is-isomorphic-to-a-subset-of-mat and several questions which are shown among linked questions there.2014-04-12

2 Answers 2

4

The fact that there are explicit well-orderings of $\mathbb{Q}$ makes it clear that AC is not needed. But in fact, if you have any countable dense subset $A$ of $\mathbb{R}$, the argument can be used to give a one-to-one function from the well-ordered subset $S$ of $\mathbb{R}$ into $A$ that does not require the Axiom of Choice, even if you cannot produce an explicit well-ordering for $A$ (or even if you don't know what $A$ is, beyond knowing that it is both dense in $\mathbb{R}$ and countable).

Since we are assuming that $A$ is countable, that means that the set of bijections $f\colon A\to\mathbb{N}$ is nonempty. Let $\mathcal{F}$ be any such bijection. This does not require AC, because we are only choosing one element from a single nonempty set.

Then we define $r\colon S\to A$ as described: given $x\in S$, we know that $(x,s(x))\cap A\neq\emptyset$. Let $m\in\mathbb{N}$ be the smallest element of the set $\{\mathcal{F}(a)\mid a\in A\cap (x,s(x))\}$. This does not require choice, since we are only using the well-ordering of $\mathbb{N}$. Then define $r(x) = \mathcal{F}^{-1}(m)$. By construction, $r(x)\in (x,s(x))\cap A$.

(In short: a bijection from $A$ to $\mathbb{N}$ induces a well-ordering $\preceq$ on $A$; pick a bijection, and define $r(x)$ to be the $\preceq$-smallest element of $A$ in $(x,s(x))$).

The Axiom of Choice is not needed, because the only "choice" was the selection of $\mathcal{F}$, and this single choice from a nonempty set does not require the Axiom of Choice.

2

A variant of Thomas Andrews' comment: choose the dyadic rational (terminating binary decimal) with the smallest number of $1$s in the interval. If there are ties, choose the smallest one in absolute value, then the positive one (if there's two with the same absolute value).