Infinite Spectrum Problem

Question

Let us work in a class theory like NBG.

For a given first order sentence $\phi$ define $\infty\text{-spectrum}(\phi)$ to be the class of all cardinal numbers $\kappa$ for which there is a model $M$ of $\phi$ such that the cardinality of $M$ is $\kappa$. Let $\text{Card}$ be the class of all cardinal numbers. Set $\text{Card}_+:=\text{Card}\setminus \{0\}$. A subclass $S$ of $\text{Card}_+$ is said to be an $\infty$-spectrum if there is a first order sentence $\phi$ with $\infty\text{-spectrum}(\phi)=S$.

Question: Let $S$ be an arbitrary $\infty$-spectrum. Does it follow that $\text{Card}_+\setminus S$ is also an $\infty$-spectrum?

Answer 1

By compactness, if $\phi$ have models of arbitrarily large finite cardinality, then $\phi$ has an infinite model, and by Lowenheim-Skolem (upward and downward) you can find models of $\phi$ of any cardinality $\kappa\geq \aleph_0$.

So, one can restrict the question to $S\subseteq \mathbb{N}\setminus \{0\}$, but I have the feeling that is a complicated question.

In fact, quoting Exercise 1.4.7(c) of Marker's book "Model Theory: an introduction":

"A subset $S\subseteq\mathbb{N}\setminus \{0\}$ is the finite spectrum of some first-order sentence $\phi$ if and only if there is a nondeterministic Turing machine $M$ running in exponential time such that given a string of $n$ 1's as input $M$ halts accepting if and only if $n\in X$."

Thus, I guess the question is whether the collection of sets that are recognizable in nondeterministic exponential time is closed under complement, but that is certainly a question that I cannot answer in my huge ignorance about Turing machines.