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

- There exists at least one model of $\varphi$ with universe of size less than or equal to $3$
- There exists no model of $\varphi$ with universe of size less than or equal to $3$
- There exists no model of $\varphi$ with universe size of greater than $7$
- Every model of $\varphi$ has a universe of size equal to $7$

6

there is no negation sign in the sentence they given

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

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

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

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

there is no negation sign in the sentence they given

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

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

@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

@srestha You are not understanding what is asked in question. Please read the answer given by Sachin.

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

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$

104 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, 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.$

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]

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?

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

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 @Sachin Mittal 1 ?

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?

52 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. **

1

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