# Cantor's Proof FAQ

679 views

### lugi...@gmail.com

Dec 14, 2006, 5:33:44 PM12/14/06
to
Cantor's Proof FAQ
The following is Cantor's Proof that there is no 1-1 correspondence
between the natural numbers and the real numbers between 0 and 1, also
called the uncountability of the reals in the interval (0,1):
1. Let A be any ordered list of real numbers between 0 and 1. In
other words, for each natural number x, there exists exactly one real
number A(x) between 0 and 1. Please note that the range of A does not
have to contain all real numbers.
2. Consider the real number f(A) such that the nth digit of f(A) is
equal to 5 if A(n)=4, and is equal to 4 if the A(n) does not equal 4.
3. f(A) cannot be an element of the range of A, since it differs in
the nth digit from the A(n).
4. Therefore, the range of A does not contain every real number. In
other words, A is not a complete list of reals.
5. Since A was arbitrary, there exists no ordered list of real
numbers, and thus the set of real numbers is uncountable.
Too many cranks try to refute this simple, elegant argument in the
following ways:
Q. Step 1 is invalid. There can be no ordered list of arbitrary real
numbers, only lists of specified real numbers. There has to exist some
kind of terminating effective procedure which specifies all the terms
on the list. This is because ordered lists are a type of potential
infinity, not actual infinity, which is impossible/too complicated.
A. Cantor's result pertains to lists of arbitrary real numbers. If
you don't believe in arbitrary real numbers, then why do you even care
to refute this theorem if it pertains to things you don't believe in?
You should just use definable real numbers, and leave stuff about
undefinable real numbers, which are absolutely essential to
mathematics, to the mathematicians who understand enough math to know
that they should embrace infinity.
Q. Step 2 is invalid. f(A) cannot be constructed, since f(A) is
designed to differ in the nth digit from A(n), and f(A) can't differ in
the nth digit from itself!
A. This is based on the misconception that Cantor's proof has to be a
proof by contradiction and must therefore assume for sake of argument
that the range of A must contain all real numbers. If you look at step
1, it explicitly rules out this possibility.
Q. Step 3 is invalid. f(A) can be an element of the range of A
because for m>n for all n,
f(A)=A(m).
A. This is based on the misconception that an infinitely large set
like the set of natural numbers must contain infinitely large members.
If you do believe that N contains infinitely large members, then
consider the set N* of all elements n of N such that n is not
infinitely large. Then N* is still infinitely large, since it has no
largest element, but N* still does not contain infinitely large
members. N is what N* is called in standard terminology.
Q. Step 5 is invalid. Just because A is incomplete, that doesn't mean
all lists of real numbers have to be incomplete. If you add f(A) to A,
you get a complete list of real numbers.
A. No you wouldn't, because you can apply the exact same argument for
A+f(A). In the beginning of the argument, we let A be arbitrary, so
the argument applies to ALL lists.

### |-|erc

Dec 14, 2006, 9:27:03 PM12/14/06
to
<lugi...@gmail.com> wrote in...

No need to use arbitrary lists, here's the actual list of all reals.

UTM(n, digit) mod 10 | n = 1,2,3...

When n gets to about 100 digits long, UTM(n) will compute any digit of pi,
it will compute e (for another value of n), just about every integer you can count to
will be computed, it will compute sin(0.5) and cos(sqrt(2)) and a host of other
formula you can put down to pen on paper. Now why are you all so intent
on destroying such a beautiful complete enumeration?

UTM(n, digit) mod 10 | n=1,2,3... computes every possible real number (between 0 and 1)
and maps them from the naturals.

the anti-diagonal real
UTM(digit, digit)+1 mod 10
can be shown not to occur anywhere on the list.

Let the anti-diagonal occur at some row m
UTM(m, digit) mod 10 = UTM(digit, digit)+1 mod 10
when m = digit
UTM(digit, digit) mod 10 = UTM(digit, digit)+1 mod 10
0 = 1 | mod 10
Therefore, the anti-diagonal does not occur on the list.
Therefore, UTM(digit, digit)+1 mod 10 is an improperly specified real.

Notice how I correctly identified the problem after finding a contradiction rather
than assuming larger than infinite sets exist.

Herc

### Newberry

