Does a subset of the natural numbers exist, that isn't a spectrum?

Question

We have had the following definition of a spectrum:

$S \subset \mathbb{N}\backslash\{0\}$ is called a spectrum, if there exists a formal language L and an L-formula $\phi$ in such a way, that for each $n \in \mathbb{N}, n \neq 0$: $n\in S \Leftrightarrow \phi$ has a model with a domain with cardinality n.

Now the question is: Is there a subset of $\mathbb{N}\backslash\{0\}$ that isn't a spectrum? I would assume there exists such a subset, that isn't a spectrum. Is my assumption correct? But even if it is correct, I don't know how this subset would look like or how I could show this. Maybe someone could help me proof my assumption or tell me why it is wrong.

Answer 1

There are essentially only countably many $\phi$, but there are uncountably many subsets.

Answer 2

Given $\phi$ and $n \in \Bbb{N}_{>0}$ it is decidable whether $\phi$ has a model of cardinality $n$, so a spectrum is a recursive set. A non-recursive set such as the set of Gödel numbers of formulas that are provable in PA (Peano arithmetic) cannot be a spectrum.

Answer 3

In fact, there is an exact characterization in terms of complexity theory of the class of spectra: $A$ is a spectrum if and only if $A$ is in the complexity class NEXP. So any set not in NEXP is not a spectrum.

See e.g. section 5.4 of the survey paper Fifty years of the spectrum problem. This means that the classic spectrum problem (about which the linked article is a survey) - "Is the complement of a spectrum a spectrum?" - is equivalent to the well-known open problem in complexity theory, "Does NEXP=coNEXP?"