Testing validity of Predicate Logic conditional statement without a Truth Tree.

Question

For the past half hour, I have been trying to prove the following statement in Predicate Logic without the use of a truth tree:

$$∃xPx∧∃xQx→∃x(Px∧Qx)$$

Which, of course, I know to be invalid. As such, I can easily show this using a truth tree.

Without a truth tree, here is my work thus far: $$(∃xPx∧∃xQx)→∃x(Px∧Qx)$$ Then I assume the conditional to be false, and try my best to follow the proof methods I learned: $$\neg[(∃xPx∧∃xQx)→∃x(Px∧Qx)]$$ $$(∃xPx∧∃xQx)\wedge\neg∃x(Px∧Qx)$$ $$(∃xPx∧∃xQx)\wedge\forall x\neg(Px∧Qx)$$ $$Pa$$ $$Qb$$ $$\neg(Pa∧Qa)$$ $$\neg(Pb∧Qb)$$

From here, I am lost. Since I don't study this formally, I may have made a mistake already.

I'm not sure if I should use De Morgan's Law and then Distributive laws.

Answer 1

You are attempting to prove a statement is not a tautology by proving the negation of the statement is a tautology.

This will not work.

Witness that $(a\to b)$ is not a tautology, and neither is its negation, $(a\wedge \neg b)$.

To prove that a statement is not a tautology, one provides a counter example: an interpretation of the predicates for which the statement is false.

For instance, let us take $P(x)$ to mean "$x$ is odd" and $Q(x)$ to mean "$x$ is even".   Under this interpretation, the statement then reads:

"If there is an odd number, and there is an even number, then there is a number that is both odd and even."

$$(\exists x\;(2\not\mid x)\wedge \exists x\;(2\mid x)) \to \exists x\;((2\not\mid x) \wedge (2\mid x))$$

Answer 2

The basic problem is that your initial statement is confusing.

You have written:

$$\exists x P(x) \land \exists x Q(x) \implies \exists x (P(x)\land Q(x))$$

This is confusing because you should have made a difference between $P$'s $x$ and $Q$'s.

If we write:

$$\exists x P(x) \land \exists y Q(y) \implies \exists x (P(x)\land Q(x))$$

we can see the problem - there is no $y$ on the RHS!

The correct statement is:

$$\exists x P(x) \land \exists y Q(y) \land (x=y)\implies \exists x (P(x)\land Q(x))$$