I just had a disturbing thought this morning. Cantor’s diagonal argument, very famous, fails. Always fails.

(Before I progress to that, any idea how I can find a computer algorithm whose speed is order of magnitude the https://en.wikipedia.org/wiki/Half-exponential_function)

Now back to Cantor’s diagonal argument. It’s his proof that the real numbers have greater cardinality than the natural numbers. From memory, it goes something like this.

Suppose that we can order the real numbers in sequence. Do this ordering. Take the first digit of the first number and change it, then the second digit of the second number and change it, the third digit of the third number and change it. etc. Then the resulting selection of digits forms a number that is not in the list. So real numbers can’t be ordered.

But there is a well known problem with this. The real number 1.0000000… is the same as the real number 0.9999999… so the second number is on the list even though all the digits are different. Somebody a hundred or so years ago must have found a workaround for this, but I don’t know what it is.

Now my construction is as follows. Write the real numbers between zero and one in binary format and parse the resulting binary tree. Use the sequence:
1.0000000…
0.0000000…
0.1000000…
0.0100000…
0.1100000…
0.0010000…
etc.

Now follow Cantor’s construction. Take one digit from each number in sequence and change it. We get result:
0.1111111…
which is equal to 1.0000000…
because it’s 1/2 + 1/4 + 1/8 + 1/16 + … = 1.

Further, no matter how we parse the binary tree after the first two numbers 1 and 0, Cantor’s diagonal argument always gives 0.1111111…
which is equal to 1.0000000…

Even further, no matter how many finite rearrangements of the above sequence we make, it doesn’t matter if 1.0000000… is in the millionth position for instance, Cantor’s diagonal argument always generates a binary number that ends …0111111… which is a number in the sequence.

Cantor’s diagonal argument only requires there be a single exception to the rule that the resulting selection of digits forms a number that is not in the list. And I’ve found that.

So the cardinality of the real numbers is the same as that of the natural numbers. Not a different cardinality as Cantor claims.

So where have I gone wrong? Or have I gone wrong?

mollwollfumble said:

I just had a disturbing thought this morning. Cantor’s diagonal argument, very famous, fails. Always fails.

(Before I progress to that, any idea how I can find a computer algorithm whose speed is order of magnitude the https://en.wikipedia.org/wiki/Half-exponential_function)

Now back to Cantor’s diagonal argument. It’s his proof that the real numbers have greater cardinality than the natural numbers. From memory, it goes something like this.

Suppose that we can order the real numbers in sequence. Do this ordering. Take the first digit of the first number and change it, then the second digit of the second number and change it, the third digit of the third number and change it. etc. Then the resulting selection of digits forms a number that is not in the list. So real numbers can’t be ordered.

But there is a well known problem with this. The real number 1.0000000… is the same as the real number 0.9999999… so the second number is on the list even though all the digits are different. Somebody a hundred or so years ago must have found a workaround for this, but I don’t know what it is.

Now my construction is as follows. Write the real numbers between zero and one in binary format and parse the resulting binary tree. Use the sequence:
1.0000000…
0.0000000…
0.1000000…
0.0100000…
0.1100000…
0.0010000…
etc.

Now follow Cantor’s construction. Take one digit from each number in sequence and change it. We get result:
0.1111111…
which is equal to 1.0000000…
because it’s 1/2 + 1/4 + 1/8 + 1/16 + … = 1.

Further, no matter how we parse the binary tree after the first two numbers 1 and 0, Cantor’s diagonal argument always gives 0.1111111…
which is equal to 1.0000000…

Even further, no matter how many finite rearrangements of the above sequence we make, it doesn’t matter if 1.0000000… is in the millionth position for instance, Cantor’s diagonal argument always generates a binary number that ends …0111111… which is a number in the sequence.

Cantor’s diagonal argument only requires there be a single exception to the rule that the resulting selection of digits forms a number that is not in the list. And I’ve found that.

So the cardinality of the real numbers is the same as that of the natural numbers. Not a different cardinality as Cantor claims.

So where have I gone wrong? Or have I gone wrong?

You’ve gone wrong by treating the sequences as the digits of reals, which is not part of Cantor’s construction and adds extra “rules”.

dv said:

You’ve gone wrong by treating the sequences as the digits of reals, which is not part of Cantor’s construction and adds extra “rules”.

I have to be wrong because every one of those sequences is a rational number. No transcendental numbers anywhere.
But if I make the sequence a sequence of transcendental numbers then it is always possible to arrange those transcendental numbers so that the diagonal is a rational number.

Ugh, Firefox is glitching on me. text is jumping up and down the screen.

The wikipedia starts with assuming that the real numbers are isomorphic to the power set on the natural numbers. But they’re not.
Because in binary 011111111… is exactly equal to 100000000…

mollwollfumble said:

dv said:

You’ve gone wrong by treating the sequences as the digits of reals, which is not part of Cantor’s construction and adds extra “rules”.

I have to be wrong because every one of those sequences is a rational number. No transcendental numbers anywhere.
But if I make the sequence a sequence of transcendental numbers then it is always possible to arrange those transcendental numbers so that the diagonal is a rational number.

Ugh, Firefox is glitching on me. text is jumping up and down the screen.

The wikipedia starts with assuming that the real numbers are isomorphic to the power set on the natural numbers. But they’re not.
Because in binary 011111111… is exactly equal to 100000000…

Nope, it’s just a sequence. It does not represent a number.

Remember: all he is proving is that noncountable infinities exist

dv said:

mollwollfumble said:

dv said:

You’ve gone wrong by treating the sequences as the digits of reals, which is not part of Cantor’s construction and adds extra “rules”.

I have to be wrong because every one of those sequences is a rational number. No transcendental numbers anywhere.
But if I make the sequence a sequence of transcendental numbers then it is always possible to arrange those transcendental numbers so that the diagonal is a rational number.

Ugh, Firefox is glitching on me. text is jumping up and down the screen.

The wikipedia starts with assuming that the real numbers are isomorphic to the power set on the natural numbers. But they’re not.
Because in binary 011111111… is exactly equal to 100000000…

Nope, it’s just a sequence. It does not represent a number.

+1