First, thank you for the full proof of the naturals vs. reals case.
Diagonalization is classically applied to show that the reals are bigger than the natural numbers, but the diagonalization argument also works to take any infinite set and construct a set of larger cardinality (namely the power set).
As for the Diagonalization and God section, this is a valid philosophical argument and has citations to back it up.Foxtrot 22:14, 14 June 2008 (EDT)
- Okay I might leave the philisophical point, but where is the axiom of choice used in that proof? DanielB 22:17, 14 June 2008 (EDT)
- You had to enumerate all the decimal representations of the reals (i.e. well-order them by the natural numbers). There is no natural way to do this without the axiom of choice. Foxtrot 22:25, 14 June 2008 (EDT)
- And that is why the contradiction occurs, because there is no way of ordering the without the axiom of choice, you assume you can and watch it fail. DanielB 22:30, 14 June 2008 (EDT)
- Okay I am starting to see the problem here, the well-order theorem is dependent on the axiom of choice. However countable sets are well ordered. DanielB 22:37, 14 June 2008 (EDT)
- Got edit-blocked twice here. We're both replying quickly :-) Basically there is no natural way of enumerating [0,1] like with the rational numbers. Even if you assume the reals are countable (as we are doing in the proof), you still have countably many decimal numbers that need to be enumerated by the natural numbers. There is a natural way to do this for the integers--alternate 0, 1, -1, 2, etc.--and there's also a way for the rational numbers using the fact that each one is natural number divided by natural number. However with the reals, not even the Archimedean property is enough to help you. You can't say: First decimal is 0, next decimal number is what? The least real number we haven't enumerated yet? But there doesn't have to be a least one, even if the reals are countable (there is not even a least rational number bigger than zero, which is why you have to do this trickery with the enumeration of the rationals). The enumeration of the decimal numbers is where you need choice. Admittedly, you don't need full choice since the set is assumedly countable, so I've fixed the entry to reflect that it's countable choice you use. Foxtrot 22:45, 14 June 2008 (EDT)
- Foxtrot you seem to be missing the essential part of the proof in that it is a proof by contaradiction. If a set is countable then it can be well ordered without using the axiom of choice. I have assumed it is countable and then created an arbritrary ordering assuming I could. I then found an number that was not in my well ordered list. Why? Because they are uncountable and you can't do this, hence a contradiction occurs and so we have proved that the numbers between [0,1] are uncountable. If you use the axiom of choice then my number would be on the list somewhere and the proof fails. DanielB 22:52, 14 June 2008 (EDT)
- Right, I think I got hung up on the reflexive instinct "enumerate implies use of Axiom of Choice", but since the set is assumed to be countable you don't need to worry about. I settle my objections. Foxtrot 00:26, 15 June 2008 (EDT)
- That's fine it is always important to double check these things so we can get them right. DanielB 19:17, 15 June 2008 (EDT)