Why can the reals be well-ordered but not countable?
June 12, 2012 10:58 AM Subscribe
Math-Filter - Set theory edition:
I am struggling with the difference between countable infinite sets and well-ordering. Longer explanation inside.
Ok the longer version:
I get that there are countably infinite sets (like natural numbers).
I get that some sets were proven to be countable by changing their order so as to set up a 1-to-1 equivalence to the natural numbers (like the rational numbers).
I get Cantor's diagonal argument for proving that the real numbers are uncountable.
I think that I understand what it means for a set to be well-ordered. (From wikipedia:"In mathematics, a well-order relation (or well-ordering) on a set S is a total order on S with the property that every non-empty subset of S has a least element in this ordering. The set S together with the well-order relation is then called a well-ordered set."
Here's where the confusion lies:
Apparantly it has been proven that there exists a well-ordering of the reals and some mathematicians think that it is likely that all sets may have a well-ordering. But if you can put a set into a well-order can't you then just count the elements in that order? Wouldn't they be in a 1-to1 relationship with the natural numbers at this point? I am definitely stuck with why something could be well-ordered but not countable.
I have googled and read wikipedia for long enough that I think I am getting more confused not less.
Thanks to anyone who can help my brain hurt less.
Ok the longer version:
I get that there are countably infinite sets (like natural numbers).
I get that some sets were proven to be countable by changing their order so as to set up a 1-to-1 equivalence to the natural numbers (like the rational numbers).
I get Cantor's diagonal argument for proving that the real numbers are uncountable.
I think that I understand what it means for a set to be well-ordered. (From wikipedia:"In mathematics, a well-order relation (or well-ordering) on a set S is a total order on S with the property that every non-empty subset of S has a least element in this ordering. The set S together with the well-order relation is then called a well-ordered set."
Here's where the confusion lies:
Apparantly it has been proven that there exists a well-ordering of the reals and some mathematicians think that it is likely that all sets may have a well-ordering. But if you can put a set into a well-order can't you then just count the elements in that order? Wouldn't they be in a 1-to1 relationship with the natural numbers at this point? I am definitely stuck with why something could be well-ordered but not countable.
I have googled and read wikipedia for long enough that I think I am getting more confused not less.
Thanks to anyone who can help my brain hurt less.
Best answer: First, for clarity, the existence of a well-ordering of the reals comes from the well-ordering principle, which says that every set may be well-ordered. This is equivalent to the axiom of choice and is somewhat controversial. You can't really construct a well-ordering of the reals.
To answer your actual question, there is a difference between a well-ordering of a set and a one-to-one correspondence with the natural numbers. Probably the easiest example to consider is 'omega plus one', which can be thought of as the natural numbers together with a "point at infinity" which is greater than any other element. You can see that it is a well-ordering: either a set contains some natural numbers and thus a least element among the naturals or it contains only infinity making that the least element. It is also certainly not equivalent to the usual ordering on the naturals because it has a greatest element. If you try to count off these extended naturals using this order, you will omit infinity. (To prove this, you have to make precise what it means to count a well-ordered set, but I think this is clear.) That set is still countable, but it has a different ordering.
posted by eruonna at 11:11 AM on June 12, 2012
To answer your actual question, there is a difference between a well-ordering of a set and a one-to-one correspondence with the natural numbers. Probably the easiest example to consider is 'omega plus one', which can be thought of as the natural numbers together with a "point at infinity" which is greater than any other element. You can see that it is a well-ordering: either a set contains some natural numbers and thus a least element among the naturals or it contains only infinity making that the least element. It is also certainly not equivalent to the usual ordering on the naturals because it has a greatest element. If you try to count off these extended naturals using this order, you will omit infinity. (To prove this, you have to make precise what it means to count a well-ordered set, but I think this is clear.) That set is still countable, but it has a different ordering.
posted by eruonna at 11:11 AM on June 12, 2012
"count the elements in that order" makes me think you're thinking of a total order as equivalent to an enumeration of elements from least to greatest, but that's not true in the general case. It's just a relation R that assigns a truth value to x R y, with a few properties like transitivity, totality, etc. If the domain of that relation isn't countable, you can't just count the elements.
posted by qxntpqbbbqxl at 11:13 AM on June 12, 2012 [1 favorite]
posted by qxntpqbbbqxl at 11:13 AM on June 12, 2012 [1 favorite]
Best answer: Well-ordering doesn't imply anything regarding being able to iterate through a set. All it tells you is that every (non-empty) subset of your well-ordered set has a least element, but as in the ω+1 example that eruonna gives, this doesn't imply that you can mechanically use this (i.e. by "counting" the lest element, removing it, and finding the next least element) to establish a correspondence with the natural numbers.
posted by j.edwards at 11:20 AM on June 12, 2012
posted by j.edwards at 11:20 AM on June 12, 2012
(I love this area of maths!)
Start with the empty set, which we will call zero. It is a well-ordering: it contains no elements and the empty ordering.
Now, if I give you a well-ordering x you can form the well-ordering x+1, which is given by adding one new element to the set x and making it larger than all the elements. So, for example, 1 is the well-ordering given by taking the empty ordering and adding a new point. 2 is the well-ordering with two points, one greater than the other. And so on.
Notice that these well-orderings are nested: 0 is a subset of 1, which is a subset of 2, which is a subset of 3, and so on. If I give you a nested list of well-orderings, you can form another well-ordering by taking their union (exercise: check that this is a well-ordering!). We call this well-ordering the limit of the nested list, or chain.
What can you do now? Well, from adding one lots of times you get the well-orderings 0,1,2,3,... . But these form a chain, so you can make a new well-ordering which is their union; we call this ω. Of course, ω is another well-ordering, so you can just add one to get ω + 1. And then add one a few more times to get ω, ω+1, ω+2, ... . But then that's a chain, so you can take its limit to get -- you guessed it! -- ω + ω, which we call 2ω. Similarly, we get 3ω, 4ω, ... up to ωω, which we call ω2. But then you can get ω2+ω, ... all the way to ω3. Then ω4, ω5, ... ωω, ..., ωωω, ..., ωωω.... The next one is called ε0. And so on ad infinitum.
But -- but but but -- these are all countable!!! See, if x is countable then x+1 is countable (since you can send the new point to 0 and shift the others along), and the limit of a chain is countable since it is a countable union of countable sets (exercise: is that true?). So are there any uncountable ones?
Well, yes! You see, all the countable ordinals just form a nested chain of ordinals. So they have a limit, which we call ω1. And ω1 certainly can't be countable, because it's greater than all countable ordinals!
If you like this stuff I can highly recommend the notes at Planet Gareth, which are where I learnt it.
posted by katrielalex at 11:25 AM on June 12, 2012
Start with the empty set, which we will call zero. It is a well-ordering: it contains no elements and the empty ordering.
Now, if I give you a well-ordering x you can form the well-ordering x+1, which is given by adding one new element to the set x and making it larger than all the elements. So, for example, 1 is the well-ordering given by taking the empty ordering and adding a new point. 2 is the well-ordering with two points, one greater than the other. And so on.
Notice that these well-orderings are nested: 0 is a subset of 1, which is a subset of 2, which is a subset of 3, and so on. If I give you a nested list of well-orderings, you can form another well-ordering by taking their union (exercise: check that this is a well-ordering!). We call this well-ordering the limit of the nested list, or chain.
What can you do now? Well, from adding one lots of times you get the well-orderings 0,1,2,3,... . But these form a chain, so you can make a new well-ordering which is their union; we call this ω. Of course, ω is another well-ordering, so you can just add one to get ω + 1. And then add one a few more times to get ω, ω+1, ω+2, ... . But then that's a chain, so you can take its limit to get -- you guessed it! -- ω + ω, which we call 2ω. Similarly, we get 3ω, 4ω, ... up to ωω, which we call ω2. But then you can get ω2+ω, ... all the way to ω3. Then ω4, ω5, ... ωω, ..., ωωω, ..., ωωω.... The next one is called ε0. And so on ad infinitum.
But -- but but but -- these are all countable!!! See, if x is countable then x+1 is countable (since you can send the new point to 0 and shift the others along), and the limit of a chain is countable since it is a countable union of countable sets (exercise: is that true?). So are there any uncountable ones?
Well, yes! You see, all the countable ordinals just form a nested chain of ordinals. So they have a limit, which we call ω1. And ω1 certainly can't be countable, because it's greater than all countable ordinals!
If you like this stuff I can highly recommend the notes at Planet Gareth, which are where I learnt it.
posted by katrielalex at 11:25 AM on June 12, 2012
Oh pants. Sorry!
posted by katrielalex at 11:25 AM on June 12, 2012 [1 favorite]
posted by katrielalex at 11:25 AM on June 12, 2012 [1 favorite]
You might find Munkres' discussion of the topic helps your intuition.
Chapter 10 in his Topology gives a nice proof that there exists an uncountable well-ordered set.
posted by Algebra at 11:27 AM on June 12, 2012
Chapter 10 in his Topology gives a nice proof that there exists an uncountable well-ordered set.
posted by Algebra at 11:27 AM on June 12, 2012
Ooh, also, I should probably answer your actual question! Suppose you have an uncountable well-order -- for example, ω1 as above. How might you go about putting it in one-to-one correspondence with the natural numbers (which, by the way, are just ω)?
It certainly has a least element, which we could pair with 0. Then we could remove 0 and look at ω1\{0}, whose least element we could call 1. And so on. But at the end, we'll just have removed the first ω entries of ω1 -- and we know that it contains ω+1, so this mapping is not surjective (onto) and hence not a bijection.
Of course, that doesn't prove that it's not countable, just that the obvious way to count its elements doesn't work. The proof that it's not countable is above.
posted by katrielalex at 11:29 AM on June 12, 2012
It certainly has a least element, which we could pair with 0. Then we could remove 0 and look at ω1\{0}, whose least element we could call 1. And so on. But at the end, we'll just have removed the first ω entries of ω1 -- and we know that it contains ω+1, so this mapping is not surjective (onto) and hence not a bijection.
Of course, that doesn't prove that it's not countable, just that the obvious way to count its elements doesn't work. The proof that it's not countable is above.
posted by katrielalex at 11:29 AM on June 12, 2012
... Actually, now that I check closer I see that he only discusses the result and not the proof itself, I seem to have remembered wrong- but you still may find his handling of the topic helpful.
posted by Algebra at 11:29 AM on June 12, 2012
posted by Algebra at 11:29 AM on June 12, 2012
Response by poster: eruonna: Probably the easiest example to consider is 'omega plus one', which can be thought of as the natural numbers together with a "point at infinity" which is greater than any other element.
Ok, so the set omega +1 is not countable because the greatest element is not a member of the naturals? (so you could never "get there" by counting)?
j.edwards: Well-ordering doesn't imply anything regarding being able to iterate through a set. All it tells you is that every (non-empty) subset of your well-ordered set has a least element, but as in the ω+1 example that eruonna gives, this doesn't imply that you can mechanically use this (i.e. by "counting" the lest element, removing it, and finding the next least element) to establish a correspondence with the natural numbers.
Also, a follow-up: in my imagination counting is a process but well-order is a finished product. Is this a correct way to think about it, or is that too restrictive?
posted by heybearica at 11:42 AM on June 12, 2012
Ok, so the set omega +1 is not countable because the greatest element is not a member of the naturals? (so you could never "get there" by counting)?
j.edwards: Well-ordering doesn't imply anything regarding being able to iterate through a set. All it tells you is that every (non-empty) subset of your well-ordered set has a least element, but as in the ω+1 example that eruonna gives, this doesn't imply that you can mechanically use this (i.e. by "counting" the lest element, removing it, and finding the next least element) to establish a correspondence with the natural numbers.
Also, a follow-up: in my imagination counting is a process but well-order is a finished product. Is this a correct way to think about it, or is that too restrictive?
posted by heybearica at 11:42 AM on June 12, 2012
No, omega+1 is countable. Send infinity to 0 and n to n+1 for every natural n. This is a one-to-one correspondence with the nautral numbers, so it is countable. That is all that it means to be countable. It is a different well-ordering than that on the natural numbers, so it provides a counterexample to the proposition that any infinite well-ordering is equivalent to the natural numbers.
posted by eruonna at 11:51 AM on June 12, 2012
posted by eruonna at 11:51 AM on June 12, 2012
Best answer: First, for clarity, the existence of a well-ordering of the reals comes from the well-ordering principle, which says that every set may be well-ordered. This is equivalent to the axiom of choice and is somewhat controversial. You can't really construct a well-ordering of the reals.
There's an old math joke that goes as follows: "The axiom of choice is obviously true, the well-ordering theorem is obviously false, and who knows about Zorn's lemma?"
Also, a follow-up: in my imagination counting is a process but well-order is a finished product. Is this a correct way to think about it, or is that too restrictive?
Imagining the process of actually physically counting the set can be helpful, but it's not the be-all and end-all of countability. Really all that matters is that you can show that a one-to-one map exists between your set S and some subset of the natural numbers. With the standard examples like the integers and the rationals, you can do sort of a graphical approach where you imagine laying all the numbers out in a line or a grid and counting them off. However, it's not always easy to construct such a "graphical" proof for countable sets that are more abstract. As an example, consider the algebraic numbers. I'm unaware of any explicit constructivist proof of their countability;1 instead, you have to resort to more general properties like the direct product of a finite number of countable sets is countable, and that the countable union of a collection of countable sets is countable.
1Of course, I'm not a proper mathematician, just an allied tradesperson. If such a proof exists, I'd be happy to see it and stand corrected.
posted by Johnny Assay at 1:35 PM on June 12, 2012
There's an old math joke that goes as follows: "The axiom of choice is obviously true, the well-ordering theorem is obviously false, and who knows about Zorn's lemma?"
Also, a follow-up: in my imagination counting is a process but well-order is a finished product. Is this a correct way to think about it, or is that too restrictive?
Imagining the process of actually physically counting the set can be helpful, but it's not the be-all and end-all of countability. Really all that matters is that you can show that a one-to-one map exists between your set S and some subset of the natural numbers. With the standard examples like the integers and the rationals, you can do sort of a graphical approach where you imagine laying all the numbers out in a line or a grid and counting them off. However, it's not always easy to construct such a "graphical" proof for countable sets that are more abstract. As an example, consider the algebraic numbers. I'm unaware of any explicit constructivist proof of their countability;1 instead, you have to resort to more general properties like the direct product of a finite number of countable sets is countable, and that the countable union of a collection of countable sets is countable.
1Of course, I'm not a proper mathematician, just an allied tradesperson. If such a proof exists, I'd be happy to see it and stand corrected.
posted by Johnny Assay at 1:35 PM on June 12, 2012
Also, a follow-up: in my imagination counting is a process but well-order is a finished product. Is this a correct way to think about it, or is that too restrictive?Heh, I think about it backwards from you.
Showing that a set is countable means demonstrating a mapping from the natural numbers to its members. That mapping, to me, is an (infinitely large) object, not a process.
Well-ordering, on the other hand, is a recipe, which takes as input a set and outputs the smallest member of that set.
posted by dfan at 4:37 PM on June 12, 2012
Here is another way of thinking about well-ordering: it just means that, given two unequal real numbers a and b, you can say which is bigger and which is smaller. This has nothing to do with actually being able to list all of the numbers.
posted by Frobenius Twist at 4:41 PM on June 12, 2012
posted by Frobenius Twist at 4:41 PM on June 12, 2012
Here is another way of thinking about well-ordering: it just means that, given two unequal real numbers a and b, you can say which is bigger and which is smaller. This has nothing to do with actually being able to list all of the numbers.Well, not quite: according to that rule it would be a well-ordering if you said that a is less than b, b is less than c, and b is less than c, but in reality it's not because you can't provide a smallest element of {a, b, c}.
But your last sentence is still true.
posted by dfan at 5:00 PM on June 12, 2012
Damn, I can't edit. I meant c is less than a for the third part, of course.
posted by dfan at 5:00 PM on June 12, 2012
posted by dfan at 5:00 PM on June 12, 2012
This thread is closed to new comments.
posted by Rubbstone at 11:09 AM on June 12, 2012