( ∀x(P(x)→Q(x)) ) → ( ∀x(P(x))→∀x(Q(x)) )
( ∃x(P(x))→∃x(Q(x)) ) → ( ∃x(P(x)→Q(x)) )
I got these in my some test series,i was not able to prove.Please help me how to prove that this implication holds,if possible please explain why converse doesn't hold
I don't know what formal proof system you have to use, but here are some informal proofs that hopefully you will be able to formalize:
I. This statement says: 'If all P's are Q's, then if everything is a P, then everything is a Q'. To prove this, do a conditional proof: Assume that all P's are Q's, and show that if everything is a P, then everything is a Q. And since that last statement is another conditional, we'll do a conditional proof for that one as well: Assume that everything is a P, and show that everything is a Q. Well, if everything is a P, and if all P's are Q's, then everything is a Q. Done!
Schematically (and pseudo-formally)
$\qquad \forall x (P(x) \rightarrow Q(x))$ (Conditional Proof Assumption 1)
$\qquad \qquad \forall x P(x)$ (Conditional Proof Assumption 2)
$\qquad \qquad \qquad$ ... [consider any arbitrary object $a$]
$\qquad \qquad \qquad P(a)$ by 2
$\qquad \qquad \qquad P(a) \rightarrow Q(a)$ by 1
$\qquad \qquad \qquad Q(a)$ by 4 and 5
$\qquad \qquad \forall x Q(x)$ by 3 through 6
$\qquad \forall x P(x) \rightarrow \forall x Q(x)$ Conditional proof 2 through 7
$\qquad \forall x (P(x) \rightarrow Q(x)) \rightarrow (\forall x P(x) \rightarrow \forall x Q(x))$ Conditional proof 1 through 8
Why does the converse ($(\forall x P(x) \rightarrow \forall x Q(x))\rightarrow \forall x (P(x) \rightarrow Q(x)) $ ) not hold? Here is a simple counterexample: take as the domain natural numbers, interpret $P(x)$ as $x$ is an even number, and $Q(x)$ as $x$ is an odd number. Since not all numbers are even, $\forall x P(x)$ is false, but any conditional with a false antecedent is true, so this means that $\forall x P(x) \rightarrow \forall x Q(x)$ is (vacuously) true. But obvviously, even numbers are not odd numbers, so $\forall x (P(x) \rightarrow Q(x)) $ is false. So, $(\forall x P(x) \rightarrow \forall x Q(x))\rightarrow \forall x (P(x) \rightarrow Q(x)) $ is false.
II. This one is best proven using a proof by contradiction. Here is a pseudo-formal proof:
$\qquad \exists x P(x) \rightarrow \exists x Q(x)$ (Conditional Proof Assumption)
$\qquad \qquad \neg \exists x (P(x) \rightarrow Q(x)) $ (Proof by Contradiction Assumption)
$\qquad \qquad \forall x \neg (P(x) \rightarrow Q(x)) $ (Quantifier Negation on 2)
$\qquad \qquad \forall x (P(x) \land \neg Q(x)) $ (Implication Negation on 3)
$\qquad \qquad \forall x P(x) \land \forall x \neg Q(x) $ (Distribution $\forall$ over $\land$ on 4)
$\qquad \qquad \forall x P(x)$ (Simplification 5)
$\qquad \qquad \forall x \neg Q(x)$ (Simplification 5)
$\qquad \qquad \exists x P(x)$ (Implied by 6, assuming domain is not empty, which is what most logics assume))
$\qquad \qquad \exists x Q(x)$ (from 1 and 8)
$\qquad \qquad \neg \exists x Q(x)$ (Quantifier Negation on 7)
$\qquad \qquad \bot$ (from 9 and 10)
$\qquad \exists x (P(x) \rightarrow Q(x)) $ (Proof by Contradiction 2 through 11)
$(\exists x P(x) \rightarrow \exists x Q(x)) \rightarrow \exists x (P(x) \rightarrow Q(x)) $ (Conditional Proof 1 through 12)
For a counterexample to the converse $\exists x (P(x) \rightarrow Q(x)) \rightarrow (\exists x P(x) \rightarrow \exists x Q(x)) $, pick some domain where some, but not all, objects are $P$'s, but nothing is a $Q$. For example, take the natural numbers again as the domain, let $P(x)$ again be $x$ is even, and let $Q(x)$ be $x$ is a unicorn. Then the antecedent $\exists x (P(x) \rightarrow Q(x)) $ is true, since there are some numbers that are not even, thus making the inside conditional (vacuously) true, The consequent $\exists x P(x) \rightarrow \exists x Q(x)$ is false however, since $\exists x P(x) $ is true (yes, there are some even numbers), but $\exists x Q(x)$ is false (no, no numbers are unicorns). Hence, under this interpretation $\exists x (P(x) \rightarrow Q(x)) \rightarrow (\exists x P(x) \rightarrow \exists x Q(x)) $ is false.