Computability in the class of Real Closed Fields

Doctoral Dissertation


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.


Attribute NameValues
  • etd-04162014-232331

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
  • 2014-04-09

Submission Date 2014-04-16
  • United States of America

  • Linear Orders

  • Turing computable embeddings

  • Logic

  • Computability

  • Computable structure theory

  • Real Closed Fields

  • University of Notre Dame

  • English

Record Visibility Public
Content License
  • All rights reserved

Departments and Units


Please Note: You may encounter a delay before a download begins. Large or infrequently accessed files can take several minutes to retrieve from our archival storage system.