Cantor's Diagonalization Proof of the uncountability of the real numbers

Hurkyl

If I'm understanding what you describe, then you truly do generate a list containing every finite decimal, no matter how long. The set of terminating decimals is, indeed, countable.

The problem is that most real numbers don't have finite decimal representations. It sounds like you have a specific algorithm in mind; can you write down the first 10 or so numbers? After that, can you tell me at what place the number 1/9 appears?

andrewr

Yes, and Yes, although your second question can't be written down inside a text terminal of this size. Representation of an integer is not the same as existence of that same integer.
There are many counting numbers which we know exist, but can't be written down inside a text terminal of this size.

You would agree, no doubt, that "0.999999999....." is a representation of a real number; and by the ellipsis I am suggesting a pattern for something which is much larger than I would like to write down, although I DO KNOW HOW to write it down -- eg: and that the representation improves in accuracy and may have a selectable accuracy for a given discussion or purpose.

The algorithm itself can be adapted for various constraints; eg: there are many such algorithms based on a similar methodology.

DO you care if I count only the positive reals, or do I need to include the negative as well?
etc.

Deveno

if you give a recursive enumeration of every real between 0 and 1, that should sufice. such an algorithm, if you indeed possess it and it does what you claim, it would be of great interest to many people.

but...it is highly likely that there is an undiscovered flaw in your algorithm, which might not easily be detectable (especially if the algorithm is of sufficient complexity).

commutative diagrams COULD be proofs. for example p→q is just a small diagram. yes, you have a "different kind of formalizing", but logical need not be lingual. the common usage of diagrams now IS informal, this is true, but formal systems can be created which aren't string manipulation. an example can be found in:

http://www.amazon.com/Laws-Form-G-Sp.../dp/0963989901

until relatively recently, geometric proofs ("pictures" a la Euclid), were the gold standard of "formal proofs". it's likely that as we accumulate more knowledge, better formal systems using more sophisticated building blocks will emerge.

(by the way, metamath is an awesome site).

why, the uniquely defined impossibly inaccessible cardinal, of course :P

andrewr

It is a simple algorithm. Don't underestimate my abilities. :)

I will tailor it to the needs of the discussion. It is probably easier to do an algorithm that counts all possible reals than one limited to [0-1).

Let me ask a question to make sure we are agreeing on a general idea:
I am going to choose a non-repeating decimal to make sure you don't think I am over-simplifying.

Take the number (2)**0.5. The representation of this real number is given to you by a counting number (2) and a function ()**0.5. I would argue that we know such a number is not finite in representation because there is no FINITE sequence of digits which repeats.
eg: the first digits in a 4 mantissa and 4 fractional representation would be: 0001.4142
By induction, the next symmetrical word size up would be:
00001.41428 ... etc.

It is not a rational number that it should be represented by any ratio of counting numbers.

The proof of the infinite nature of the decimal representation is *inductive* in that no matter how many digits I show you, you can claim there is a representation with n+1 digits.

It is not necessary to write all the digits down to show that it is infinite, but simply to show that it grows without bound. But, none the less, the only way to express this number is a mapping through a function (sqrt) of a counting number. The sequence of digits, however, 1.41428.... is unique.

I am going to assume that a sequence that preserves previously made digits and adds new ones in a predictable (inductive) pattern is sufficient to show the signature of a unique real number; and that likewise, a counting number may be converged to by a signature (in the reverse direction). Such a pattern, that one may work out to any desired number of digits (without END and therfore infinite) is sufficient to show the existence in the decimal system of such a number. Eg: The sequence 1.41428.... no matter what algorithm produces it, so long as it matches the sequence of digits with not a single exception to the algorithm of sqrt(2) ... must be considered to have produced the same rational number.

I let you ponder that for a bit, because I want to give you the best answer I can.
(This is starting to get fun.... I wish people would help me with my simple statistics and propagation of error problems IF I complete this successfully ..... deal? )

And now the question, is the signature of the rational number inductively matched to all possible digits sufficient to indicate that it has been counted? (I am not saying we actually match all infinite digits, but that we show they *WILL* match.)

Hurkyl

I don't have time to write more, so I'll make a series of brief comments.


Saying "the list X contains 0.1, 0.11, 0.111, 0.1111, and every other (terminating) decimal of that form" is very different from saying "the list X contains 1/9". In fact, the two statements have absolutely nothing to do with one another.


