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

Prime numbers exists only for positive integers, because if we have included -ve numbers then -1 would have divided all number which violates the definition of prime numbers.

In above example let P=(∀zz∣x⇒((z=x)∨(z=1))  and Q =∃w(w>x)∧(∀zz∣w⇒((w=z)∨(z=1))) if P itself false fo -ve integers then no need to check for Q in above example for -ve integers P is itself false; So, P=false then P→ Q is always true.

So, from above explanation S3 must be valid option

S2 is is any way true since x and w are prime numbers and for positive integers prime number exists

S1 should be false. because for every prime number x there exist another prime number where x<y , so finite set option is wrong.

So answer → (C) S2 and S3 are true

---

So to check you have to check if for given Domain it is always true or not.

So you can broadly see this is of type (A→ B) → C  and for it to be true you should analyze what cases for A,B,C exists for which it can be true for example:

A           B          C

F          T/F        T

T            T          T

T            F         T/F

you should take each domain given and then check for A,B,C by cases as shown above if it is true then that domain is valid. I think you can check it in like 1 min or so, yeah done

---

visualization to understand what question asking

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

@Deepakk Poonia (Dee)

Beautifully analysed.

1--I just want to confirm one thing.. You are saying the predicate formula is wrong for x=-1 because every integer w greater than -1 is divisible by -1,1,w. But we want w to be divisible by only 1,w.

And hence the rhs of implication is false for -1.

This makes entire implication false.

Is my understanding correct??

2--And one more doubt. If the leftmost for all x is replaced by there exists x, then all options are correct right??

3--Also i feel that they should have given z=w instead of w=z. That would've made nore sense right??

---

@Deepakk Poonia (Dee)

i am getting a doubt that is my 2nd question meaningful?? i mean when i tried to translate it into a english sentence, i couldn't get a meaningful translation..

---

I have answered your second question in much detail manner..so why do you think it's not meaningful?

---

sorry i couldn't get proper english translation earlier.The translation i got now is

"There is a integer x in the domain such that if x is divisible by only 1 or itself,then there is a integer w in the domain greater than x which is divisible by only 1 or itself."

Also may i know how this is not satisfied for  "Non-empty Finite set of number where all the numbers  except 1(if in the domain) are pair-wise co-prime."

because for the domain {1,2,3,5,7,11} there is element x=3 and w=5 satisfying the predicate formula

---

@Deepakk Poonia (Dee) Great analysis sir...

---

Absolute GEM of an answer. What an explanation! Thank You @Deepak Poonia Sir. This shows even small concepts like divisibility are needed with proper understanding! 

---

@Arjun Sir, please put this answer in the GO PDF Version. There, the other answer of @Digvijay Pandey is provided.

---

@Abhrajyoti00  Answers to GO PDF are automatically added – all best answers and answers marked as useful will be included there. This answer selection happened just after the last version of GO PDF was made.

---

@Deepak Poonia Sir,

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

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 and -w also.

And for other integers we are not considering bcz first part will be false and false → everything = true.

Sir plz clear this doubt.

---

@samarpita Can you explain your doubt a bit more?

---

@Abhrajyoti00 

Sir has written “every number is also divisible by -1”. Why sir hasn’t written -w?

And we are not considering other integers w bcz for any integers except -1 and 1 will have four factors: 1,-1, w, -w. So,$(\forall z $ $z|x \Rightarrow ((z=x) V (z=1)))$ this becomes false and false => anything is true.

I just want to confirm all the above statements are correct or not.

---

Yes @samarpita your observation is correct. It should be “because every number is also divisible by $-1,-w$ “

Eg: If $x = -1$, then first part $(∀z \ z∣x ⇒ ((z=x)∨(z=1)))$ is true, and second part $\exists w\ (w>x) \land (\forall z\ z|w\Rightarrow((w=z) \lor (z=1))$ is false for $z = -1,-w$ as $(-1,-w)$ belong to set of integers. To note: Here $(w>x)$ so, $w \neq -1.$ Taking $w=3$, $z$ can take the values $= {-3,-1,1,3}$. So for $(-1,-3)$, $z$ does divide $3$ but it does not satisfy $\forall$ condition of being $1 \ or \ 3$.

So, statement $S3$ is wrong. 

Also, your other statement is also correct.  

And we are not considering other integers w bcz for any integers except -1 and 1 will have four factors: 1,-1, w, -w. So, $\forall z|x⇒((z=x)V(z=1)))$ this becomes false and false => anything is true.

So, for other integers, we don't even have to check the other conditions on right.

@Deepak Poonia Sir it needs edit.

---

Adding as another clear comment for better explanation:-

To note (in the 2^nd and 3^rd conditions): 

Here $(w>x)$ so, $w \neq -1.$

Taking $w=3$ which is ofcourse $>x \ (-1)$,

$z$ can take the values $= {-3,-1,1,3}$ as all of them divide $3$ and belong to set of integers.

So for $(-1,-3)$, $z$ does divide $3$ but it does not satisfy $\forall$ condition of being $1 \ or \ 3$.

So, statement $S3$ is wrong. 

---

 prime number (or a prime) is a natural number  greater than 1 that is not a product of two smaller natural numbers 

https://en.wikipedia.org/wiki/Prime_number

 

so sir why are you considering x = -1 as in antecedent it is given that if x is a prime number then in consequent it is given that there exist a w > x 

 

if at all if x = -1 is not even a prime number why you jump to consequent part

 

correct me if I am wrong because mistakes are allowed today not in Exam

---

@THE_GODXX

The antecedent is NOT saying that $x$ is a prime number. 

The antecedent is: $ ( \forall z \: z | x \Rightarrow (( z=x) \vee (z=1)))$

Let’s call this antecedent as $A(x).$

Now, consider $S_3$ as the domain.

Does $x = 2$ satisfy $A(x)$ ?

Think about it.

The answer is, No. Because, consider $z= -1;$ So, we have $z | x$ But $z \neq 1$ and $z \neq x.$

Now, Read my answer again, without having preconceived opinion like “prime number” etc.. Because the word “prime" is not mentioned in the question anywhere. So, solve the questions by proper reasoning. 

---

You considered set of integers domain and saying that there does not exist any integer greater than -1. What about the positive integers. So i say s2 and s3 satisfies the given condition.

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

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

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

@Arjun sir, please confirm this answer because as per ravindra babu ravula sir’s answer key the answer is S1&S3

---

If you are following him you can very well not come to GO. Please follow reasoning.

---

Thanks for the explanation sir

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.