The Journal of Symbolic Logic

Research Article

Classifying model-theoretic properties

Chris J. Conidis

Department of Mathematics, University of Chicago, 5734 S. University Avenue Chicago, Illinois 60637, USA, E-mail: conidis@math.uchicago.edu

Abstract

In 2004 Csima, Hirschfeldt, Knight, and Soare [1] showed that a set AT 0′ is nonlow2 if and only if A is prime bounding, i.e., for every complete atomic decidable theory T, there is a prime model computable in A. The authors presented nine seemingly unrelated predicates of a set A, and showed that they are equivalent for sets. Some of these predicates, such as prime bounding, and others involving equivalence structures and abelian p-groups come from model theory, while others involving meeting dense sets in trees and escaping a given function come from pure computability theory.

As predicates of A, the original nine properties are equivalent for sets; however, they are not equivalent in general. This article examines the (degree-theoretic) relationship between the nine properties. We show that the nine properties fall into three classes, each of which consists of several equivalent properties. We also investigate the relationship between the three classes, by determining whether or not any of the predicates in one class implies a predicate in another class.

(Received March 27 2007)