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.


1 Answer 1


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.

  • $\begingroup$ 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? $\endgroup$ Aug 11, 2019 at 21:23
  • 1
    $\begingroup$ 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. $\endgroup$ Aug 11, 2019 at 21:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.