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.

In the formula $\forall x, P(x)$, it is true when all the objects in a certain set have property $P$.

But when you have the formula $\forall x, P(x) \rightarrow Q(x)$, what needs to be true here? Do the predicates $P$ and $Q$ need to be true, or the whole formula?

I ask this because I was reading about universal modus ponens, of which the hypothesis is:

$\forall x$, if $x$ makes $P$ true, then $x$ makes $Q$ true

But what about if $P(x)$ is not true? $Q(x)$ could be true than also. If the answer is going to be "because it has an $\forall$, so all objects must have property $P$ and $Q$", what is than the difference between $\rightarrow$ and $\wedge$?

share|improve this question
1  
Read $∀x: P(x) → Q(x)$ as For all $x$ such that $P(X)$ you have $Q(x)$. –  k.stm Mar 25 '13 at 10:42
add comment

3 Answers

up vote 0 down vote accepted

When you have $\forall x\varphi(x)$ then the formula is true if and only if for every $x$, $\varphi(x)$ is true. In the case where $\varphi(x)$ is a material implication, that is $P(x)\rightarrow Q(x)$, then we require that every $x$ that satisfies $P$ will also satisfy $Q$.

That is, for every $x$ it holds that if $P(x)$ is true, then $Q(x)$ is true.

If you think about $P$ and $Q$ as sets, this simply means that $P\subseteq Q$.

This is contrary to saying that for every $x$ both $P$ and $Q$ are true, in which case we are only asserting that every $x$ is in the intersection of $P$ and $Q$, which is to say that both equal to the universe of discourse.

share|improve this answer
    
Right, so what I get from your first sentence is that the formula as a whole should be true. But $P(x) \rightarrow Q(x)$ is also true when $P$ isn't true. How does it work than? –  Garth Marenghi Mar 25 '13 at 14:03
    
@Garth: That's just how conditionals work. If the assumption is false, then the whole statement is true. For every day $x$, if the day is rainy, then I will wear my coat. Does that get true only if every day is both rainy and I wear my coat? That would suck, living in the Israeli desert... Days that are not rainy are not interesting. Elements which do not satisfy $P$ are not interesting. But those that do, must also satisfy $Q$. –  Asaf Karagila Mar 25 '13 at 14:10
add comment

The difference between $\alpha \land \beta$ and $\alpha \to \beta$ is that in the first both $\alpha$ and $\beta$ have to be true, however, the second operator forces $\beta$ to be true if $\alpha$ is true (that is, when $\alpha$ is false, then $\beta$ might take any value). The first one usually reads $\alpha$ and $\beta$, where the second $\alpha$ implies $\beta$.

When writing things like $\forall x.\ P(x) \land Q(x)$ we require both $P(x)$ and $Q(x)$ to be true for all $x$. On the other hand, $\forall x.\ P(x) \to Q(x)$ requires only $Q(x)$ to be true when $P(x)$ is (note that $x$ is same in both cases). In other words, $Q(x)$ has to be true for all $x$ that satisfy $P(x)$.

I hope this helps ;-)

Edit:

To give you some concrete example that would emphasize the difference, let

\begin{align} \phi_1 &= \forall x.\ \Big(P(x)\land\forall y.\ Q(y)\Big), \\ \phi_2 &= \forall x.\ \Big(P(x) \land Q(x)\Big), \\ \phi_3 &= \Big(\forall x.\ P(x)\Big) \land \Big(\forall y.\ Q(y)\Big), \\ \psi_1 &= \forall x.\ \Big(P(x) \to \forall y.\ Q(y)\Big), \\ \psi_2 &= \forall x.\ \Big(P(x) \to Q(x)\Big), \\ \psi_3 &= \Big(\forall x.\ P(x)\Big) \to \Big(\forall y.\ Q(y)\Big). \end{align}

Then $\phi_1$, $\phi_2$ and $\phi_3$ are all equivalent, however, $\psi_1 \to \psi_2 \to \psi_3$, but in general $\psi_3 \not\to \psi_2$, $\psi_2 \not\to\psi_1$ and $\psi_3 \not\to\psi_1$.

share|improve this answer
    
Thank you for your answer. For some weird reason, I have difficulty getting this straight. Is it true that you don't look at the values that make $P(x)$ not true because $Q$ could be either true or false? Or that you say, "well it say's $\forall$", so if there's at least one that doesn't satisfy property $P$, then the whole thing isn't true. –  Garth Marenghi Mar 25 '13 at 13:55
    
@GarthMarenghi In a formula $\forall x.\ P(x) \to Q(x)$, when $P(x)$ is false, then $Q(x)$ does not matter. In other words, $Q(x)$ for all $x$ such that $P(x)$. For example, let $P(x)$ be "$x$ is divisible by $4$" and $Q(x)$ be "$x$ is divisible by $2$" in a universe of natural numbers. Then, our statement is: $x$ is divisible by 2 for all $x$ such that $x$ is divisible by 4. Note that there are some $x$ for which $Q(x)$ is true, but $P(x)$ is not. Finally, $\forall x.\ P(x) \to Q(x)$ would be also true in universe of numbers divisible by, for example, $8$, where $\forall x.\ P(x)$ is true. –  dtldarek Mar 25 '13 at 19:04
    
Thank you for the additional information! –  Garth Marenghi Mar 27 '13 at 11:50
add comment

You can observe that:
$$\forall_x (P(x)\to Q(x)) \equiv$$$$ \lnot \exists_x (P(x) \land \lnot Q(x))$$ which you can read for example as:
There is no x that could satisfy P, and not Q at the same time.

share|improve this answer
    
That's a good one, thanks! –  Garth Marenghi Mar 27 '13 at 11:51
add comment

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.