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

[Jorriss]

This is kind of off topic but I'm curious why graphs can not be proofs (I have not taken a course on logic)?

 

[micromass]

more to the point: many proofs in algebraic topology or category theory amount to: diagram-chasing. the diagram IS the proof, in some cases.

A commutative diagram is not a proof. And many mistakes in category theory actually amount to misleading diagrams. A commutative diagram is a suggestion of a proof. It is merely an illustration.

If you look at Bourbaki, then they show that they treat commutative diagrams very rigorously. They try to prove everything with algebraic means.

To me, a proof is correct if it formilizable in some kind of logical system. You don't actually NEED to formalize it, but just giving a suggestion that it can be done is good enough.

 

[Hurkyl]

Precisely what Henri Poincare warned Cantor not to do (i.e. not to think of infinity as a completed thing)

Ah joy, "completed infinity".

Just for your information, I have never encountered somebody who uses that terms that could give an even quasi-rigorous account of what the term means.

From observing people who use it, I quite honestly believe that it literally means "I am unwilling or unable to engage in one more layer of abstraction, and thus have failed to recognize that we're talking about the same idea." (I don't mean insult by this, except possibly in the 'unwilling' case)

 

[micromass]

This is kind of off topic but I'm curious why graphs can not be proofs (I have not taken a course on logic)?

Hmmm, I don't think I'm expressing myself clearly enough.

There are actually two kind of proofs: informal and formal proofs.

By the very definition, a proof is formal. A proof is defined as a sequence of logical algebraic steps. Each step follows from another step by applying an inference rule.

These things are the actual proofs. However, they are EXTREMELY hard to read. If all math books would consist out of formal proofs, then math books would be unreadable.

That's why we allow informal proofs. An informal proof presents people the basic ideas and reasoning of a proof. An informal proof suggests that the formal proof can be carried out if one would want to do so.

All textbooks contain informal proofs (and it's good that they do). Text books like to work with a lot of text and a lot of pictures to make it easier on the student. But one should always keep in mind that one should be able to formalize the proof.

And indeed, one can formalize all the proofs. An example is given by http://us.metamath.org/index.html which contains thousands of proofs including the celebrated Hahn-Banach theorem. This site shows what actual formal proofs look like. And as one can see, it is completely unreadable. (the site also shows formal proofs in plane geometry, including constructibility).

I am NOT advocating that everybody should be using formal proofs in journals or education. Quite the contrary. But the students should be well-aware that the formal proof can be carried it if one wants to do it.

 

[Jorriss]

Hmmm, I don't think I'm expressing myself clearly enough.

There are actually two kind of proofs: informal and formal proofs.

By the very definition, a proof is formal. A proof is defined as a sequence of logical algebraic steps. Each step follows from another step by applying an inference rule.

These things are the actual proofs. However, they are EXTREMELY hard to read. If all math books would consist out of formal proofs, then math books would be unreadable.

That's why we allow informal proofs. An informal proof presents people the basic ideas and reasoning of a proof. An informal proof suggests that the formal proof can be carried out if one would want to do so.

All textbooks contain informal proofs (and it's good that they do). Text books like to work with a lot of text and a lot of pictures to make it easier on the student. But one should always keep in mind that one should be able to formalize the proof.

And indeed, one can formalize all the proofs. An example is given by http://us.metamath.org/index.html which contains thousands of proofs including the celebrated Hahn-Banach theorem. This site shows what actual formal proofs look like. And as one can see, it is completely unreadable. (the site also shows formal proofs in plane geometry, including constructibility).

I am NOT advocating that everybody should be using formal proofs in journals or education. Quite the contrary. But the students should be well-aware that the formal proof can be carried it if one wants to do it.

I better see what you're getting at now. Thank you for clarifying.

 

[micromass]

I better see what you're getting at now. Thank you for clarifying.

Just to clarify it some more: if I see a graph somewhere which intuitively shows me something, then I will accept this as proof. Any mathematical journal (except logic-journals) will accept it as a valid proof. If you write it on the exam, then the professor will accept it as proof (except in a logic class). But it's not a formal proof in the strict sense of the word.

 

[Hurkyl]

mm: I think the point Deveno makes (and maybe that Jorriss is wondering about) is that proof theory can be cast in settings other than string processing.

For example, arithmetic expressions and equations in category theory are often presented in graphs.

In Categories, Allegories, Freyd introduces the idea of a Q-sequence (and a Q-tree) that consists of a path through a category and a sequence of quantifiers, which can replace the role of formulas.

Applied to the category of finitely-presented categories, he uses them to prove a metatheorem that an equivalence functor preserves and reflects a property if and only if it can be expressed on a blackboard.

 

[andrewr]

I really don't understand what you're trying to say. The axiom of choice has nothing, absolutely nothing to do with Cantor's diagonalization.

IN my discussions of Aleph Not with my brother, the Axiom of choice does come up.
But, set that aside -- what I am saying is that I believe I can show an algorithm which will demonstratably count every possible decimal number in the decimal notation system, uniquely, and once.

eg: 1.01 will be counted exactly once, as will 2.01, 2.011, 2,0000001, etc.
I am not trained in formal mathematical proofs with respect to Aleph not, etc, so excuse my vagueness.
However, my understanding is that the Real numbers are representable by the decimal notation system; and that the "Ideal" representation of all real numbers is spanned by a mantissa and fraction portion that becomes more and more perfect as the number of digits in each is allowed to grow arbitrarily large.

If I were to demonstrate an algorithm which showed that all possible decimal numbers can be counted with a distinct index; say 'i' so that any imaginable real number would exist "somewhere" in a sequence defined by an index (i) which is an integer from 0 to as large as one likes. eg: every possible decimal number could be found by a static algorithm called f(i).

The only issue which would come up is the representation of 0.99999999... vs. 1.00000... and whether or not they are distinct numbers as i becomes arbitrarily large.

If I am following the argument correctly, Cantor appears to be claiming that such a unique counting is impossible. So if I gave a simple counter-example in decimal notation -- would such an algorithm be of use in this discussion?

 

[Hurkyl]

eg: 1.01 will be counted exactly once, as will 2.01, 2.011, 2,0000001, etc.

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]

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?

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]

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.

if you give a recursive enumeration of every real between 0 and 1, that should sufice. such an algorithm, if you indeed possesses 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).

