Prove that the set of nonprime numbers $>0$ is a spectrum

Question

$\textbf{6.10 Exercise.}$ A set $M$ of natural numbers is called a $\textit{spectrum}$ if there is a symbol set $S$ and an $S$-sentence $\varphi$ such that $$M=\{n\in\mathbb{N}\mid\varphi\text{ has a model containing exactly }n\text{ elements}\}.$$ Show: (d) the set of nonprime numbers $>0$ is a spectrum.

This is an exercise from Ebbinghaus' Mathematical Logic, I did all the others with some help, but I don't know exactly how to solve this one.

Answer 1

Here's an argument that generalizes nicely to similar sets in place of the composites, at the cost of resulting in less natural structures:

Take as our language $\{U,V,f\}$ where $U,V$ are unary relation symbols and $f$ is a binary function symbol. Now we can whip up a sentence in this language which intuitively says that the domain is a "nondegenerate rectangle" with sides corresponding to $U$ and $V$ and "coordinatized" by $f$:

$U$ and $V$ each hold of at least two elements, their intersection has exactly one element, and for each $x$ there is exactly one pair $(a,b)$ such that $U(a), V(b)$, and $f(a,b)=x$.

While for this particular problem the ring theoretic strategy suggested in the comments is much nicer, the above brute-force approach generalizes immediately to more complicated sets like "all numbers which can be written as a product of seventeen numbers $>1$" (just use seventeen unary predicates and have $f$ be seventeen-ary). See also this old answer of mine for a more difficult extension. Finally, this way of thinking is the first step towards proving that every $\mathsf{NEXPTIME}$-decidable set is a spectrum (the converse is also true, but this is the hard direction).

The survey paper Fifty years of the spectrum problem (Durand/Jones/Makowsky/More) may be of interest.