Dec 14, 2006, 10:41:27 PM12/14/06
to

Cantor's proof is based on the misconception that in an n x n matrix
the n can be infinite.

### Virgil

Dec 15, 2006, 1:40:28 AM12/15/06
to
"|-|erc" <h@r.c> wrote:

What Herc does is to assume that there are only countably many reals,
and use that assumption to prove there are only countably many reals.

In logical circles that is circular and therefore invalid.

### |-|erc

Dec 15, 2006, 2:45:06 AM12/15/06
to
"Virgil" <vir...@comcast.net> wrote in

> "|-|erc" <h@r.c> wrote:
> > Therefore, the anti-diagonal does not occur on the list.
> > Therefore, UTM(digit, digit)+1 mod 10 is an improperly specified real.
> >
> > Notice how I correctly identified the problem after finding a contradiction
> > rather than assuming larger than infinite sets exist.
> >
> > Herc
>
> What Herc does is to assume that there are only countably many reals,
> and use that assumption to prove there are only countably many reals.
>
> In logical circles that is circular and therefore invalid.

I don't prove there are countably many reals, I merely show that diagonalisation
does not prove there are uncountably many reals.

What does a UTM count to?
Every integer
Every rational
Every maths expression, real, rational, irrational that you can type in your calculator
Every possible sequence of digits (to infinite length) on a real

Really what's left?
Herc

### Virgil

Dec 15, 2006, 3:33:28 AM12/15/06
to
"|-|erc" <h@r.c> wrote:

> "Virgil" <vir...@comcast.net> wrote in
> > "|-|erc" <h@r.c> wrote:
> > > Therefore, the anti-diagonal does not occur on the list.
> > > Therefore, UTM(digit, digit)+1 mod 10 is an improperly specified real.
> > >
> > > Notice how I correctly identified the problem after finding a
> > > rather than assuming larger than infinite sets exist.
> > >
> > > Herc
> >
> > What Herc does is to assume that there are only countably many reals,
> > and use that assumption to prove there are only countably many reals.
> >
> > In logical circles that is circular and therefore invalid.
>
> I don't prove there are countably many reals, I merely show that
> diagonalisation
> does not prove there are uncountably many reals.

Cantor's first proof suffices.

>
> What does a UTM count to?
> Every integer
> Every rational
> Every maths expression, real, rational, irrational that you can type in
> Every possible sequence of digits (to infinite length) on a real

Where is one of these wondrous UMTs? If you are speaking of Universal
Turing Machines, none exist.

### |-|erc

Dec 15, 2006, 4:08:42 AM12/15/06
to
"Virgil" <vir...@comcast.net> wrote ...

> "|-|erc" <h@r.c> wrote:
>
> > "Virgil" <vir...@comcast.net> wrote in
> > > "|-|erc" <h@r.c> wrote:
> > > > Therefore, the anti-diagonal does not occur on the list.
> > > > Therefore, UTM(digit, digit)+1 mod 10 is an improperly specified real.
> > > >
> > > > Notice how I correctly identified the problem after finding a
> > > > rather than assuming larger than infinite sets exist.
> > > >
> > > > Herc
> > >
> > > What Herc does is to assume that there are only countably many reals,
> > > and use that assumption to prove there are only countably many reals.
> > >
> > > In logical circles that is circular and therefore invalid.
> >
> > I don't prove there are countably many reals, I merely show that
> > diagonalisation
> > does not prove there are uncountably many reals.
>
> Cantor's first proof suffices.

which one is that, UTM(digit, digit)+1 mod 10 doesn't fit, or the box that
contains the numbers of all the boxes that don't contain their own numbers?

> >
> > What does a UTM count to?
> > Every integer
> > Every rational
> > Every maths expression, real, rational, irrational that you can type in
> > Every possible sequence of digits (to infinite length) on a real
>
> Where is one of these wondrous UMTs? If you are speaking of Universal
> Turing Machines, none exist.

Sure they do, in theory and practice, some of them are consise programs now.

Herc

### lugi...@gmail.com

Dec 15, 2006, 6:30:45 AM12/15/06
to
Can you give a proof that it computes every real number?

