in Mathematical Logic retagged by
22,331 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

21 Comments

Sir , on which concept this question was asked.In Keneth Rosen book their is no such type of question given and also their is no concept of MODEL in this book.Plzz tell me from which book I can study these type of concept?????

My email Id = [email protected]
2
2
This question is from the very basics of model and universe -- can be easily answered by those who studied those concepts but can only be wrongly answered by those who studied only by solving problems.
12
12

@Arjun sir, with due respect, this question is not very easy. and it's always the basics which makes the question difficult. In maths we study mostly by solving problems. and for someone out there like Manjul Bhargava, most of the math will be easy. but for most of the undergrad student, this problem was not so clear. Your comment implies that if someone could not answered this question in the exam, he didn't studied this topic at all but it's not true.

86
86
1
1
few things I want to confirm, if equality was not present then we could say that "there exists a model of size at least 3"?

can we say "There exists at least one model of φ with a universe of size less than or equal to 1"? For s=201 and rest, all can be anything?
1
1
I didnot understand ,please explain somewhat more  anyone how to approach
0
0

you are Awesome !

0
0
i think B will also be the answer ....
0
0
Great and easy to understand answer. Written in manner that even average student like me can understand very easily
0
0
Sachin Mittal Sir, from which book  u have studied this topic(concepts) or which teacher have told u this concept as this was new concept asked first time in 2018 from topic first order logic and what new concepts can gate ask on tihis topic in future????????
0
0
Can you explain the significance of "possibly equality, but no function symbols"? Also would anything have changed if $$\Psi$$ wasn't quantifier free .
0
0

If in the question it is asked  that we have $ \forall s \forall t \forall u \forall v \forall w \forall x \forall y $ s(t,u,v,w,x,y) then what would have been the answer @Sachin Mittal 1 ?

0
0
I think then it would be $D)$
0
0

@srestha suppose if I consider Singleton set = {100} ,then no matter what value of any variable the above predicate is true so model of size one  also existing  I think so or not?

0
0
There are 7 variable. If all 6 variables are 0, then why we declare all 7 variables, rather declare only 1 variable.
0
0
can any one help me why option "c" is not correct
2
2
@Winner @srestha , Answer would still be (A) consider Universe being a singleton set {200}, again equation Given By Sachin Would satisfy.
1
1
edited by
This is well explained. For studying these concepts like model so on and so forth, I would suggest to read any textbook on Artificial Intelligence rather than simply searching on Discrete Math books which I am doing so. Because when you read those books you would also realize the use of studying logic.

I am referring Artificial Intelligence A Modern Approach by Russell, Norvig
1
1

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