Re: diagonal argument on ordered array of reals


Ten wrote:
On 6 Nov 2006 08:23:47 -0800, "Randy Poe" <poespam-trap@xxxxxxxxx> wrote:


Ten Letters wrote:
On Sun, 5 Nov 2006 21:23:07 -0500, David Marcus
<DavidMarcus@xxxxxxxxxxxxxx> wrote:

Ten Letters wrote:
On Sun, 5 Nov 2006 12:34:26 -0500, David Marcus <DavidMarcus@xxxxxxxxxxxxxx> wrote:
Ten Letters wrote:

Let's be clear about the shape of my argument.

You appear to be trying to show that the reals are countable. Please
confirm.

Not directly, no. Though I had some barmy and quite superficial fun
at the end of my original post with the idea that they might be (well, it
was good for me), I rather suspect that they are not. I am purporting to
find fault with Cantor's argument that they are not. This is a crazy thing
to do, I know, especially for someone like me whose maths, as I've
admitted, is probably at the bottom of the class for this group. I'm sure I
follow in a long line of cranks who have tried to do the same thing.

Yep.

Yet
there is something about Cantor's argument which invites this. The result
pops out like magic, like a winning lottery line,

Perhaps.

in a way that doesn't
seem to advance our knowledge of the subject.

On the contrary, it is a wonderful insight by Cantor.

(Some quite reputable figures
have thought it pure hocus pocus.)

You must be using a different definition of "reputable" (or perhaps of
"hocus pocus").

This must seem like a cruel thing to
say, since before Cantor there was no satisfactory theory of the infintite.
But the proof is not transparent. Why, for instance, are the reals
uncountable? Why is there this uncountable density in an interval of the
reals?

Logically, a proof tells you "why". Of course, different proofs may tie
in better with what you already understand and so may be more
enlightening. There are many other proofs, if you don't find this one
illuminating. For example, you can prove that the power set of any set
has greater cardinality than the original set. This also proves the
reals are uncountable. In the book "Topology" by Munkres, there is the
following theorem. If a nonempty compact Hausdorff space is such that
every point is a limit point, then it is uncountable. This implies that
a closed interval of real numbers is uncountable.

The bent of my argument is that Cantor's argument is faulty, or at
least incomplete. I can see how the way I presented my argument could make
it look as if I was trying to present a construction of the reals. But this
ordering of the finite reals, whilst it serves a purpose in the argument,
is of course a side-show. The business part of the list, its hypothetical
nature, is evident in the infinite reals, the ones which have an infinite
number of significant binary places (no trailing 0s anymore).

The list is a
hypothetical one, as it is in Cantor. If this wasn't obvious, I apologize.

What does the word "hypothetical" mean?

Potentially a very interesting question. But to treat it plainly:
suppositional, we suppose that the reals are all there for the sake of
argument, exactly as Cantor does in his proof.

The problem is that while Cantor starts with an arbitrary list, you
specify that, in your list, the real numbers that have only a finite
number of nonzero binary digits must come first. Once you do this, it is
pointless to assume the list includes all real numbers, since it is
already clear that you never get to any real number that has an infinite
of nonzero binary digits.

Saying that the "infinite reals" come at the end is basically cheating.
If you have stuff at the end (after the items labeled with a natural
number), then it isn't a list. A list of reals is a function with domain
the natural numbers and range the real numbers.

If you want to show the reals
aer countable, then you need to "list" them, i.e., show us a
correspondence between the natural numbers and the reals such that every
real corresponds to a natural number.

Of course, you can't do this because Cantor proved that you can't.

If you're taking that for granted we might as well stop here. There
is one particular step in my argument which I might have elaborated on
more. I accept, in a sense, that Cantor's argument works for an arbitray
array of reals. My argument is that he's assuming that if it works for an
arbitrary array of then it works for all arrays,

That's what the word "arbitrary" means. In other words, we start with a
list and all we assume about it is that it is a list of reals. From
there, we construct a real that is not on the list, thus showing that no
list of reals can include all reals.

and it doesn't.

Why not?

Since this is already a kind of
concession that the reals aren't countable, perhaps this is where the
answer to my argument lies. I need to think some more about this. Is it
still necessary to prove that the assumption that the array is square leads
to a contradiction?

The business of whether pt 11111....... is in the list, given its
notional nature, is entirely non-essential. I am at liberty to include it.

Where you include it affects what number you construct from the
diagonal.

Yes. What's the problem? Don't mean to sound flippant. I'm probably
missing something.

You are missing two things:

1. You can't put stuff at the end of a list. If you do, it isn't a list.

2. The construction starts with a list and produces a real number not on
the list. The number not on the list depends on the list. There is no
claim that there is a single real number that is missing from every
list.

I've just realized what my mistake is, and it is a very stupid one,
though not the one some people seem to think I'm making. It is that of
failing to read Cantor's argument properly. I simply missed the condition
that the list should be of non-terminating decimals (or binaries).

This is incorrect. The list is completely arbitrary. That's what
makes it a proof that all such lists are incomplete.

If the list were restricted, the proof would only apply to lists
that met the restrictions.

I
thought I was just reprising his argument but with an ordering imposed on
the list.

