0
$\begingroup$

Specify two predicates $P(x)$ and $Q(x)$ over the universe of positive integers such that the proposition $\exists x(P(x) \wedge Q(x))$ is false while the proposition $(\exists x(P(x))) \wedge (\exists x(Q(x)))$ is true. Your answer must clearly specify the predicates and explain why the first proposition is false while the second is true.

1 Answers 1

3

This exercise may be clearer if the meanings of the logical formulae are rewritten in English:

(1) "$(\exists x(P(x))) \wedge (\exists x(Q(x)))$" means that some positive integer is $P$, and some other positive integer, possibly different, is $Q$.

(2) "$\exists x(P(x) \wedge Q(x))$" means that there is a positive integer which is both $P$ and $ Q$ at once.

Any choice of mutually exclusive predicates $P(x)$ and $Q(x)$, neither of which never holds, will satisfy (1) but not (2). For example, you could take $P(x)$ to be "$x=1$" and $Q(x)$ to be "$x=2$", or $P(x)$ to be "$x$ is odd" and $Q(x)$ to be "$x$ is even".