GATE CSE 2019 | Question: 35

Question

Consider the first order predicate formula $\varphi$:

$\forall x [ ( \forall z \: z | x \Rightarrow (( z=x) \vee (z=1))) \rightarrow \exists w ( w > x) \wedge (\forall z \: z | w \Rightarrow ((w=z) \vee (z=1)))]$

Here $a \mid b$ denotes that  $ ’a \text { divides } b’ $ , where  $a$ and $b$ are integers. Consider the following sets:

• $S_1: \{1, 2, 3, \dots , 100\}$
• $S_2:$ Set of all positive integers
• $S_3:$ Set of all integers

Which of the above sets satisfy $\varphi$?

• A. $S_1$ and $S_2$
• B. $S_1$ and $S_3$
• C. $S_2$ and $S_3$
• D. $S_1, S_2$ and $S_3$

Comments

U can eliminate option using Euclid's Theorem : the number of primes is infinite. But this is not actual interpretation of give predicate formuale. For actual interpretation u can see @Deepak Poonia sir answer ..And for s3 consider x =-1 and check u will get T-->F 

---

took some time to realise its not as hard as it looks

---

This Might be Helpful
https://youtu.be/EzcwG1ztcEg?t=499

Answer 1

Answer : Only S2 satisfies given formula $\psi.$ Hence, None of the options in correct. 

Wait, I know you might not agree with me, but read the whole answer first.

---

In all the other answers to this question, the interpretation that is given is "for every prime number(x) there exist another prime number(y) where x<y."

This interpretation is WRONG. 

Why is this interpretation wrong ?

---

Divisibility Definition :  If a and b are integers, a divides b if there is an integer c such that ac = b.

The notation a | b means that a divides b.

Hence, $5$ is divisible by $1,5,-1,-5.$ $1$ is divisible by $1,-1.$ 1 divides everything. So does −1.

General definition of Prime :  "An integer n > 1 is prime if its only positive divisors are 1 and itself. 

The first few primes are  2, 3, 5, 7, 11, 13, 17, 19, 23, 29, . . . .

An integer n > 1 is composite if it isn’t prime."

http://sites.millersville.edu/bikenaga/number-theory/divisibility/divisibility.pdf

https://primes.utm.edu/glossary/page.php?sort=Divides

---

Now, Take the following set as domain for the given formula $\psi$ : Set of All integers.

For Set of ALL integers, the given formula $\psi$ DOES NOT satisfy. Because for element $-1$ in the domain, $\psi$  will become false. See, for $x=-1$, first part will become true i.e. for $x =-1,$ (∀z  z∣x ⇒ ((z=x)∨(z=1)))   will become true because only $1,-1$ divides $-1$. But for $x=-1,$ 2nd part will become false. i.e. For $x=-1,$ There does not exist any number $w > -1$ in the domain such that that $w$ is divisible by only $w,1$ because every number is also divisible by -1, $-w$. So, for $x = -1,$ $\psi$ becomes false. Hence, $\psi$ is NOT satisfied by the set "Set of All integers."

