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?

  • 2
    $\begingroup$ The title says "countable" and the question says (correctly) "uncountable". $\endgroup$ – Asaf Karagila Oct 24 '16 at 20:26
  • 8
    $\begingroup$ He means that no uncountable set of real numbers is well-ordered in the usual order on $\Bbb R$. $\endgroup$ – Brian M. Scott Oct 24 '16 at 20:27
  • $\begingroup$ @user.3710634: The OP is their own person. Let them first acknowledge this, or clarify otherwise. (And by the way, this is why I am usually very adamant that the body of the question should be self-contained, and not depend on the title.) $\endgroup$ – Asaf Karagila Oct 24 '16 at 20:37
  • 2
    $\begingroup$ You can define a well order in any set, included $\Bbb R$ or $\Bbb C$, but these order relations are not compatible with the structure of a field. $\endgroup$ – Masacroso Oct 24 '16 at 21:37
  • $\begingroup$ See also this post and other questions linked there. $\endgroup$ – Martin Sleziak Nov 2 '16 at 11:59

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.

  • 1
    $\begingroup$ Note the parallels in the questions "Is there a well-ordered uncountable subset of real numbers?" and "Is there a surjective function from a subset of $\mathbb{N}$ to $2^{\mathbb{N}}$?" The latter question allows you to choose both a function and a subset, so I would personally interpret the former question as allowing you to choose both an ordering and a subset. $\endgroup$ – Michael Oct 24 '16 at 22:27
  • 1
    $\begingroup$ In any case, one reason I am on stackexchange is to help people solve problems, and I find it personally fulfilling if an answerer demonstrates he/she has understood my answers/comments. I gave this answer to demonstrate to Henning that I understood his comments and the thought process behind them. I would have interpreted the question entirely via "Interpretation 1" without Henning's help. I also explained the two possible interpretations in my answer above. I am not sure why I get a "-1" but perhaps I gave too many comments on the last question and (unintentionally) raised tempers. $\endgroup$ – Michael Oct 24 '16 at 22:36
  • $\begingroup$ Why is your clarified question not equivalent to "Is there a black white cat?" $\endgroup$ – Spencer Oct 25 '16 at 3:09
  • $\begingroup$ @Spencer : I assume your view is that "$\mathbb{R}$ is a set of objects together with an ordering and field axioms." Another view is "$\mathbb{R}$ is an uncountable set of objects that can be visualized by a line and indexed via unique decimal expansions." It is useful to use $\mathbb{R}$ as a concrete example of an uncountable set. That is why phrases like "a well ordering of the reals" make sense and are not contradictory. These phrases are used all the time, including in the questions and answers here: math.stackexchange.com/questions/6501/… $\endgroup$ – Michael Oct 25 '16 at 3:49
  • 1
    $\begingroup$ Thanks, this answer finally made it clear to me where i was getting confused. $\endgroup$ – Burnsba Oct 25 '16 at 12:16

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

  • 5
    $\begingroup$ It's probably worth pointing out that the phrasing "choosing a rational point from each interval" isn't meant to suggest that the axiom of choice is being used. We can simply use the first rational number according to some standard enumeration of $\mathbb{Q}.$ $\endgroup$ – Mitchell Spector Oct 24 '16 at 20:49
  • 5
    $\begingroup$ @Michael: Note that the question asks for a well-orderED uncountable set of real, not for a well-orderABLE uncountable set of reals. The use of "ordered" implies that the question is speaking about an already existing order, which in case of a set of reals where nothing else is specified is ... the usual order on the reals. It could certainly have been phrased more clearly, but there is no real doubt what the question means. $\endgroup$ – hmakholm left over Monica Oct 24 '16 at 21:05
  • 3
    $\begingroup$ @HenningMakholm : I don't see any natural implications such as you speak of, so I find it a bit off-putting for you to conclude "there is no real doubt what the question means." Your last comment also seems to suggest a subtle distinction between "the possibility of being ordered" and "the existence of an order" and I do not understand that distinction (it seems to be a likely point of confusion for the un-initiated in this area, like me). I am only vaguely familiar with this area, so I take from the current answers "don't try to understand it unless you are an expert." $\endgroup$ – Michael Oct 24 '16 at 21:18
  • 2
    $\begingroup$ @HenningMakholm : Thanks. You continue to use language that I find a bit off-putting ["the only order it can reasonably be asking about" implies "Michael is unreasonable."] Haha. Anyway I understand my statement of the question, but we can agree to disagree that the original statement was clear (and hence I am unreasonable in your mind, I will live to accept that!) $\endgroup$ – Michael Oct 24 '16 at 21:33
  • 3
    $\begingroup$ @Michael: Feel free to propose a different order that you think it is reasonable for the question to be asking about. Just remember that it has to be a particular order that the answerer has no control over (again again again because the word is "well-orderED", which you persist in ignoring -- and that persistence is definitely not reasonable!) $\endgroup$ – hmakholm left over Monica Oct 24 '16 at 21:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.