For any first order sentence $A$ at least one of $\mathrm{Sp}(A)$ or $\mathrm{Sp}(\neg A)$ is cofinite My approach is different, but this includes an answer. Also this MSE question is related. I assume the first order language $\mathcal{L}$ to have constant symbols, predicate symbols (including the identity predicate $=$) and operation symbols. The result is true, as you can read in the first link above. I have a question regarding the viability of my approach:
Let $A$ be an $\mathcal{L}$-sentence. The spectrum of $A$ is the set $\mathrm{Sp}(A)=\{m\geq 1:\mbox{there is $M\vDash A$ with $|U_{M}|=m$}\}$, where $M$ denotes an $L$-structure and $U_{M}$ denotes its domain.
Attempt at a proof (First I assume $\mathcal{L}$ has no operation symbols): Let $S$ be the set of sentences:

*

*$\alpha_{m}:=\exists x_{1}\ldots\exists x_{m}\,\neg((x_{1}=x_{2})\vee(x_{1}=x_{3})\vee\ldots\vee(x_{m-1}=x_{m}))$, for all $m\geq 1$.

*$\forall \bar{x}\,P\bar{x}$, for all predicates $P\in\mathcal{L}$ (where $\bar{x}$ denotes a $k$-tuple according to the $k$-arity of the predicate $P$).

*$(a=b)$, for all constants $a,b\in\mathcal{L}$.

First, the set $S$ is satisfiable. One may take simply a structure $M$ having domain $\mathbb{N}$, all constants interpreted as $0$ and each $k$-ary predicates interpreted as the cartesian product of $k$ copies of $\mathbb{N}$.
Now, I would like the set $S$ to be complete in the sense that given an $\mathcal{L}$-sentence $A$, either $S\vDash A$ or $S\vDash\neg A$. Why? because if $S$ is complete, say $S\vDash A$, by the Compactness Theorem there is a finite set $S_{0}\subseteq S$ such that $S_{0}\vDash A$. Then, there is a positive integer $n_{0}$ larger than any $m\in\mathbb{N}$ such that $\alpha_{m}$ is in $S_{0}$. But this means $S_{0}$ and hence $A$ is satisfiable in domains of cardinality $n$ for each $n\ge 0$, i.e. $\mathrm{Sp}(A)$ is cofinite (similarly, we obtain $\mathrm{Sp}(\neg A)$ is cofinite if $S\vDash \neg A$).
Hence, my question is: Is the set $S$ complete in the sense described above? It would be enough to show that any two structures satisfying $S$ are elementary equivalent. But I don't see how to do this.
Remark on a language with operations symbols: First, perform the well-known passage from a language with operations to an operation-free one. Then, for each new predicate $F$ corresponding to a $k$-ary operation $f$, in 2. above instead of the sentence
$$\forall x_{1}\ldots\forall x_{k}\,\forall y\,Fx_{1}\ldots x_{n}y,$$
add to $S$ the sentence
$$\forall x_{1}\ldots\forall x_{k}\,\exists y\,(Fx_{1}\ldots x_{k}y\wedge \forall z\,(Fx_{1}\ldots x_{k}z\Rightarrow (y=z))),$$
or equivalently, the sentence $\forall x_{1}\ldots\forall x_{k}\,\exists y\,\forall z\,(Fx_{1}\ldots x_{n}z\Leftrightarrow (y=z))$.
The argument above applies to this modified set $S$ without modifications.

EDIT: I can prove the equivalent statement that for any $L$-sentence $A$, either $S\vDash A$ or $S\vDash\neg A$ is by using induction on the degree of the sentence. Does anyone know another way?
 A: Yes, $S$ is indeed complete. Here is an easy argument for showing this:
Lemma: Let $T$ be any first-order $L$-theory with only infinite models, and suppose $T$ is $\kappa$-categorical for some cardinal $\kappa\geqslant\max\{\aleph_0, |L|\}$. (This means that any two models of $T$ of size $\kappa$ are isomorphic.) Then $T$ is complete.
Proof: Suppose $T$ is not complete; then there is a sentence $\phi$ such that $T\not\vdash \phi$ and $T\not\vdash\neg\phi$. By the completeness theorem, there are thus $L$-structures $M$ and $M'$, each a model of $T$, such that $M\models\phi$ and $M\models\neg\phi$. By the hypothesis on $T$, $M$ and $M'$ are infinite. Thus, by the Lowenheim-Skolem theorem (in particular the "upwards" version if $|M|$, resp $|M'|$, is smaller than $\kappa$ and the "downwards" version if $|M|$, resp $|M'|$, is greater than $\kappa)$, we can find $L$-structures $N$ and $N'$ of size $\kappa$ that are elementarily equivalent to $M$ and $M'$. But this means $N\models T\cup\{\phi\}$ and $N'\models T\cup\{\neg\phi\}$; since isomorphic structures are elementarily equivalent, this contradicts that $T$ is $\kappa$-categorical. $\blacksquare$
[Note that we really do need both the assumption on $\kappa$ and the assumption that $T$ has only infinite models here. In the first case, let $T$ be your favorite incomplete theory with infinite models, and then let $(c_i)_{i\in\mathbb{R}}$ be a family of fresh constant symbols. Then $T\cup\{c_i\neq c_j:i\neq j\in\mathbb{R}\}$ is still incomplete, but it is $\aleph_0$-categorical since it has no countable models! In the second case, let $\phi$ be any countably categorical sentence with an infinite model (eg the conjunction of the theory of dense linear orders without endpoints), and let $\psi$ be a sentence in the same language with two non-isomorphic models of size $n$ for some $n\in\omega$. Then the theory $\{\exists^{=n}x(x=x)\to\psi\}\cup\{\exists^{> n}x(x=x)\to\phi\}$ is still countably categorical but is not complete.]
Okay, now note that your theory $S$ has only infinite models. Thus by the lemma we need only show that your theory $S$ is categorical in some sufficiently large cardinal $\kappa$. In fact, $S$ is categorical in any cardinal; indeed, if $M$ and $M'$ are models of $S$ with the same cardinality, let $f:M\to M'$ be any bijection such that $f(c^M)=c^{M'}$ for each constant symbol $c$ in the language. (This makes sense since $c^M$ is fixed as $c$ varies, by definition of $S$.) You can check that $f$ is a bijective $L$-embedding, hence an isomorphism, so we are done.
A: Atticus Stonestrom's answer suggested to me a way to show directly that any two structures satisfying $S$ are elementary equivalent. Thus, proving that $S$ is complete.
First, notice that $S$ is not satisfiable in any finite domain. That is, all the models of $S$ are infinite.
Next, as Atticus shows in his answer, any two structures of the same cardinality satisfying $S$ are isomorphic. But then, if $M$ and $M$ are structures satisfying $S$, both must be infinite, and by the Löwenheim-Skolem Theorem there are structures $N$ and $N'$ satisfying $S$, both having the same cardinality, and such that $M\equiv N$ and $M'\equiv N'$. But then $N\cong N'$ imples $M\equiv M'$, as desired.
Finally, it is not difficult to show that a (consistent, which our $S$ is) set of sentences in some first order language is complete if and only if any two models of the set are elementary equivalent.