A commutative diagram is not a proof. And many mistakes in category theory actually amount to misleading diagrams. A commutative diagram is a suggestion of a proof. It is merely an illustration.

If you look at Bourbaki, then they show that they treat commutative diagrams very rigorously. They try to prove everything with algebraic means.

To me, a proof is correct if it formilizable in some kind of logical system. You don't actually NEED to formalize it, but just giving a suggestion that it can be done is good enough.

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:

https://www.amazon.com/dp/0963989901/?tag=pfamazon01-20

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).

Ah joy, "completed infinity".

Just for your information, I have never encountered somebody who uses that terms that could give an even quasi-rigorous account of what the term means.

From observing people who use it, I quite honestly believe that it literally means "I am unwilling or unable to engage in one more layer of abstraction, and thus have failed to recognize that we're talking about the same idea." (I don't mean insult by this, except possibly in the 'unwilling' case)

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

 

[andrewr]

if you give a recursive enumeration of every real between 0 and 1, that should sufice. such an algorithm, if you indeed possesses 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).

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 therefore 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 \sqrt{2} doesn't "grow without bound" -- it's just a number, it doesn't make sense to "grow". The number is \aleph_0.


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, ...)

 

[pbuk]

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]

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

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.

 

[pbuk]

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]

Leucippus, let me offer you a variant of Cantor's proof, that show that your consideration of "slope" is irrelevant:

{... snip for brevity ...}

we continue in this way.

now the "slope" is "even worse" the diagonal is not even as steep as before. nevertheless, no matter which n we pick, the diagonal number differs from the first n numbers in our list, so it differs from every number on our list (it differs from the k-th number in the 10^k-1-th digit).

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 let's 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 anyone 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.

@ micromass: i disagree with the contention that if a proof can only be demonstrated graphically, it isn't valid. for what is a formal system, if not a few squiggles on paper? is that not graphical? i don't know about you, but i read most of my mathematics.

more to the point: many proofs in algebraic topology or category theory amount to: diagram-chasing. the diagram IS the proof, in some cases. there's no logical reason why "pictures" can't be made every bit as unambiguous and consistent as well-formed formulas. constructing a length with a compass and straight-edge IS a proof of constructibility (a concept which can be expressed purely algebraically).

