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/)