Re: Cardinality of Set of Computable Numbers?

From: James Waldby (j-waldby_at_pat7.com)
Date: 12/26/03 

Date: Thu, 25 Dec 2003 19:26:31 -0600

Lee Rudolph wrote:
> "Russell Easterly" <logiclab@comcast.net> writes:
...
> >I have read that the set of computable numbers is countable.
> >
> >Let S be the set of all computable numbers
> >and assume S is countable.
> >
> >Since S is countable there is a function, f(),
> >that maps S to the natural numbers.
> >Using f() to order S, define a diagonal number, d.
> >d is a computable number not in S.
>
> To correctly conclude that "d is a computable number not in S"
> by "Using f()", you would have to know that f is a computable
> function (in, essentially, whatever sense you are using
> "computable" in the phrase "computable numbers").
>
> >Therefore,
> either
> >S can't be the set of computable numbers
> or f isn't computable. Correct conclusion: no such f is
> computable.

I don't agree that that is the problem per se. What is wrong
is that d is not well-defined, ie, not shown to exist. It is
not good enough to merely say "define a diagonal number, d".
If d is based on, for example, digit j of f(j), the process
will fail by f(j) having fewer than j digits, which is the case
for most computable numbers, expressed in any base.
-jiw

Relevant Pages

  • Re: Cantor Confusion
    ... To what number maps the edge that goes left from the ... But you stated that you had constructed a surjection. ... its expansion that digit. ... The shares of every edge I use add ...
    (sci.math)
  • Re: Contradicrtion-free mathemattics (The new nonstandard analysis
    ... >digit: by chosing it at random from the basic integers. ... trichotomy law. ... that makes trichotomy fail, so convince me by telling me what they are. ...
    (sci.math)
  • Re: Contradicrtion-free mathemattics (The new nonstandard analysis
    ... >A normal number is well-defined because there is a rule for finding every>digit: by chosing it at random from the basic integers. ... trichotomy law. ... that makes trichotomy fail, so convince me by telling me what they are. ...
    (sci.math)
  • Re: Proof that the diagonal is useless, redundant, noise,
    ... UTM *may* FAIL TO HALT for some of these pairs. ... There is no rightmost digit TO WHICH to add the 1. ...
    (sci.logic)
  • Re: pll: who uses _Bool
    ... I fail to see how the hypothetical usage of the # operator is ... the unadorned use of such digits can generate an int type constant, ... The characters 'true' are simply another glyph for the digit '1'. ...
    (comp.lang.c)