Question

Consider the first order predicate formula $\phi$:

$\forall x[(\forall zz\mid x\Rightarrow ((z=x)\vee (z=1)))\Rightarrow \exists \omega (\omega >x)\wedge (\forall zz\mid \omega \Rightarrow ((\omega =z)\vee (z=1)))]$

Here 'a | b' denotes that 'a divides b'. where a and b are integers. Consider the following sets:
$S_1$:{1,2,3,...,100}
$S_2$: Set of all positive integers
$S_3$: Set of all integers

Which of the above sets satisfy $\phi$?

• A. $S_1$ and $S_3$
• B. $S_2$ and $S_3$
• C. $S_1$,$S_2$ and $S_3$
• D. $S_1$ and $S_2$

Answer 1

The correct option is B $S_2$ and $S_3$

$\forall x[\forall z|x\Rightarrow ((z=x)\vee (z=1))\Rightarrow \exists \omega (\omega >x)\wedge (\forall zz|\omega \Rightarrow \left(\right(\omega =z)\vee (z=1\left)\right)\left)\right]$

The predicate $\phi$ simple says that if z is a prime number in the set then there exists another prime number is the set which is larger. Clearly $\phi$ 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} $\phi$ is false since for prime number 97 $ϵ$ $S_1$ there exists no prime number in the set which is greater.