# How to prove two propositions equivalent?

I was given the question:

Determine if $\exists x (P(x) \implies Q(x))$ and $\exists xP(x) \implies \exists x Q(x)$ are equivalent, i.e., always have the same truth value. If they are not equivalent figure out if one implies the other. Prove that you have correctly determined the most general logical relationship between the two expressions. Be sure to include examples if the two expressions are not equivalent.

How do I go about doing this? Would I simplify each proposition and see if they simplify to the same thing? And if they are not equivalent, how would I see if one implies the other? Thanks.

-
"Equal" is not the same as "equivalent". –  Andres Caicedo Nov 2 '12 at 0:44
Have you tried out any concrete "examples"? "There exists something such that (if it is P, then it is Q)" vs. "if there exists something such that it is P, then there exists something such that it is Q"...I've translated generically; perhaps it's enough for you to better understand the differences (hint) between the two propositions? –  amWhy Nov 2 '12 at 0:51
To prove equivalence, you need to be able to derive one from the other, or "simplify" as you mention. Equivalence can also be proven by establishing that each statement implies the other. Equivalence would be the most general relationship then. If the expressions are not equivalent, you can prove this by providing a valid counterexample. Then you'd need to determine whether one of the statements implies the other (whether if one is true, the other cannot be false); if so you'd need to prove it. Implication would be the most general relationship then. –  amWhy Nov 2 '12 at 0:57
@AndresCaicedo I edited accordingly. –  amWhy Nov 2 '12 at 1:22

Let the universe be all the people on Earth, $\,P(x):=x\,$ is a mother , $\,Q(x):=x\,$ is a man, so

$$\exists\,x\left(P(x)\rightarrow Q(x)\right)=\,\text{exists a person s.t. if it is a mother then it is a man}$$

$$(\exists\,x\,P(x))\rightarrow (\exists\,x\,Q(x))=\,\text{if there exists a mother then there exists a man}$$

Do you think the above are equivalent?

-
That makes it much more simple to understand. I would say no, they are not equivalent. But I also don't see how one would imply the either using this universe/example? –  Jakemmarsh Nov 2 '12 at 2:59

HINTS:

1. What if $Q(x)$ is $x\ne x$, and $P$ is such that $\exists xP(x)$ and $\exists x\big(\lnot P(x)\big)$ are both true?

2. One of the propositions does imply the other.

-

I like to develop intuition with a specific universe. In this case, I take $x$ as having two values, say $0$ and $1$.

Then the first statement becomes $(\lnot P(0) \lor Q(0)) \lor (\lnot P(1) \lor Q(1))$.

The second statement becomes $(\lnot(P(0) \lor P(1)) \lor (Q(0) \lor Q(1))$.

It is straightforward to see that the assignment $P(0) = F, P(1)=T, Q(0) = F, Q(1) = F$ results in the first formula having the value $T$, while the second is $F$. Hence the formulas are not equivalent.

Rewriting the formulas as $\lnot P(0) \lor \lnot P(1) \lor Q(0) \lor Q(1)$ and $(\lnot P(0) \land \lnot P(1)) \lor Q(0) \lor Q(1)$ suggests that the second formula implies the first.

To prove this (loosely) we need only show that if the second formula is true, then so is the first.

The second formula can be true in two ways:

(1) $\exists x P(x)$ is false, in which case $\forall x \lnot P(x)$ is true, from which is follows that $\forall x (\lnot P(x) \lor Q(x))$ is true, from which we have $\forall x (P(x) \Rightarrow Q(x))$ and finally $\exists x (P(x) \Rightarrow Q(x))$ is true.

(2) $\exists x P(x)$ is true and $\exists x Q(x)$ is true. Since $\exists x Q(x)$ is true, it follows that $\exists x (\lnot P(x) \lor Q(x))$ is true, which is equivalent to $\exists x ( P(x) \Rightarrow Q(x))$.

Formalizing the proof needs more input from you...

-
What are the rules for converting a proposition like this to ands/ors/negations? –  Jakemmarsh Nov 2 '12 at 19:57
Depends on your rules... –  copper.hat Nov 2 '12 at 20:10