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

26 Comments

I marked B
2
2

how did you arrive at that option @Ashwin  ?

0
0
I think it should be B
4
4
answer B
0
0
In made easy's answer key,the answer is b..
0
0

@ Ashwin

why do u think B true?

Any valid reason

0
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
8
8
sir, can u suggest a book from which we can read these topics
0
0
This is a great question…...lots of logic concepts can be cleared from this….
0
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
0
Thats exactly what i hav thought also....
0
0
And that's exactly what will get you negative in GATE :) Most people struggle in GATE because of the bad material they follow.
13
13
1
1

 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
0
negation means $\sim$, there is not that sign in expression, na?
0
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
0
ok, I shall try to elaborate.
0
0
edited by

@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

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

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
0
First of all can you write an expression for B with negation?
0
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
0
No. B and C are talking about some property of the model and they require a different representation than the current given $\varphi$
0
0
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