# Show that $\forall x (P(x) \rightarrow Q(x)) \wedge \exists x P(x) \implies\exists x Q(x)$

show that $$\forall x (P(x) \rightarrow Q(x)) \wedge \exists x P(x) \implies\exists x Q(x)$$

$$\forall x (P(x) \rightarrow Q(x)) \wedge \exists x P(x) \implies (P(y) \rightarrow Q(y)) \wedge P(y) \quad (\text{using universal specification}) \\ \implies\;\; Q(y) \quad (\text{using modus ponens}) \\ \implies\;\; \exists x Q(x)\quad (\text{using existential generalization})$$

Hi. I am confused about a proof in my discrete mathematics textbook. I have written the question and proof above. My textbook uses $$\implies$$ to mean tautologically implies. And, $$\rightarrow$$ means a normal if then statement. Right, so my textbook states that

Universal Specification: Let $$P(x)$$ be a predicate on x and the set $$A$$ be the universe of discourse for $$x$$ . If we assume $$P(x)$$ is true for all $$x \in A$$ , then it can be concluded that the predicate $$P$$ is also true for any arbitrary element $$y \in A$$, that is, $$\forall x P(x) \implies P(y)$$

By this US, I can see how $$\forall x (P(x) \rightarrow Q(x)) \implies (P(y) \rightarrow Q(y))$$. However, I don't understand how US implies that the $$\exists x P(x)$$ part implies $$P(y)$$.

• @copper.hat I think I get that part. But it's the parts with the underbrace that doesn't make sense to me. How does US imply those parts? $\forall x (P(x) \rightarrow Q(x)) \wedge \underbrace{\exists x P(x)} \implies (P(y) \rightarrow Q(y)) \wedge \underbrace{P(y)}$ Commented Oct 30, 2023 at 2:26
• In the formula on the left, $x$ is followed by the quantifier $\forall$ (and also $\exists$) so it's a parameter, not a free variable. And for any parameter in a formula, if you replace it with other variable you also need to replace all of its appearances in the formula with that variable. Commented Oct 30, 2023 at 7:18
• The details of this proof depend on how exactly Existential and Universal Introduction/Generalization and Existential and Universal Elimination/Instantiation/Specification are defined Commented Oct 30, 2023 at 12:44

Applying existential instantiation to $$\forall x (P(x) \rightarrow Q(x)) \land\exists x P(x) \implies\exists x Q(x)$$ gives $$\forall x (P(x) \rightarrow Q(x)) \land P(y)$$ and now using universal specification we get $$(P(y) \rightarrow Q(y)) \land P(y)$$ from which $$Q(y)$$ follows. To finish, apply existential generalization.

• Ok, thanks I get it. I wonder why the textbook didn't include the step of applying the existential instantiation and just instead put both steps under the umbrella of universal specification. Commented Oct 30, 2023 at 4:49
• I guess you could do $\forall x (P(x) \rightarrow Q(x)) \land\exists x P(x)$ which is the same as $\exists x P(x) \land \forall x (P(x) \rightarrow Q(x))$ which implies $\exists x ( P(x) \land (P(x) \rightarrow Q(x))$ from which we get $P(y) \land (P(y) \rightarrow Q(y))$, but that is certainly not what was written above. Commented Oct 30, 2023 at 4:54

It is strange how the author combines both universal and existential specification in one step. In my proof here, using a form of natural deduction, I do existential specification on line 4, then universal specification on line 5.

Plain text version:

1   ALL(x):[P(x) => Q(x)] & EXIST(x):P(x)
Premise

2   ALL(x):[P(x) => Q(x)]
Split, 1

3   EXIST(x):P(x)
Split, 1

4   P(y)
E Spec, 3

5   P(y) => Q(y)
U Spec, 2

6   Q(y)
Detach, 5, 4

7   EXIST(x):Q(x)
E Gen, 6

8   ALL(x):[P(x) => Q(x)] & EXIST(x):P(x)
=> EXIST(x):Q(x)
Conclusion, 1