GATE2018-28

11.8k views

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$

edited
2
I marked B
0

how did you arrive at that option @Ashwin  ?

4
I think it should be B
0
0
0

why do u think B true?

Any valid reason

6
So, B) and C) already false
For every model it is not true as three there exists sign before s,t and u. So, D) false
Only option A) is remaining
0
sir, can u suggest a book from which we can read these topics
0
This is a great question…...lots of logic concepts can be cleared from this….
0

@Arjun sir

Three is a website who say's B is the answer with following description please verify it.

φ=∃s∃t∃u∀v∀w∀x∀y ψ (s,t,u,v,w,x,y) "∃"there exists quantifier decides whether a sentence belong to the model or not.
i.e., ~∃ will make it not belong to the model. ①We have ‘7’ elements in the universe, So max. size of universe in a model= ‘7’
②There are three '∃' quantifiers, which makes that a model have atleast “3” elements. So, min. size of universe in model = ‘7’.
(A) is False because: ②
(B) is true
(C) is false because of ①
(D) is false, because these all models with size {3 to 7} not only ‘7’.

0
Thats exactly what i hav thought also....
5
And that's exactly what will get you negative in GATE :) Most people struggle in GATE because of the bad material they follow.
0

So, B) and C) already false
For every model it is not true as three there exists sign before s,t and u. So, D) false
Only option A) is remaining

@srestha Can you please explain this procrdure of eliminating the options. Not getting the 'no negation...So, B and C already false

0
negation means $\sim$, there is not that sign in expression, na?
0

Yes, but how you're using that to infer that this is not correct.

There exists no model of φ with universe of size less than or equal to 3

Can you please elaborate in a bit detail your thinking process. Your elimination process for the options.

0
ok, I shall try to elaborate.
0

@N

Can u write down an expression "There exists no model of φ with universe of size less than or equal to 3" without any negation sign??

Then plz write it down.

0

0

@Arjun Sir

yes, read it. But tell me one thing, is it really possible, writing an expression without negation for B) and C)??

I think it is not possible.

0
First of all can you write an expression for B with negation?
0

B)$$\varphi \equiv \exists \: s \: \exists \: t \: \exists \: u \: \forall \: v \: \forall \: w \forall \: x \: \forall \: y \:\sim\psi(s, t, u, v, w, x, y)$$

C)$$\varphi \equiv \exists \: s \: \exists \: t \: \exists \: u \: \forall \: v \: \forall \: w \forall \: x \: \forall \: y\forall \: z \:\sim \psi(s, t, u, v, w, x, y)$$

These will be expression for B) and C)

right?

0
No. B and C are talking about some property of the model and they require a different representation than the current given $\varphi$
1
I havenot got, what u mean here.

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

right?
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?

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, u ,x \text{ and } y$ then $\Phi$ is always satisfiable for any values (or write like this - for all values) of $v, u ,x \text{ and } y$ . The key point is you have to choose values of $s ,t \text{ and } u$ carefully and once u fixed 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
1
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]
9
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.
58

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

0
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?
0
I didnot understand ,please explain somewhat more  anyone how to approach
0

you are Awesome !

0
i think B will also be the answer ....
0
Great and easy to understand answer. Written in manner that even average student like me can understand very easily
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
Can you explain the significance of "possibly equality, but no function symbols"? Also would anything have changed if $$\Psi$$ wasn't quantifier free .
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

0
I think then it would be $D)$
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
There are 7 variable. If all 6 variables are 0, then why we declare all 7 variables, rather declare only 1 variable.
1
can any one help me why option "c" is not correct
0
@Winner @srestha , Answer would still be (A) consider Universe being a singleton set {200}, again equation Given By Sachin Would satisfy.

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.

0
Sir please explain how option c is false.
1

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

0

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

0
Nice 1 kiran sir.

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
0

Related questions

1
9.1k views
Which one of the following well-formed formulae in predicate calculus is NOT valid ? $(\forall _{x} p(x) \implies \forall _{x} q(x)) \implies (\exists _{x} \neg p(x) \vee \forall _{x} q(x))$ $(\exists x p(x) \vee \exists x q (x)) \implies \exists x (p(x) \vee q (x))$ ... $\forall x (p(x) \vee q(x)) \implies (\forall x p(x) \vee \forall x q(x))$
Which one of the following well-formed formulae is a tautology? $\forall x \, \exists y \, R(x,y) \, \leftrightarrow \, \exists y \, \forall x \, R(x, y)$ $( \forall x \, [\exists y \, R(x,y) \, \rightarrow \, S(x, y)]) \, \rightarrow \, \forall x \, \exists y \, S(x, y)$ ... $\forall x \, \forall y \, P(x,y) \, \rightarrow \, \forall x \, \forall y \, P(y, x)$
Let $P(x)$ and $Q(x)$ ...
Let $a(x, y), b(x, y,)$ and $c(x, y)$ be three statements with variables $x$ and $y$ chosen from some universe. Consider the following statement: $\qquad(\exists x)(\forall y)[(a(x, y) \wedge b(x, y)) \wedge \neg c(x, y)]$ ... $\neg (\forall x)(\exists y)[(a(x, y) \vee b(x, y)) \to c(x, y)]$