Question

Give a Fitch-style natural deduction proof of the sentence ∀x(P (x) ∨ ∃yQ(y)) → (∀xP (x) ∨ ∃yQ(y)).

Hint: You will need to use RAA. If it helps, you may assume you already proved ¬∀xP (x) → ∃x¬P (x) (indeed, you proved this in Problem Set 7, problem 6(c)).

Answer 1

The Fitch-style natural deduction proof involves using Reductio Ad Absurdum (RAA) to show that the negation of the conclusion leads to a contradiction, which confirms the original conclusion must be true.

Step-by-step explanation:

The goal is to provide a Fitch-style natural deduction proof for the logical sentence ∀x(P(x) ∨ ∃yQ(y)) → (∀xP(x) ∨ ∃yQ(y)) using Reductio Ad Absurdum (RAA). This form of argument involves showing that a negation of the conclusion leads to a contradiction, thus the original conclusion must be true.

To structure the proof, we:
1. Assume the negation of the conclusion (¬(∀xP(x) ∨ ∃yQ(y))) to lead to a contradiction (for RAA).
2. From this assumption, we infer that both ¬∀xP(x) and ¬∃yQ(y) must be true.
3. Using the logical equivalence of ¬∀xP(x) to ∃x¬P(x) (proved in a prior problem set), and because we have assumed ¬∃yQ(y), we have ∃x¬P(x) and ¬∃yQ(y) as our assumptions.
4. We can then use these assumptions to derive a contradiction with the initial premise ∀x(P(x) ∨ ∃yQ(y)) as neither of the disjuncts in the premise can be true under our assumptions.
5. Having reached a contradiction, we can conclude by RAA that ¬(∀xP(x) ∨ ∃yQ(y)) is false and hence ∀x(P(x) ∨ ∃yQ(y)) → (∀xP(x) ∨ ∃yQ(y)) must be true.