# Are Spectrums Recursive?

Logic Level 4

Given a first order vocabulary $\sigma$ and a sentence $\varphi$ over $\sigma$, a subset $M \subseteq \mathbb{N}$ of natural numbers is called the spectrum $\varphi$ if for each $n \in M$, there is a model satisfying $\varphi$ containing exactly $n$ elements.

For example, the spectrum of the following sentence is the set of even numbers.

$\forall x ~ \left [S(x) \iff \neg T(x) \\ \land~ f(f(x))=x \\ \land~ S(x) \iff T(f(x))\right ]$

A set $M \subseteq \mathbb{N}$ is said to be recursive if given a natural $n$, a Turing Machine can determine whether $n \in M$ or $n \not \in M$.

Which of the following are true?

×