Random Thoughts

[Kernel Sohcahtoa]

I've been brushing up on logic via reading Velleman's How to Prove It.  Here's a random problem: show that ∃x(P(x)∨Q(x)) is equivalent to ∃xP(x)∨∃xQ(x). In other words, we want to show that ∃x (the existential quantifier) distributes over disjunction.

Note.

---

The hint provided in the book is to first show that ~∀x~(P(x)∨Q(x)) is equivalent to ∃x(P(x)∨Q(x)) .

~∀x~(P(x)∨Q(x)) is equivalent to ∃x~~(P(x)∨Q(x)) (quantifier negation law) which is equivalent to ∃x(P(x)∨Q(x)) (double negation law)

---

Solution

---

The statement ∃x(P(x)∨Q(x))
is equivalent to ~∀x~(P(x)∨Q(x))
which is equivalent to  ~∀x(~P(x)∧~Q(x)) Demorgan's law
which is equivalent to  ~(∀x~P(x)∧∀x~Q(x)) (∀x (the universal quantifier) distributes over ∧ (conjunction))
which is equivalent to  ~∀x~P(x)∨~∀x~Q(x) Demorgan's Laws
which is equivalent to  ∃x~~P(x)∨∃x~~Q(x) (quantifier negation law)
which is equivalent to  ∃xP(x)∨∃xQ(x) (double negation law)
 

---