Prev: Pi berechnen: Ramanujan oder BBP
Next: Group Theory
From: the_wign on 27 Sep 2006 22:35
Cantor's proof is one of the most popular topics on this NG. It
seems that people are confused or uncomfortable with it, so
I've tried to summarize it to the simplest terms:

1. Assume there is a list containing all the reals.
2. Show that a real can be defined/constructed from that list.
3. Show why the real from step 2 is not on the list.
4. Conclude that the premise is wrong because of the contradiction.

The steps are simple except for a possible debate about defined /
constructed. I don't think anyone believes the proof is invalid
because of that debate however.

There seems to be another area that seems to be a problem
though. The problem is that step #2 doesn't seem valid. If we
assume the list contains all the real numbers, then defining or
constructing a real number in terms of that list would be
self-referential. The number from step #2, that is normally defined
digit-by-digit along the diagonal, must have its digits (or at least
one of them) defined as not equal to itself, if we are to assume the
list contains all the real numbers. Certainly the conclusion in that
case is that the premise is wrong or that the construction is not
valid, but the conclusion can't be simply that the premise is wrong.

This same problem appears in the "power-set" theorem, where we
have a definition of a set, S, which is a subset of N, defined in
terms of the image of a function, f, whose image is assumed to be
the power-set of N. If the image of f is assumed to be the power-set
of N and S is defined in terms of f, then S must necessarily be
defined in terms of itself. Again, if we assume that the image of
f is P(N), then defining S as a set whose elements are defined
to be elements not in the image of f is a self-referential definition
of S because S is also a subset of N, making it meaningless.
Certainly a meaningless definition can't be used to prove a
contradiction.

I'm guessing that the "discussions" that occur stem from the fact
that mathematicians disagree that the seemingly self-referential
definitions are a problem but it's not intuitively obvious why that is
so, therefore many people feel the need to try to refute the proofs.
The problem is that it really isn't clear why mathematicians seem to
accept the self-referential definitions.

From: cbrown on 28 Sep 2006 00:25
the_wign(a)yahoo.com wrote:
> Cantor's proof is one of the most popular topics on this NG. It
> seems that people are confused or uncomfortable with it, so
> I've tried to summarize it to the simplest terms:
>
> 1. Assume there is a list containing all the reals.
> 2. Show that a real can be defined/constructed from that list.
> 3. Show why the real from step 2 is not on the list.
> 4. Conclude that the premise is wrong because of the contradiction.
>
> The steps are simple except for a possible debate about defined /
> constructed. I don't think anyone believes the proof is invalid
> because of that debate however.
>
> There seems to be another area that seems to be a problem
> though. The problem is that step #2 doesn't seem valid. If we
> assume the list contains all the real numbers, then defining or
> constructing a real number in terms of that list would be
> self-referential. The number from step #2, that is normally defined
> digit-by-digit along the diagonal, must have its digits (or at least
> one of them) defined as not equal to itself, if we are to assume the
> list contains all the real numbers. Certainly the conclusion in that
> case is that the premise is wrong or that the construction is not
> valid, but the conclusion can't be simply that the premise is wrong.
>

Why not?

The thing is, we can "see" that the argument itself (i.e., that we can
construct a number distinct from the list of numbers which we assume is
complete) follows logically, in the same way that we "see" that the
premises "All men are mortal" and "Socrates is a man" implies that
"Socrates is mortal".

