6
$\begingroup$

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)

3 Answers 3

4

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

  • 0
    @peat: Yes, that sounds right.2012-10-12
2

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.

  • 0
    Ok, thanks for holding out hope - looking forward to advance :)2012-10-12
2

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.

  • 0
    Glad it helped. Frankly, it took me some time experimenting with a proof system on some digital designs before I developed a proper appreciation for the subtleties of $\Rightarrow$ (particular when dealing with temporal logic).2012-10-12