# Factoring out universal quantifier in combination with an implication

I just began studying maths and so far everything made sense after tinkering around with it a little bit (e.g. $\lnot(\forall x \in M : A(x)) = \exists x \in M : \lnot A(x)$ thinking "not all math students are dumb means that there's at least one who is not dumb")

I already prooved this statement right (sry I'm not a native speaker) $( \forall x:P(x))\Rightarrow q = \exists x:(P(x)\Rightarrow q)$, but is there any example (like the one given above) for this as well? I just cannot understand why factoring out the universal quantifier makes any difference... (although I know it has to be right)

-

I think the most complete way to intuitively convince oneself of $$\tag{1} \bigl((\forall x : P(x))\Rightarrow Q\bigr) \Leftrightarrow \exists y : (P(y)\Rightarrow Q)$$ is to make sure that there is no possible way it can be false, by a case analysis of the truth values of $\forall x:P(x)$ and $Q$:

• Suppose $Q$ is true. Then the $\cdots\Rightarrow Q$ is true no matter what is to the left of the arrow, so $(1)$ becomes $T \Leftrightarrow \exists y : T$, and both sides of this is true.

• Suppose $Q$ is false and $\forall x:P(x)$ is also false, that is, there is an $x_0$ such that $\neg P(x_0)$. Then the left-hand side of $(1)$ is true (because $F\Rightarrow F$ is true). Right right-hand side is also true, because we can chose $y$ to be $x_0$, and $P(y=x_0)\Rightarrow Q$ is then $F\Rightarrow F$ which is true.

• Suppose $Q$ is false but $\forall x:P(x)$ is true. Then the left-hand side of $(1)$ is false, and we must see that the right-hand side is false too. But it is false because there cannot be any $y$ that makes $P(y)\Rightarrow Q$ true. Because we're assuming $\forall x:P(x)$, it no matter which $y$ we choose, $P(y)$ will hold, so $P(y)\Rightarrow Q$ is $T \Rightarrow F$ which is false.

In each of the three cases $(1)$ is true -- and together these cases cover every possible meaning $P$ and $Q$ can have, so $(1)$ is always true.

By the way, the $\Leftarrow$ direction of $(1)$ can be seen more constructively. Suppose $\exists y:(P(y)\Rightarrow Q$, and then again suppose $\forall x:P(x)$. In particular $P(y)$ must be true when $y$ is the one such that $P(y)\Rightarrow Q$. But then $Q$ is true! This proves $$\bigl(\exists y:(P(y)\Rightarrow Q)\bigr) \Rightarrow \bigl((\forall x:P(x))\Rightarrow Q\bigr)$$ However, the opposite direction is more tricky, and in fact cannot be seen to be true without using some sort of case analysis along the way (or some other proof principle that is equivalent to case analysis). This is because it is not valid in intuitionistic logic, which rejects the principle that one of $\forall x:P(x)$ or $\exists x:\neg P(x)$ must necessarily be true. (Equivalently, intuitionistic logic denies that "it must be true because there is no way for it to be false" is a valid way of arguing).

-
I don't quite get the "Then the left-hand side of (1) is false, and we must see that the right-hand side is true too." part, what do you mean by that? –  Peter Oct 12 '12 at 15:19
@peat: Horrible typo on my part. Try now. –  Henning Makholm Oct 12 '12 at 15:24
Ahhhh... so it's because the negated $\exists$ means there is no $y$ so that $P(y)$ is true while a negated $\forall$ would only mean that there is one (or more) $y$ so that $P(y)$ is false, can I put it like that? –  Peter Oct 12 '12 at 15:35
@peat: Yes, that sounds right. –  Henning Makholm Oct 12 '12 at 15:37
Thanks a lot :) –  Peter Oct 12 '12 at 15:42

Recall that $p\to q$ is logically equivalent to $\lnot p\lor q$. Thus, $\big(\forall x P(x)\big)\to q$ is logically equivalent to $\lnot\big(\forall x P(x)\big)\lor q$, which you already know is logically equivalent to $\exists x\big(\lnot P(x)\big)\lor q$. Similarly, $\exists x\big(P(x)\to q\big)$ is logically equivalent to $\exists x\big(\lnot P(x)\lor q\big)$. Thus, the claim is that

$$\exists x\big(\lnot P(x)\big)\lor q\;\equiv\; \exists x\big(\lnot P(x)\lor q\big)\;.\tag{1}$$

This is intuitively reasonable, because $q$ says nothing about $x$: intuitively, $q$ and $\exists x (q)$ say the same thing.

A little less informally, if there’s an $x$ that does not have property $P$, then both expressions are true regardless of $q$, and if there is no such $x$, then each is true if and only if $q$ is true. Thus, in all cases they are either both true or both false.

Alternatively, if $q$ is true, $\lnot P(x)\lor q$ is true no matter what $x$ might be, so both sides of $(1)$ are true. If $q$ is false, then $\exists x\big(\lnot P(x)\big)\lor q$ is true if and only if $\exists x\big(\lnot P(x)\big)$ is true, i.e., if and only if some $x$ does not have property $P$. But $\exists x\big(\lnot P(x)\lor q\big)$ is also true if and only if $\exists x\big(\lnot P(x)\big)$ is true, so in all cases the two sides of $(1)$ are both true or both false.

-
Phew...seems legit, but there isn't there any way to explain this with dumb students or the like? ^^ –  Peter Oct 12 '12 at 15:18
@peat-ar: That was the closest thing to a genuinely intuitive approach that I could think of, I’m afraid. –  Brian M. Scott Oct 12 '12 at 15:23
Thanks a lot for the detailed explanation! I guess I have to get more of a mathematician to understand this though :/ (I get all the single steps, but yet it's hard to understand the whole) –  Peter Oct 12 '12 at 15:42
@peat-ar: Understanding the individual steps is an important first step. As you progress, you’ll find yourself understanding larger chunks at a time, but there will probably always be proofs whose overall shapes are very hard to grasp. –  Brian M. Scott Oct 12 '12 at 15:44
Ok, thanks for holding out hope - looking forward to advance :) –  Peter Oct 12 '12 at 15:49

Brian & Henning have given excellent, precise answers above.

Here is an imprecise attempt at providing some intuitive 'feel'.

I think of $x$ as being a representative element of some countable set $\{x_1,x_2,...\}$.

I think of $(\forall x P(x))$ as $(P(x_1) \land P(x_2) \land ...)$, and I think of $(\exists x R(x))$ as $(R(x_1) \lor R(x_2) \lor...)$.

We have $A \Rightarrow B$ is the same as $\lnot A \lor B$.

Then $( \forall x:P(x))\Rightarrow q$ becomes $\lnot (P(x_1) \land P(x_2) \land ...) \lor q = (\lnot P(x_1) \lor \lnot P(x_2) \lor ...) \lor q$,

The statement $\exists x:(P(x)\Rightarrow q)$ becomes $((\lnot P(x_1) \lor q) \lor (\lnot P(x_1) \lor q) \lor...)$ which is logically the same as the statement above.

-
Cool, thanks for this super comprehensive answer! However both would read like "For all x, P(x) implies q", am I right? –  Peter Oct 12 '12 at 17:04
Not exactly, either "(for all x, P(x)) implies q" or "for some x, (P(x) implies q)". –  copper.hat Oct 12 '12 at 17:13
I think of $\forall$, $\land$ and $\cap$ in similar terms. Similarly for $\exists$, $\lor$ ad $\cup$. –  copper.hat Oct 12 '12 at 17:15
Sorry, my fault, what I meant was: $\forall x : (P(x) \Rightarrow q)$ would read the same, but be something different as $(\forall x : P(x)) \Rightarrow q$, right? –  Peter Oct 12 '12 at 17:30
Intuition is served well if you just consider $x$ to range over just 2 values. Let $P_1=P(x_1), P_2 = P(x_2)$ for simplicity. Then $\forall x:(P(x)\Rightarrow q)$ becomes $(\lnot P_1 \land \lnot P_2) \lor q$, and $(\forall x:P(x))\Rightarrow q$ becomes $\lnot P_1 \lor \lnot P_2 \lor q$. An assignment of $(P_1,P_2,q) = (T,F,F)$ shows that these are not equal. –  copper.hat Oct 12 '12 at 18:48