Prove that, for any sentence A of the predicate calculus with identity, at least one of spectrum(A) and spectrum(¬ A) is cofinite

Question

I got the following exercise:

Prove that, for any sentence A of the predicate calculus with identity, at least one of spectrum(A) and spectrum(¬ A) is cofinite.

I already tried to prove this theorem by a proof by contradiction. So suppose spectrum(A) and spectrum(¬ A) are both not cofinite. Then clearly, spectrum(A) and spectrum(¬ A) are infinite. Thus A and ¬ A have both infinite models. But I don't no how to go on ...

Could you please help me, dear stackexchange?

We got the hint that the following lemma is helpful: For any firstorder sentence s, if spectrum(s) is infinite, then s has an infinite model.

Answer 1

Despite the comments thread, the result is true. Although it can be a bit tricky to see.

To start with, let's consider an obvious possible line of attack for producing a counterexample: restricting to finite structures with some property. E.g., there is a sentence $\varphi$ whose spectrum is infinite but not cofinite, in the context of groups: namely $\varphi=$"There is an element of order $2$." However, if we try to turn this into an actual counterexample, we would look at either $\varphi_1=$"If the structure is a group, it has an element of order $2$" or $\varphi_2=$"The structure is a group and has an element of order $2$." The spectrum of $\varphi_1$ is cofinite - the non-groups - and the spectrum of $\neg \varphi_2$ is cofinite - again, the non-groups. So restricting to the groups context breaks everything.

So here's the hint: fix a first-order sentence $\varphi$ in some language. Say the prespectrum of $\varphi$, $pres(\varphi)$, is the complement of the spectrum of $\neg\varphi$. Intuitively, $n\in pres(\varphi)$ if, no matter how I interpret the symbols in $\varphi$ on a set of size $n$, I get a model of $\varphi$. Then:

• If $\varphi$ and $\neg\varphi$ each have co-infinite spectra, then $pres(\varphi)$ and $pres(\neg\varphi)$ are each infinite.

• Can you see how to convert a sentence $\psi$ with some symbols into a sentence in the empty language $\psi'$, such that the spectrum of $\psi'$ contains $pres(\psi)$ and has empty intersection with $pres(\neg\psi)$? (HINT: Think about some things that e.g. a unary relation could be . . .) If you can do this, you'll have reduced the problem to the empty language case.

Answer 2

Ok well I just looked it up. Take the theory that says there are at least $n$ elements for each $n$, and in which all constants are equal and all relations are satisfied by all tuples. There is essentially only one model of this theory and if that model satisfies $\sigma$ then some finite set of the axioms will imply $\sigma$ and so $\sigma$ has cofinite spectrum.