In David Marker's introduction to model theory, one corollary of theorem 4.2.11 is that, for $T$ a complete theory in a countable language, if $\mid S_n(T)\mid<2^{\aleph_0}$, then $T$ has a prime model (where $S_n(T)$ is the set of complete $n$-types mutually satisfiable with $T$). At the end of the section he then comments:
We note that it is possible for there to be prime models even if $\mid S_n(T)\mid=2^{\aleph_0}$. For example, $Th(\mathbb{N}, +, \cdot, <, 0, 1)$ and RCF have prime models.
I'm struggling with the first example in this statement; it's not at all clear to me why the set of complete $n$-types mutually satisfiable with $Th(\mathbb{N}, +, \cdot, <, 0, 1)$ has uncountable cardinality. So my question is this:
What do the complete $n$-types of $Th(\mathbb{N}, +, \cdot, <, 0, 1)$ look like?
First I'm trying to ascertain if $T=Th(\mathbb{N}, +, \cdot, <, 0, 1)$ has quantifier elimination (just arguing by the test in corollary 3.1.12). If it does, then wouldn't the definable subsets of any model of $T$ just be finite boolean combinations of intervals and finite sets? In which case any complete $n$-type would have to be uniquely determined by such a boolean combination, and so the set of $n$-types would be countable.
Clearly there's something wrong in that argument, but I don't know where; can anyone give me some insight here?
edit: On second thought I don't think $T$ has quantifier elimination; for instance, it's clear that $\phi(v):=\exists x\space v=2\cdot x$ defines an infinite and coinfinite subset of $\mathbb{N}$, which would contradict quantifier elimination.
Best Answer
I don't think there's any nice description of the complete $n$-types: $Th(\mathbb{N}, +, \cdot, <, 0, 1)$ is a very complicated theory. It's easy to show there are uncountably many for any $n\geq 1$, though. Just note that if $S$ is any set of primes, there is a (not necessarily complete) $1$-type which says $x$ is divisible by each element of $S$ but not divisible by any prime not in $S$. These $1$-types for different values of $S$ are all incompatible, so they can be extended to distinct complete $1$-types (or $n$-types for any $n\geq 1$). Since there are $2^{\aleph_0}$ different sets of primes, this gives $2^{\aleph_0}$ different complete $1$-types.