Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 3 down vote accepted

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".

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.