The class of Real Closed Fields (RCF) has nice model theoretic properties, among them Ominimality and quantifier elimination. We examine RCF and the nonelementary 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 nonelementary 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 quantifierfree types are isomorphic. Then K < ARCF.A computable structure A is relatively Deltaalpha categorical if for any copy B, isomorphicto A there is a Deltaalpha 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 Deltaalpha categorical if it has a formally Sigmaalpha 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 Delta2 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 Deltaalpha 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 Deltaalpha categorical and not relatively Deltabeta categorical for any ordinal beta less than alpha.
Computability in the class of Real Closed Fields
Doctoral DissertationAbstract
Attribute Name  Values 

URN 

Author  Victor A Ocasio 
Advisor  Julia F. Knight 
Contributor  Greg Igusa, Committee Member 
Contributor  Julia F. Knight, Committee Chair 
Contributor  Peter Cholak, Committee Member 
Contributor  Russell Miller, Committee Member 
Degree Level  Doctoral Dissertation 
Degree Discipline  Mathematics 
Degree Name  PhD 
Defense Date 

Submission Date  20140416 
Country 

Subject 

Publisher 

Language 

Record Visibility  Public 
Content License 

Departments and Units 
Files
Thumbnail  File Name  Description  Size  Type  File Access  Actions 

OcasioVA042014D.pdf  480 KB  application/pdf  Public 
1 entry found