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

I don't think negative numbers(like -3, -5) can be considered as prime.
Hence only S2 should be correct.

but no such option.

thats why i left it blank, thinking that i will get marks due to wrong options

---

Respected Administrators,

Please make all three “implies” symbol same, in above question 

either represent all three by “->” or by  “=>”

---

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

 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.