Question

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 φ?

Accepted Answer

The correct answer is (C) S2 and S3. The inner condition '∀z(z|x ⇒ (z=x ∨ z=1))' means 'the only divisors of x are x itself and 1' — i.e. x is prime or x=1. So φ says: for every x that is 1-or-prime, there exists a STRICTLY LARGER 1-or-prime w — i.e. 'primes are unbounded above' within the domain. For S1={1,...,100} (finite), the largest prime in range (97) has no larger prime within S1, so φ FAILS. For S2 (all positive integers) and S3 (all integers), Euclid's theorem guarantees infinitely many primes, so for any x a larger prime always exists (and for x≤0 or non-prime x, the implication is vacuously true) — φ holds for both S2 and S3.

Explanation