From: madore@ens.fr (David Madore)
Newsgroups: sci.math.num-analysis,sci.math.research,sci.math.symbolic,sci.math
Subject: Re: Apologies
Date: 15 Jun 1998 19:02:39 GMT
In article <6m3njr$je9@gap.cco.caltech.edu>,
Toby Bartels wrote:
>Obviously, a computable number is namable, because the formula can be
>.
>But I don't know enough practical analysis to decide
>whether every namable number is computable.
>Could there possibly be a formula which is not approximately solvable?
>Something which defines a unique real number,
>but we don't know what that number's digits are?
The standard term is ``definable'': a real number x is definable iff
there is a predicate P(t) such that x is the only t such that P(t).
Obviously only countably many real numbers are definable.
Not all definable real numbers are computable: the real number whose
n-th digit is 0 iff the n-th Turing machine stops and 1 otherwise is
definable but it is not computable.
A related notion is that of ordinal definability: it corresponds to
definability where arbitrary ordinal constants are allowed in the
formulae. The argument that shows that not all real numbers are
definable no longer works, and in fact it is consistant that all real
numbers are ordinal definable. It is also consistent that there
exists a real number that is not ordinal definable.
One last concept, but probably the most important, is that of
constructibility: a number is constructible iff it belongs to the
smallest class containing the ordinals and closed under the Godel
operations, the class L (the constructible universe). Now all
constructible real numbers are ordinal definable, and the converse is
consistent (but it is also consistent that there exists a real number
that is ordinal definable but not constructible). Finally, it is
consistent that all real numbers are constructible, and also it is
consistent that some real number is not constructible. In fact, there
are only aleph_1 constructible real number so the negation of the
continuum hypothesis implies that many real numbers are not
constructible.
--
David A. Madore
(david.madore@ens.fr,
http://www.eleves.ens.fr:8080/home/madore/)