# $n$-types of the theory of natural numbers?

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.

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.
• Thanks a lot, that's quite clear. Is my rough sketch of an argument that $Th(\mathbb{N}, +, \cdot, <, 0, 1)$ does not admit quantifier elimination correct? Obviously need to fill in details/casework but would an argument along those lines work? Aug 11 '19 at 21:23
• Yeah. Any quantifier-free formula is just a Boolean combination of polynomial inequalities. With one variable, it's easy to show that the set of elements of $\mathbb{N}$ satisfying such a formula must be either finite or cofinite. So, for instance, it cannot be the even numbers. Aug 11 '19 at 21:27