The Atomic Model Theorem
Status: submitted
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 RCA0, others are equivalent to
ACA0. One, that every atomic theory has an atomic model, is
not provable in RCA0 but is incomparable with
WKL0, more than Pi11 conservative
over RCA0 and strictly weaker than all the combinatorial
principles of Hirschfeldt and Shore [2007] that are not
Pi11 conservative over RCA0. A
priority argument with Shore blocking shows that it is also
Pi11-conservative over BSigma2. We
also provide a theorem provable by a finite injury priority argument
that is conservative over ISigma1 but implies
ISigma2 over BSigma2, 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