Question: I was just browsing through the Puzzle section on Noam Elkies website. The puzzle can be found [here](http://www.math.harvard.edu/~elkies/Misc/sol6.html). 

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?

Answer: 
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.
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).