there is many people who think that a mathematical result "isn't true" until it is proven formalizable in (first- or second-) order logic in a formal language that has encoded the axioms of Zermelo-Frankel set theory. this is unfortunate.

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...

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.

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

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.

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

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.

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.

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,...

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??

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.

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]

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.

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.

 

[pbuk]

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?

 

[pbuk]

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.

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]

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.

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

But how can he claim to have ever created a number that is not already on the list of ALL rational 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 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?

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

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?

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

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?

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

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"?

It doesn't.

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.

Agreed.

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.

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

 

[Leucippus]

Sigh...
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.

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.

This is important. Infinite and cardinal sizes indeed do not exist in reality (I think). But this is COMPLETELY irrelevant.

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?

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.

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.

 

[pbuk]

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.

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.

 

[Leucippus]

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.

Ok MrAnchovy. I get it now!

You've answered my question and solved the whole problem. I was indeed viewing the proof incorrectly.

Unfortunately it doesn't help.

Why does it not help?

Because it would be a totally futile and meaningless "proof". In fact, he would be supposedly 'proving' something that necessarily falls out of how he is defining a "Real Number".

He's simply demanding that a "Real Number" is necessarily an "infinite" decimal expansion by definition and assuming that a "Rational Number" cannot be described by an "infinite" decimal expansion.

Another problem is that his "proof" would obviously work for any numbers. Not just reals.

Think of it this way. Just take the decimal point in his proof in his proof away.

What do you have left? A list of natural numbers.

You can go down that list in precisely the same way and proof that even the Natural Numbers can't be put into a correspondence with themselves.

How so?

Well, let's try it.

Start our list with the arbitrary natural number of 1

1

We cross that out and replace it with any arbitrary digit (say 9) So we have a "new number" 9.

Lets continue, we'll need a two digit number to work on next so let's choose 23 our list so far looks as follows:

1
23

Replace the 3 with 5. Our newly constructed number is 95.

Move down another row pick another arbitrary natural number, we'll need one that is at least 3 digits wide or more, let's pick 3476 just for fun.

Here's our new list

1
23
3476

Now we need to replace the 7 with something other than 7, let's choose 8.

Our new number is now 958, and so on.

So we currently have a list of natural numbers

1
23
3476

And thus far we've created a "new number" 958 that isn't on this list.

