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 Delta[Special characters omitted] categoricity.;We consider the class DG, of daisy graphs, a non-elementary subclass of the class of undirected graphs. Each A ∈ DG codes a family S of subsets of o. A set S ∈ S is coded in A by a "daisy" consisting of a center and loops of size 2n + 3 if n ∈ S and 2n + 4 if n ∉ S. We show that each of DG and ARCF is TC embeddable into the other. We use ≡tc to denote this.;Theorem 1: DG ≡tc ARCF.;To prove Theorem 1 we construct a computable perfect tree T whose paths rep- resent 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 ≤ tcACRF.;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 R L, and if l1 < l 2 ∈ L then for every n ∈ N, l[Special characters omitted] 1 < l2.;Theorem 3: If a computable linear order L is relatively Delta[Special characters omitted] categorical, then RL is relatively Delta[Special characters omitted] categorical.;The proof of Theorem 3 involves passing from a computable Sigma alpha formula ϕ(x¯) in the language of linear orders to a computable Sigma(1+alpha) formula ϕ(x¯ ) such that for all a ∈ L, L |= ϕ(a) iff for all a * ≈ a, RL |= ϕ*( a.;Theorem 4: For arbitrarily large computable ordinals alpha, there is a real closed field that is relatively Delta[Special characters omitted] categorical and not relatively Delta[Special characters omitted] categorical for any beta < alpha. (Abstract shortened by UMI.).