##
The Atomic Model Theorem and Type Omitting

Status: published in the *Transactions of the American Mathematical
Society* 361
(2009) 5805 - 5837.

Availability: PostScript, DVI, and PDF

**Abstract.** We investigate the complexity of several classical
model theoretic theorems about prime and atomic models and omitting
types. Some are provable in RCA_{0}, others are equivalent to
ACA_{0}. One, that every atomic theory has an atomic model, is
not provable in RCA_{0} but is incomparable with
WKL_{0}, more than Pi^{1}_{1} conservative
over RCA_{0} and strictly weaker than all the combinatorial
principles of Hirschfeldt and Shore [2007] that are not
Pi^{1}_{1} conservative over RCA_{0}. A
priority argument with Shore blocking shows that it is also
Pi^{1}_{1}-conservative over BSigma_{2}. We
also provide a theorem provable by a finite injury priority argument
that is conservative over ISigma_{1} but implies
ISigma_{2} over BSigma_{2}, and a type omitting
theorem that is equivalent to the principle that for every X there is
a set that is hyperimmune relative to X. Finally, we give a version of
the atomic model theorem that is equivalent to the principle that for
every X there is a set that is not recursive in X, and is thus in a
sense the weakest possible natural principle not true in the
omega-model consisting of the recursive sets.

drh@math.uchicago.edu