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 
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 
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.
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.
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".
I think you mean aleph_1 = 2^aleph_0 for CH.
Yes, I do. Thanks for catching that.
> If CH, then x r than r > x, no matter which r you picked.
I realize this comment is over 3 years old, but I’m just curious what you meant by “then x r than r > x”… is there a typo here? What you’re explaining sounds very interesting, so I’m just a little frustrated that I can’t understand what appears to be a key portion of it.
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.
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.
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.
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.
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.
A sequence by definition is countable. And not any old countable well-order, but a particular well-order called ω, which is the order type 1, 2, 3, 4, 5, … It’s true that one can consider an uncountable ordinal as a generalized sequence, but it’s not a sequence. Mark you should read about the ordinals, they’re very cool.
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.
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.
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.
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.
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.
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.
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.
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. 🙂
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.
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.
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.
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.
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.
I realize this is a bit late, but….
Minor point: There are two different diagonalization proofs. The Cantor diagonalization proof does not guarantee “that *every* rational number would be in the list.” To the contrary, it looks at a very small subset of the rationals: Every decimal containing only two digits, such as 0’s and/or 1’s. These certainly don’t include “every” rational, but they are enough for Cantor’s diagonalization trick to do its work.
The proof that the rationals are countable uses a different sort of diagonalization.
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.)
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).
My first sentence is missing the final phrase “is false”
Completely wrong. The w.o. theorem gives you a well-order of an uncountable set. Such things exist without Choice, in fact. The union of all countable ordinals is an ordinal that can’t be countable (since a set can’t contain itself) hence it’s the first uncountable ordinal. What the w.o. theorem gives you is a well-ordering of the reals. But it’s not a SEQUENCE, which by definition is the order type of the natural numbers in its standard order 1, 2, 3, 4, …
Way below your usual high standards, Mark. Read up on ordinals and in particular uncountable ones.
I would say that the issue is not the inability to identify the well-ordering relation, the arguement presented only shows that there is a set that can be put into an injection with the natural numbers, but not that it is a surjective function so even if you have the relation it doesn’t help the arguement.
Here is where your reasoning appears problematic: when you remove the smallest element from a well-ordered set, you get another set, which can be well-ordered, but the new well-ordering is not necessarily a sub-order of the initial one. You can remove the smallest element according to this new well-ordering but… in the remaining the order has changed, again. So in the end you just get an enumeration of some real numbers. Looks like you got a very mild case of Cantor-crankery infection. Nothing a little diagonalization can’t cure 😉
I asked the original question and thanks to the post and some answers here, I was able to come to understanding of why well ordering doesn’t contradict cantor. However, it doesn’t precisely correspond to an answer given so I thought I’d post my reasoning. Firstly, it doesn’t matter whether the well ordering is < or whether the relationship that produces the well ordering changes when you remove an element. Neither would stop you placing a set into one to one correspondance.
Rather it is the fact that while well ordering guarentees that every element has a successor it does not guarentee that every element has a predecessor e.g. for the integers you can have the well ordering (0,1,2,3,4,5… -1,-2,-3,-4, …). In this case if you take the smallest element each time and place them in one to one correspondance with the natural numbers you exclude (-1,-2,-3,-4,…) because -1 has no predecessor it will never be reached. I'm not sure of the technical term but I could call this a discontinuity (and will do so).
For the integers you can have the alternative well ordering (0,-1,1,-2,2,-3,3,…) which has no discontinuities. If my understanding is correct for any finite number of discontinuities you can create an alternative well ordering without discontinuities (just take the smallest element of the first section, then the second, then the third etc, then repeat for the next smallest elements, etc) however, you cannot do so if there is an infinite number of discontinuities. The reals will have an infinite number of discontinuities, there is no way to produce a well ordering where each number has a predecessor. Or as Cantor says your sequence will always miss numbers out.
This, as many have said before, is completely wrong and I feel it should be removed or rewritten.
The thing is that a well ordering won’t by itself give you a bijection _even when a bijection exists otherwise_.
If it did, then the well-ordering theorem would disprove diagonalization, even though you don’t get a “useful” well order.
The simplest example why a well ordering won’t give you a bijection is constructing a bijection between aleph_0 (natural numbers) and aleph_0 + 1 (the set of natural number, plust aleph_0 which is greater than every natural number).
Both sets are countable, and a simple bijection would be 0 -> aleph_0, 1->0, 2->1 …
However, if you were to enumerate it by recursively removing the smallest element, you would get a function f(n) = n. However, that function is not surjective, as there is no n such that f(n) = aleph_0.
Well-ordering has been done before Zermelo in the following way:
It was usual to argue as follows: From the set A to be well-ordered take by arbitrary choice an element and denote it as a_0, then from the set A \ {a_0} an element a_1, then an element from the set A \ {a_0, a_1} and so on. If the set {a_0, a_1, a_2, …} is not yet the complete set A, we can choose from A \ {a_0, a1, a_2, …} an element a_omega, then an element a_ (omega+1), and so on. This procedure must come to an end, because beyond the set W of ordinal numbers which are mapped on elements of A, there are greater numbers; these obviously cannot be mapped on elements of A.
This naiveté is reported as late as in 1914 by Felix Hausdorff, obviously without reservations because he remarks: “We cannot share most of the doubts which have been raised against this method.” Hausdorff only deplores the undesired impression of a temporal process but confirms that the element a_omega is fully determined in the sense of transfinite induction and claims that every single action of choosing an element as well as their order has to be understood as timeless. “In order to support this timeless approach E. Zermelo has got the lucky idea to choose from the scratch from every non-empty subset A’ of A one of its elements a’ = f(A’), such that we do no longer have to wait until it is the turn of A’ but for every set, whether or not it will come up, an element is available prae limine. The system of successive choices has been replaced by a system of simultaneous choices which in practical thinking of course is as unfeasible.” [F. Hausdorff: “Grundzüge der Mengenlehre”, Veit, Leipzig (1914); reprinted: Chelsea Publishing Company, New York (1965) p. 133f]
Of course the original method as well as the “timeless” one introduced by Zermelo are wrong. Timeless nonsense is nonsense nevertheless. The mistake committed by Zermelo’s in his “proof” is his assumption that there is always “a first” element following a given one. That is only possible in a sequence, i.e., in a countable set. The details can be found here: “An invalid step in Zermelo’s proof of well-ordering” in https://www.hs-augsburg.de/~mueckenh/Transfinity/Transfinity/pdf
Regards, WM
Dm’s (diagonal methods) are all wrong. So, dm-based wel-ordering theorem is wrong, too. Thus, they are both equivalent and contradictory with each other; it is only natural by the principle of explosion (ex falso quodlibet). That is what the above arguments of yours are about.
If you see ω as a symbol for the potential infinity, the well-ordering notion may live; but the present set-theoretical well-ordering theorem won’t.