In the given case, if we accept the premises, the result of the
argument is that if the premise is true ("there is a list of all
reals"), then it still follows that "every list of reals, complete or
not, misses at least one real", and thus the absurd conclusion ("the
complete list of all reals misses at least one real").

To continue the analogy, if we accept the premises "All men are
mortal", "Socrates is a man", and "Socates is not mortal", then it
follows that at least one of our /premises/ is false, not that the
logic which demonstrates the absurdity is false.

> This same problem appears in the "power-set" theorem, where we
> have a definition of a set, S, which is a subset of N, defined in
> terms of the image of a function, f, whose image is assumed to be
> the power-set of N. If the image of f is assumed to be the power-set
> of N and S is defined in terms of f, then S must necessarily be
> defined in terms of itself. Again, if we assume that the image of
> f is P(N), then defining S as a set whose elements are defined
> to be elements not in the image of f is a self-referential definition
> of S because S is also a subset of N, making it meaningless.
> Certainly a meaningless definition can't be used to prove a
> contradiction.

A definition can be meaningful, and yet not be satisfied by any
mathmeatical object. For example, suppose we say that a natural number
p is "oddven" is p is both odd and even. This definition is meaningful
(in the sense that, for any natural number n, we can unambiguously say
that n either is or is not oddven), but there are no natural numbers
which are oddven.

In the same way, the definition of "T is a list of all real numbers" is
meaningful, and yet there is no such list T.

>
> I'm guessing that the "discussions" that occur stem from the fact
> that mathematicians disagree that the seemingly self-referential
> definitions are a problem but it's not intuitively obvious why that is
> so, therefore many people feel the need to try to refute the proofs.
> The problem is that it really isn't clear why mathematicians seem to
> accept the self-referential definitions.

Because they're not "self-referential" in the way you seem to use the
term. The proof that there is no T such that T is a complete list of
the reals follows from the fact that every list of reals misses at
least one real, just as the proof that there are no natural numbers n
which are oddven follows from the fact that a number which is even must
neccessarily not be odd.

Cheers - Chas

From: Peter Webb on 28 Sep 2006 00:36

<the_wign(a)yahoo.com> wrote in message
news:1159410937.013643.192240(a)h48g2000cwc.googlegroups.com...
> Cantor's proof is one of the most popular topics on this NG. It
> seems that people are confused or uncomfortable with it, so
> I've tried to summarize it to the simplest terms:
>
> 1. Assume there is a list containing all the reals.
> 2. Show that a real can be defined/constructed from that list.
> 3. Show why the real from step 2 is not on the list.
> 4. Conclude that the premise is wrong because of the contradiction.
>
> The steps are simple except for a possible debate about defined /
> constructed. I don't think anyone believes the proof is invalid
> because of that debate however.
>
> There seems to be another area that seems to be a problem
> though. The problem is that step #2 doesn't seem valid. If we
> assume the list contains all the real numbers, then defining or
> constructing a real number in terms of that list would be
> self-referential. The number from step #2, that is normally defined
> digit-by-digit along the diagonal, must have its digits (or at least
> one of them) defined as not equal to itself, if we are to assume the
> list contains all the real numbers. Certainly the conclusion in that
> case is that the premise is wrong or that the construction is not
> valid, but the conclusion can't be simply that the premise is wrong.
>
> This same problem appears in the "power-set" theorem, where we
> have a definition of a set, S, which is a subset of N, defined in
> terms of the image of a function, f, whose image is assumed to be
> the power-set of N. If the image of f is assumed to be the power-set
> of N and S is defined in terms of f, then S must necessarily be
> defined in terms of itself. Again, if we assume that the image of
> f is P(N), then defining S as a set whose elements are defined
> to be elements not in the image of f is a self-referential definition
> of S because S is also a subset of N, making it meaningless.
> Certainly a meaningless definition can't be used to prove a
> contradiction.
>
> I'm guessing that the "discussions" that occur stem from the fact
> that mathematicians disagree that the seemingly self-referential
> definitions are a problem but it's not intuitively obvious why that is
> so, therefore many people feel the need to try to refute the proofs.
> The problem is that it really isn't clear why mathematicians seem to
> accept the self-referential definitions.
>

Its not "self-referential" in the sense of being a circular argument.

You produce ANY list of all Reals, I can show you a missing real. Therefore
I can do it for ALL lists, and hence there is no complete list of Reals.

Obviously you have to tell me the list first, as there is no single Real
which is missing from every list, or that Real could be made the first entry
on a new list. The Real is different on every list, and depends on the list.

You have three balls, red green and blue. I state you cannot put them all
into two boxes, such that no box contains two or more balls. Here is my
proof:

If you put a red ball into one box, green into another box, then there is
nowhere to put the blue ball (and so on for the other two possibilities).

This requires me to know which boxes you put each ball into, but its not
self-referential. If you the blue ball is left out, you can't just put the
blue ball into box #1 and move the red ball out and say - "see, you can put
all the balls into two boxes". This is what anti-Cantor cranks do all the
time - we identify the Real not on the list (the ball that has been
excluded) and then they change the list to include that Real (change what
boxes the other balls go into) and say "see, it is on the list" ("see, I can
put the blue ball into a box").





From: Virgil on 28 Sep 2006 01:21
In article <1159417542.425540.214160(a)i3g2000cwc.googlegroups.com>,
cbrown(a)cbrownsystems.com wrote:

> the_wign(a)yahoo.com wrote:
> > Cantor's proof is one of the most popular topics on this NG. It
> > seems that people are confused or uncomfortable with it, so
> > I've tried to summarize it to the simplest terms:
> >
> > 1. Assume there is a list containing all the reals.
> > 2. Show that a real can be defined/constructed from that list.
> > 3. Show why the real from step 2 is not on the list.
> > 4. Conclude that the premise is wrong because of the contradiction.

That is a proof by contradiction, which many constructionists object to.

One can modify it slightly to get a more direct proof:
1. Assume one is given any list of reals (i.e., an arbitrary function
with domain N and codomain R, the only condition being that there is one
real for each natural number)
2. Show that a real can be defined/constructed from that list in such a
way as not to be a member of that list.
3. Conclude that every list must omit at least one real, so no list is
complete.
From: mueckenh on 28 Sep 2006 07:06

Peter Webb schrieb:

> You produce ANY list of all Reals, I can show you a missing real. Therefore
> I can do it for ALL lists, and hence there is no complete list of Reals.
>
> Obviously you have to tell me the list first, as there is no single Real
> which is missing from every list,

No?

But the set of all lists is countable (as is any quantized or
discontinuous set), so is the set of all list entries. Nevertheless,
there is no real number missing in every list? So every real number is
in at least one of the list? So every real number is one element of a
countable set of entries? And there is nothing real really outside of
this countable set?

Regards, WM

 |  Next  |  Last
Pages: 1 2 3 4 5 6 7 8 9 10 11
Prev: Pi berechnen: Ramanujan oder BBP
Next: Group Theory