Re: Cardinality of Set of Computable Numbers?

From: Daniel W. Johnson (panoptes_at_iquest.net)
Date: 12/29/03 

Date: Sun, 28 Dec 2003 20:58:30 -0500

Russell Easterly <logiclab@comcast.net> wrote:

> Let R be the set of all rational numbers, r, such that 0 <= r < 1.
> If R can be ordered such that the diagonal is a rational number,
> the diagonal proof shows the rationals to be uncountable.

And if my grandmother had wheels, she'd be a wagon.

There are several ways to put that subset of the rational numbers into
one-to-one correspondence with the positive integers.

> Most people will argue that the diagonal of this set must be
> an irrational number. I have never seen a proof of this.
> It is easy to come up with a list of rationals that have a rational
> diagonal. The set I give above is one such set.

Of course, that set was not all of the rationals in that range.

Here is an example of the beginning of a complete list:

0
1/2
1/3
2/3
1/4
3/4
1/5
2/5
3/5
4/5
1/6
5/6
1/7
...

Identifying a rational given its position (or vice-versa) is probably
going to require generating the list up to that position, but this list
is obviously complete. Therefore, the set of rational numbers in [0,1)
is countable.

You want a proof that any such complete list has an irrational diagonal?
Okay:

Assume that a complete list with a rational diagonal can be found. The
diagonalization process would generated a rational number not in the
list. This would contradict the assumption. Therefore, either the list
is incomplete or the diagonal is not rational. (My list is complete, so
the diagonal must not be rational. Your list had a rational diagonal,
but was obviously incomplete.)

When applied to an allegedly complete list of the reals in [0,1), the
diagonally-generated number does not have the option of being other than
real, so the only possible conclusion is that the list was incomplete. 

-- 
Daniel W. Johnson
panoptes@iquest.net
http://members.iquest.net/~panoptes/
039 53 36 N / 086 11 55 W

Relevant Pages

  • Re: Dedekind Cuts, Fundamental Sequences: why?
    ... viewing the rational numbers as being incomplete, ... Completeness of the reals means that the least upper bound axiom is specified. ... real analysis course bored the piss out of me because most of it was ... rationals) to be even more obvious. ...
    (sci.math)
  • Re: Dedekind Cuts, Fundamental Sequences: why?
    ... viewing the rational numbers as being incomplete, ... Completeness of the reals means that the least upper bound axiom is ... real analysis course bored the piss out of me because most of it was ... rationals) to be even more obvious. ...
    (sci.math)
  • Re: Dedekind Cuts, Fundamental Sequences: why?
    ... viewing the rational numbers as being incomplete, ... Completeness of the reals means that the least upper bound axiom is ... that every Cauchy sequence converges. ... rationals) to be even more obvious. ...
    (sci.math)
  • Re: Cardinality of Set of Computable Numbers?
    ... et cetera, et cetera." ... Cantor's diagonalization, but a different kind of diagonal analogy ... I've drawn zigzagging across the diagonals of the grid. ... and you're done -- you have a complete list of all the rationals. ...
    (comp.theory)
  • Re: Cardinality of Set of Computable Numbers?
    ... >> the diagonal proof shows the rationals to be uncountable. ... > Identifying a rational given its position (or vice-versa) is probably ... > diagonalization process would generated a rational number not in the ... > is incomplete or the diagonal is not rational. ...
    (comp.theory)