15,383 views

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

1. $S_1$ and $S_2$
2. $S_1$ and $S_3$
3. $S_2$ and $S_3$
4. $S_1, S_2$ and $S_3$

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

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

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/gate2019-35?show=328696#c328696

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.

edited

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 2nd and 3rd 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.

$\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.

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

reshown
If you are following him you can very well not come to GO. Please follow reasoning.
Thanks for the explanation sir
$\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)

1 comment

edited

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.