A representation cannot become "more accurate". "0.9999..." is notation for a specific decimal: the decimal with a 9 in every position to the right of the decimal point (and that decimal, in turn, can be interpreted as notation for the real number 1).

When I say every position, I really mean every. The decimal 0.999 has a zero in its millionth's place, for example. 0.999... has a 9 in that place. Pick positive integer x you like: 0.999... has a 9 in the position x places to the right of the decimal.


0.9999 is an approximation to 0.999.... 0.999999 is another (better) approximation to 0.999.... An algorithm that sequentially considers the numbers 0.9, 0.99, 0.999, 0.9999, and so forth does not produce a "representation that changes to become more accurate". Instead, it produces an infinite sequence of different representations of approximations to 1, each one more accurate than the last.



An algorithm that behaves in the aforementioned way, incidentally, is in of itself an exact representation of 1. (where the notation is that we interpret a program that outputs a convergent sequence as notating the limit of that sequence)



Unless you're designing the algorithm specifically for that purpose (or a similar one), it is rather difficult to devise an algorithm whose first time outputting a 'simple' number (like 1/9) happens after so many iterations that you cannot write it down -- even if we insist that you have to write it in decimal form.



The number of digits in the decimal representation of [itex]\sqrt{2}[/itex] doesn't "grow without bound" -- it's just a number, it doesn't make sense to "grow". The number is [itex]\aleph_0[/itex].


Rational numbers (even integers) can be limits of sequences of terminating decimals whose number of non-zero digits grows without bound. (e.g. the sequence 0.1, 0.11, 0.111, ...) (e.g. the sequence 0.1, 0.011, 0.00111, 0.0001111, 0.000011111, ...)

MrAnchovy

Yes andrewr you can add √2 to the countably many rational numbers and you will still have countably many numbers. By extension you can add all the quadratic irrationals and you will still have countably many, in fact you can add all the roots of polynomial equations and you will have all the algebraic numbers in your list, which is countable.

Are you satisfied that you can create any number possible and put it on the list? So therefore there does not exist any number that is not on the list? Good, because that is exactly the hypothesis that starts Cantor's proof - that all real numbers can be written down in a list such that each real number can be mapped to an integer (its place on the list). Cantor's diagonal argument constructs a number that can plainly be seen not to be on the list: if you pick any number in the list in position n, the constructed number is different from the number on the list at least in it's nth decimal digit. The hypothesis was clearly wrong.

Far from contradicting Cantor's proof, you have simply demonstrated that you can produce a list that is the starting point for that proof.

SteveL27

No. There is no "starting point" for the proof.

Cantor asks us to consider a list of ALL the real numbers. He then constructs a real number not on that list, showing that ANY such list is necessarily incomplete. Therefore there can be no list of all real numbers.

Cantors proof has NOTHING to do with taking some countable list and trying to add numbers to it. That's a misunderstanding that's a source of much confusion.

MrAnchovy

Yes my last sentence was not correct. What I should have said was:

