0
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

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 ...
$\endgroup$
  • $\begingroup$ thank you, also can you please refer me any source/link to strengthen my concept, I've jut started with this subject. $\endgroup$ – Geeklovenerds Oct 4 '18 at 5:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.