GATE Computer Science (CS) 2019 Solved Papers

Question : 45 of 65

Marks: +1, -0

Consider the first order predicate formula

ϕ :

∀ x[(∀ z \;\; z ∣ x ⇒((z=x) ∨(z=1))) ⇒ ∃ w(w>x) ∧(∀ z

z ∣ w ⇒((w=z) ∨(z=1)))]

Here 'a

∣ {b}^{'}

denotes that 'a divides

{b}^{'}

, where

{a}

and

{b}

are integers. Consider the following sets:
S1.

\{1,2,3, . . ., 100\}

S2. Set of all positive integers
S3. Set of all integers
Which of the above sets satisfy

ϕ

Solution:

∀ x[∀ z ⊗ x ⇒((z=x) ∨(z=1)) ⇒ ∃ w(w

>x) ∧(∀ z z ⊗ w ⇒((w=z) ∨(z=1)))]

The predicate

φ

simply says that if

z

is a prime number in the set then there exists another prime number is the set which is larger.
Clearly

φ

is true in

{S}_{2}

and

{S}_{3}

since in set of all integers as well as all positive integers, there is a prime number greater than any given prime number.
However, in

{S}_{1}:\{1,2,3, . . . . . . 100\} φ

is false since for prime number

97 ∈ {S}_{1}

there exists no prime number in the set which is greater.
So correct answer is C

Go to Question:

Prev Question

Next Question