diagonal argument on ordered array of reals

Diagonal Argument on Ordered Array of Reals 4th Nov 2006


'Construct the reals in [0,1] combinatorially by increasing
significant binary places. 0-> means trailing 0s

infinitely.

One binary place
0 0->
1 0->

Two binary places
0 0 0->
0 1 0->

Three binary places
0 0 0 0->
0 0 1 0->

etc.

Actually, after the first two entries, every other entry is
redundant. So instead:

0 0->
1 0->
0 1 0->
1 1 0->
0 0 1 0->
0 1 1 0->
1 0 1 0->
1 1 1 0->
etc.

In each block, i.e. for a given number of significant binary
places, the numbers are in ascending order for size.
The last number, if we have the closed interval, will be 1 1 1
1.......

There are other redundancies, i.e. the equivalence of, for e.g., pt
0111....... to pt 1000..... These will not make

any difference to my arguments, and can be regarded, if you wish, as
remaining.

Clearly, as the number of significant binary places increases as n,
the number of entries increases as 2 to the power

n. The question is, as n -> infinity, does this flatten out the array. If
inf = 2 to the inf, the array is square, and we can

apply the diagonal argument.
Before we do so, let us look at the minimum distance from the last
significant binary point in a number to the

diagonal. This is given by:
dist = 2 to the (n - 1) minus (n - 1) for finite n > 1, and is 0 at
n = 1 (the first number, 0, is on the diagonal).

For finite n, the distance increases as n increases.
If 2 to inf = inf, then for an infinite significant number of
binary places the distance will be 0. I.e. the

infinitely long reals can be thought of as terminating on the diagonal, in
the limit. Everything in the square to the right

of the diagonal is trailing 0s.
So the diagonal consists of an infinite series of 0s followed by
who knows what.

What then is the inverse of the diagonal? It's an infinite series
of 1s followed by who knows what. Is this in the

list? Technically perhaps not, but it seems fairly obvious it must be
equivalent to an infinite series of 1s, which is.
In any case, there is a simple expedient to avoid the wkw. Place
the last number first. Then, except for the first

entry, every number in the diagonal is 0. Then the inverse is 01111..,
which is in the list. More precisely, as I have

arranged the reals (before placing the last number first), the diagonal is
the limit of all the reals, in effect the same

limit as the right hand side of the square. The phase space, as it were, of
the reals cannot extend beyond the diagonal. And

if we put the last number first, the limit is in effect shifted to the
left, and the reals cannot even reach the diagonal to

set up a conflict with it.

But isn't Cantor's argument a perfectly general one? If a new
number is obtained by taking the inverse in SOME array,

doesn't that prove the point? In a sense it is a general argument, in that
it doesn't specify how the reals are arranged. But

remember this is a reductio argument, and what my array brings out is that
there is an unexamined assumption that what will

be true for any old jumbled array will always be true. That it's jumbled is
precisely the point. It makes a difference

whether they are jumbled or precisely arranged.
There is of course nothing sacrosanct about the diagonal. We just
need some mapping such that each and every real is

to be changed once and every binary point is affected just once. Can we
somehow jumble the mapping to compensate for the fact

that the reals are specially arranged? I believe it's fairly obvious that
this is not so. Whatever mapping you choose, the

whole space of the square will have to be covered. In fact this picture of
all these reals crossing the diagonal is quite

misleading. Even in a jumbled list relatively few do, and the vast majority
approach it as the limit.


The power set argument appears to be much more incisive. Let me
rehearse it quickly.
The set of subsets of a set with n elements is 2 to the n.
Assume that 2 to the inf = inf.
So there can be a 1 to 1 correspondence between the elements of an infinite
set and the subsets of that set.
Let A = (a, b, c.........). Let S(A) be a subset of A. Then:

A All S(A)

