Predicate Logic: $ ∀x (P(x) \lor Q(x)) ⊢ ∀xP(x) \lor ∀xQ(x) $

Question

The exercise ask me to prove it using natural deduction or show a example that false the sequent. How do i prove it using natural deduction ?

$ \forall x (P(x) \lor Q(x)) ⊢ ∀xP(x) \lor \forall xQ(x) $

I tried:

1.$ ∀x (P(x) \lor Q(x)) $

2. $ x_0 $
3. $ P(x_0) V Q(x_0) $

Then I tried to use the or-exclusion rule but i can not figure out how to get $P(x_0)$ from $Q(x_0)$

Answer 1

What you'll find is that you cannot prove the statement. It is false. Whenever you're hitting dead ends in a proof, try considering a counterexample.

Let's look at the outcomes from flipping a coin: $P(x)$: "x is heads," $\;\;Q(x)$: "x is tails", with x belonging to the domain of all coins.

Then we can say truthfully that $$\forall x (P(x)\lor Q(x)).$$

But there's a problem with the RHS: It's claiming that $$\forall x (P(x)) \lor \forall x (Q(x))$$

That is, the right hand side claims that every coin tossed turns of heads, or else, every coin tossed turns of tails.

Answer 2

This isn't true.

Let $P(x)$ be "x is a banana" and $Q(x)$ be "x isn't a banana" and $x$ be from the space of all fruit.

Then the predicate is true because every fruit either is or is not a banana. It doesn't follow that either all fruits are bananas or all fruits are not bananas.

So for a counter example simply choose $P(x) = \lnot Q(x)$. And a space for which some elements $P(x)$ is true and other elements $P(x)$ is false.