> the anti-diagonal real
> UTM(digit, digit)+1 mod 10
> can be shown not to occur anywhere on the list.
>
> Let the anti-diagonal occur at some row m
> UTM(m, digit) mod 10 = UTM(digit, digit)+1 mod 10
> when m = digit
> UTM(digit, digit) mod 10 = UTM(digit, digit)+1 mod 10
> 0 = 1 | mod 10
> Therefore, the anti-diagonal does not occur on the list.
> Therefore, UTM(digit, digit)+1 mod 10 is an improperly specified real.
>
Just because the "anti-diagonal" doesn't occur in your list, how do you
know it is improperly specified?

What is your definition of "properly specified real?"

> Notice how I correctly identified the problem after finding a contradiction rather
> than assuming larger than infinite sets exist.

Instead of looking for a specific counterexample to Cantor's result,
examine the proof I provided above which works for an arbitrary lists
of reals. Try to find an error if you can.
>
> Herc

### lugi...@gmail.com

Dec 15, 2006, 6:33:07 AM12/15/06
to
Which step of the proof I provided above do you find in error and why?

### lugi...@gmail.com

Dec 15, 2006, 6:36:20 AM12/15/06
to
Universal turing machines exist. General-purpose computers are
universal turing machines. They exist, Herc is just using them in his
obviously invalid refutation of Cantor's proof.

### Arturo Magidin

Dec 15, 2006, 11:59:44 AM12/15/06
to

<lugi...@gmail.com> wrote:
>Cantor's Proof FAQ

>The following is Cantor's Proof that there is no 1-1 correspondence
>between the natural numbers and the real numbers between 0 and 1, also
>called the uncountability of the reals in the interval (0,1):

You should add "strictly" before "between 0 and 1".

>1. Let A be any ordered list of real numbers between 0 and 1. In
>other words, for each natural number x, there exists exactly one real
>number A(x) between 0 and 1. Please note that the range of A does not
>have to contain all real numbers.

I would rephrase the clause after "In other words", to avoid
misinterpretation. I would say:

In other words, A is a function whose domain is the natural
numbers, and whose range is contained in (0,1); for each natural
number x, A(x) is a real number between 0 and 1.

>2. Consider the real number f(A) such that the nth digit of f(A) is
>equal to 5 if A(n)=4, and is equal to 4 if the A(n) does not equal 4.

Before doing this, you need to specify that A(x) will be given its
decimal representation, and in the case of dual representations, you
should explicitly pick one; I suggest specifying that you will use a
tail of zeros when there are two of them.

>3. f(A) cannot be an element of the range of A, since it differs in
>the nth digit from the A(n).

First, add that since the decimal representation of f(A) contains only
4s and 5s, it has one and only one decimal representation.

You also need to fix 3 a bit. For example, suppose that A(1) is
.50000000....

Then your definition of f(A) has the first decimal digit equal to
4. However, you cannot conclude from the fact that f(A) has first
decimal digit equal to 4 and A(1) has first decimal digit equal to 5
that A(1) and f(A) are different, because A(1) has a second decimal
the fact that the second digit of f(A) will not be a 9 and so f(A) is
not the "other" decimal representation of A(1).

This should be added ahead of time, when you say that f(A) has only
one decimal representation, and so if it differs from a number x in a
single digit of any decimal representation for x, then it will be
different from x.

>4. Therefore, the range of A does not contain every real number. In
>other words, A is not a complete list of reals.

Replace "real numbers" with "real number strictly between 0 and
1". I mean, we already knew it did not contain 3/2, after all.

--
======================================================================
"It's not denial. I'm just very selective about
what I accept as reality."
--- Calvin ("Calvin and Hobbes" by Bill Watterson)
======================================================================

Arturo Magidin
magidin-at-member-ams-org

### Bob Kolker

Dec 15, 2006, 1:34:20 PM12/15/06
to
Arturo Magidin wrote:
>
> You should add "strictly" before "between 0 and 1".

The open parens indicate the open interval. End points not included.
This is standard mathematical notation. [0,1] is the interval with the
endpoints.

Bob Kolker

### Arturo Magidin

Dec 15, 2006, 1:55:09 PM12/15/06
to
In article <4ug85fF...@mid.individual.net>,

Yes, I know.

Since I assumed he was writing it up asking for suggestions, I noted a
few places where he might want to clarify and tighten the

