Question 38

The sentence is:

where $\psi$ is quantifier-free and contains no function symbols (only predicate symbols and equality).

Assume $\varphi$ is true in a model $\mathcal{M}$ with universe $U$ of size 7. Then there exist elements $s_0, t_0, u_0 \in U$ such that for all $v, w, x, y \in U$, $\psi(s_0, t_0, u_0, v, w, x, y)$ is true in $\mathcal{M}$.

Consider the substructure $\mathcal{M}'$ with universe $U' = \{s_0, t_0, u_0\}$. Notice that $|U'| \le 3$. Since $\psi$ contains no function symbols, $U'$ is closed under all operations (which are trivial). Because $\psi(s_0, t_0, u_0, v, w, x, y)$ holds for all elements of $U$, it holds in particular for all $v, w, x, y \in U' \subseteq U$.

Thus, $\mathcal{M}'$ is a valid model of $\varphi$ with universe size $\le 3$. This proves that there exists at least one model of $\varphi$ with universe of size less than or equal to 3.