Does well-ordering contradict Cantor?

The other day, I received an email that actually excited me! It’s a question related to Cantor’s diagonalization, but there’s absolutely nothing cranky about it! It’s something interesting and subtle. So without further ado:

Cantor’s diagonalization says that you can’t put the reals into 1 to 1 correspondence with the integers. The well-ordering theorem seems to suggest that you can pick a least number from every set including the reals, so why can’t you just keep picking least elements to put them into 1 to 1 correspondence with the reals. I understand why Cantor says you can’t. I just don’t see what is wrong with the other arguments (other than it must be wrong somehow). Apologies for not being able to state the argument in formal maths, I’m around 20 years out of practice for formal maths.

As we’ve seen in too many discussions of Cantor’s diagonalization, it’s a proof that shows that it is impossible to create a one-to-one correspondence between the natural numbers and the real numbers.

The Well-ordering says something that seems innoccuous at first, but which, looked at in depth, really does appear to contradict Cantor’s diagonalization.

A set S is well-ordered if there exists a total ordering <= on the set, with the additional property that for any subset T \subseteq S, T has a smallest element.

The well-ordering theorem says that every non-empty set can be well-ordered. Since the set of real numbers is a set, that means that there exists a well-ordering relation over the real numbers.

The problem with that is that it appears that that tells you a way of producing an enumeration of the reals! It says that the set of all real numbers has a least element: Bingo, there’s the first element of the enumeration! Now you take the set of real numbers excluding that one, and it has a least element under the well-ordering relation: there’s the second element. And so on. Under the well-ordering theorem, then, every set has a least element; and every element has a unique successor! Isn’t that defining an enumeration of the reals?

The solution to this isn’t particularly satisfying on an intuitive level.

The well-ordering theorem is, mathematically, equivalent to the axiom of choice. And like the axiom of choice, it produces some very ugly results. It can be used to create “existence” proofs of things that, in a practical sense, don’t exist in a usable form. It proves that something exists, but it doesn’t prove that you can ever produce it or even identify it if it’s handed to you.

So there is an enumeration of the real numbers under the well ordering theorem. Only the less-than relation used to define the well-ordering is not the standard real-number less than operation. (It obviously can’t be, because under well-ordering, every set has a least element, and standard real-number less-than doesn’t have a least element.) In fact, for any ordering relation \le_x that you can define, describe, or compute, \le_x is not the well-ordering relation for the reals.

Under the well-ordering theorem, the real numbers have a well-ordering relation, only you can’t ever know what it is. You can’t define any element of it; even if someone handed it to you, you couldn’t tell that you had it.

It’s very much like the Banach-Tarski paradox: we can say that there’s a way of doing it, only we can’t actually do it in practice. In the B-T paradox, we can say that there is a way of cutting a sphere into these strange pieces – but we can’t describe anything about the cut, other than saying that it exists. The well-ordering of the reals is the same kind of construct.

How does this get around Cantor? It weasels its way out of Cantor by the fact that while the well-ordering exists, it doesn’t exist in a form that can be used to produce an enumeration. You can’t get any kind of handle on the well-ordering relation. You can’t produce an enumeration from something that you can’t create or identify – just like you can’t ever produce any of the pieces of the Banach-Tarski cut of a sphere. It exists, but you can’t use it to actually produce an enumeration. So the set of real numbers remains non-enumerable even though it’s well-ordered.

If that feels like a cheat, well… That’s why a lot of people don’t like the axiom of choice. It produces cheatish existence proofs. Connecting back to something I’ve been trying to write about, that’s a big part of the reason why intuitionistic type theory exists: it’s a way of constructing math without stuff like this. In an intuitionistic type theory (like the Martin-Lof theory that I’ve been writing about), it doesn’t exist if you can’t construct it.