presentation. That was one. He wrote:

The following is Cantor's Proof that there is no 1-1
correspondence between the natural numbers and the real numbers
between 0 and 1, also called the uncountability of the reals in
the interval (0,1)

Now, the proof is by no means restricted to the real numbers in (0,1);
it works equally well if we allow the list to include 0 or 1. So
saying that "it is also called" the uncountability of reals in (0,1)
is a bit of a fudge. Which is why I suggested that, when he first says
what he is doing, he write explicitly "strictly", so that it is clear
that what he says it is also called is indeed the same thing.

### Virgil

Dec 15, 2006, 5:53:04 PM12/15/06
to
"|-|erc" <h@r.c> wrote:

> "Virgil" <vir...@comcast.net> wrote ...
> > "|-|erc" <h@r.c> wrote:
> >
> > > "Virgil" <vir...@comcast.net> wrote in
> > > > "|-|erc" <h@r.c> wrote:
> > > > > Therefore, the anti-diagonal does not occur on the list.
> > > > > Therefore, UTM(digit, digit)+1 mod 10 is an improperly specified real.
> > > > >
> > > > > Notice how I correctly identified the problem after finding a
> > > > > contradiction
> > > > > rather than assuming larger than infinite sets exist.
> > > > >
> > > > > Herc
> > > >
> > > > What Herc does is to assume that there are only countably many reals,
> > > > and use that assumption to prove there are only countably many reals.
> > > >
> > > > In logical circles that is circular and therefore invalid.
> > >
> > > I don't prove there are countably many reals, I merely show that
> > > diagonalisation
> > > does not prove there are uncountably many reals.
> >
> > Cantor's first proof suffices.
>
> which one is that

Look it up.

> > > What does a UTM count to?
> > > Every integer
> > > Every rational
> > > Every maths expression, real, rational, irrational that you can type in
> > > Every possible sequence of digits (to infinite length) on a real
> >
> > Where is one of these wondrous UMTs? If you are speaking of Universal
> > Turing Machines, none exist.
>
> Sure they do, in theory and practice, some of them are consise programs now.

Is there any UTM currently in existence which is guaranteed to take ANY
finite program, however large, and run it?

What about a program that allows one pass over the contents of the tape
then requires erasing of everything on the tape before proceeding to
wtite something?

### Newberry

Dec 15, 2006, 7:48:31 PM12/15/06
to

Step 4. Since f(A) is not in the list and the list contains all the
reals, it clearly follows that f(A) does not exist.

### MoeBlee

Dec 15, 2006, 8:56:14 PM12/15/06
to
Newberry wrote:
> Step 4. Since f(A) is not in the list and the list contains all the
> reals, it clearly follows that f(A) does not exist.

Just personally, I'd prefer not to use the notation 'f(A)'. But the
object described in his argument is PROVEN to exist. Moreover, it's
simply a non sequitur to assert that all real numbers are in the list.

MoeBlee.

### |-|erc

Dec 15, 2006, 10:28:12 PM12/15/06
to
"Virgil" <vir...@comcast.net> wrote

If you argue UTMs don't exist, then TMs don't exist, and neither does any construction
in mathematics, circles don't exist, pi doesn't exist! Computers can emulate UTMs up to a point.
We can merely define a finite UTM, FUTM which comes with a tolerance rating and
then we make sure we are using the right machine for the right input whenever we are
required to physically run the programs, which for the sake of countability theory may never occur.

Herc

### Virgil

Dec 15, 2006, 10:29:48 PM12/15/06
to
"Newberry" <newb...@ureach.com> wrote:

Or that the list does not actually contain all reals.

When a contradiction appears, it may be because any one of the
assumptions leading to is is wrong. In order to conclude a particular
assumtion as the cause, one must demonstrably exclude all others.

### |-|erc

Dec 15, 2006, 10:36:55 PM12/15/06
to
"Virgil" <vir...@comcast.net> wrote in

> > > Which step of the proof I provided above do you find in error and why?
> >
> > Step 4. Since f(A) is not in the list and the list contains all the
> > reals, it clearly follows that f(A) does not exist.
>
> Or that the list does not actually contain all reals.
>
> When a contradiction appears, it may be because any one of the
> assumptions leading to is is wrong. In order to conclude a particular
> assumtion as the cause, one must demonstrably exclude all others.

