retagged by
19,834 views
66 votes
66 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$?

  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$
retagged by

10 Answers

Best answer
64 votes
64 votes

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 

edited by
71 votes
71 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.
edited by
22 votes
22 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 !
edited by
11 votes
11 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)
edited by
Answer:

Related questions

26 votes
26 votes
4 answers
2
Arjun asked Feb 7, 2019
19,280 views
Consider the following matrix:$R = \begin{bmatrix} 1 & 2 & 4 & 8 \\ 1 & 3 & 9 & 27 \\ 1 & 4 & 16 & 64 \\ 1 & 5 & 25 & 125 \end{bmatrix}$The absolute value of the product ...
33 votes
33 votes
4 answers
3
Arjun asked Feb 7, 2019
16,081 views
Suppose $Y$ is distributed uniformly in the open interval $(1,6)$. The probability that the polynomial $3x^2 +6xY+3Y+6$ has only real roots is (rounded off to $1$ decimal...