Re: Cardinality of Set of Computable Numbers?
From: Arthur J. O'Dwyer (ajo_at_nospam.andrew.cmu.edu)
Date: 12/29/03
- Next message: Russell Easterly: "Re: Cardinality of Set of Computable Numbers?"
- Previous message: Arthur J. O'Dwyer: "Re: Cardinality of Set of Computable Numbers?"
- In reply to: Russell Easterly: "Re: Cardinality of Set of Computable Numbers?"
- Next in thread: Daniel W. Johnson: "Re: Cardinality of Set of Computable Numbers?"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: Sun, 28 Dec 2003 23:12:16 -0500 (EST)
On Sun, 28 Dec 2003, Russell Easterly wrote:
>
> "Daniel W. Johnson" <panoptes@iquest.net> wrote...
> > 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.
> > Here is an example of the beginning of a complete list:
> >
> > 0
> > 1/2
> > 1/3
> > 2/3
> > 1/4
> > 3/4
> > 1/5
> > ...
> >
> > 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.
>
> Maybe. That is the point of the proof.
Right. The *proof* *proves* it. That's why Daniel writes, "Therefore,
et cetera, et cetera." It's equivalent to the abbreviation "Q.E.D."
There's no reason to say "Maybe."
[I repeat my opinion that you should search Google before continuing
to post in this thread. Pedagogy is fun, and I'll be the first to admit
I have benefitted greatly from it, but it tends to clutter up the groups
if it's let run amok, IMHO.]
> How are you proving your list is complete?
Actually, he didn't -- he just said, "It's obvious," and moved on.
A rigorous proof would use the traditional "diagonal method" -- NOT
Cantor's diagonalization, but a different kind of diagonal analogy
I think attributed to Godel. It involves laying out the plane of
(positive) rational numbers as follows:
1/1--1/2 1/3--1/4 ...
.' .' .'
2/1 2/2 2/3 2/4 ...
| .' .'
3/1 3/2 3/3 3/4 ...
.'
4/1 4/2 4/3 4/4 ...
|
... ...
You'll need a fixed-width font to see the ASCII-art "line" that
I've drawn zigzagging across the diagonals of the grid. This line
obviously passes through every number in the grid. And every
positive rational number is *somewhere* on that grid, as you can
see from the way it's laid out. So the line passes through every
positive rational number, in sequence. "Straighten out" the
line, and remove duplicates, and add zero and the negative rationals,
and you're done -- you have a complete list of all the rationals.
It begins
0, 1, -1, 1/2, -1/2, 2, -2, 3, -3, 1/3, -1/3, 1/4, -1/4, 2/3, ...
and continues to infinity. Now match up the elements of that
list, one-to-one, with the positive integers
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, ...
Ta-da!
[The next bit has been re-ordered for clarity.]
> To prove that the set contains all rational numbers
> you will have to show there is no way to order
> the set such that the diagonal is rational.
> There are a lot of ways to order a set of rationals.
>
> > 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.
[Q.E.D.]
-Arthur
- Next message: Russell Easterly: "Re: Cardinality of Set of Computable Numbers?"
- Previous message: Arthur J. O'Dwyer: "Re: Cardinality of Set of Computable Numbers?"
- In reply to: Russell Easterly: "Re: Cardinality of Set of Computable Numbers?"
- Next in thread: Daniel W. Johnson: "Re: Cardinality of Set of Computable Numbers?"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