Given 2 options, a formula is wrong, or a hyperinfinite set must exist
go with the simpler.

Herc

### Newberry

Dec 15, 2006, 11:01:26 PM12/15/06
to

ABSOLUTELY!! Concluding that the list does not contain all the reals
antidiagonal real does not exist any more than r < 3.14 & r > 3.14.

### Virgil

Dec 15, 2006, 11:27:19 PM12/15/06
to
"|-|erc" <h@r.c> wrote:

The contradiction arises out of two claimed assumptions:
(1) The list contains all real numbers, and
(2) The number constructed is not on the list.

Since (1) is no part of the original diagonal proof, it is irrelevant.

The original proof merely assumes one has a list of reals, with no other
requirement than that it be a list of reals. There is no original
assumption that it need contains all reals.

Then (2) concludes that the diagonal is not in THAT list, with no

The theorem has established that, given an arbitrary list of reals,
there is a real not in that list.

Those who attempt to require proof by contradiction are apparently
unaware that the original proof did not do so.

### |-|erc

Dec 15, 2006, 11:47:26 PM12/15/06
to
"Virgil" <vir...@comcast.net> wrote ...

That's a misleading way to prove it, because if its arbitrary then it MAY
be complete, so you have to consider that possibility.

STEP 1
GIVEN AN ARBITRARY LIST OF REALS

STEP 2a
THE LIST IS NOT COMPLETE

STEP 3a
THE LIST IS COMPLETE

STEP 4
CONCLUSION

Isn't it easier just to make step 1 assume a complete list of reals and use

Given that the assumption in Cantors proof is a complete list of reals, it
changes the fact that your new construction must fit into the list (as its complete)
and therefore has to be properly encoded, which is where your contradiction
comes from.

Summary:
You can't assume an arbitrary list without assuming a complete list as one option.
You can't asssume a complete list and then ignore that assumption making new
ill defined constructions.

Herc

### lugi...@gmail.com

Dec 16, 2006, 8:20:02 AM12/16/06
to
When did I say A contains all the reals? In fact, I even said in Step
1: "Please note that the range of A does not need to contain all real
numbers." I am just starting with an arbitrary list A of reals,
whether it contains all reals or just some of them. I am then
constructing a real number f(A) that is not on the list. Since A was
arbitrary, for each list, there exists a real number the list does not
contain. I do not need to assume that A contains all reals. So it
does not "clearly follow" that f(A) does not exist. f(A) does exist.

Do you have any other objections about the proof?

### Newberry

Dec 16, 2006, 10:18:12 AM12/16/06
to

### george

Dec 16, 2006, 2:09:35 PM12/16/06
to

lugi...@gmail.com wrote:
> Cantor's Proof FAQ
> The following is Cantor's Proof that there is no 1-1 correspondence
> between the natural numbers and the real numbers between 0 and 1, also
> called the uncountability of the reals in the interval (0,1):

This is incredibly stupid.
In the first place, you have titled the thread a FAQ, yet there
are no Q's (questions), Frequently Asked or otherwise, in it.

In the second place, Cantor's theorem IS NOT ABOUT
uncountability of the reals. It is about unmappability
of a set onto its powerset. Simply understanding THAT
would ELIMINATE At Least Half of the actually Frequently

### lugi...@gmail.com

Dec 16, 2006, 4:44:38 PM12/16/06
to
george wrote:
> lugi...@gmail.com wrote:
> > Cantor's Proof FAQ
> > The following is Cantor's Proof that there is no 1-1 correspondence
> > between the natural numbers and the real numbers between 0 and 1, also
> > called the uncountability of the reals in the interval (0,1):
>
> This is incredibly stupid.
> In the first place, you have titled the thread a FAQ, yet there
> are no Q's (questions), Frequently Asked or otherwise, in it.
>
crackpots.

> In the second place, Cantor's theorem IS NOT ABOUT
> uncountability of the reals. It is about unmappability
> of a set onto its powerset. Simply understanding THAT
> would ELIMINATE At Least Half of the actually Frequently
When did I say this was about Cantor's theorem? This is about Cantor's
diagonal argument that there are more real numbers than natural
numbers. This is of course provable from Cantor's theorem, but Cantor
proved it separately using his diagonal argument.

