# Which statements is necessarily true for Models in first-order logic sentence given?

This questin is asked in GATE EXAM.

Consider 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?

A) There exists at least one model of φ with universe of size less than or equal to 3

B) There exists no model of φ with universe of size less than or equal to 3

C) There exists no model of φ with universe size of greater than 7

D)Every model of φ has a universe of size equal to 7

=====================================================

My take- For empty set universal quantifiers are always true while existential quantifier are always false, hence, there exist at least one model with 3 elements, as it is given equality is also possible hence model is also possible for less than three elements, thus OPTION A.

Am I correct?

Also, from where can I study such concepts!

The answer is indeed A, but your reasoning is a bit off: specifically, quantification over the emptyset is irrelevant here (although I think your intuition is coming from the right place). Also, you haven't used the assumption that the language has no function symbols, which is crucial.

• Can you construct a counterexample if we allow function symbols? HINT: What does the sentence "$$\forall x(x\not=f(x)\wedge x\not=f(f(x)))$$" imply about the size of the structure? Do you see how to generalize this?

Rather, you can argue as follows:

• Let $$M\models\varphi$$. (It doesn't matter how big a model we pick, here.)

• Since $$M\models\varphi$$ we get witnesses $$a,b,c\in M$$ - possibly not distinct - such that $$M\models\forall v,w,x,y[\psi(a,b,c,v,w,x,y)]$$.

• Because the language of $$M$$ has no function symbols, $$N=\{a,b,c\}$$ forms a substructure of $$M$$. Now, do you see why we have $$N\models\forall v,w,x,y[\psi(a,b,c,v,w,x,y)]$$ (and hence $$N\models\varphi$$) as well?

• HINT: remember that $$\psi$$ has no quantifiers, and by cutting down to a smaller structure we only restrict the possible values for the universal quantifiers - there's a general fact here about how sentences of the form [universal quantifiers][quantifier-free part] behave with respect to taking substructures ...
• thank you, also can you please refer me any source/link to strengthen my concept, I've jut started with this subject. – Geeklovenerds Oct 4 '18 at 5:42