The GATE Grind

GATE 2018 CS – Question 38

Engineering Mathematics · Discrete Mathematics: Propositional and First Order Logic · 2 marks · Multiple choice

Consider 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(s,t,u,v,w,x,y)$ is a quantifier-free first-order logic formula using only predicate symbols, and possibly equality, but no function symbols. Suppose $\varphi$ has a model with a universe containing 7 elements.

Which one of the following statements is necessarily true?

  1. There exists at least one model of $\varphi$ with universe of size less than or equal to 3.
  2. There exists no model of $\varphi$ with universe of size less than or equal to 3.
  3. There exists no model of $\varphi$ with universe of size greater than 7.
  4. Every model of $\varphi$ has a universe of size equal to 7.

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) There exists at least one model of $\varphi$ with universe of size less than or equal to 3.

Explanation

In a 7-element model, pick witnesses $s,t,u$ and restrict the universe to those (at most 3) elements. Since the remaining quantifiers are all universal and there are no function symbols, the substructure is still a model. So a model of size at most 3 exists.