### Dave Seaman

Dec 16, 2006, 6:59:32 PM12/16/06
to
On 16 Dec 2006 11:09:35 -0800, george wrote:

> lugi...@gmail.com wrote:
>> Cantor's Proof FAQ
>> The following is Cantor's Proof that there is no 1-1 correspondence
>> between the natural numbers and the real numbers between 0 and 1, also
>> called the uncountability of the reals in the interval (0,1):

> This is incredibly stupid.
> In the first place, you have titled the thread a FAQ, yet there
> are no Q's (questions), Frequently Asked or otherwise, in it.

By my count, the OP had 55 lines. The first 19 contained the proof, and
the rest were Q and A.

> In the second place, Cantor's theorem IS NOT ABOUT
> uncountability of the reals. It is about unmappability
> of a set onto its powerset. Simply understanding THAT
> would ELIMINATE At Least Half of the actually Frequently

All of the objections that were addressed in the Q and A could be
rephrased to apply to the proof involving powersets.

--
Dave Seaman
U.S. Court of Appeals to review three issues
concerning case of Mumia Abu-Jamal.
<http://www.mumia2000.org/>

### george

Dec 19, 2006, 2:40:13 PM12/19/06
to

lugi...@gmail.com wrote:
> Instead of looking for a specific counterexample to Cantor's result,
> examine the proof I provided above which works for an arbitrary lists
> of reals. Try to find an error if you can.

The "error" is simply that because your original arbitrary
list is infinite, "computing its anti-diagonal" must take an
infinite amount of time, and must therefore never finish,
and therefore your decision to instruct someone to compute
and use the RESULT of such a computation is simply inadmissible:
Itsimply can't be performed in practice.
That this is NOT sufficient to make "anti-diagonal of a denumerably
long list" something "incorrectly specified" is NOT understood by
by the frequent askers of this question.

### Randy Poe

Dec 19, 2006, 2:53:28 PM12/19/06
to

george wrote:
> lugi...@gmail.com wrote:
> > Instead of looking for a specific counterexample to Cantor's result,
> > examine the proof I provided above which works for an arbitrary lists
> > of reals. Try to find an error if you can.
>
> The "error" is simply that because your original arbitrary
> list is infinite, "computing its anti-diagonal" must take an
> infinite amount of time, and must therefore never finish,

There is no requirement to compute it.

The question is does it exist. Does it have an n-th digit for
every n.

Do I need to compute the trillion-th digit of pi to conclude
that it has a trillion-th digit?

- Randy

### Virgil

Dec 19, 2006, 2:57:49 PM12/19/06
to
"george" <gre...@cs.unc.edu> wrote:

Since for any given number listed, one can show in finite time that the
diagonal is not equal to that number, you objection fails.

### george

Dec 19, 2006, 3:20:29 PM12/19/06
to

> george wrote:
> > The "error" is simply that because your original arbitrary
> > list is infinite, "computing its anti-diagonal" must take an
> > infinite amount of time, and must therefore never finish,
>
> There is no requirement to compute it.

Randy Poe wrote:
Of course there is, in "Their" opinion. "They" can always insist that
if it's provably not computable, THAT CONSTITUTES
a proof that it provably doesn't exist. Short of that,
they could insist that they want to be constructive and
that until YOU can compute it, YOU haven't proved that
it must -- OR EVEN CAN -- exist.

>
> The question is does it exist.

Obviously, they say it doesn't.

> Does it have an n-th digit for every n.

Each of those n's is finite.
The overall thing is infinite. Unless you know
that first-order logic is compact, this MIGHT make
a difference. THEY think it makes a difference.

> Do I need to compute the trillion-th digit of pi to conclude
> that it has a trillion-th digit?

Obviously, if Pi doesn't exist, then it doesn't contain any digits
at all, trillionth or otherwise. And if your contention is that Pi
is infinitely long, that for EVERY one of infinitely many n, there
is an nth digit of Pi, AND THAT LEADS TO A CONTRADICTION,
then "they" are perfectly free to pin the "error" on your claim that
every digit of Pi exists. The fact that the contradiction is actually
due to something else entirely will be quite lost on them.

