Re: (Not quite) Cantor's diagonal proof

From: Dave Seaman (dseaman_at_no.such.host)
Date: 10/19/04 

Date: Tue, 19 Oct 2004 06:37:14 +0000 (UTC)

On Tue, 19 Oct 2004 04:36:40 GMT, Saint Cad wrote:

> "Norman Megill" <nm@nospam.see.signature.domain.invalid> wrote in message
> news:kOCdnS7PSPzdG-7cRVn-sA@rcn.net...

><snip>

>> I have seen discussions on sci.math and sci.logic from time to time in
>> which doubts have been expressed that the real numbers are uncountable.

> I don't think any serious mathematician doubts that the reals are
> uncountable, but can raise questions as to the validity of Cantor's Diagonal
> Proof. For example, we construct a real number not on the list. OK, simply
> add it to the bottom of the list. The list should still be of countable
> cardnality. You retort that you can now construct another real not in the
> list. Add that to the bottom. We continue back and forth, so at which
> point does the list become uncountable? I'm sure that someone can come up
> with a valid reason why this approach does not invalidate the Diagonal
> Proof, but I think it does demonstrate that Cantor's proof by itself does
> leave a bit to be desired.

No, it doesn't demonstrate that. The form of Cantor's proof is to show
that for every mapping f: N -> R there is a real number x (depending on
f) such that x is not in the range of f. Notice that this statement is
precisely the logical negation of the statement "there is a surjection
from N onto R".

Perhaps you are familiar with epsilon-delta proofs in analysis. The
proof that a real function f is continuous at a point in its domain takes
the form "for every epsilon > 0 there exists delta > 0 (depending on
epsilon) such that blah blah blah". Why is it that no one ever attempts
to demonstrate a flaw in such proofs by picking a different epsilon after
the proof is done? It's exactly the same idea as picking a different f
after the proof in the previous paragraph is done.

In the former case we say "Let f: N->R be given. Let x = _________.
Then x is not in the range of f because ____________, Q.E.D."

In the latter case we say "Let epsilon > 0 be given. Let delta =
________. Then blah blah blah holds because ____________, Q.E.D."

The structure of the two proofs is exactly the same. There is no point
in trying to introduce a different f (or a different epsilon) because
every possible f (or epsilon) was already considered in the proof, and
none is left over.
        

> Here's another question. Suppose I list all of the repeating and
> terminating decimals (i.e. rationals). What in Cantor's proof prevents me
> from finding some sort of order for them so that I can use the diagonal
> method to create a repeating decimal not in the list, thereby "proving" that
> the rationals are uncountable?

First of all, the problem is with rationals that have dual
representations, such as 0.999... = 1.000.... Not every repeating
decimal has a dual representation. In fact, the only numbers that have
dual representations are those that end in all 9's or all 0's. The
diagonal construction can be arranged so that all the digits generated on
the diagonal are 1's and 2's (say), thus avoiding any possibility that
the new digit string will be an alternate representation of something
already on the list.

>I know that I can't actually do this (the
> rationals are countable), but it would take someone else to explain why in
> order to dismiss this "counter" to his method. Again, Cantor's method may
> be shown to not be invalid, but it take more than just his method by itself.

The number produced by the diagonal argument (correctly constructed)
necessarily differs from each number in the original list. It follows
that if the original list contains all the rationals (which is possible)
then the generated number must be irrational. 

-- 
Dave Seaman
Judge Yohn's mistakes revealed in Mumia Abu-Jamal ruling.
<http://www.commoncouragepress.com/index.cfm?action=book&bookid=228>

Relevant Pages

  • Re: (Not quite) Cantors diagonal proof
    ... epsilon) such that blah blah blah". ... > terminating decimals (i.e. rationals). ... decimal has a dual representation. ...
    (sci.logic)
  • Re: Possreps and numeric types
    ... I respectfully suggest any finite representation of rationals will fail to have many desirable algebraic properties. ... I admit I used epsilon somewhat sloppily and not necessarily with the exact meaning used when discussing a particular floating-point implementation. ... I used it to mean the distance to the representable predecessor or successor of any representable rational value. ...
    (comp.databases.theory)
  • Re: Cantors Diagonal Argument
    ... >> Ross A. Finlayson wrote: ... >>> Do you claim that there is not a rational between any two rationals, ... >>> the reals), the property of density in the reals implies that between c ... and reordering always allows dual representation. ...
    (sci.logic)
  • Re: Cantors Diagonal Argument
    ... >> Do you claim that there is not a rational between any two rationals, ... >> and irrationals alternate in the reals, ... Between them there is an infinite set of ... and reordering always allows dual representation. ...
    (sci.logic)
  • Re: Is one-to-one mapping valid for comparing infinite-sized sets?
    ... Dedekind cut definition or the Cauchy seqeunce definition of the Reals, ... If you are claiming that the rationals are not an ordered set, ... there is no such thing as an "infinitum ... And Salviati's epsilon cannot itself be a smallest positive rational, ...
    (sci.math)