Consider the first-order logic sentence phi = exists s exists t exists u forall v forall w exists 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 phi has a model with a universe containing 7 elements. Which one of the following statements is necessarily true? A. There exists at least one model of phi with universe of size less than or equal to 3 B. There exists no model of phi with universe of size less than or equal to 3 C. There exists no model of phi with universe size of greater than 7 D. Every model of phi has a universe of size equal to 7
GATE 2018 · Discrete Mathematics · First Order Logic · medium
Answer: Option A: there exists at least one model of phi with universe of size less than or equal to 3.
- Count the existential witnesses: The prefix is exists s exists t exists u forall v forall w exists x forall y. The first three (s, t, u) are unconditional witnesses; the inner exists x depends on v, w but its value may be chosen inside the already-fixed set. The forall variables (v, w, y) need no new elements.
- Build a model of size <= 3: Take the 7-element model and map every element onto the chosen s, t, u. Since psi has no function symbols, predicate truth can be preserved by identifying elements; the universally quantified v, w, y simply range over these <= 3 elements, and x is picked among them. This yields a model with universe size <= 3.