in Mathematical Logic retagged by
22,281 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$
in Mathematical Logic retagged by
by
22.3k views

4 Comments

I havenot got, what u mean here.

Still in predicate logic it is impossible to write a -ve sentence without any negation.

right?
1
1
Can anyone explain in the question that what is meant by "possibly equality, but no function symbols", does it mean predicate symbols can be same?
3
3
In the Question it is clearly mentioned that ¢(s,t,u,v,w,x,y) is a logic formula that does not use any function symbol so in place of v,w,x,y we can't take empty set.
0
0

3 Answers

169 votes
169 votes
Best answer

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

4 Comments

Can someone please explain to me what would be the changes if this – 

using only predicate symbols, and possibly equality, but no function symbols

was not given?  

0
0

@Deepak Poonia sir there is a slight typing error

let anyone choose values of v,w,x and y then Φ is always satisfiable for any values (or write like this - for all values) of v,w,x and y.

Sir it will be w, instead of u.

2
2

@sandmuk754 I think, because the universe size for the model can also be >7 however, we need to carefully choose 3 compulsory elements (s, t, and u) from it that can serve as a model for the given predicate (meaning, satisfy the given predicate).

0
0
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.

4 Comments

Sir please explain how option c is false.
0
0

@manisha11 It's the worst if you know the concept. Studying such can get you negative marks in GATE. 

1
1

@Kiran Kumar Pasupule
=3 is possible no?
<3 agreed isn't possible.
Kindly help here

0
0
Nice 1 kiran sir.
0
0
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

1 comment

answer may be 'b'
0
0
Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true