Hence, Answer should be Only S2. But none of the options match (Doesn't mean that correct answer will change because options do not match..)

---

Correct interpretation :

Given predicate formula says "For every number $x$ in the domain, if $x$ is such that $x$ is divisible by only $1,x$ among all the elements in  the whole domain , then there exists some number $w > x$  in the domain such that $w$ is divisible by only $1,w$ among all the elements in  the whole domain.

Clearly, S2 satisfies $\psi.$ Neither $S1,S3$ satisfies $\psi.$

---

This comment might be helpful as well :

https://gateoverflow.in/302813/gate-cse-2019-question-35?show=405093#c405093 

Comments

@Deepak Poonia Sir, Correct me if I'm Wrong but i think there is some problem with the scope of w 

How can we say like there exists some number w >x  in the domain such that w is divisible by only 1,w among all the elements in  the whole domain.

As the scope of w ends after ∃w(w>x) 

I'm Really not able to understand what do we do with this w in the (∀z  z∣w ⇒ ((w=z) ∨ (z=1)) )

 

---

+1  @Divon_John 

I feel the same. One pair of bracket is clearly missing if we wanted the $\exists \mathrm{w\; over\; entire\; (}$(w>x)∧(∀zz∣w⇒((w=z)∨(z=1))))

---

What you said is correct, however I think S3 is still satisfiable, because it is true by default. 

$\forall z (z \mid x \implies ((z = x) \lor (z = 1)))$ is  F
$\exists w ((w > x) \land (\forall z (z \mid w \implies ((w = z) \lor (z = 1)))))$ is F too

F → F = T 

Therefore$,\phi \; =\; T$for S3, by default, so still satisfiable, I think

Answer 2

$\forall x[( \forall z\ z|x\Rightarrow((z=x) \lor (z=1)))\Rightarrow \exists w\ (w>x) \land (\forall z\ z|w\Rightarrow((w=z) \vee (z=1)))]$

Lets divide above statement into three parts:
1. $(\forall z\ z|x\Rightarrow((z=x) \lor (z=1)))$
2. $\exists w\ (w>x)$
3. $(\forall z\ z|w\Rightarrow((w=z) \lor (z=1))$

$\forall x[1\Rightarrow2\Rightarrow3]$

Meaning of each part:
1. If $x$ is PRIME this statement is TRUE
2. If there there exist a $w$ which is greater than $x$ this statement is TRUE
3. If $w$ is prime (Keep in mind $z$ is local here) this statement is TRUE

That means for every $x$ there exist a $w$ which is greater than $x$ and it is prime.

• $S_1$ : FALSE. If $x=97$ then $101$ is not in the $S_1$
• $S_2$ : TRUE
• $S_3$ : TRUE. Negative cant be PRIME so statement $1$ is FALSE. Apply logic of implication, if $p$ is false in $p \Rightarrow q$, statement is TRUE.

Comments

Sir ,

A small doubt, it asks which of the following sets satisfy phi, and not , for which of the following sets it is valid.

---

what is the difference between them @Gaurav Parashar 1

---

@Digvijay Pandey sir  @Arjun sir I have one small doubt for statement like  (∀x  P(x) ⇒ Q(x) ) how should I interpret it wether we assume scope of  ∀x only to P(x) or also to Q(X). I get confused I have read somwehere quantifiers are having highest priority then all other logical connectives.

---

@Digvijay Pandey 

That means for every x there exist a w which is greater than x and it is prime.

No, this is not the correct interpretation for the given predicate formula. 

This interpretation will become false for the following set : $Set \,\,of\,\, all\,\, even\,\,  \,\, numbers \,\, greater \,\, than \,\, 2 $ i.e. $ S = \{ 4,6,8,...... \}$ 

For set $S$ above, the interpretation "for every $x$ there exist a $w$ which is greater than $x$ and it($w$) is prime" will return false.  But for this set $S$, given predicate formula $\psi$ will be True.

---

Correct interpretation :

Given predicate formula says "For every number $x$ in the domain, if $x$ is such that $x$ is divisible by only $1,x$ among all the elements in  the whole domain , then there exists some number $w > x$  in the domain such that $w$ is divisible by only $1,w$ among all the elements in  the whole domain.

---

In all the other answers to this question, the interpretation that is given is "for every prime number(x) there exist another prime number(y) where x<y."

This interpretation is WRONG. 

Why is this interpretation wrong ?

---

Divisibility Definition :  If a and b are integers, a divides b if there is an integer c such that ac = b.

Hence, $5$ is divisible by $1,5,-1,-5.$ $1$ is divisible by $1,-1.$ 1 divides everything. So does −1.

Standard(General) definition of Prime :  "An integer n > 1 is prime if its only positive divisors are 1 and itself. 

The first few primes are  2, 3, 5, 7, 11, 13, 17, 19, 23, 29, . . . .

An integer n > 1 is composite if it isn’t prime."

http://sites.millersville.edu/bikenaga/number-theory/divisibility/divisibility.pdf

https://primes.utm.edu/glossary/page.php?sort=Divides

---

Now, Take the following set as domain for the given formula $\psi$ : Set of All integers.

For Set of ALL integers, the given formula $\psi$ DOES NOT satisfy. Because for element $-1$ in the domain, $\psi$  will become false. See, for $x=-1$, first part will become true i.e. for $x =-1,$ (∀z  z∣x ⇒ ((z=x)∨(z=1)))   will become true because only $1,-1$ divides $-1$. But for $x=-1,$ 2nd part will become false. i.e. For $x=-1,$ There does not exist any number $w > -1$ in the domain such that that $w$ is divisible by only $w,1$ because every number is also divisible by -1. So, for $x = -1,$ $\psi$ becomes false. Hence, $\psi$ is NOT satisfied by the set "Set of All integers."

Hence, Answer should be Only S2. But none of the options match (Doesn't mean that correct answer will change because options do not match..)

---

Moreover, in the answer(above), you have divided the given formula in three parts. But it is not so. 2nd and 3rd part are not individual but it makes one part as a whole. $\exists w$ in the 2nd part is applied on whole remaining formula i.e. the scope of $\exists w$ is the whole remaining formula (to the right). 

  So, the given formula is basically $\forall x [1 \rightarrow 2]$ 

where $2$ is : $ \exists w ( w > x) \wedge (\forall z \: z \mid w \Rightarrow ((w=z) \vee (z=1))) $

Here $1$ says "$x$ is a divisible by only 1,$x$ in the whole doamin" 

$2$ says "There exists a $w > x$ which is also divisible by only 1,$w$ in the whole domain "

So, whole formula interprets as "For every number $x$ in the domain, if $x$ is divisible by only $1,x$ among all the elements in  the whole domain , then there exists some number $w > x$  in the domain such that $w$ is divisible by only $1,w$ among all the elements in  the whole domain.

---

@Akanksha Agrawal

Whatever you have read, is not wrong. But whenever an author writes a book, he describes some conventions that he'll be using throughout the book and so all the examples and questions in that particular book should be interpreted as per those conventions. So, what you said is a convention followed by Keneth rosen, in order to use less number of parentheses or brackets to make the expression look nice and not too much crowded. 

But different authors may opt for different conventions. Here in the question, I think they have followed the convention that the scope of a quantifier is as long as you can take, until a closing parentheses occurs for that quantifier. (this convention was used in one of the courses I took in IISc.. Professor in the beginning described that this convention he'll be following).

Like in the part $1,$ $"( \forall "$ means that now until you find a closing parentheses to this opening parentheses, it will be scope of $\forall z$ quantifier. Similarly, For $\exists w$ , there is no opening parentheses for $\exists w$ because they intend to make its scope the whole remaining expression, so they did not need to put opening parentheses for $\exists w.$ 

Ideally, in GATE exam, they should give the expression in proper parentheses. 

Most of the times, you will find GATE questions to be properly framed. 

Now, How do we know that the quantifiers in this question has the scope as described above and not according to the convention followed by Kenneth rosen ? 

That's because Assume that you follow Kenneth rosen's conventions then $\exists w$ will have scope only til $(w > x) $ i.e. $\exists w (w > x)$ is one whole part and $\exists w$ won't have any scope any further. But then what is $w$ in the remaining part i.e. $ (\forall z \: z \mid w \Rightarrow ((w=z) \vee (z=1)))  $ ??

Here, in the remaining part $w$ will be a free variable and hence, we CAN NOT interpret the given formula $\psi$ until/unless we are provided with the interpretation of $w.$ Similarly for $\forall z$ in the part $1$ and $forall z $ in the part 2. 

---

I'd again say that in GATE most questions are framed unambiguously and this question should have been framed in a better way by providing proper parentheses....But one can "understand the convention" followed by the question setter by looking at the formula. So, Technically there is no ambiguity But still it should have been framed in better way.

Refer my answer here for few more details : 

https://gateoverflow.in/302813/gate2019-35?show=328427#a328427

---

thank you sir, nice explaination

---

@techbd123 @Satbir @chirudeepnamini @ankitgupta.1729

Help me with this question, please.

My question is why it has to be prime?

What's wrong with $\mathbf{\dfrac{4}{4}}$

---

@`JEET

A number is a prime iff it is divisible only by itself and 1(and not any other number)

 for example 5 is a prime because it is divisible by only 1,5.

But 4 is not because it is divisible by 1,2,4.(it has a divisor other than 1 and 4)

The first statement is given as "for all z,z divides x implies either z is equal to x or z is equal to 1."

"z divides x" is equivalent to "x is divisible by z".

so rewrite this as "for all z,x is divisible by z implies either z is equal to x or z is equal to 1."​​​​​​​​​​​​​​

which is clearly definition of prime ,

let me know if you have any doubt..

Edit:

The proper definition of prime numbers:

An integer n > 1 is prime if its only positive divisors are 1 and itself

---

Yes, that was the standard definition of prime.

Wasn't coming to my mind.

Thanks.

---

A number is a prime iff it is divisible only by itself and 1(and not any other number)

What do you mean by "number" here?.. An integer or natural number or real number or positive integer..?

for example 5 is a prime because it is divisible by only 1,5.

5 is also divisible by $-1,-5.$ Hence, according to your definition of prime number above, $5$ is Not a prime number.

---

Divisibility Definition :  If a and b are integers, a divides b if there is an integer c such that ac = b.

Hence, $5$ is divisible by $1,5,-1,-5.$ $1$ is divisible by $1,-1.$ 1 divides everything. So does −1.

General definition of Prime :  "An integer n > 1 is prime if its only positive divisors are 1 and itself.

An integer n > 1 is composite if it isn’t prime."

http://sites.millersville.edu/bikenaga/number-theory/divisibility/divisibility.pdf

---

For this question, Only S2 satisfies the given first order logic formula $\psi.$

Refer here my comment :

https://gateoverflow.in/302813/gate2019-35?show=327668#c327668

---

@chirudeepnamini
You described correctly. 👍

---

@Deepakk Poonia (Dee)

I don't think there is any "standard" definition for prime numbers. We commonly use prime numbers for positive integers.

Definitions depend on context. In the answer, it is written that "negative can't be prime" but  A negative integer can also be a prime in the context of ring theory of abstract algebra. Here, definition of prime numbers is different. For example, considering the ring of integers $\mathbb{Z}$, "$-5$" is a prime number because its divisiors are $+5,-5,+1,-1$ where  $+1,-1$ are units of ring.

---

I meant "General" definition that we mostly use in mathematics and in number theory. I had written "General" in the bracket.. I have removed the term "standard" .

But it doesn't matter. What I wanted to point out is that the given formula is NOT satisfied by the S3 set which all the other answers and even the final GATE answer key are saying otherwise.

---

@Deepakk Poonia (Dee) sir

I also checked it above formula is not satisfying for -1.I didn't noticed it even though any one didn't noticed it till now.

Thank you sir.

---

Had your basics been more strong,  it would have been good, but anyhow

Here is an excerpt from IIT ROPAR.

 

 

$\forall [f \Rightarrow g ] \Rightarrow ( \forall f\Rightarrow \forall g)$

---

that’s a great explanation. but just a doubt, is it correct to force our knowledge on the given propositional statement. it is nowhere said that the give sentence(or propositional statement) is also the definition of prime numbers or for negative x , w should also be divisible by -1 (since it is not so you said that for set S3 the given proposition is not valid) . whether or not x is negative, both the properties(z=x or z=1) is true if x is of such nature, and same goes for w if w>x. Pls verify what i have said.

---

for stmt. 3, -1 is true and can come in 1st part bcoz divided by only itself and 1 but there is no no. exists in 2nd part, means 2nd part is false. therefore stmt. 3 is false. (bcoz every greater no. will divided by -1 also apart from itself and 1)

---

@Deepak Poonia sir, is it not the case that, prime numbers are only positive and not defined for negative numbers. therefore false-> anything makes stmt.3 also true. or, is prime numbers defined for negative numbers also? or it's not strictly the case of prime numbers rather only a case of specific divisibility condition?

---

@mayanksinghchandel In the question it is not given that it is prime or not, they defined prime number with only divisiblity rule, in that case -1 is the only prime number possible if we take statement 3 domain, in all other prime numbers -1 will be a factor so it would be true. so only statement 2 is correct, what Deepak sir explained was correct.

Answer 3

It means, for every prime number$(x)$ there exist another prime number$(y)$ where $x < y$.

Therefore S1 should be false.

S2 and S3 are true !

Comments

Thanks for the explanation sir

---

Why is this answer marked wrong?

---

Refer best answer of this question.

This answer assumed only prime numbers grater than 1. However, domain accomadate negative numbers too.

Answer 4

$\forall $ X from the set,
IF    {$\forall $ Z,
           IF Z divides X
            THEN either Z=X or Z=1} $\leftarrow$ X is a prime num
THEN   {$\exists $ W : W > X and
               $\forall$Z,
                  IF Z divides W
                  THEN either Z=W or Z=1}$\leftarrow$ W is a prime num

OR,
$\forall$ X, IF X is a prime num
THEN $\exists$ another prime number W >X

The above statement is not true for bounded sets like in S1 : there is no prime num greater than 97 under 100, so if we choose X=97 then we can't chose any W.
Only S2 and S3.
Ans C)

Comments

The above statement is not true for bounded sets like in S1

The given formula is certainly not valid for the set $S_1$ But It could be valid/true for Bounded sets. 

For example, Any subset of positive integers which doesn't have a prime number in the set, will satisfy the given formula.

Set $S = \{ 4,6 \}$ will satisfy the given formula. And similarly you can make many finite sets which will satisfy the given formula. 

Answer 5

S1 is a subset of S2 & S3.

If S1 doesn't satisfy the given relation, S2 & S3 would also not satisfy.

 

If we closely observe the options, we can eliminate 2 options (B & C).

[Hint : S1 is subset of S2, which in turn is subset of S3].

Answer should be either A or D.

I took risk (as the probability of getting it right was 0.5) & marked it as A.

Answer 6

Consider $(\forall z\ z|x \rightarrow((z=x) \vee (z=1)))=P$ , and
$\exists w\ (w>x)\wedge (\forall z\ z|w \rightarrow ((w=z)\vee (z=1))) =Q$.

The question becomes $\forall x[P\rightarrow Q]$.

Consider $x=3,z=5 \ and\ w=10$. Consider Q first:
w > z = TRUE
(5|10 = TRUE $\rightarrow$ (5=10)$\vee$(z=1) = FALSE), and we know that $TRUE\rightarrow FALSE=FALSE$ therefore Q becomes FALSE.

Consider P next:
(5|3 = FALSE $\rightarrow$ (5=3)$\vee$(5=1) = FALSE), and $FALSE\rightarrow FALSE = TRUE$ therefore P becomes TRUE.

$\varphi=[TRUE\rightarrow FALSE]=FALSE$ So S1 will be false.
Looking at options, Option C automatically becomes right answer.