GATE 2018 CS Q.28: solution and answer

Official answer: ASource: Official answer key, GATE 2018 CS (IIT Guwahati)

1. Let $M$ be the given model with 7 elements. Since $M\models \exists s\exists t\exists u\forall v\forall w\forall x\forall y\psi$, there are witnesses $a,b,c\in M$ (not necessarily distinct) such that $\forall v\forall w\forall x\forall y\psi (a,b,c,v,w,x,y)$ holds in $M$.

2. Let $U=\{a,b,c\}$. It is non-empty and has at most 3 elements.

3. There are no function symbols, so restricting every predicate (and equality) to $U$ gives a valid sub-structure $M^{\prime }$ with universe $U$. No function needs $U$ to be closed.

4. $\psi$ is quantifier-free, so for any $v,w,x,y\in U$ its truth value is the same in $M^{\prime }$ as in $M$. Every such $v,w,x,y$ is also an element of $M$, where $\psi (a,b,c,v,w,x,y)$ holds. Hence $M^{\prime }\models \forall v\forall w\forall x\forall y\psi (a,b,c,v,w,x,y)$.

5. Taking $s,t,u=a,b,c$ in $M^{\prime }$ gives $M^{\prime }\models \phi$. So $\phi$ has a model of size at most 3, which is option (A).

6. The other options are not forced. Take $\psi$ to be $s=s$. Then $\phi$ is true in every non-empty universe, so it has models of size 1 (against B), of size 8 (against C) and of size other than 7 (against D).