Gate2019 cs Q45

0. Consider the first order predicate formula 𝜑:
∀𝑥 [(∀𝑧 𝑧|𝑥⇒((𝑧=𝑥)∨(𝑧=1)))⇒∃𝑤 (𝑤>𝑥)∧(∀𝑧 𝑧|𝑤⇒((𝑤=𝑧)∨(𝑧=1)))]
Here 'a|b' denotes that 'a divides b', where a and b are integers. Consider the following sets:
S₁ {1,2,3,…,100}
S₂ Set of all positive integers
S₃ Set of all integers
Which of the above sets satisfy 𝜑?

Answer
Comment
Array

Option : C
Explanation :
∀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₂ and S₃ 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, 2, 3, .....100} ϕ is false since for prime number 97 ∈ S₁ there exists no prime number in the set which is greater. So correct answer is C.

Forgot your password?

I agree with the Terms.