Spectrum of elements in a set Suppose that $X$ is a spectrum. Is $\mathbb{N}\setminus X$ a spectrum?
By spectrum, we mean that it is the set containing all natural numbers $n$ s.t. there is a model of $\phi$ with exactly $n$ elements (for some first-order sentence $\phi$ in some language $\mathcal{L}$).
 A: (Edited in response to comments)
I don't know the answer - nobody does! This is an open problem, which means that proving that spectra are closed under complements or providing a counterexample (an example of a spectrum $X$ whose complement $\mathbb{N}\setminus X$ is not a spectrum) would be a new mathematical result.
In a comment on your previous question, boumol posted a link to the following note on finite spectra by Stanley Burris: https://www.math.uwaterloo.ca/~snburris/htdocs/WWW/PDF/spectra.pdf
The following paragraph from these notes answers your question:
"In 1956, Asser looked at the question of whether the complement of
a spectrum is again a spectrum - the problem is still open. A fascinating
result was proved by Jones and Selman in 1974 when they showed that a
subset of $\mathbb{N}$ is a spectrum iff it can be accepted by some nondeterministic Turing machine in time $2^{O(n)}$. From this it follows that if NP is closed under complements, i.e., NP = co-NP, then spectra are also closed under complements. Consequently to show that spectra are not closed under complements is at least as difficult as showing NP $\neq$ co-NP, and hence P $\neq$ NP."
Explaining the classes NP and co-NP is outside the scope of this response, but the take-away message from this paragraph is that if you could show that spectra are not closed under complements, you would also have managed to solve one of the most important open problems in mathematics and computer science by proving that P$\neq$NP. So this is hard.
