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.

  • $\begingroup$ 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$.) $\endgroup$
    – Karl
    Apr 12 at 23:34
  • $\begingroup$ I have no clue how to start this proof. Usually when I get started then I am good. $\endgroup$
    – Molly Wilk
    Apr 12 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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.