Consider the first order predicate formula phi: forall x [ (forall z z|x => ((z = x) v (z = 1)) ) -> exists w (w > x) ^ (forall z z|w => ((w = z) v (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 phi? A. S1 and S2 B. S1 and S3 C. S2 and S3 D. S1, S2 and S3
GATE 2019 · Discrete Mathematics · First Order Logic · medium
Answer: Only S2 and S3 satisfy phi, so the answer is C.
Decode the divisor condition as 'prime': The antecedent forall z (z|x => z=x or z=1) is true exactly when x is prime (1 qualifies vacuously). The bracket inside exists w similarly says w is prime. So phi becomes: forall prime x, exists prime w with w > x.
Evaluate phi on each domain: S1 = {1,...,100}: the prime x = 97 has no larger prime w <= 100, so phi is FALSE. S2 = positive integers: by Euclid there are infinitely many primes, so for every prime x a larger prime w exists -> phi TRUE. S3 = all integers: the positive primes are still present and unbounded above, so phi TRUE.