2
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ Read $∀x: P(x) → Q(x)$ as For all $x$ such that $P(X)$ you have $Q(x)$. $\endgroup$
    – k.stm
    Commented Mar 25, 2013 at 10:42

3 Answers 3

2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Commented Mar 25, 2013 at 13:55
  • $\begingroup$ @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. $\endgroup$
    – dtldarek
    Commented Mar 25, 2013 at 19:04
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ That's a good one, thanks! $\endgroup$ Commented Mar 27, 2013 at 11:51
0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$ Commented Mar 25, 2013 at 14:03
  • $\begingroup$ @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$. $\endgroup$
    – Asaf Karagila
    Commented Mar 25, 2013 at 14:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .