One of De Morgan's laws state that ¬∃x P(x) is equivalent to ∀x ¬P(x), but how would one go about formally proving this? Numerous attempts to find a solution have been futile, even proofwiki.org does not have a solution for this.
Using Natural Deduction rules.
First part :
1) ¬∃xP(x) --- premise
2) P(x) --- assumed [a]
3) ∃xP(x) --- from 2) by ∃-intro
4) ⊥ --- contradiction, from 1) and 3)
5) ¬P(x) --- from 2) and 4) by ¬-intro (or →-intro, if we agree on the abbreviation ¬ϕ : = ϕ → ⊥), discharging [a]
6) ∀x ¬P(x) --- from 5) by ∀-intro, where x does not occur free in any undischarged assumptions.
Thus, from 1)-6) we have : ¬∃xP(x) ⊢ ∀x ¬P(x) and with a final application of →-intro we conclude with :
⊢ ¬∃xP(x) → ∀x ¬P(x).
The second part is similar, derive : ∀x ¬P(x) ⊢ ¬∃xP(x) and conclude by →-intro with :
⊢ ∀x ¬P(x) → ¬∃xP(x).
Finally, apply ↔-intro.
To prove equivalence of P and Q we need to establish P → Q and Q → P.
Case ∀x ¬P(x) → ¬∃x P(x)
- Assume ∃x P(x).
- Eliminate the existential quantifier of (1) with x=x0: P(x0).
- Apply the universal quantifier to x0: ¬P(x0).
- Contradiction between (2) and (3): P(x) and ¬P(x).
- Therefore, the assumption in (1) must be incorrect: ¬∃x P(x).
Case ¬∃x P(x) → ∀x ¬P(x)
- Assume for some x0 that P(x0).
- Introduce the existential quantifier: ∃x P(x).
- Contradiction with the assumption.
- Therefore, ¬P(x0).
- Introduce the universal quantifier: ∀x ¬P(x).