Cantor's diagonal argument (I guess technically this comes under set theory)

[jeffceth]

I have a question about the potentially self-referential nature of cantor's diagonal argument (putting this under set theory because of how it relates to the axiom of choice).

If we go along the denumerably infinite list of real numbers which theoretically exists for the sake of the example, then by definition after some finite amount of time we will reach the number which cantor is constructing by going along and making his nth digit differ from the nth number in the list. At this point, the digit at this position is altered. But then, by definition, we did not in fact reach the number cantor was constructing after all. Is it not possible to imagine that, for example, every time this occurred the number being constructed was moved 'further down the line' on the denumerable list, so to speak, ie for example's sake to position n+100 where n is the number currently being analysed. Thus at any given time Cantor's construction is in the denumerable list, but it just keeps getting altered so that it never gets reached. Since in any finite amount of time Cantor will never complete his number, does his construction then actually prove that there is in fact a number which is not in the denumerable list? This self-referential conundrum seems to lie more along the lines of an example of Godel's incompleteness theorem applied than as an actual proof for the non-denumerability of the reals. Am I missing something that makes Cantor's argument a little more solid?

sincerely,
jeffceth

 

[AKG]

What does "time" have to do with anything? Given a set of countably infinite real numbers, you can choose a number such that the nth digit of that number is different from the nth digit of the nth number, for ALL n. This doesn't mean that it's first true for the first number, then the second, then as time goes on, we reach the 100th number, etc. It has nothing to do with time. Simply, for all n, the nth digit of our new number is different from the nth digit of the nth number in the set. It's as though we "simultaneously" do this for each of the infinity elements of the set.

 

[jeffceth]

What does "time" have to do with anything? Given a set of countably infinite real numbers, you can choose a number such that the nth digit of that number is different from the nth digit of the nth number, for ALL n. This doesn't mean that it's first true for the first number, then the second, then as time goes on, we reach the 100th number, etc. It has nothing to do with time. Simply, for all n, the nth digit of our new number is different from the nth digit of the nth number in the set. It's as though we "simultaneously" do this for each of the infinity elements of the set.

your reply implicitly assumes that cantor's argument is valid. However, from the position that the argument may not be, 'time' is being used as a reference point to refer to the point in the denumerable list currently being assessed. From this perspective, if Cantor's construction is always just a few numbers further along than the point that is being calculated, or assessed, it is always in the denumerable list, but just never reached. This would mean that Cantor's argument is not in fact valid.

sincerely,
jeffceth

 

[CrankFan]

If we go along the denumerably infinite list of real numbers which theoretically exists for the sake of the example, then by definition after some finite amount of time we will reach the number which cantor is constructing by going along and making his nth digit differ from the nth number in the list.

No, this is clearly wrong. If that real (the real you are saying Cantor constructs) is the kth real number in the list, then its kth digit will differ from the kth digit of the real number which is shown to be a counter example. This contradicts the assumption that we had a complete list of reals -- so we reject the assumption.

It's true that if you postulate the existence of a complete list of real numbers then you can deduce from that postulate that a complete list of real numbers exists. No big surprise, but that's not what's meant when some proposition is supposed for the sake of a proof by contradiction. We reject those propositions assumed to exist if they result in contradictions.

That the reals aren't denumerable can be proven in many ways and is not limited to proofs by contradiction

 

[CrankFan]

your reply implicitly assumes that cantor's argument is valid.

If you think the notion of time is relevant then you either don't understand the proof or you're being exposed to a strange version of it. What source are you using?

 

[AKG]

your reply implicitly assumes that cantor's argument is valid. However, from the position that the argument may not be, 'time' is being used as a reference point to refer to the point in the denumerable list currently being assessed. From this perspective, if Cantor's construction is always just a few numbers further along than the point that is being calculated, or assessed, it is always in the denumerable list, but just never reached. This would mean that Cantor's argument is not in fact valid.

sincerely,
jeffceth

