##
The Atomic Model Theorem and Type Omitting

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

Availability: journal
version and preprint

**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
Π^{1}_{1} conservative over RCA_{0} and
strictly weaker than all the combinatorial principles of Hirschfeldt and
Shore [2007] that are not Π^{1}_{1} conservative over
RCA_{0}. A priority argument with Shore blocking shows that it is
also Π^{1}_{1}-conservative over BΣ_{2}.
We also provide a theorem provable by a finite injury priority argument
that is conservative over IΣ_{1} but implies
IΣ_{2} over BΣ_{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