Re: Cardinality of Set of Computable Numbers?

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

Date: Mon, 29 Dec 2003 03:17:11 -0500

Russell Easterly <logiclab@comcast.net> wrote:

> How are you proving your list is complete?

Any rational in [0,1) can be uniquely written as a ratio between two
coprime nonnegative integers m/n. That is an entry among the first
n(n-1)/2 + 1 entries on the list, although specifying the exact location
involves a summation on the Euler phi-function. Anyway, that entry on
the list corresponds to no other rational. (This last proviso is
moderately important, because some people like to present "complete"
lists of reals in which a given list entry can have more than one real
number associated with it.)

> 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.

I just proved that the set contains all rational numbers in [0,1).

To prove that a given integer is even, is it necessary to show both that
its units digit in base two is 0 and that its units digit in base ten is
in {0,2,4,6,8}?

> There are a lot of ways to order a set of rationals.

If you are talking about the complete set of rationals, the number of
ways is the same as the number of real numbers. If you think a relevant
ordering exists, either point out a flaw in my proof or describe the
ordering.

Otherwise, you might as well quibble with a proof that "the sum of any
finite set if even numbers is not odd" by pointing out that "there are a
lot of ways to choose a set of even numbers". 

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

Relevant Pages

  • Re: An uncountable countable set
    ... I gave one in this newsgroup a few days ago for the rationals ... for *all* lists of rationals. ... can be applied digit by digit. ... You can do so *if* you take dual representations in account. ...
    (sci.math)
  • Re: Uncountable many reals without Cantor
    ... > set, with regards to the rationals not being complete, gapless, yet ... A great many lists ... < theorems about finite trees. ... do with actual rationals, naturals, or reals. ...
    (sci.logic)
  • Re: An uncountable countable set
    ... countably infinite subset of the list numbers left which are not yet ... well-order the set of rationals for more than, say, 20 elements. ... and all is instantaneously ordered by magnitude. ... Until "mueckenh" demonstrates that he can at least put a finite lists ...
    (sci.math)
  • Re: Uncountable many reals without Cantor
    ... No; in the rationals' case ... contradiction beacuse the original list was only ... The class of things you get by taking limits of infinite lists ...
    (sci.logic)
  • Re: (Not quite) Cantors diagonal proof
    ... > I don't think any serious mathematician doubts that the reals are ... but that it applies simultaeously to all lists. ... creation of a list creates the non-member along with it. ... > terminating decimals (i.e. rationals). ...
    (sci.logic)