### george

Dec 19, 2006, 3:22:35 PM12/19/06
to

There IS NO given number listed.
JEEzus. There is an INFINITE LIST of numbers listed.

> one can show in finite time that the
> diagonal is not equal to that number,

It does NOT follow from that you can anti-diagonalize ANYthing
INfinite with only finite time.

> you objection fails.

But not due to any reason have anything to do with any finite case
(as you wrongly claim here).

T

### Randy Poe

Dec 19, 2006, 3:25:30 PM12/19/06
to

george wrote:
> > george wrote:
> > > The "error" is simply that because your original arbitrary
> > > list is infinite, "computing its anti-diagonal" must take an
> > > infinite amount of time, and must therefore never finish,
> >
> > There is no requirement to compute it.
>
>
> Randy Poe wrote:
> Of course there is, in "Their" opinion.

Who are "they". Certainly not anyone advancing Cantor's
proof of the uncountability of reals. That is an existence
proof, not a claim of computability.

> "They" can always insist that
> if it's provably not computable, THAT CONSTITUTES
> a proof that it provably doesn't exist.

No, I've never heard any mathematician claim that the
computable reals are the only ones that exist. In fact,
most reals are known to be uncomputable.

> Short of that,
> they could insist that they want to be constructive and
> that until YOU can compute it, YOU haven't proved that
> it must -- OR EVEN CAN -- exist.

The proof shows that there exists a number which is
different from the n-th number on the list, for every n. It
does that without explicit computation. There is no "they"
insisting on computability. You are arguing with a strawman.

- Randy

### lugi...@gmail.com

Dec 19, 2006, 6:34:17 PM12/19/06
to
Randy Poe wrote:
> george wrote:
> > > george wrote:
> > > > The "error" is simply that because your original arbitrary
> > > > list is infinite, "computing its anti-diagonal" must take an
> > > > infinite amount of time, and must therefore never finish,
> > >
> > > There is no requirement to compute it.
> >
> >
> > Randy Poe wrote:
> > Of course there is, in "Their" opinion.
>
> Who are "they". Certainly not anyone advancing Cantor's
> proof of the uncountability of reals. That is an existence
> proof, not a claim of computability.
>
> > "They" can always insist that
> > if it's provably not computable, THAT CONSTITUTES
> > a proof that it provably doesn't exist.
>
> No, I've never heard any mathematician claim that the
> computable reals are the only ones that exist.
In that case, you've never heard of constructivists. Constructivism, a
rather stupid philosophy in my opinion, believes that only what can be
"constructed," or computed, actually exist.

### lugi...@gmail.com

Dec 19, 2006, 6:39:14 PM12/19/06
to
george wrote:
> > george wrote:
> > > The "error" is simply that because your original arbitrary
> > > list is infinite, "computing its anti-diagonal" must take an
> > > infinite amount of time, and must therefore never finish,
> >
> > There is no requirement to compute it.
>
>
> Randy Poe wrote:
> Of course there is, in "Their" opinion. "They" can always insist that
> if it's provably not computable, THAT CONSTITUTES
> a proof that it provably doesn't exist. Short of that,
> they could insist that they want to be constructive and
> that until YOU can compute it, YOU haven't proved that
> it must -- OR EVEN CAN -- exist.
>
I addressed the constructivist objection you pointed out in my FAQ.
Basically it boils down to this: if someone believes that uncomputable
real numbers do not exist, then the statement that the uncomputable
real numbers are uncountably infinite is vacuously true. For this
reason, constructivists, shouldn't have a problem with Cantor's Proof.

### Albrecht

Dec 20, 2006, 10:05:58 AM12/20/06
to

lugi...@gmail.com schrieb:

> george wrote:
> > lugi...@gmail.com wrote:
> > > Cantor's Proof FAQ
> > > The following is Cantor's Proof that there is no 1-1 correspondence
> > > between the natural numbers and the real numbers between 0 and 1, also
> > > called the uncountability of the reals in the interval (0,1):
> >
> > This is incredibly stupid.
> > In the first place, you have titled the thread a FAQ, yet there
> > are no Q's (questions), Frequently Asked or otherwise, in it.
> >