0
$\begingroup$

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.

$\endgroup$
2
  • $\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
    Commented Apr 12, 2021 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
    Commented Apr 12, 2021 at 23:54

1 Answer 1

0
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .