Another question I have is about isomorphisms of enumerations.Cool Hand wrote:Perhaps you could expound on your dissatisfaction with Cantor's diagonal method and others could critique it.
It's obvious that if there's a bijection between set S and the counting numbers, then the cardinality of set S is aleph_0.
Is the converse true? If set S has cardinality of aleph_0, then is it always the case that it can be enumerated in the form used in Cantor's diagonal argument?
How about the inverse? If there is no bijection between S and the counting numbers, does that mean S cannot have a cardinality of aleph_0?
Moving on . . .
On page 421 of Douglas Hofstadter's book, Godel, Escher, Bach, he gives an example of Cantor's diagonal argument. An example I believe to be flawed. I'm going to leave out some of Hofstadter's description of Cantor's argument, assuming that you already know it.
He goes on to explain why that number is not in the original list, using Cantor's diagonal argument. But there is a fatal flaw in his choice of the digits for the number d, which should be immediately obvious to those who have been following your thread about 0.999... = 1.Hofstadter wrote:Let us consider just real numbers between 0 and 1. ... Since real numbers are given by infinite decimals, we can imagine that the beginning of the table might look as follows:
r(1): . 1 4 1 3 9 2 6 5 3 . . .
r(2): . 3 3 3 3 3 3 3 3 3 . . .
r(3): . 7 1 8 2 8 1 8 2 8 . . .
r(4): . 4 1 4 2 1 3 5 6 2 . . .
r(5): . 5 0 0 0 0 0 0 0 0 . . .
The digits that run down the diagonal are in boldface: 1, 3, 8, 2, 0, ... Now those diagonal digits are going to be used in making a special real number d, which is betwen 0 and 1 but which we will see, is not in the list. ... Suppose, for example, that we subtract 1 from the diagonal digits (with the convention that 1 taken from 0 is 9). Then our number d will be:
. 0 2 7 1 9 . . .
Hofstadter says that d cannot be equal to r(5) because even if all the other digits of d matched up with r(5), the fifth digit does not. Except Hofstadter overlooks that r(5) can also be expressed as .49999... in which the fifth digit IS the same as d. So he has not proven that d is not in the list.
However, this flaw is a result of the way he chooses the digits for d. Instead of subtracting 1 from each digit of the diagonal to make d, suppose we subtract 3, and the flaw seems to be fixed. Or is it?
Can you see why I have an uneasy feeling about Cantor's diagonal argument?