Thursday, March 1, 2007

Another crack at old Georg

Just as our faith in Cantor grew in the last post, doubt is once again starting to creep in. I'm talking about the well-ordering principle, which says, unsurprisingly enough, that any set can be well-ordered. What this means for the reals is that there is a total ordering relation (which most emphatically is not the usual "less than" relation on R) -- let's denote it by x <' y -- that well-orders the reals. This relation induces the ordering
a <' b <' c <' ...
and every real number r will eventually appear in this chain.

Now the $1.64 question is: why can't we apply Cantor's diagonal argument to this well-ordering to construct a number that doesn't appear in the chain?


Unknown said...

Hey Leo, I think the answer to this one is that diagonalization is a countable operation (you change the n-th digit of the n-th number in the sequence) whereas clearly the list of reals is uncountable.


Aryeh said...

Yes. The "matrix dimensions" don't match -- you have a countable number of columns (the digits) and an uncountable number of rows (the reals). If you try to diagonalize, you run out of decimal places! More formally, Cantor's diagonalization relied on a one-to-one mapping between the "rows" and "columns" which doesn't exist here.

[BTW, thanks for killing the fun for all the non-math PhD readers :-)
Got any thoughts on my geometry question (last post)? Know any ppl who might? Unlike my other questions, I actually don't know the answer!! ]