##
Bounding Prime Models

Status: published in the *Journal of
Symbolic Logic*, vol. 69 (2004), pp. 1117 - 1142.

Availability: PostScript, DVI, and PDF

**Abstract.** A set *X* is *prime bounding* if for every
complete atomic decidable (CAD) theory *T* there is a prime
model *A* of *T* decidable in *X*. It is easy to see
that *X* = 0' is prime bounding. Denisov claimed that every
*X* <_{T} 0' is *not* prime bounding, but we
discovered this to be incorrect.
Here we give the correct characterization that the prime bounding
sets
*X* <=_{T} 0' are exactly the sets which are not
low_{2}. Recall that
*X* is low_{2} if *X*'' <=_{T} 0''. To
prove that a low_{2} set *X* is *not* prime bounding
we use a 0'-computable listing of the array of sets {*Y* :
*Y* <=_{T} *X*} to build a CAD theory *T*
which diagonalizes against all potential
*X*-decidable prime models *A* of *T*. To prove that
any *non*low_{2} *X* is indeed prime bounding, we
fix a function *f* <=_{T} *X* that is not
dominated by a certain 0'-computable function that picks out
generators of principal types. Given a CAD theory *T*, we use
*f* to eventually find, for every formula consistent with
*T*, a principal type which contains it, and hence to build an
*X*-decidable prime model of *T*. We prove the prime
bounding property equivalent to several other combinatorial
properties, including some related to the limitwise monotonic
functions which have been introduced elsewhere in computable model
theory.

drh@math.uchicago.edu