GATE 2018 CS – Question 38
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?
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.
More Discrete Mathematics: Propositional and First Order Logic questions
- GATE 2015 CS (CS1) Q19
- GATE 2016 CS (CS1) Q11
- GATE 2017 CS (CS1) Q11
- GATE 2017 CS (CS1) Q12
- GATE 2017 CS (CS1) Q39
- GATE 2014 CS (CS1) Q11
All Discrete Mathematics: Propositional and First Order Logic questions →