2

I'm trying to understand the logical structure of statements of the form $ (\forall x\ \mathsf{P}(x)) \implies \mathsf{Q}$, where $x$ does not occur in $\mathsf{Q}$. To prove such statements it is sufficient to prove that $ \mathsf{P}(c) \implies \mathsf{Q}$, for some $c$ in $x$'s domain. This can be seen in two ways:

Either

$$ \begin{array}{rl} & \forall x\ \mathsf{P}(x) \\ & \mathsf{P}(c) \\ & \mathsf{Q} \\ \hline \therefore & \forall x\ \mathsf{P}(x) \implies \mathsf{Q}\end{array} $$

Or,

$\forall x \ \mathsf{P}(x) \implies \mathsf{Q}$ is logically equivalent to $ \lnot \forall x \ \mathsf{P}(x) \lor \mathsf{Q}$, which is logically equivalent to $ \exists x \ \lnot \mathsf{P}(x) \lor \mathsf{Q}$, which is logically equivalent to $ \exists x \ (\lnot \mathsf{P}(x) \lor \mathsf{Q})$, which is equivalent to $ \exists x \ ( \mathsf{P}(x) \implies \mathsf{Q})$ amounts to showing the same thing.

All this is fine and dandy, and I'm able to see how it all fits together "formally". However, I'm trying to get an intuitive sense of why proving such propositions involve just exhibiting a special case, $ \mathsf{P}(c)$, that implies $\mathsf{Q}$. Is there an easy way to see this, preferably with some concrete examples? Such statements don't seem to be quite common in my undergraduate courses.

Maxis Jaisi
  • 1,553
  • 1
    $(\forall x \ \mathsf{P}(x)) \implies \mathsf{Q}$ is certainly not logically equivalent to $ \exists x \ (\mathsf{P}(x) \implies \mathsf{Q})$, actually the latter is strictly stronger than the former. – Did Oct 13 '16 at 07:50
  • Perhaps I've misunderstood the manipulations in https://gowers.wordpress.com/2013/12/09/a-little-paradox/. If so, please correct me. – Maxis Jaisi Oct 13 '16 at 08:12
  • 1
    Huh?? Gowers' post ends with: "What has gone wrong here? If you can give a satisfactory answer, then you will have a good grasp of what mathematicians mean by “implies”." So it seems you misunderstood the author's purpose big time. – Did Oct 13 '16 at 08:15
  • If your aim is to get a solution of Gowers' exercise, just say so instead of misleading your readers. – Did Oct 13 '16 at 08:17
  • Hence, my pleading "Please correct me." By the way, thanks for pointing this out --- it seems that there's more confusion to clear apart from the ones I've asked in the main question. – Maxis Jaisi Oct 13 '16 at 08:17
  • It is not true that I wanted to ask about Gowers's post. The main thing is to understand the questions I posed, and I inadvertently used the deductions he'd written to "justify" the second reason, which I initially thought was sound. It now seems that it isn't. Also, it is not true that I'd intended to mislead the readers here. – Maxis Jaisi Oct 13 '16 at 08:21
  • You "derivation" is not correct; consider : $(\forall x (x \ge 0)) \to (0=1)$. It is clearly false in the domain $\mathbb N$ of natural numbers. – Mauro ALLEGRANZA Oct 13 '16 at 09:24
  • An "intuitive" example can be : $(∀x(x≥0))→(0 \ge 0)$ as well as $(∀x(x≥0))→(1 \ge 0)$. – Mauro ALLEGRANZA Oct 13 '16 at 09:26
  • Gowers' post is about the misunderstanding following the usual way of reading the connective $\to$ ("if..., then...") as "implies". In his example, he shows that the logical equivalence gives us a wrong conclusion if it is udes in a context where "implies" is needed, i.e. where the premise is true (we have to stress the fact that a conditional is true also when the antecedent is false). – Mauro ALLEGRANZA Oct 13 '16 at 12:40
  • In a nutshell, to say "$A$ implies $B$" means that we can prove $B$ from $A$ (plus other axioms or already proved theorems). As we said above, from $(\forall x P(x))$ you cannot prove $Q$ whatever, and this is the gist of Gowers' notes. – Mauro ALLEGRANZA Oct 13 '16 at 14:30
  • I think (?) I'm getting close to understanding what you mean. But from $ \forall a (a+z=a)$ ($a$, $z$ are real numbers), we can definitely prove that $z=0$. What is different about this case from $ \forall x P(x) \implies Q$? – Maxis Jaisi Oct 13 '16 at 14:36

2 Answers2

1

I assume that you are asking for an "intuitive explanation" of why :

$(∀x \ P(x)) → Q$ and $∃x \ (P(x) → Q)$

are equivalent if $x$ is not free in $Q$.

Form left to right : assume that $(∀x \ P(x)) → Q$ holds.

We have two cases :

(i) $Q$ is true; in this case, by the truth table for conditional : $A \to Q$ is true for $A$ whatever. Thus, also $P(c) \to Q$ is true for $c$ whatever.

And thus we have that $∃x \ (P(x) → Q)$ holds.

(ii) $∀x \ P(x)$ is false; in this case, we have that for some $c$ : $P(c)$ is false and so $P(c) \to Q$ is true (for that $c$).

And thus again we have that $∃x \ (P(x) → Q)$ holds.

In the same way we can prove the case form right to left.

The above argument follows exactly Gowers' manipulations.

By easy transformations, the original formula is equivalent to :

$(\exists x \ \lnot P(x)) \lor Q$.

Thus, whe have only to apply the truth-conditions for $\lor$ (its truth-table).

Either $Q$ is true or there is some $c$ such that $\lnot P(c)$ holds.

But to say that $\lnot P(c)$ holds for some $c$ is the same as : $\forall x \ P(x)$ does not hold.

Mauro ALLEGRANZA
  • 94,169
  • I can see why it works. But if I take a more contrived example:

    "For every human who has a vital organ, the organ must be a heart."

    So to prove that statement, it suffices to just pick a human, John, say, and check that his vital organ is a heart. Then we'd have proven the quoted statement. But I still feel uneasy about it...

     – Maxis Jaisi Oct 13 '16 at 12:03
  • @MaxisJaisi - again you are on the wrong path... You cannot prove $(\forall x Px) \to Q$ because it is not valid (i.e. it is not a logical truth). This means that you can find interpretations where it is true (it is satisfied) and other interpretations where it is false. What I've shown you is the validity of the equivalence, assuming that this is the "uneasy" fact. As per my comment above, your purported proof of $(\forall x Px) \to Q$ is wrong. – Mauro ALLEGRANZA Oct 13 '16 at 12:08
  • Or suppose we want to show that if $a$ has the property that its sum with any real number equals the real number itself, then $a=0$. To show this we simply pick any real number, say $1$, and show that $a=0$. Then we have proven the claim. Is this usual in higher mathematics? – Maxis Jaisi Oct 13 '16 at 12:08
0

Complementing Mauro's answer,

$$\begin{array}{rl} \forall x ( P (x) ) \to Q &\equiv \neg \forall x ( P (x) ) \lor Q\\ &\equiv \exists x ( \neg P (x) ) \lor Q\\ &\equiv \exists x ( \neg P (x) \lor Q)\\ &\equiv \exists x ( P (x) \to Q)\end{array}$$

Rodrigo de Azevedo
  • 1