Far from contradicting Cantor's proof, you can use Cantor's diagonal argument to construct a counter-example to show that your (andrewr's) assertion that you can list all of the real numbers using some algorithm is incorrect.

Leucippus

Why should I be impressed by this? You still haven't convinced me that you could ever reach the "bottom" of a list that would even contain all rational numbers.

This seems to be the point that everyone is not fully understanding.

I'm not the slightest bit worried about the list that you care "creating" as you are crossing numbers out. That list is totally meaningless.

Why?

Well it should be obvious.

Stop your diagonalization process at any point. You claim to now have a number that is not on the list above where you are working. So? Big deal.

What so you have at that point? What number have you just created thus far?

Well, clearly since you've stopped you have a truncated decimal number. I can absolutely guarantee that you are standing there holding a valid Rational number. In other words, you haven't created a "new number" that isn't already on the list Rational numbers.

All you've succeeded in doing it proving that the number you've created thus far is not on the list above where you are working. But you haven't demonstrated that it is a "new number" that can't already be on the list of Rational numbers.

In fact, it can easily be shown that this will always be the case.

Let say that you have gone out ten places and you have created the following "new number":

0.3854736394

That number cannot possibly be on your list above where you are working. But clearly as a truncated number it must necessarily already be on the list of rational number.

Moreover, no matter which numeral your process chooses for the next supposedly "New Number" I can guarantee that the number you create will be on the list of Rational Numbers.

This should be extremely ease to see.

How many digits do we have to chose from to use as our replacement digists? Well we have ten of them 0 thru 9. So let's try that and see if we can create a "New Number" that isn't already a valid Rational Number using this process:

Here's the number we're claiming is already a "New Number" that can't already be on the list of Rational Numbers:

0.3854736394

Granted this is cheating because I've stopped the process. But bear with me,....

What can we possible add to this number next? Well we can tack on anything between or including 0 thru 9. So lets do that,...


0.38547363940
0.38547363941
0.38547363942
0.38547363943
0.38547363944
0.38547363945
0.38547363946
0.38547363947
0.38547363948
0.38547363949

I've just created ten supposedly "New Numbers" that potentially could not be on the list above where I'm working. So big deal? All of these numbers (ever single last one of them) must necessarily be on a list of Rational numbers. In fact, you can take that even further and proclaim that there must necessarily be infinitely many Rational numbers that begin with any one of the numbers listed above and have a different sequence of numerals after that.

Take the original number we've created and just add any arbitrary digits to it that you care to chose on a whim and you've got yet another Rational number:

0.3854736394abcdefghijklmnopqrstuvwzyz etc. (potentially to infinity, what's going to stop you ever)

Chose any arbitrary digit from 0 to 9 for the letter variables above and you'll have a perfectly legitimate Rational number.

So at not point in this process can you claim to have created a "New Number" that can't be on the list of Rational Numbers. In fact, you can be absolutely guaranteed that you will always have a valid Rational Number at ALL TIMES in your process.

So what's Cantor's point? That if you continue this process out to "infinity" you will have somehow miraculously created a sequence of numerals that can't be Rationalized.

But wait? When would this occur? When could Cantor ever actually COMPLETE this infinite process in order to claim to have created a NEW NUMBER that isn't already on the list of Rational Numbers?

He hasn't proven anything at all. All he's done is rely on the "the definition" that we claim that real decimal expansion never quist going whereas a supposedly "Rational Number" must truncate.

But what sense is there truly to even claiming that a Rational Number "must truncate"?

What sense does that truly make? What would ever prevent you from adding yet another numeral digit to a string of numerals representing a Rational Number?

At the very BEST, all Cantor has done is claim that Real numbers must be expressed using infinite decimal expansions and all Rational Numbers must truncate. But that's not a proof of anything. It's just an assumption of an arbitrary man-made definition.

Unless Cantor can actually show that he can successfully "complete" this infinite process and actually have obtained a "new sequence of numerals" that can't already be on a list of Rational numbers, then he hasn't proven anything.

This is why I agree with Henri Poincare on this point. Pretending that an infinite process could be "completed" is an absurd idea to begin with and will always result in utterly meaningless or absurd results.

Cantor hasn't proven anything with this proof other than he's still clinging to the idea of a "completed infinity". He's trying to treat infinity as though it can be thought of as being finite.

It makes not sense for Cantor to even proclaim to have created a "new number" unless he can "complete" his process and show us this "new number" that he has created.

But he can NEVER do that because his process requires that it must never STOP, if it ever is said to STOP what does he have? He's standing there holding perfectly valid Rational Number.

So his so-called "proof" is nothing short of utter absurdity.

Well, I am in agreement with you on the, quite passionately actually.

In fact, I take precisely the opposite view of Micromass. If you can show me graphically, or physically something the totally defines mathematical formalism, then as far as I'm concerned it's the mathematical formalism that must then necessarily be wrong. Certainly not physical reality.

And currently we have no physical proof (or even reason to believe) that anything can be infinite much less that multiple cardinal sizes of infinities should exist.

micromass

Sigh...

There is no bottom, that's the point. There is no end point.

You don't stop your diagonalization process. It continues for an infinite number of times.

You haven't demonstrated that because you can't. Clearly, if you stop your process then you will get a valid rational number. If you don't stop your process then you get a real number not on your list.

Yes. It is cheating. So don't stop the process. You have to continue it.

I'm not even reading the rest since it is so comically wrong. Instead of giving all these arguments, why not find an error in the formal proof??

This is important. Infinite and cardinal sizes indeed do not exist in reality (I think). But this is COMPLETELY irrelevant. You have to see mathematics as a series of symbols which don't carry meaning. Mathematics is about manipulating those symbols. Whatever meaning the symbols have, is completely irrelevant. We interpret it as some kind of infinity. But this is simply an interpretation and not the theory itself.

Leucippus

Surely you meant to say, Cantor asks us to consider a list of ALL the "rational" numbers. He then constructs a real number not on that list.

But how can he claim to have ever created a number that is not already on the list of ALL rational numbers?

The way he can possibly claim to have done this if he does indeed take his process out finitely (without ever terminating it).

But if he never terminates it, then how can he claim to have "created" a new number?

It seems to me that all he's doing is trying to depend on an idea that "real" numbers must be infinite whilst rational numbers are thought of as somehow needing to terminate.

But in truth, why should a Rational number need to ever terminate?

What would cause a Rational number need to terminate? Aren't the Rational numbers themselves supposed to be infinite in size? (i.e. unbounded, unending)

All a Rational number is, is a fraction of Natural Numbers.

So we can write:

123/321

That's a rational number.

How about 1234/4321?

That's a rational number too.

How about 12345/54321

Again a rational number.

In fact, is there any reason why we would need to stop this process?

Clearly there is no end to the Rational numbers we can create. That's why they are considered to be an infinite set of numbers.

So what sense does it even make to claim that a Rational Number should necessarily "terminate"?

We have no reason to even place this restriction on the numerators and denominators of the fractions that define them.

In short, we actual have no logical reason to claim that a Rational number must terminate.

That's just an arbitrary idea made up by mankind to try to make a distinction between a "Rational Number" and a "Real Number".

But do we truly even need a concept of "Real Numbers" at all?

I say no, we don't.

The very idea of "Real Numbers" is an erroneous idea that is not even required to describe physical reality. There is nothing in physical reality that even requires this concept.

MrAnchovy

Leucippus you are still insisting that there are more rows than there are columns: do you think that there are flaws in each of these arguments that I have presented?

MrAnchovy

NOOOOOO - Cantor asks us to construct a list of all the real numbers. He then constructs a real number not on that list, proving that such a list cannot exist.

micromass

No, Cantor asks us to consider a list of all REAL numbers.

Take:

0.1
0.11
0.111
0.1111
0.11111
0.111111
...

then Cantor diagonalization yields 0.1111111111... which is not on this list. This is a simple example. Cantor diagonalization ALWAYS yields a number not on the list. Cantor wants you to look at a list of ALL real numbers and it will construct a number not on the list.

The formal proof clarifies this. There is no question of "terminating". Cantor diagonalization is not a dynamical process.

It doesn't. 1/3=0.33333... never terminates.

What process?? Do you mean taking the limit?? The limit of rational numbers doesn't need to be rational.

It doesn't.

Agreed.

Take a a square with side 1m. What is the size of its diagonal? Is this rational?

Leucippus

Talk about a comical statement. If you don't stop your process you'll never be able to claim have ever 'gotten' anything.

I'm telling you that Henri Poincare is right. The very idea that you can pretend to have completed an infinite process without stopping it is an utterly absurd and meaningless idea.

It's simply nonsense.

It makes no sense.

As a physicist it's not irrelevant to me. As a physicist why should I even be remotely interested in a mathematical formalism that is built on band-aides and crutches that have absolutely nothing at all to do with the physical reality that I might be interested in studying?

Why should I apply a mathematical formalism to reality if that formalism has nothing to do with reality?


Well, that's fine for someone who might be interested in totally abstract meaningless logical systems.

But as a physicist why should I be interested in playing such games?

I may as well play dominoes if I'm going to do that.

I'm more interesting in finding (or creating) a "mathematical formalism" that can actually be used to properly describe the true nature of reality.

MrAnchovy

If I want to put a diagonal brace in a frame with sides of 1 unit I require √2 which is not rational.

If I want to put a tyre on a wheel I will need ∏ which is not rational.

If I want to calculate how much ²³⁵U I have left in a rector after 1 month I need e which is not rational.

micromass

This thread is going off-topic. Therefore:

Moderator note: This thread will only deal with Cantor's diagonalization proof. The invalidity of infinity and real numbers will be considered off-topic and the post will be deleted. If you want to discuss this topic, create a new thread.

Furthermore, since informal arguments are clearly not convincing.

Moderator note: This thread will only deal with the rigorous version of Cantor's proof which is found in post 24 or in any serious set theory book.