"There is no well-ordered uncountable set of real numbers"

Question

I recently learned (from Munkres) about the axiom of choice, and how it implies the well-ordering theorem.

I've looked through various posts about how to well-order the reals (e.g. this one) but the related proofs are beyond me. From what I gather, the gist of it is that well-ordering for the reals is "possible" even though it is "unknowable."

Then I came across this question:

Q [From a recent Mathematics GRE] Is there a well-ordered uncountable set of real numbers?

A No

With subsequent proof.

Does he mean there is no (non-arbitrary maybe?) definition for the set of well-ordered real numbers -- that yes, a well-ordered uncountable set of real numbers exists, but "we can't get there" -- or is something else going on? Does the well-ordered theorem not apply to all sets?

Answer 1

I give this as a separate answer since I have made too many comments already on the existing answer. This summarizes what I take away from the discussion with Henning.

Original question: "Is there a well-ordered uncountable subset of real numbers."

Clarified question: "Is there a well-ordered uncountable subset of real numbers (using the usual ordering on the reals)."

Interpretation 1 of original language: The question asks about existence of an ordering, so it appears we get to choose both an ordering and a subset. Well, the axiom of choice implies there exists an ordering for which the reals themselves are well-ordered. Then, we can just take a subset of reals being the full set itself. Done. This question is kind of stupid. The only structure of reals here that is used is that the set of reals is uncountable. We could repeat the same question with any uncountable set of objects.

Interpretation 2 of original language: Let's suppose we are forced to use the original ordering of the reals. So we are only allowed to choose a subset. The structure of the problem now is such that the problem is interesting. We must use both the property that the reals are uncountable together with existing properties of the usual ordering on the reals. This is likely the correct interpretation because it is the only one in which the problem is interesting.

Observation: On an exam, there is not time to solve the problem two ways and then try to interpret the problem in a way that is interesting. I would naturally assume "interpretation 1" and then I would be quite confused why the exam is asking such a weird question.

---

I usually view sets as existing independently of temporal concepts (i.e., “outside of time”). The past-tense language used by Henning in comments above is helpful and is consistent with his interpretation of the problem (which is interpretation 2). Interpretation 2 is likely the one intended by the person who designed the question. However, it is not the only interpretation. In fact, interpretation 2 never even occurred to me until the comment-discussion with Henning. I would have gotten this question wrong on the exam, not because it is a hard question, but because I interpreted the question differently.

Thus, it would have been nicer if the original question emphasized that we should use the usual ordering on the reals, so we are only allowed to choose a subset. One uses the usual ordering on the reals almost always, but one can consider different orderings when set theory questions about “well orderings” arise.

Answer 2

You have to distinguish between two things:

1. A set can be well-ordered.
2. A set with a natural linear ordering is well-ordered with that natural ordering.

The axiom of choice implies that every set can be well-ordered. But of course not every set which has a natural linear order is well-ordered. You don't need to venture to the real numbers. Both $\Bbb Z$ and $\Bbb Q$ have a natural linear order which is most definitely not well-ordered.

The point is that given a set of real numbers, if it is well-ordered in the usual ordering of the real numbers, then it is countable. We can prove this by choosing a canonical rational point from each interval between a point and its successor. This choice of rational numbers is not using the axiom of choice, since we can always choose a canonical rational number from an interval (e.g., represent each rational as $\frac pq$ where $p,q\in\Bbb Z$, $p>0$ and $\gcd(p,q)=1$; then consider the rational with the smallest $p$ possible in the interval, and find the one with the denominator closest to $0$ (the positive if both options exist) that match this numerator).

And the main confusion people have with the well-ordering theorem, is that if $X$ is a set which has a natural linear ordering, then there is absolutely no reason for any well-ordering to agree with the natural linear ordering. Much like how we can define well-orderings of $\Bbb N$ which disagree with the usual ordering, or how we can define a well-ordering of the rational numbers which certainly disagrees with their natural order.

(What is true, as you mention, is that we cannot specifically define a set of real numbers in the language of set theory such that $\sf ZF$ proves that this set is both uncountable and can be well-ordered. Namely, it is consistent with the failure of the axiom of choice that only countable sets of real numbers can be well-ordered.)