a <-> (a, b)
b <-> (e, g, h, j)
c <-> (
etc.

In general, sometimes the element will be in the corresponging
subset.
E.g. in the first entry a is in (a, b), but in the second entry b
is not in (e, g, h, j)
Create the set Q which contains all the elements which are not
included in their corresponding subset. Q itself will

be a subset S(A), which must have a corresponding element, say q. Then
asking if q belongs to Q leads to a contradiction.

The trouble with reductios is that their assumptions are often more
complicated than they appear. Essentially this is

another diagonal argument.
Let us use the idea of a binary expansion as a selection function
or selection set.
Thus pt 1011... can mean the first element is selected (the first
binary place is 1), the second element is rejected

(corresponding to the 0 in second place), the third and fourth elements are
selected, and so on. Then what the argument boils

down to is this:

..........................
..........................
...0......................
.....0....................
..........................
..........................
..........0...............
..........................
.............0............
..........................
..........................
..........................
...1.1....1..1...X........

The construction of Q essentially amounts to creating a diagonal
with 0s in certain places, and 1s everywhere else.

The contradiction is derived by pointing out that there will be a number in
the list with the opposite values in the

corresponding binary places, which then collides with the diagonal where
the two lines intersect.

This argument is somehow both neater and harder to grasp, perhaps.
But as far as my argument goes it makes no

difference. For my argument is that there is a way of ordering the elements
so that they do not even reach the diagonal.


If my reasoning is sound, does that mean that inf. = 2 to inf.? I
don't know. Perhaps there are other arguments

against it, or more convincing versions of the same ones. it's interesting,
though, to speculate what the consequences might

be. Perhaps the idea of a one to one correspondence is not as clear as it
seems. Perhaps the definition of infinity having

equality with a proper subset is suspect.
I like the idea of elastic naturals. For instance I would like to
retain the common sense idea that ....-3 -2 -1, 0,

1 2 3...... is bigger than 1 2 3....... Bigger by precisely 0 -1 -2 -3..
When we compare
0 1 2 3 4 5 6.......
with
0 1 -1 2 -2 3 -3.........
which no doubt is interesting and important, maybe the naturals have got
stretched in the comparsion. After all, it's as

though we've wrapped up the infinity on the left hand side and shoved over
to the right hand side.
So then, 1 2 3.....
is shrunk in comparison with 1 4 9 16.........
or with 1 1 2 3 5 8 13...
but is stretched in comparison with the integers, and stretched in
comparison with the rationals. Is stretched to breaking

point in comparison with the reals?

There is one radical step we could take to enumerate the reas [0,
1], if inf = 2 to inf.
We are used to decimal (or binary or whatever) expansions going from left
to right, with greater accuracy at smaller scales.

What if the other way around was feasible?
Take an infinite row of 0s.
Snip it somewhere.
Discard the right hand portion.
Let the decimal point be at infinity to the left.
Change the 0 next to the cut to 1.
That can be our first real. (After 0 = pt 0000...........0000)
1st pt0000.............00001
2nd pt0000.............00002.
etc.
Each real will be its own count.
pt 47 recurring will be the 4747..................47th number, and so on.


I appreciate that the elegant genius of Cantor's arguments,
together with the lure of infinity, must attract

attention from people whose set theory and number theory and whatever
theory is not up to scratch. I confess (it's probably

obvious) that I count myself among them. i haven't thought about these
issues for years. I came across a book on

(mathematical) infinity, 'All This And More' by David Foster Wallace. I was
surprised as I knew this author only as a writer

of fiction. (By the way I think the book is a great treatment of the
subject. The style can be a little fussy.) I don't know

if surprise is a good enough excuse. Hope this wasn't too cranky.


Ten Letters jlongdensquiggleclaracouk
.

Relevant Pages

  • Re: how to list all of the real numbers
    ... those with the undecideable continuum hypothesis, yet none of them, ... continuum's cardinality is thus simply equivalent to a lesser cardinal ... does not hold where the reals are a set. ... Infinity in numbers does actually exist. ...
    (sci.math)
  • Re: how to list all of the real numbers
    ... does not hold where the reals are a set. ... could be used as a proof for the existence of limit ordinals. ... concept of "adjacent points" is provably inconsistent in geometry. ... and the infinity of the codomain. ...
    (sci.math)
  • Re: Cantors diagonal proof wrong?
    ... > infinity, you are making some basic assumptions on what an idea is. ... > of the size of an infinite set is a contradiction in itself). ... > So you just reverse the digits in the integer to create the real. ... > this mapping is one to one and covers all the reals in that range. ...
    (sci.math)
  • Cantors diagonal proof wrong?
    ... When I was shown Cantor's diagonal proof that the number of reals was not ... infinity, you are making some basic assumptions on what an idea is. ... of the size of an infinite set is a contradiction in itself). ... So you just reverse the digits in the integer to create the real. ...
    (sci.math)
  • Re: diagonal argument on ordered array of reals
    ... 'Construct the reals in combinatorially by increasing ... The question is, as n -> infinity, does this flatten out the array. ... inf = 2 to the inf, the array is square, and we can ... of the diagonal is trailing 0s. ...
    (sci.math)