Consider the first order predicate formula 𝜑 ∀𝑥 [(∀𝑧 𝑧|𝑥 ⇒ ((𝑧 = 𝑥) ∨ (𝑧 = 1))) ⇒

August 2, 2023

Q. Consider the first order predicate formula 𝜑: ∀𝑥 [(∀𝑧 𝑧\|𝑥 ⇒ ((𝑧 = 𝑥) ∨ (𝑧 = 1))) ⇒ ∃𝑤 (𝑤 > 𝑥) 𝖠 (∀𝑧 𝑧\|𝑤 ⇒ ((𝑤 = 𝑧) ∨ (𝑧 = 1)))] Here ‘𝑎\|𝑏’ denotes that ‘𝑎 divides 𝑏’, where 𝑎 and 𝑏 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 𝜑?
(A) S1 and S2	(B) S1 and S3	(C) S2 and S3	(D) S1, S2 and S3

Ans: (C) S2 and S3

Solution: