retagged by
22,169 views
77 votes
77 votes

Consider the first-order logic sentence

$$\varphi \equiv \exists \: s \: \exists \: t \: \exists \: u \: \forall \: v \: \forall \: w \forall \: 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 $\varphi$ has a model with a universe containing $7$ elements.

Which one of the following statements is necessarily true?

  1. There exists at least one model of $\varphi$ with universe of size less than or equal to $3$
  2. There exists no model of $\varphi$ with universe of size less than or equal to $3$
  3. There exists no model of $\varphi$ with universe size of greater than $7$
  4. Every model of $\varphi$ has a universe of size equal to $7$
retagged by

3 Answers

Best answer
169 votes
169 votes

Answer - A.

Quick logic review - 

$\alpha : \forall x \exists y \hspace{.5em}y<x$

Is $\alpha$ true for domain of all integers ?, Yes it is true. You pick any number $x$, I can always give you $y$ that is less than your number $x$. 

Is $\alpha$ true for domain of  Non Negative integers $\{0, 1,2,3,\dots\}$ ? No,  it is not true. (You pick any number $x$) If you pick $0$ then I can not give you $y$ which is less than $0$.

Definition of $\text{Model }$ - Domain for which my sentence is true. For above sentence $\alpha$, all integers is model and there can be many other models, like -  real numbers.

(Definition of $\text{Co Model }$- Domain for which my sentence is False.)


Given that  Predicate $\Phi \equiv \exists s \exists t \exists u \forall v \forall w \forall x \forall y   \Psi (s,t,u,v,w,x,y)$ has a model with universe containing $7$ elements. I.e.  there is a domain with 7 elements which satisfies my  $\Phi$ .

Now let $\Phi \equiv \exists s \exists t \exists u \forall v \forall w \forall x \forall y  \hspace{.5em} s+t+u+v+w+x+y \gt 200$. Can you suggest me a set (domain) that is model for $\Phi$ ?. (i.e. the domain for which you can satisfy $\Phi$ ).

 $\{10,20,30,40,50,60,100\}$, now if I choose $s=50$, $t=60$ and $u=100$ $^{[1]}$ and let anyone choose values of $v, w ,x \text{ and } y$ then $\Phi$ is always satisfiable for any values (or write like this - for all values) of $v, w,x \text{ and } y$ . The key point is you have to choose values of $ s ,t \text{ and } u$ carefully and once you fix these values then it should work for all remaining universal quantifiers values.

Actually I have problem with first element of set "$10$". Can I remove it and the resultant set will still work as model ?  $\{20,30,40,50,60,100\}$, Of course this is model for $\Phi$ (Why ? - take $s=50, t=60$ and $u=100$ and let any other variable value be anything).

Similarly, $\{50,60,100\}$ is also model for $\Phi$. 

Idea is once you have your $\bf{s, t \text{ and } u}$ in set then that set is model (because remaining quantifiers can take any value).

Even the singleton set $\{100\}$ is also model for $\Phi$.

Now there is always one model of universe size $3$, and depending on your predicate you can have model of less than size $3$ too (like above singleton set).

$^1$ $s=t=u=100$ also works.


Now, Lets generalize this for better understanding-

let $\Phi$ has following model of size $7-  \{e_1,e_2,e_3,e_4,e_5,e_6,e_7\}$, and let $s=e_2, t=e_5, u=e_1$ is the only setting which works for any (for all) values of $v,w,x \text{ and }y$, then Can we reduce model size ?- Yes, we can have a model of size $3\;\{e_1,e_2,e_5\}$. Can we reduce size further ?- We can not ( Because $s=e_2, t=e_5, u=e_1$ is the only setting which works for any value of $v,w,x,y)$. But if $s = t$ or $t = u,$ we can even have a model of size less than $3.$

edited by
71 votes
71 votes

Answer: A 
A formula is satisfiable for some interpretation then such interpretation is called a model.

Now it is given that for universe of size 7 there is a model. That means there is an interpretation where this formula is true.

8 votes
8 votes

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.
Hence OPTION A
 

reshown by
Answer:

Related questions