Spectrum of a sentence $\varphi$ with no equality sign

Question

Assume $\varphi$ is a sentence without the equality relation. Show that if $k \in Sp(\varphi)$ and $n > k$ then $n \in Sp(\varphi)$.

$Sp(\varphi)$ is the spectrum of $\varphi$, so it is the set of all positive integers $n$ for which a finite model of $\varphi$ with $n$ elements exists.

My idea was the it doesn't matter which which relation comes up in the sentence because the only one which is the "same" in the formal language and the interpretation of the model is the equality relation. Furthermore the assignment for the variables in the sentence doesn't matter because there are no free variables. Can someone help me a hint how to formulate a proof and can tell me if I have left something out?

Answer 1

The key toward solving this problem is the following construction:

Suppose $L$ is a relational language (no function or constant symbols), and $M$ is a non-empty $L$-structure. Let $a$ be an element of $M$. We define a new structure $M'$, the "blow-up" of $a$ by $n$ new elements:

• The domain of $M'$ is $M\cup \{a_1,\dots,a_n\}$.
• Let $\pi\colon M'\to M$ be the function defined by $\pi(b) = b$ for $b\in M$ and $\pi(a_i) = a$ for all $1\leq i\leq n$.
• For any $n$-ary relation symbol $R\in L$, and any tuple $(b_1,\dots,b_n)$ from $M'$, define $(b_1,\dots,b_n)\in R^{M'}$ if and only if $(\pi(b_1),\dots,\pi(b_n))\in R^M$.

In other words, the elements $a_1,\dots,a_n$ are "clones" of the element $a$ in that they relate to other elements of the structure in exactly the same way $a$ does.

Now prove by induction on the complexity of the formula $\psi$, that for any $L$-formula $\psi(x_1,\dots,x_n)$ without equality, and for any tuple $(b_1,\dots,b_n)$ from $M'$, we have $M'\models \psi(b_1,\dots,b_n)$ if and only if $M\models \psi(\pi(b_1),\dots,\pi(b_n))$.

It follows that if $\varphi$ is an $L$-sentence without equality, and $M\models \varphi$ with $|M| = k$, then picking any element $a\in M$, and letting $M'$ be the blow-up of $a$ by $(n-k)$ new elements, we have $M'\models \varphi$ with $|M'| = n$.