Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $\mathfrak{M} = \langle R, +,\times,> \rangle$ be such that $R$ is the set of real numbers and $\mathfrak{M} \models RA^1$ (the first-order axioms for the reals). Do we have characterisations of the isomorphism types of such $\mathfrak{M}$ for which $>,+,\times$ are real-computable, where some interesting model of `real computability' is used (e.g. Pour-El/Richards, Blum/Smale,...)?

One extreme answer would be that all isomorphism types of continuum-sized models of $RA^1$ are still possible. Another extreme answer would be that only the isomorphism type of $\mathbb{R}$ is possible. In the latter case, we would have a Tennenbaum phenomenon for the reals...

share|improve this question
    
Leon, welcome to MathOverflow! And what a great question! –  Joel David Hamkins Dec 20 '12 at 9:46
    
Cuold you also add a link to a definition/explanation of "Tennenbaum phenomenon" –  Qfwfq Dec 20 '12 at 9:52
2  
Tennenbaum proved that no nonstandard model of PA has a computable presentation. en.wikipedia.org/wiki/Tennenbaum's_theorem –  Joel David Hamkins Dec 20 '12 at 10:32

1 Answer 1

This is a very interesting question!

One way to interpret the question is like this: we have the structure $\langle\mathbb{R},{+},{\cdot},{\lt}\rangle$, which is a real-closed field, and Tarski proved that this theory is both complete and decidable. You want to know, what are the real-closed subfields of $\langle\mathbb{R},{+},{\cdot},{\lt}\rangle$ that are decidable with respect to the various models of computability on the reals? Or at least, what are the order-types of these structures?

Note first that there are an enormous number of distinct real-closed subfields of $\mathbb{R}$, namely, $2^{2^{\aleph_0}}$ many, since the transcendence degree of $\mathbb{R}$ over $\mathbb{Q}$ is the continuum $2^{\aleph_0}$, and if one fixes a set $T$ of continuum many algebraically independent reals, then for any subset $A\subset T$, one may form $\mathbb{R}_A$, the real-algebraic closure of $A$ in $\mathbb{R}$, and these will be distinct real-closed subfields of $\mathbb{R}$, since they fill different cuts in $\mathbb{Q}$. There are $2^{2^{\aleph_0}}$ many such subsets $A$. (I am unsure whether these subfields all also have distinct order-types, which you asked about; but it would seem very reasonable that they do---perhaps someone can post about this.)

It follows as a general conclusion that most real-closed subfields of $\mathbb{R}$ are not computable with respect to any of the usual concepts of computability on the reals, for there are simply too many of them, and only countably many programs. Even if one allows real parameters to be used as oracles in the computations, this would still make only continuum many program/parameter combinations, but strictly greater than the continuum many real-closed subfields, and so not all of them are computable.

For some of the models, one can say more. In the Blum-Shub-Smale model of computability, which you mentioned, for example, in fact the only BSS-decidable real-closed subfield of $\mathbb{R}$ is the whole field. The reason is that in the BSS model, no decidable set is both dense and co-dense (see Corollary 1 of Wesley Calvert, Ken Kramer and Russell Miller, Noncomputable Functions in the Blum-Shub-Smale Model), but any proper subfield of $\mathbb{R}$ would be dense and co-dense.

Meanwhile, with the infinite-time Turing machine model of computability, there are infinitely many distinct real-closed subfields of $\mathbb{R}$. The reason is that there are infinitely many algebraically independent but ITTM computable reals, and these will generate distinct ITTM computable real-closed subfields.

In my article Infinite time computable model theory, written with Russell Miller, Dan Seabold and Steve Warner, we discuss in section 2 various natural subfields with respect to ITTM computability, including the fact that $$\mathbb{R}_f\prec\mathbb{R}_w\prec\mathbb{R}_e\prec\mathbb{R}_a\prec\mathbb{R},$$ where these are, respectively, the finite-time decidable reals, the infinite-time writable reals, the infinite-time eventually writable reals, the infinite-time accidentally writable reals, and all reals.

Another way to interpret the question, a way for which I have little to say, would be to ask not about real-closed subfields of $\mathbb{R}$, which are all Archimedean, but rather to ask which real-closed non-Archimedean fields have computable presentations (computable with respect to these real computational models). This interpretation might be a closer match with the Tennenbaum phenomenon in arithemtic.

share|improve this answer
    
It appears to follow from results in the infinite time computable model theory paper that if $V=L$, then there is a non-Archimedean real-closed field with an ITTM-computable presentation. –  Joel David Hamkins Dec 20 '12 at 13:20
    
Dear Joel, Thanks very much for your answer. Part 1 of your answer is very interesting. It was really part 2 that I meant to ask. You put it nicely: which real-closed fields of size continuum but not necessarily archimedean have computable presentations (computable with respect to these real computational models)? [So your comment above this speaks to this question!] –  Leon Horsten Dec 20 '12 at 14:01

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.