Looking for references: Banning non-computable numbers
brian tivol
Unfortunately, this is going to be another one of those "Hey, I sorta
tossed this idea around and it doesn't seem immediately wrong; does
anyone know more about it?" sort of posts. Essentially, I'm
interested in what happens to our favorite fields of math when we do
not allow non-computable numbers.
I've seen a few different ways to construct the real numbers and, in
each case, I can't really see how non-computable numbers even get
admitted into the system in the first place. Standard extensions from
rationals seem to involve adding the roots of polynomials and the
limits of series, each of which produce computable numbers.
Eventually, the construction directs you to take the limit of a tower
of fields, and I'm not utterly convinced that numbers admitted in that
way are non-computable. Even if I were so convinced, though, I could
argue that such a step is distasteful (by likening it to saying "Sure,
with infinite time you could trisect an angle, so, yeah, let's add
that to our set") and decide that my set of axioms just doesn't allow
for non-computable numbers.
So, what happens to math when only computable numbers exist? Cantor's
proof that there are uncountably many reals will fail in the same way
that the Halting Problem fails. All sets of numbers are countable, in
fact, letting us try out some math with only one size of infinity.
That concept is somewhat pretty; while it causes havok in set theory,
that havok is manageable, and a change like that may also have
pleasant benefits for areas like projective geometry. Areas like
algebra and logic seem to be wholly unaffected, and
engineering-friendly calculus gets by without major noticeable
changes. I'll lose my favorite definition of a random sequence of
numbers if non-computable numbers are thrown out, but who needs 'em
anyway? [smiley]
Is there a (good?) paper or book dealing with this idea? Have I
missed something obvious and come across as an idiot?
--brian
G. A. Edgar
<ti...@mit.edu> wrote:
> Unfortunately, this is going to be another one of those "Hey, I sorta
> tossed this idea around and it doesn't seem immediately wrong; does
> anyone know more about it?" sort of posts. Essentially, I'm
> interested in what happens to our favorite fields of math when we do
> not allow non-computable numbers.
>
> I've seen a few different ways to construct the real numbers and, in
> each case, I can't really see how non-computable numbers even get
> admitted into the system in the first place. Standard extensions from
> rationals
The two standard methods I know are: Dedekind cuts and Cauchy
sequences.
> seem to involve adding the roots of polynomials and the
> limits of series, each of which produce computable numbers.
No, only the limit of a "computable" series can be proved computable.
Any real number (computable or not) is the sum of a series or
rationals (for example, its decimal expansion).
> Eventually, the construction directs you to take the limit of a tower
> of fields, and I'm not utterly convinced that numbers admitted in that
> way are non-computable. Even if I were so convinced, though, I could
> argue that such a step is distasteful (by likening it to saying "Sure,
> with infinite time you could trisect an angle, so, yeah, let's add
> that to our set") and decide that my set of axioms just doesn't allow
> for non-computable numbers.
>
> So, what happens to math when only computable numbers exist? Cantor's
> proof that there are uncountably many reals will fail in the same way
> that the Halting Problem fails. All sets of numbers are countable, in
> fact, letting us try out some math with only one size of infinity.
> That concept is somewhat pretty; while it causes havok in set theory,
> that havok is manageable, and a change like that may also have
> pleasant benefits for areas like projective geometry. Areas like
> algebra and logic seem to be wholly unaffected, and
> engineering-friendly calculus gets by without major noticeable
> changes. I'll lose my favorite definition of a random sequence of
> numbers if non-computable numbers are thrown out, but who needs 'em
> anyway? [smiley]
Tell us what the theory of the Lebesgue integral will look like.
>
> Is there a (good?) paper or book dealing with this idea? Have I
> missed something obvious and come across as an idiot?
>
> --brian
You can try Errett Bishop's book Foundations of Constructive Analysis.
--
Gerald A. Edgar ed...@math.ohio-state.edu
KRamsay
|So, what happens to math when only computable numbers exist?
You could look at Beeson's _Foundations of Constructive Mathematics_
which talks in one chapter about what is true under such an assumption.
You have to alter your logic, which takes getting used to.
The least upper bound principle isn't valid for recursive reals. One
can exhibit a computable sequence of computable reals which is
nondecreasing and bounded above, but whose upper bound is
uncomputable. Enumerate the Turing machines T1,T2,T3,... and let
a_n be the sum of 2^{-i} over T_i for i<=n which halt within n steps
when started with a blank tape. Each a_n can be computed from n, and
a_n is even a rational number with denominator dividing 2^n. But the
least upper bound is an uncomputable real whose n-th bit is 1 when the
n-th Turing machine halts.
Keith Ramsay "Thou Shalt not hunt statistical significance with
kra...@aol.com a shotgun." --Michael Driscoll's 1st commandment
KRamsay
KRamsay
Norman D. Megill
brian tivol <ti...@mit.edu> wrote:
>
>I've seen a few different ways to construct the real numbers and, in
>each case, I can't really see how non-computable numbers even get
>admitted into the system in the first place.
In standard constructions they get introduced at the point of assuming
that the power set of a countable set exists. For example, in the
complete formal proof of the Dedekind set construction at
http://www.shore.net/~ndm/java/mmexplorer/mmexplorer.html ,
the precise place this assumption is made is in step 2 of
the theorem http://www.shore.net/~ndm/java/mmexplorer/npex.html .
(Notation: N_q is the set of positive rationals, N_p is the set
of positive reals, "epsilon V" means "is an element of V (the
universe)" i.e. "is a set".)
--Norm