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

Dark Mode

15,383 views

47 votes

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

- $S_1$ and $S_2$
- $S_1$ and $S_3$
- $S_2$ and $S_3$
- $S_1, S_2$ and $S_3$

1

1

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

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

0

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

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

0

46 votes

Best answer

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.

2

edited
Oct 11, 2022
by Abhrajyoti00

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.

0

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.

0

60 votes

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

1

0

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.

0

20 votes

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 !

Therefore S1 should be false.

S2 and S3 are true !

9 votes

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

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)

edited
Dec 10, 2019
by Deepak Poonia

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.

3