I had a question about two first order logic formulas given in this lecture in the series on Discrete Mathematical Structures from IIT.
The instructor says (at 36:19 in the video) that the following two statements are equivalent:
- $\exists x (P(x) => Q(x) )$
- $\forall x P(x)$ => $\exists x Q(x)$
In the first statement my understanding is that X is bound such that we are talking about the same value of x for P(x) and Q(x). In words, statement 1 seems to be saying that if we have P(3), then that implies Q(3)... not Q(4) or Q(5) or some other number.
In the second statement it seems there are two bindings of 'x'. For any 'x' (say x=3) P(x) (that is, P(3) in this case) implies that there exists some 'x' (we are in a different scope now) such that Q(x) is true. For this second scope x need not be three. So if we have P(3), this simply means there is some other value -- say 25 -- for which Q is true.. that is Q(25) is true (in this case.)
Does that seem right ? It is quite likely that the IIT professor has it right and i'm just confused. Wouldn't be the first time. Anyway.. thanks in advance for the help.
Edit: Sorry for the jumbled explanation of why I am confused. Here is a more complete example.
Say we have S = {1,2,3} and P(1), P(2), and Q(1) all true.
In this case, statement one clearly holds because P(1) => Q(1). Statement two holds as well because it is NOT true that P(x) for all x in S.
If we were to extend the 'P' predicate's coverage so that P(3) = true, then the first statement would continue to hold. Furthermore, the 'for all' condition in the second statement would now hold (it didn't hold until now.) And the consequent of statement two would also hold, since there is an x (namely, 1) for which Q is true (Q(1) = true). So working through the simple example I have to admit it works ! It just didn't feel right. Confirmation that this does indeed hold true ( from bof and Mauro, thanks guys!) motivated me to try some examples. And yeah.. it does work out.
Comment : The "intuitive" proof needs some more details.
Assume that $∃x(P(x) \to Q(x))$ holds : this means that there is an object $a$ in the "uiverse of discourse" (for example : the natural numbers) such that the conditional $P(a) \to Q(a)$ holds.
But now we need some care : the conditional $p \to q$ holds either when both $p$ and $q$ are true or when $p$ is false.
Thus we have to consider two cases :
(i) both $P(a)$ and $Q(a)$ are true : consider now $∀xP(x) \to ∃xQ(x)$. Again, we have two possibilities : either $∀xP(x)$ is true, in which case, having that $Q(a)$ is true, also $\exists x Q(x)$ is true, and thus the conditional : $∀xP(x) \to ∃xQ(x)$ holds; or $∀xP(x)$ is false, and this is enough to conclude again that $∀xP(x) \to ∃xQ(x)$ holds.
(ii) $P(a)$ is false; if so, clearly $\forall xP(x)$ is false, and again this is enough to conclude that $∀xP(x) \to ∃xQ(x)$ holds.
__
The same approach can be used starting from $∀xP(x) \to ∃xQ(x)$ to show that it implies $∃x(P(x) \to Q(x))$ ...