I'm stuck in this exercise from Mathematical Logic, Ebbinghaus and would appreciate some help.
A set M of natural numbers is called a spectrum if there is a symbol set S and an S-sentence $\phi$ such that
M= {$n\in \mathbb{N} $| $\phi$ has a model cointaining exactly n elements}.
Show:
(a) Every finite subset of {1,2,3...} is a spectrum. (b) For every $m \geq 1$, the set of numbers $ > 0$ which are divisible by m is a spectrum.
I believe that some sentence with equality only would suit for part (a). However, I'm having some trouble to formalize an answer. Thank you.
(a) : your idea is correct, equality suffices to do the trick. Can you find a sentence $\phi_m$ written with equality such that $M\models \phi$ if and only if $M$ has $m$ elements ?
Having done that, if $D$ is such a finite subset, what can you say about the sentence $\displaystyle\bigvee_{m\in D}\phi_m$?
(b) Fix $m$. Can you write a sentence in a language with only $R$ that states that $R$ is an equivalence relation such that each equivalence class has exactly $m$ elements? Can you see how that helps ?