The Countable (Dedekind) Reals

[bobmax]

In your judgement, where does Cantor's Diagonal Argument go wrong?

Cantor's diagonal argument is wrong because it claims to actualize the infinite.
It treats the infinite as if it were a thing.
And in so doing it falls into contradiction.
Because he considers an infinite elaboration possible, after which another elaboration takes place.
A nonsense.

So much so that following the same procedure it is possible to show that not even positive integers are countable!
It is in fact sufficient to put many zeros to the left of each number. As many as you need (infinite). And then apply the diagonal argument.
An absurdity.

[Skepdick]

In your judgement, where does Cantor's Diagonal Argument go wrong?

What do you mean by "wrong"? It doesn't go "wrong" anywhere per se. Diagonalisation is a very powerful and broadly applicable argument which defeats various claims for countability for all the usual number system encodings.

Which is why the video explains (in great depth) how to construct and encode Real numbers in a way that they can't be diagonalized by using various tricks which undermine the necessary properties of the system exploited by diagnalisation.

Perhaps this additional context will help you. A useful/relevant snippet.

Lawvere’s fixed point theorem

And this is what Lawvere realized: The diagonal argument establishes the relationship between the existence of a surjection on the one hand, and the existence of a no-fix-point mapping on the other hand. So far it’s been easy to find a no-fix-point functions. But let’s reverse the argument: If there is a surjection A -> (A -> Y) then every function Y -> Y must have a fixed point. That’s because, if we could find a no-fixed-point function, we could use the diagonal argument to show that there is no surjection.

But wait a moment. Except for the trivial case of a function on a one-element set, it’s always possible to find a function that has no fixed point. Just return something else than the argument you’re called with. This is definitely true in Set, but when you go to other categories, you can’t just construct morphisms willy-nilly. Even in categories where morphisms are functions, you might have constraints, such as continuity or smoothness. For instance, every continuous function from a real segment to itself has a fixed point (Brouwer’s theorem).

As usual, translating from the language of sets and functions to the language of category theory takes some work. The tricky part is to generalize the definition of a fixed point and surjection.

[alan1000]

This is not an area of mathematical philosophy that I'm very familiar with... but I believe that if one wanted to prove that the real numbers are countably infinite, it will be necessary to disprove Cantor's Diagonal Argument. What is the disproof of the argument?

[alan1000]

I'm still waiting.

[Skepdick]

This is not an area of mathematical philosophy that I'm very familiar with... but I believe that if one wanted to prove that the real numbers are countably infinite, it will be necessary to disprove Cantor's Diagonal Argument. What is the disproof of the argument?

I'm still waiting.

Why have you waited more than a month to watch/understand a 1 hour video?

Here is the part of the video literally called Beating diagonalization

[bobmax]

This is not an area of mathematical philosophy that I'm very familiar with... but I believe that if one wanted to prove that the real numbers are countably infinite, it will be necessary to disprove Cantor's Diagonal Argument. What is the disproof of the argument?

Why?

Cantor's diagonal argument may well be wrong without that real numbers are countably infinite.

In fact, the argument is incorrect. While the infinite is undecidable, as it does not exist.

[Skepdick]

Why?

Cantor's diagonal argument may well be wrong without that real numbers are countably infinite.

In fact, the argument is incorrect. While the infinite is undecidable, as it does not exist.

Bah! That stupid word "exists" can literally be used as a predicate and used to perform computations.

If the infinite does not exist then you should be able to prove the finite output of this Haskell program.

Code: Select all

reverse [0..]

[0..] is literally a representation of ℕ. If you don't believe me - check for yourself. Every number you can think of is in there.

[wtf]

This is not an area of mathematical philosophy that I'm very familiar with... but I believe that if one wanted to prove that the real numbers are countably infinite, it will be necessary to disprove Cantor's Diagonal Argument. What is the disproof of the argument?

Posted at 4:38am forum time.

I'm still waiting.

Posted at 4:41am forum time, three minutes later.

That gave me a chuckle. No worries, I'm an impatient type too.

For the doubters, Cantor gave not one, not two, but three separate proofs that the reals are uncountable. By far the simplest and most striking is Cantor's theorem, which shows that any set has strictly smaller cardinality than its powerset.

This beautiful theorem shows that not only do the reals have larger cardinality than the natural numbers (because the reals are easily bijected to the powerset of the naturals); but that also there is an endless hierarchy of cardinalities, each strictly larger than the previous one.

Why have you waited more than a month to watch/understand a 1 hour video?

That's from a talk by Andrej Bauer, a noted constructivist mathematician. Of course the constructive reals are countable (* see below). The standard reals are uncountable. Cantor's results pertain to the standard reals. But note that even constructive mathematicians believe in infinite sets; whereas @Bobmax does not. @Bobmax wrote:

In fact, the argument is incorrect. While the infinite is undecidable, as it does not exist.

I noted that you replied to @alan1000, but @alon1000 was not doubting Cantor's result, he was challenging doubters for a refutation. I believe your remark was more properly addressed to @Bobmax.

(*) According to this MO thread, the constructive reals are NOT constructively countable, if I'm understanding the thread correctly. It's a bit technical.

https://mathoverflow.net/questions/3064 ... athematics

This reply by Neel Krishnaswami is particularly enlightening.

If you are working in classical mathematics, and regard the computable reals to be those real numbers for which a program exists to generate their digits, then they are countable, since there are at most (classically) countably many programs.

However, if you are working in intuitionistic mathematics, then after you construct the real numbers you can prove using a standard diagonalization argument that the reals are not countable. This shows that the real numbers are not constructively countable. There is no computable construction which puts the computable reals into bijective correspondence with the natural numbers, since that would require the ability to solve the Halting problem -- ie, how do you tell if two programs generate the same stream of digits?

The bottom line seems to be that if we restrict ourselves to constructive math, the computable reals are indeed countable; but we can not PROVE that using constructive math, since there is no computable bijection from the natural numbers to the computable reals.

I don't know how the video you linked gets around that, if it does.

[Skepdick]

This reply by Neel Krishnaswami is particularly enlightening.

If you are working in classical mathematics, and regard the computable reals to be those real numbers for which a program exists to generate their digits, then they are countable, since there are at most (classically) countably many programs.

However, if you are working in intuitionistic mathematics, then after you construct the real numbers you can prove using a standard diagonalization argument that the reals are not countable. This shows that the real numbers are not constructively countable. There is no computable construction which puts the computable reals into bijective correspondence with the natural numbers, since that would require the ability to solve the Halting problem -- ie, how do you tell if two programs generate the same stream of digits?

It's not particularly surprising.

The inequality relation is undecidable for infinite precision reals.

x < y doesn't halt for x=0, y = 0.0000.... (maybe a non-0).

That's because the blank tape (can a Turing machine determine that all of the cells are blank?) problem reduces to the halting problem.

[wtf]

It's not particularly surprising.

The inequality relation is undecidable for infinite precision reals.

x < y doesn't halt for x=0, y = 0.0000.... (maybe a non-0).

That's because the blank tape (can a Turing machine determine that all of the cells are blank?) problem reduces to the halting problem.

I'm glad to see that you agree. If so, can you explain the relevance of the video you linked? If the constructive reals are classically countable but can not be proved to be constructively countable, how is "Beating Diagonalization" accomplished, as the video claims?