25 thoughts on “Does well-ordering contradict Cantor?”

  1. I don’t think that’s correct. If the Axiom of Choice said there was a countable enumeration of the reals, then the Axiom of Choice would contradict Cantor’s proof. What it and the Well-Ordering Principle mean is that one can produce a list of the real numbers, and count them off, one by one, and after you’ve produced your function from the natural numbers to (part of) the reals, you’ll find there’s an uncountably infinite number of real numbers left. There’s a least element of that set, but it will be the successor of no real. That will be start of another enumerable subset of the reals, but again, there will an uncountably infinite number of real numbers left over. There will be an uncountably infinite number of real numbers that are the successor of no real number, so while you have this series of lists, it can’t be rearranged into a countably infinite list.

    1. The well-ordering principle says that there is a bijection between some (in this case, uncountable) ordinal and R. It’s correct (cf. Cantor) that no countable ordinal will do.

      There’s no contradiction because while you could pick “least” elements from R and index it that way, you’d have to do it an uncountable number of times. This is why the Axiom of Choice (equivalent to WOP) makes people uncomfortable: it involves not only “making” infinitely many “choices” but sometimes making uncountably infinitely many choices. Computationally, this is absurdity, but AoC only claims that a suitable mathematical object exists.

      Now, where it does get weird is if the Continuum Hypothesis is true and |R| = 2^|N|. If CH is used (and it’s formally independent of ZFC, which means that a valid mathematics exists with it, and another valid mathematics exists without it) then we have a bijection between R and w_1, which is the least uncountable ordinal and the (uncountable, by construction) set of all countable ordinals. Thus, we can index R where each real number has a countable index, even though there are uncountably many of them. (In the same way, we can index Z or Q where every object has a finite index, but neither set is finite. The logic is similar insofar as the set of finite numbers is the smallest infinite ordinal.)

      So, here’s where gets interesting. Let (R, <) be a well-ordering. Pick *any* real r. If CH, then x r than r > x, no matter which r you picked. This contradicts our intuition (“mediocrity principle”) about “random” choices from sets, insofar as if we picked a random element x of a totally ordered finite set, we can provably expect there to be about as many a > x as b < x. And there is no such thing as a uniform random choice from a countable set, so we don't have that problem with countable sets. But we start getting weird results (that don't matter in practice, but exist set-theoretically) in probability if we start talking about, e.g. "random reals".

  2. This isn’t correct. The real problem is that you may not exhaust the set by continually looking at successors. Take the ordinal w+1, for example. Every element has a successor, and every subset has a least element, but you’ll never exhaust the set starting with successors to zero.

    1. I admit that this kind of stuff is way out at the limit of my mathematical
      knowledge, so it’s likely that I got it wrong. (As I’ve said many times: I’m
      not a mathematician; I’m a computer scientist and math hobbyist!)

      But my recollection of this stuff is that there’s almost a contradiction here,
      because of transfinite induction. Induction relies on the successor property actually
      being able to make a kind of progress through the set. We get around the order problems
      using the limit case – so by combining the limits with the successor property, we can
      do induction over the reals.

      To me, that’s still very similar to Banach-Tarksi – where we have a ‘cut’ that’s impossible to specify because it has an uncountably infinite structure. As I understand it, that’s what’s going on in the well-ordering of the reals: it’s a higher-order infinite structure that’s almost a “sequence”. So viewed by a less-than-expert mathematical intuition, it’s a higher-order sequence that’s impossible to grab, because it’s not actually the thing you’d like it to be.

      1. Transfinite induction begs the question. When you do ordinary induction, you’re using the order type of the natural numbers. When you do transfinite induction, however, you’re using a different ordinal. In this case, the ordinal is exactly the order type on the reals, so all you’ve done is put the reals into correpondence with themselves.

        On the other hand, uncountable ordinals are weird. But it’s an interesting fact that you do not need the axiom of choice to define an uncountable ordinal. But I couldn’t tell you how — maybe a real expert can step in.

        1. Counntable ordinals het eierd. Srarch ‘large countable ordinals’ on wikipedia. Even very large integers can get wierd: search for busy beaver on scott aaronson’s blog.

      2. In fact, you can exhibit well-orderings of uncountable sets that are rather easy to look at—the well-ordering of ordinals does it. (Countable ordinals are enough). I’m not 100% positive the axiom of choice is at no point needed, but I don’t think it is.

        However, you can’t really exhibit an uncountable order, but for other reasons (not involving the axiom of choice I think): to actually have uncountably many elements of a set, you need elements that *individually* can’t be written down. But that’s not an issue with ordinals. There are only countably many finite strings, and they’re too few for ordinals *and* for reals.

        Still, if we start looking at ordinals, we see (if I don’t screw up details, I read this ages ago in Bertrand Russell’s “Introduction to mathematical philosophy”, now online at http://people.umass.edu/klement/russell-imp.html):

        First, a progression (sequence isomorphic to naturals):
        0, 1, 2, 3, …
        Then, a progression of progressions:
        ω, ω + 1, ω + 2, ω + 3, …
        ω·2, ω·2 + 1, ω·2 + 2, ω·2 + 3, …
        ω·3, ω·3 + 1, ω·3 + 2, ω·3 + 3, …

        Then, a progression of progressions of progressions, repeating the above from each of ω², ω³, …, ω^ω
        ω·ω, ω·ω + 1, ω·ω + 2, ω·ω + 3, …
        ω·ω + ω, ω·ω + ω + 1, ω·ω + ω + 2, ω·ω + ω + 3, …
        ω·ω + ω·2, ω·ω + ω·2 + 1, ω·ω + ω·2 + 2, …

        Much more…

        What you’ll see is there are too many elements without an immediate predecessor (I’ll guess an uncountable number of them), so even if each natural-like sequence (Russell calls them *progressions*) is countable, there’s an uncountable number of progressions.

        Regarding ordinals that can’t be written down (which I just learned about), see https://en.wikipedia.org/wiki/Large_countable_ordinal.

  3. I’m not sure your answer covers it, actually. I don’t think the 1-1 correspondence is defeated by merely a lack of constructed well-orderings of the reals. I think that there is a more important distinction to made between cardinal numbers and ordinal numbers. Well-ordered sets correspond with order types. 1-1 correspondence is about cardinalty, but ordinality requires something more.

  4. While agreeing with your conclusion…Although the well ordering principle gives every element a successor it doesn’t give every element a predecessor. Elements without a predecessor occur as the limits of countable increasing chains. Your enumeration procedure would only get you as far as the first limit.

  5. Although I’ve enjoyed many of your previous posts, I’m going to disagree with you here. In particular, from where I’m sitting, it looks like you’re equivocating your way out of the question. The spirit of the question is not so much “why can’t we use the well ordering theorem to construct an enumeration” and more “why can’t we use the well ordering theorem to prove that there is an enumeration.”

    At the surface, it seems the same, but when your argument hinges on not being able to construct the well ordering of the reals to justify not being able to construct the enumeration it is important. The point is, we would like to be able to use the well ordering to prove that the reals are enumerable, even if we can’t in any more objective sense specify the enumeration i.e. we want to know why the given argument is not a disproof in ZFC. The real reason that this does not work is not non-constructibility, because there are other, constructible, well orderings that do not produce an enumeration of the elements using this method: just take the ordinals through omega (or the set of natural numbers and another element considered to be greater than all the naturals). Then the enumeration given by this construction is f(n)=n, and there is no n for which f(n)=omega, essentially because it cannot be reached by induction.

    1. Diagonalization provides an enumeration but does that enumeration satisfy a_i+1 > a_i for any definition of ‘>’? Apologies if I’ve missed the point but that sounds like the crux of why the two concepts aren’t in contradiction.

  6. I’m not sure this explanation is correct. A well-ordering can produce an enumeration of a countable subset of the reals, but this will necessarily be a proper subset.

  7. Spoke a little too fast. w+1 has a maximal element, but everything else still applies (i.e., it is still a well-order). w+w is an example without a maximal element.

  8. Well-ordering shows that you can enumerate some reals. It doesn’t show that you can enumerate *all* of them. This is the issue, not the constructibility of the well-ordering.

  9. When I read the users question, I had an “intuitive” idea why the well ordering does not provide you an enumeration of all reals: The interval from 0 to 1 already contains an infinite amount of numbers. So if you start with the set of all positive reals, and always take the smallest one, you’ll never reach or even exceed 1.

    I think that might be easier to understand than your proof – on the other hand, intuition is often wrong with maths. But it’s an “intuitive” counter-argument to an “intuitive” hypothesis. 🙂

    1. Unfortunately, this intuition opens another can of worms. What if, instead of real numbers, I considered just the rational ones (in the internal from 0 to 1)? The argument about always taking the smallest one and never reaching or even exceeding 1 would still apply… but it certainly wouldn’t allow us to conclude that rationals cannot be enumerated (since the set of all rationals actually is countable).

      When dealing with problems like this, one needs to be careful not to mix up unrelated orderings: on one hand we have a well-ordering given to us, which we cannot assume anything extra about, while on the other hand, we also have the “usual” ordering of real numbers (which is not a well-ordering). We cannot expect the first one to “match” the second one in any way; it could very well be the case that the well-ordering places all the numbers “greater” than 1 (in the usual sense) somewhere between 0 and 1, thus making the argument about “reaching 1” fail completely.

  10. Oh, that one’s very simple. The smallest uncountable ordinal ω₁ is defined as (the order type of) the set of all countable ordinals: this set has cardinality ℵ₁. Ordinals corresponding to larger cardinal numbers are defined similarly. Of course it requires first establishing that such a set can be formed, but that follows from a few applications of the power set axiom and the separation schema. Indeed, no choice axiom required.

  11. Mathematician here. You’re wrong. What you did is define an injective map from the natural numbers to R, but you haven’t proven it’s surjective; in fact, Cantor’s diagonal argument shows that it will not be.

    Let me make an easier example: the set N ={0,1,2,…} can be well ordered in the usual way (0<1<2…) but also in many others. E.g., you can decide that every odd number is larger than every even number, and keep the ordering aming odds and evens. So now the order is (0,2,4,6…. 1,3,5….) this is a well ordered set, in that every nonempty subset has a smallest element.

    If you apply your argument, you get a bijection from N to the set of even numbers.

    1. Nice example!

      And a more useful reply than many of the others here, because people who are familiar with order types and transfinite ordinals are likely to already know the answer to the question.

  12. My formal mathematics was a long time ago but…
    I recall that Cantor’s diagonalization method worked because its construction guaranteed that *every* ration number would be in the list and reached in a finite number of steps. It appears to me that while this well=ordered theorem allows one to generate an ordered list of reals, there is no guarantee that every real is in the list.

  13. I’m also uncertain about another part of this post:

    “It’s very much like the Banach-Tarski paradox: we can say that there’s a way of doing it, only we can’t actually do it in practice. In the B-T paradox, we can say that there is a way of cutting a sphere into these strange pieces – but we can’t describe anything about the cut, other than saying that it exists.”

    Are you sure you are correctly characterizing the result here? While I am quite familiar with nonconstructive existence proofs, I seem to recall that the original paper DID in fact offer a construction, as have subsequent publications. So what do you mean by “we can’t actually do it in practice”? If you mean that we cannot accomplish this with a physical object, that is totally different because the proof based on Axiom of Choice uses a decomposition of a set into nonmeasurable sets, which do not occur in chemical matter because, as a combination of atoms, chemical matter is discrete and measurable. But we can do this with continuous sets, if we assume the Axiom of Choice, which counts in mathematics as “we can actually do this in practice.”

    (Fun little thought: If it turns out that spacetime itself is discrete, then what we’re left with is a procedure that is possible in an idealized world of continous mathematics, but poses no crisis in the empirical world of discrete reality, but the jury is still out on whether spacetime is discrete or continuous.)

  14. Sorry to nitpick but your claim that you can’t define a well-ordering relation on the reals. It is true that no Borel relation can well-order the reals but if V=L then there is a \Delta^1_2 well ordering of the reals. This means there is a formula \phi(x,y) in the language of set theory (indeed expressible as a AE and EA formula quantifying over the reals) which defines a well order on the reals.

    Basically, the trick is to define x < y just if x is built at an earlier level L_\alpha of the constructable universe than y or they are built at the same level and (bootstraping off the wellordering of finite sequences of L_\alpha induced by Con(ZFC + There is no definable well ordering of the reals) (though I’m a little fuzzy on moving from there is no projective well ordering of the reals to there is no definable well ordering but I think you do some crazy tricks with countable models).

Leave a Reply