And I'm saying that you shouldn't look at in terms of "time", or in terms of some point in the list "currently" being assessed. Let's assume we have a set of countably infinite real numbers. Can we have such a set? Or at some point in time, we have the first 997239882938 elements, then as time goes on, we have more elements of that set? No. All at once, we have all infinity elements of the set. Now, since all infinity elements of that set are there, and exist for us to deal with, instantaneously choose the nth digit of the nth element of the set. Let's say we a set with two two-digit numbers. With our left hand, we pick the first digit of the first number, and the second of the second number "simultaneously". Now, imagine we have countably infinite hands. We simultaneously pick the nth digit from the nth number. Or, let's say we have 5 numbers of 5 digits, and we have a stamp which we stamp across the diagonal, highlighting the kth digit of the kth number. Now imagine we have the set Cantor used, and an infinitely long stamp. We stamp the diagonal (thereby stamping the kth digit of the kth number simultaneously).

Just as we simultaneously choose all infinity of those digits, we simultaneously alter all of them, and we get a new number that isn't already in the list.

 

[NateTG]

The number constructed in Cantor's diagonal argument is not necessarily a computable number (http://en.wikipedia.org/wiki/Computable_numbers) . That does not mean that it is not a real number.

Although this might not be a particularly satisfying answer to your question, my best guess is that your notion of what a real number is, and the standard notion of what a real number is are different.

 

[Hurkyl]

For the reals to be denumerable, an enumeration must exist. Let L be any such enumeration.

Note at this point L is fixed; it does not change...

 

[Ethereal]

What do you think of this page:

http://homepage.mac.com/ardeshir/ArgumentAgainstCantor.html

I didn't write it nor am I supporting its arguments, just asking for your opinions.

 

[matt grime]

The author is an idiot.

1. If decimal is on the list it is at some finite position on the list, so counter argument 1 is crap.

2. The probability argument is evidently rubbish, not specifying what k is, or n, and would only work if the decimals were terminating.
The fact that, even if he understood probability, there were a decimal expansion on the list matching any expansion up to the k'th place doesn't mean that there is a place where it matches in all components. Simple counter list:

List the expanisions 0.0, 0.1, 0.2, 0.3, 0.4 ... 0.9, then .01, .02, .03, ... .99, then all the three digit decimals, then all 4 digits and so on.

Given any x, there is an element matching it to the first k places, in fact infinitely many, yet all elements on the list are rational, and x is an arbitrary real.


3. The final clinching argument presumes that there are naturals which have an infinite number of non zero terms in the base 10 expansion.

So, apart from presuming all decimals are terminating and all natural numbers not, in their decimal expansions, and not understanding the argument at all, nor how to negate statements properly...

Anyone care to point out to the crankish author where he's gone wrong? Perhaps by sending him any of the other proofs...

 

[CrankFan]

What do you think of this page:

http://homepage.mac.com/ardeshir/ArgumentAgainstCantor.html

I didn't write it nor am I supporting its arguments, just asking for your opinions.

It's incorrect.

The author of that site seems to think that the number proven not to be on the list is somehow on the list. He doesn't understand the proof.

(1) Every real number on the list corresponds to a unique natural number. This is what it means when we say we have a "list" of real numbers.

(2) The number that is shown to not be on the list has a different kth digit than the kth real number in the list.

The author of that website seems to think that the counter-example number is on the list. If that's true, then by (1) there is a unique natural number k associated with it. We also know by (2) that the kth digit of the number shown to be a counter example differs from the kth digit of the kth entry in the list -- so that number can't be on the list.

 

[shmoe]

What do you think of this page:

http://homepage.mac.com/ardeshir/ArgumentAgainstCantor.html

I didn't write it nor am I supporting its arguments, just asking for your opinions.

His argument 'against' Cantor was old and uninspiried.

His argument 'disproving' Cantor was an inspired leap of crackpottery. The idea that you can take a fixed list and then assume that the numbers on it would behave randomly was terrific. His misunderstanding of probability that followed was fairly mundane, but does a decent job of beffudlement.

What's truly classic though was his 'clinching' argument. This guys natural numbers can have an infinite number of digits. That's nice. I wish mine could. It would have been handy for scaring children on Halloween.

 

[Zurtex]

Anyone care to point out to the crankish author where he's gone wrong? Perhaps by sending him any of the other proofs...

The author assumes that all infinities have the same cardinality and you can treat infinity like a number as the author has done by using it in probability by saying infinity over infinity is 1.