Computability in the class of Real Closed Fields

The class of Real Closed Fields (RCF) has nice model theoretic properties, among them O-minimality and quantifier elimination. We examine RCF and the non-elementary subclass of RCF composed of archimedean real closed fields, ARCF, from a computable structure theory perspective. Also, we explore connections with the class of linear orders (LO). We focus on two main notions: Turing computable embeddings and relative categoricity.The notion of Turing computable embedding (TCE) is an effective version of the Borel embedding defined by Friedman and Stanley in 1989 [1]. In fact, many Borel embeddings are computable. The relation < is a preordering on classes of structures. In [1], the authors provide a computable Borel reduction showing that LO is a maximal element of the preordering defined by TCE’s. An embedding, due to Marker and discussed by Levin in his thesis, shows that LO < RCF, hence RCF is also maximal.We consider the class DG, of daisy graphs, a non-elementary subclass of the class of undirected graphs. Each structure A in DG codes a family S of subsets of the natural numbers N. We show that each of DG and ARCF is TC embeddable into the other. We use = to denote this.Theorem 1: DG = ARCF.To prove Theorem 1 we construct a computable perfect tree T whose paths represent algebraically independent reals. We pass from an element of DG to a family of paths through T, and from there to a real closed field which is the real closure of this family of reals.We generalize Theorem 1 and obtain the following.Theorem 2: Let K be a class of structures such that any A, B satisfying the same quantifier-free types are isomorphic. Then K < ARCF.A computable structure A is relatively Delta-alpha categorical if for any copy B, isomorphicto A there is a Delta-alpha relative to B isomorphism between A and B, here 'alpha' stands for a computable ordinal. Ash, Knight, Manasse, and Slaman, and independently Chisholm, showed that a structure is relatively Delta-alpha categorical if it has a formally Sigma-alpha Scott family of formulas. Results by Nurtazin imply that a real closed field is relatively computably categorical if it has finite transcendence degree. Later work by Calvert shows that if a real closed field is archimedean then it is relatively Delta-2 categorical.Marker’s embedding takes a linear order L to a real closed field we denote by RL. Essentially RL is the real closure of L, where the elements of L are positive and infinite in RL, and if l is less than s in L, then all positive powers of l are less than s in RL.Theorem 3: If a computable linear order L is relatively Delta-alpha categorical, then RL isrelatively Delta-(1+alpha) categorical.The converse of Theorem 3 holds for alpha = 1. We show it also holds for alpha a natural number, assuming further computability properties on one copy of L. We are able then to show the following.Theorem 4: For arbitrarily large computable ordinals, there is a real closed field that is relatively Delta-alpha categorical and not relatively Delta-beta categorical for any ordinal beta less than alpha.