tennenbaum phenomena for the reals?

Question

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...

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.

Answer 2

In computable analysis, the core notion is that of a represented space, which is a pair $(X,\delta)$ of a set $X$ and a partial surjection $\delta : \subseteq 2^\omega \to X$. The idea is that we code the elements of $X$ by binary sequences, and the computation then happens on the binary sequences. I'll write $\mathbf{X}$ in the following (just like we often suppress mentioning the topology explicitly for a topological space).

The question now becomes: Let's say we have a represented space $\mathbf{X}$, together with computable operations $+,\times: \mathbf{X} \times \mathbf{X} \to \mathbf{X}$ and a computable predicate $< : \mathbf{X} \times \mathbf{X} \to \mathbb{S}$. Furthermore, we know that $(\mathbf{X},+,\times,<)$ is a real-closed field. How restrictive are these conditions?

The answer is: Not very restrictive at all. For example, every real-closed subfield of $\mathbb{R}$ shows up in this way - we can just restrict the standard representation of $\mathbb{R}$ to the subfield.

What happens when we restrict ourselves to the case where we really are dealing with the reals? The constraints are not even enough to force $\mathbf{X}$ to contain any computable points at all - we probably should add $0$ and $1$ as constants to the signature. But this still doesn't cut it - we can have a representation that makes everything work, but at the same time enforces that every non-integer has only names computing the Halting problem.

If we add division as partial computable function, and effective Cauchy completeness (meaning a map that takes a sequence $(a_n)_{n \in \mathbb{N}}$ with $\forall i,j \geq k \ |a_i - a_j| <2^{-k}$ and outputs its limit), then we got enough to prove that our represented space is computably isomorphic to the usual reals $\mathbb{R}$.

Unfortunately, I don't really have anything to say about realizing non-Archimedian real-closed fields as represented space. But this is an interesting question!