Project ForgeConsider the first-order logic sentence φ ≡ ∃s∃t∃u ∀v∀w∀x∀y ψ(s,t,u,v,w,x,y), where ψ(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 φ has a model with a universe containing 7 elements. Which one of the following statements is necessarily true?
- There exists at least one model of φ with universe of size less than or equal to 3
- BThere exists no model of φ with universe of size less than or equal to 3
- CThere exists no model of φ with universe of size greater than 7
- DEvery model of φ has a universe of size equal to 7
Explanation
For an ∃*∀* prenex sentence with no function symbols (the Bernays–Schönfinkel class), if it's satisfiable at all, it has a model whose universe size is at most the number of existentially quantified variables — the existential witnesses can always be reused to build a small model, since the universal part must hold for every element regardless of how many there are. Here there are 3 existential variables (s,t,u), so a model of size ≤3 must exist.
Source: GATE CS 2018 (2018)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.