How to know when to use $P(x)\wedge Q(x)$ and when to use $P(x)\to Q(x)$?

Question

When translating English phrases to mathematical statements using logical quantifiers, I find that I'm having trouble knowing the difference between $P(x)\wedge Q(x)$ and $P(x)\to Q(x)$.

For example:

Translate the following sentences using logical quantifiers:

1. All rationals are real
2. No rationals are real
3. Some rationals are real
4. Some reals are rational

My notes say the following:

• $Q(x)$: $x$ is rational

• $R(x)$: $x$ is real

  1. All rationals are real: $(\forall x)(Q(x)\to R(x))$
  2. No rationals re rel: $(\forall x)(Q(x)\to\neg R(x))$
  3. Some rationals are real: $(\exists x)(Q(x)\wedge R(x))$
  4. Some reals are rational: $(\exists x)(R(x)\wedge Q(x))$

So I have to wonder: Why, for number 1 and 2 is it not right to say $(\forall x)(Q(x)\wedge R(x))$? I've gotten many questions like this wrong because I said $A\to B$ when it was supposed to be $A\wedge B$.

Answer 1

Note that it is typically the case that $\forall$ is accompanied by $\rightarrow$, and $\exists$ by $\land$.

For all $x$, if $x$ is $P$ then $x$ is $Q$.

Exists some $x$ such that $x$ is $P$ and $x$ is $Q$.

Exercise:

Negate $\forall x(P(x) \rightarrow Q(x))$

• $\lnot \forall x(P(x) \rightarrow Q(x)) \equiv \exists x\lnot(P(x) \rightarrow Q(x)) \equiv \exists x \lnot(\lnot P(x) \lor Q(x)) \equiv \exists x (P(x) \land \lnot Q(x))$

Negate $\exists x(P(x) \land Q(x))$

• $\lnot \exists x(P(x) \land Q(x)) \equiv \forall x \lnot(P(x) \land Q(x)), \equiv \forall x (\lnot P(x) \lor \lnot Q(x)) \equiv \forall x(P(x) \rightarrow Q(x))$

Moving the negation inward, and see the form you arrive at in each case.

Answer 2

Suppose that $P(x)$ is something like "$x$ is rational". When you say "for all rational $x$, $Q(x)$ holds", what you're saying is "for all $x$, if $x$ is rational then $Q(x)$". That is: $$\forall x(P(x) \to Q(x))$$ When you say "there exists a rational $x$ such that $Q(x)$", what you're saying is "there exists an $x$, which is rational and also $Q(x)$". That is: $$\exists x(P(x) \wedge Q(x))$$

So the general rule is:

• $\forall$ uses $\to$
• $\exists$ uses $\wedge$

There's a more fundamental reason for this. $A \to B$ is the same as $\neg A \vee B$, and $\exists$ is the same as $\neg \forall \neg$. ("There exists a red car" is the same as saying "it's not the case that all cars aren't red".) So... $$\begin{align} &\exists x (P(x) \wedge Q(x))\\ \text{is equivalent to}\ &\neg \forall x \neg (P(x) \wedge Q(x))\\ \text{is equivalent to}\ &\neg \forall x (\neg P(x) \vee \neg Q(x))\\ \text{is equivalent to}\ &\neg \forall x (P(x) \to \neg Q(x))\end{align}$$ So really the $\wedge$ in the $\exists$ case does, in some sense, 'come from' a $\to$. The converse also holds.