Applications of computability theory to prime models and differential geometry
Robert Irving Soare, Barbara F. Csima · 2003
We consider the Turing degrees of prime models of complete decidable theories. In particular we show that every complete decidable atomic theory has a prime model whose elementary diagram is low. If we have a complete decidable atomic theory with all types of the theory computable, we show that for every degree d with 0 < d ≤ 0′, there is a prime model with elementary diagram of degree d. We say that a set X is prime bounding if for every complete decidable atomic theory T there is a prime model U of T decidable in X. In joint work with Denis Hirschfeldt, Julia Knight, and Robert Soare, we give the characterization that the prime bounding sets X ≤T ∅ ′ are exactly the sets which are not low2. Recent results of Alex Nabutovsky and Schmuel Weinberger in differential geometry have required the construction by Robert Soare of a certain sequence of computably enumerable sets. Weinberger later asked for a stronger sequence, which we construct. In addition, he introduced an ordering with geometric applications and asked for its computability theoretic properties, which we study.