And we can continue down the list like this just like Cantor and end up with precisely the same situation he has. (i.e. we can create a supposedly "new" natural number that isn't already on the list of numbers that we have created in this way)

Does that mean that we can create a new Natural Number that isn't already on the list of Natural Numbers? And that the Natural Numbers must then be "uncountably infinite" just like the Reals?

This so-called "proof" doesn't prove anything. In fact, if it proves anything at all it proves that the Natural Numbers must have the same weird cardinality as the reals because we can use the very same process as Cantor used to prove it for the Natural Numbers too.

So how are we any further ahead toward proving anything unique?

 

[micromass]

Ok MrAnchovy. I get it now!

You've answered my question and solved the whole problem. I was indeed viewing the proof incorrectly.

Unfortunately it doesn't help.

Why does it not help?

Because it would be a totally futile and meaningless "proof". In fact, he would be supposedly 'proving' something that necessarily falls out of how he is defining a "Real Number".

He's simply demanding that a "Real Number" is necessarily an "infinite" decimal expansion by definition and assuming that a "Rational Number" cannot be described by an "infinite" decimal expansion.

Another problem is that his "proof" would obviously work for any numbers. Not just reals.

Think of it this way. Just take the decimal point in his proof in his proof away.

What do you have left? A list of natural numbers.

You can go down that list in precisely the same way and proof that even the Natural Numbers can't be put into a correspondence with themselves.

How so?

Well, let's try it.

Start our list with the arbitrary natural number of 1

1

We cross that out and replace it with any arbitrary digit (say 9) So we have a "new number" 9.

Lets continue, we'll need a two digit number to work on next so let's choose 23 our list so far looks as follows:

1
23

Replace the 3 with 5. Our newly constructed number is 95.

Move down another row pick another arbitrary natural number, we'll need one that is at least 3 digits wide or more, let's pick 3476 just for fun.

Here's our new list

1
23
3476

Now we need to replace the 7 with something other than 7, let's choose 8.

Our new number is now 958, and so on.

So we currently have a list of natural numbers

1
23
3476

And thus far we've created a "new number" 958 that isn't on this list.

And we can continue down the list like this just like Cantor and end up with precisely the same situation he has. (i.e. we can create a supposedly "new" natural number that isn't already on the list of numbers that we have created in this way)

Does that mean that we can create a new Natural Number that isn't already on the list of Natural Numbers? And that the Natural Numbers must then be "uncountably infinite" just like the Reals?

This so-called "proof" doesn't prove anything. In fact, if it proves anything at all it proves that the Natural Numbers must have the same weird cardinality as the reals because we can use the very same process as Cantor used to prove it for the Natural Numbers too.

So how are we any further ahead toward proving anything unique?

No. If you do that same prace on the natural numbers then you get a number which extends indefenitely to the left. For example ...999999999. This is NOT a natural number, so this doesn't apply. (instead, it's a so called p-adic number, Cantors diagonalization shows that the p-adics are not countable).

The difference with Cantor diagonalization on the reals is that you end up with a number which extends indefinitely after the decimal point. This IS a real number.

 

[pbuk]

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.

Awww, I was getting so close to this:

If there are as many rows (real numbers) as there are columns then you can construct the diagonal number which is not in any row, hence the contradiction that shows that this cannot be the case.

If there are more rows (real numbers) than there are columns (natural numbers) then... we don't need to construct anything - this is exactly what we are trying to prove!

 

[Preno]

Because it would be a totally futile and meaningless "proof". In fact, he would be supposedly 'proving' something that necessarily falls out of how he is defining a "Real Number".

Yes, that is how proofs generally work.

 

[Leucippus]

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.

With all due respect doesn't this seem to be a bit restrictive?

You just asked me yourself, "What process?? Do you mean taking the limit?? The limit of rational numbers doesn't need to be rational."

A question like that demands addressing the very concept of LIMIT.

You, as a mathematician, should be fully aware that the LIMIT process of calculus does not prove the existence of what the limit equals. On the contrary all that is required to prove a limit is that certain trends and conditions have been proven. The actual result (i.e. the number that the limit is equal to) cannot be said to necessarily "exist".

Surely you're aware of this. You can prove that a "limit exists" for functions where the value of the limit is undefined and therefore in terms of the "function" itself that point does not exist.

So a taking any process to a limit does not imply that the result has any actual "existence".

That may seem to have nothing to do with Cantor's diagonalization proof, but it's very much a part of it. Cantor is claiming that because he can take something to a limit that necessarily proves that the thing the limit is pointing too exists.

That's actually a false use of Limits anyway.

The epsilon-delta definition of limits won't even support any such conclusions.

So is that "off-topic" or is it required information concerning the proof in question?

The proof basically demands that something has been taken to a limit.

So how could that topic not be part of the proof?

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.

Well, I've already voiced my views on this.

If an informal intuitive or graphical argument can be shown to trump a mathematical axiom, then which should be accepted as being more reasonable?

Actually if you demand that we stick solely to the axioms of set theory then how could we ever show that they are flawed? They would necessarily contain those flaws.

Finally, and very sincerely,...

If you don't feel that this forum is the proper venue for fleshing out these kinds of ideas, then may I ask if you can point to an appropriate forum or website where an intuitive approach to reason is deemed acceptable to discuss.

It not my intent to step on anyone's toes.

But I seriously would like to flesh out these ideas with people who are at least intelligent and professional enough to be capable of comprehending the points I'm attempting to address.

Clearly since these are concerns associated with mathematical formalism, it only makes sense to discuss them with people who at least have some understanding of mathematics.

But it seems to be rather fruitless if they are just going to demand that the status quo cannot be challenged without first accepting the very axioms that are in question.

Where can I propose ideas like these without having them immediately dismissed simply because they are indeed challenging sacred axioms?

Or has mathematics become a religion where any suggestion that its axioms might contain flaws is considered totally unacceptable blaspheme?

You can't very well use a formal axiomatic system to disprove itself.

If there are "flaws" in the formal system they must necessarily be address from an external intuitive approach.

That's my position on that.

So can you suggest a website math forum where intuitive reasoning has not yet been cast asunder as being totally worthless?