Re: diagonal argument on ordered array of reals

On 7 Nov 2006 11:18:10 -0800, "William Hughes" <wpihughes@xxxxxxxxxxx>
wrote:


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


These three posts have been a great help. At last I begin to
understand what you are saying, and clearly there is a good deal of muddle
and ignorance in my thinking.I understood that it was part of the
hypothesis that the reals would be numbered, but hadn't thought through
what the consequences of this were, thinking of it in fact as something
that could just be tagged on at the end of constructing the array. I also
had been puzzled as to how, if what you were all saying is true, could
there be any need for Cantor's proof. But you have helped me see that just
because the reals have infinite subsets doesn't mean that there could not
be some special arrangement of the reals which could be put in 1:1 C with
N. So I understand I cannot just add things on the end of an infinte list
and still call it a list. I would have to somehow weave them into the
array, but then the diagonal would be involved in a way which would allow
Canor's proof to bite.
There is something more, because there is something peculiarly
about this combinatorial construction that I started out with that commends
itself to us, falaciously or otherwise, as a genuine list. But before I go
on I should say I am grateful to you for persevering. I know (did know, but
temporarily forgot) how difficult it can be to unravel other people's
muddles. Considering the general nature of usenet, and the fact that I
started out here like an ignorant prick, this is all the more remarkable.
In what follows, I may be going beyond what was strictly in my
original post, but it is something which I think I have been in two minds
about all along. There may too be a connection with one or two comments in
this thread which have gone so far over my head I could see a vapour trail.
Let me write this down one more time:

1) .0
2) .1
3) .0 1
4) .1 1
5) .0 0 1
6) .0 1 1
-----------
-----------

DON'T STOP



It seems to me that what we have here is something which understood
as carried out to infinity produces every real (in the interval).
The limit of this process is not something stuck somewhere in the
middle of a table with finite reals above and infinite reals below. It is
the whole set of reals.
The point is not that you cannot add something to the end of it and
still call it a list, it is that there isn't anything else to add to it.
It is true that the process produces an infinite number of
rationals. But that doesn't mean that that is all it produces. The
irrationals don't have to be tagged on to the end of this process, they are
already there in its infinite completion. We don't need any more labels.
Because there is an infinity of these progressivley longer rationals
doesn't mean they can be broken off the irrationals they are pursuing. Zeno
does indeed come to mind, as Ross said. (Not that I am at all sure we're
both firing from the same quiver.)

How then does it appear that we can write them down in the same
table (forget about lists), as if they were on a par with each other?

Like:

.0 0 1 1 0->

.0 1 recurring

.0 1 1 0 0 1 0 1......denoting a real which we have only partially
specified.

The answer I think is that you can't. It's all illusion. The
infinitely long rationals are a special case. If I've got this right, any
given infintite rational (in other words one that ends with a recurring
part) can be eliminated by changing the number base (even though whatever
number base you choose will have infinte rationals). It's only the
irrationals which are essentially infinite. You can not put them in an
ordered list, not even a hypothetical one. Any trailing dots might as well
be vertical ones, denoting uncertainty about its position in the list.
Switching to decimals for clarity, let's say we wish to denote a particular
irrational by:

.. 3 1 4 1 5 9 2 ..............

So put it next to

.. 3 1 4 1 5 9 2 0 0 0 0 0 0....

Then we get another digit. It's

.. 3 1 4 1 5 9 2 6.............

OK. Move it down next to

.. 3 1 4 1 5 9 2 6 0 0 0 0......

and so on. It doesn't matter that it can be calculated to arbitray high
accuracy (pi div by 10). It's absolute position can never be fixed.

I'm not sure whether it matters whether the list is ordered or not.
You just can't finish specifying which irrational you mean.

I better stop there, as I've probably already involved myself in
half a dozen further muddles different to the ones I started out with.

Ten Letters






.

Relevant Pages

  • Re: (sketch of a) Proof that the set of Real Numbers doesnt exist
    ... >> an infinite set and its powerset ... > both rationals and reals are numbers between rational numbers. ... assigned to rational numbers and pairs of open sets assigned to irrational ...
    (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: Cantor Confusion
    ... mathematicians are used to thinking on much higher ... the corresponding distinction between rationals and reals is ... between potentially infinite and perfectly infinite. ...
    (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: Rational numbers, irrational numbers: each dense in real numbers
    ... Among the notions of why there are "more" irrationals than rationals ... reals, ... Then, particular rationals of smaller numerators, after one and zero, ... as well in these infinite expansions have various ...
    (sci.math)
Loading