A "list" in this context is a mapping N->R. By definition, there
is a first element, a second, ... one for each n in N.

If you include all the reals (rationals and all), you produce a
diagonal about which it is completely missing the point to say its inverse
is not on the list.

The proof shows this is not possible.

This is what I found frustrating about some of the
responses. It is a non-number, something with an infinite number of 0s
followed by

An infinite number of 0's is not followed by anything, since
it has no end.

Also, it is incorrect to say the proof constructs a "non-number",
since the point of the proof is to construct a number.
Specifically, a number not on the original list.

an infinite number of other values most which are impossible to
determine. If that was a consequence of Cantor's proof then there would
indeed be something wrong with it.
Thanks for your considered responses. Sorry if I have wasted yours
and others time. At least now I understand the need for that condition on
the reals. As for the brainless know-it-alls who think you can dismiss what
someone says without even thinking about it - well, never mind.

If you're going away, I'm sorry you're doing so with such
serious misconceptions remaining.

- Randy


I'm bginning to wonder if going away wouldn't be the best thing. I
feel increasingly uncomfortable that I might be squandering the valuable
time of people, like yourself, who have put real effort into their replies.
Next time, if there is a next time, I will make sure I know my stuff before
opening my mouth. This was like an itch I couldn't reach. What I wanted
from posting here was, not to get into a row for the sake of it, but to be
put out my misery, so to speak, and quickly. It may be that I am making a
mistake which, while it seems elementary to you, is something I do not have
the mathematical knowledge and grasp to understand easily. You're right of
course. The condition on the reals that I was talking about was simply
about, in some versions, eliminating the ambiguities to do with e.g. pt
0111......... = pt 1000000000...........So anxious am I to be done with
this, I got my head in a spin. I was too quick to upgrade myself from crank
to fool, though no doubt most will still think me both.

If you can bear it, I still don't fully understand what is
incoherent about taking Cantor's hypothetical list of reals and imposing an
order on it, in the way outlined. It begins with an infinite number of
finite reals, ones that finish with infinite trailing 0s, a subset of the
rationals. All that is OK. We already knew there are infinite subsets of
the reals. So the whole list is not exhaused by this subset. It does not
matter how the rest are arranged. What matters is that they are already
infinitely far down in the list.

This is your problem. There is nothing "infinitely far down" a list.
A list
doesn't have a place "infinitely far down" where anything could be.
Every place in a list is "finitely far down".

So if you start out by putting all the rationals with terminating
decimals
on the list, you use up every place in the list. There is no place for
any real number (rational or not) with a nonterminating decimal.

This is itself does not mean that there is no list of reals. Consider
two
lists

A = 0,2,4,6, ...
B = 1,3,5,7 ...

If we try to make a list C, by first puting all the elements of A on
the list,
we find that C doesn't have any more room, so we can't put any elements
of B on the list. But we can make list D, by first taking an element
from
A, then an element from B, then an element from A, then an element from
B,
and so on. You end up with

D = 0,1,2,3,4 ...

So we need to know that there is no possible ordering of the reals that
would lead to a list of the reals.

We first prove: Given any list of reals L, there is a real d(L) which
is not
in the list.

[This must be true for *any* L. Note, if we are given a list L, we
know the value of the nth decimal place of the nth element of L.
So we can determind d(L). Note further, if we are given L_1 we can
determine L_2, that does contain d(L_1). However, L_2 does
not contain d(L_2). We could then make L_3 which contains d(L_1)
and d(L_2). However, this will not contain d(L_3). No matter what we
do we have to end up with a list, L. When we do this list will not
contain d(L)]

So we have: for any list L, L is not a complete list of the real
numbers.
Equivalently, there is no complete list of the real numbers

- William Hughes

.

Relevant Pages

  • Re: A wise decision
    ... Cantor showed how infinite sets could have different cardinality, ... i.e. irrationals like e.g. pi as well as the "other" reals. ... i.e. mistakes already at the level of mathematics. ...
    (sci.math)
  • Re: Real Discontinuity in Cantor Diagonal
    ... On the other hand IF by "infinite list" it is meant simpy that there ... diagonalization is to be performed, then that's ok but in THIS case n ... only some of the reals and not all of them. ... Nothing whatever in anything I just said about lists ...
    (sci.logic)
  • Re: An uncountable countable set
    ... >> complete ordered field (he uses reals to exemplify). ... Thagt means that at no time have we ever completed an infinite number of iterations. ... Cantor's second proof was never applied to the reals, ... > Considering that the set of finite naturals is ultimately finite, as> Wolfgang has been trying to express, that's not a surprising result. ...
    (sci.math)
  • Re: Real Discontinuity in Cantor Diagonal
    ... On the other hand IF by "infinite list" it is meant simpy that there ... only some of the reals and not all of them. ... of naturals is correct, there is exactly that implicit extrapolation ... by a mere discontinuous analogy with "all finite lists of reals" (as ...
    (sci.logic)
  • Re: Towards disproof of Omega 2
    ... > A very hugely infinitely many different single lists, ... > scheme") MUST FAIL to represent MOST reals. ... > that you could've defined SOME representation scheme that represented ... all coin sequences are computable to infinite length? ...
    (sci.logic)
Loading