# I am stuck trying to figure out this formal proof. I need to prove (∃𝑥𝑃(𝑥)→∀𝑦𝑄(𝑦))→∀𝑥∀𝑦(𝑃(𝑥)→𝑄(𝑦))

Using the Fitch application and only Intro and Elim rules (& REIT if necessary), prove that (∃𝑥𝑃(𝑥)→∀𝑦𝑄(𝑦))→∀𝑥∀𝑦(𝑃(𝑥)→𝑄(𝑦)) is a logical truth (i.e. prove it from no premises). Have the Fitch program check your proof, then submit (to the D2L folder) a picture, screenshot or scan of a printed copy, showing the check marks.

• Can you say more about what you're stuck on? Do you understand intuitively why this formula is true? Can you figure out which deduction rule must be used for the last step of your proof? (Hint: the desired sentence is of the form $A\to B$.)
– Karl
Commented Apr 12, 2021 at 23:34
• I have no clue how to start this proof. Usually when I get started then I am good. Commented Apr 12, 2021 at 23:54

Here's a semi-formal proof for you.

Suppose $$\exists x P(x) \to \forall y Q(y)$$.

Now suppose we have $$P(c)$$. Then by existential introduction, we have $$\exists x P(x)$$. Then we have $$\forall y Q(y)$$. Then in particular, we have $$Q(d)$$ by universal elimination.

Thus, we have $$P(c) \to Q(d)$$ by implication introduction. Then we have $$\forall y (P(c) \to Q(y))$$ by universal introduction. Then we have $$\forall x \forall y (P(x) \to Q(y))$$ by universal introduction.

Then we have $$(\exists x P(x) \to \forall y Q(y)) \to \forall x \forall y (P(x) \to Q(y))$$ by implication introduction.

Translated into Fitch, we have

Problem: |- (((∃x)Px → (∀y)Qy) → (∀x)(∀y)(Px → Qy))

1 |_ ((∃x)Px → (∀y)Qy) Assumption
2 | |_ c Flag
3 | | |_ d Flag
4 | | | |_ Pc Assumption
5 | | | | (∃x)Px 4 ∃I
6 | | | | (∀y)Qy 1,5 →E
7 | | | | Qd 6 ∀E
8 | | | (Pc → Qd) 4-7 →I
9 | | (∀y)(Pc → Qy) 3-8 ∀I
10 | (∀x)(∀y)(Px → Qy) 2-9 ∀I
11 (((∃x)Px → (∀y)Qy) → (∀x)(∀y)(Px → Qy)) 1-10 →I