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

first-order-logiclogicpredicate-logic

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!

Best Answer

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 ...
Related Question