The GATE Grind

GATE 2019 CS – Question 45

Engineering Mathematics · Discrete Mathematics: Propositional and First Order Logic · 2 marks · Multiple choice

Consider the first order predicate formula $\varphi$:

$$\forall x\left[(\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)))\right]$$

Here '$a|b$' denotes that '$a$ divides $b$', where $a$ and $b$ are integers. Consider the following sets:

S1. $\{1,2,3,\dots,100\}$

S2. Set of all positive integers

S3. Set of all integers

Which of the above sets satisfy $\varphi$?

  1. S1 and S2
  2. S1 and S3
  3. S2 and S3
  4. S1, S2 and S3

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) S2 and S3

Explanation

$\varphi$ says that for every prime $x$ (or 1) there is a larger prime $w$. This holds over the positive integers and over all integers because there are infinitely many primes, but it fails over $\{1,\dots,100\}$ for the prime 97.