GATE CS 2018 Q28 — Propositional and First Order Logic

Given the first-order logic sentence:

$$\varphi \equiv \exists s \exists t \exists u \forall v \forall w \forall x \forall y \; \psi(s, t, u, v, w, x, y)$$

where $\psi$ is a quantifier-free formula containing only predicate symbols (and possibly equality) but no function symbols.

We are given that $\varphi$ has a model $M$ with a universe $U$ of size $7$. Since $M \models \varphi$, there must exist three elements $a, b, c \in U$ (not necessarily distinct) such that for all $v, w, x, y \in U$:

$$M \models \psi(a, b, c, v, w, x, y)$$

Now, let us construct a new structure $M'$ with a universe $U' = \{a, b, c\}$. Since $a, b, c$ are elements of $U$, we have $U' \subseteq U$. The size of $U'$ is at most $3$ (i.e., $|U'| \le 3$).

Because the language contains no function symbols, $M'$ is a well-defined substructure of $M$ under the restricted domain $U'$.

For any elements $v, w, x, y \in U'$:

1. Since $U' \subseteq U$, these elements also belong to $U$.
2. Therefore, $\psi(a, b, c, v, w, x, y)$ is true in $M$.
3. Since $\psi$ is quantifier-free, its truth value is preserved in the substructure $M'$. Thus, $\psi(a, b, c, v, w, x, y)$ is true in $M'$ for all $v, w, x, y \in U'$.

This implies that $M'$ satisfies the sentence $\varphi$:

$$M' \models \exists s \exists t \exists u \forall v \forall w \forall x \forall y \; \psi(s, t, u, v, w, x, y)$$

Thus, $M'$ is a model of $\varphi$ with a universe of size $|U'| \le 3$. This guarantees that there exists at least one model of $\varphi$ with a universe of size less than or equal to $3$.