Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
To say $(\forall x)(Q(x)\wedge R(x))$ is to say that all numbers in your universe are real and rational. –  A.P. Apr 6 '13 at 23:38
    
Well - this example may not be the best, given that I already know that this can't be true. But I've seen examples where stuff was made up completely, like "All my poultry dance the Tango". I had said $(\forall x)(Poultry(x)\to Dance(x))$ and it was marked wrong. To this day I don't know if I was right and the marker of the assignment was wrong... but I didn't contest it. –  agent154 Apr 6 '13 at 23:43
1  
That example looks right to me (compare with your #1). –  A.P. Apr 6 '13 at 23:45
    
...unless you needed to specify that the poultry was yours, in which case you'd need something like $$\forall x(\text{Poultry}(x) \wedge \text{Mine}(x) \to \text{DanceTango}(x))$$ –  Clive Newstead Apr 6 '13 at 23:47
    
In the example you give, you'd be correct, unless as Clive noted, you were simply missing a conjunct: "x is mine". then you'd want "for all x[if(x is poultry and x is mine) then x dances the tango.] The primary connective under the "for all" quantifier is an implication. –  amWhy Apr 6 '13 at 23:52

2 Answers 2

up vote 3 down vote accepted

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

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.