I am to prove the validity of the formula:
$$\forall x [P(x)\rightarrow G(x)]\rightarrow [\exists x P(x) \rightarrow \exists x G(x)]$$
So I should prove that the expression above equals 1.
I am getting rid of implications:
$$\forall x [\neg P(x)\lor G(x)]\rightarrow [\forall x \neg P(x) \lor \exists x G(x)]$$
$$\exists x [P(x) \land \neg G(x)]\lor [\forall x \neg P(x) \lor \exists x G(x)]$$
and now brackets are useless :
$$\exists x [P(x) \land \neg G(x)]\lor \forall x \neg P(x) \lor \exists x G(x)$$
As Ekin said, I need to make $\forall x \neg P(x) \lor \exists x G(x)$ look like negation of $\exists x [P(x) \land \neg G(x)]$
I still can not fige out how to make it
UDP, seems like i've got a solution:
$$\exists x [P(x) \land \neg G(x)] \lor \exists x G(x)\lor \forall x \neg P(x)$$
And now $\exists x$ can be moved:
$$\exists x [P(x) \land \neg G(x) \lor G(x)] \lor \forall x \neg P(x)$$
So now I see ths situation in brackets:
$$x\lor\neg x \land y = x \lor y$$
G(x) stands for x
$\neg G(x)$ stands for $\neg x$
$P(x)$ stands for y
Is it possible to make like the above with predicates?
It becomes into this:
$$\exists x [ G(x)\lor P(x)] \lor \forall x \neg P(x)$$
Changing $$\forall x \neg P(x)= \neg(\exists x P(x))$$
Then it looks like this :
$$\exists x [ G(x)\lor P(x)] \lor \neg(\exists x P(x))$$
I'm opening up the breackets :
$$\exists x G(x)\lor \exists x P(x) \lor \neg(\exists x P(x))$$
The last two gives 1. So it looks like:
$$\exists x G(x)\lor 1 = 1$$
Which equals 1.
Am I right at my solution?
Best Answer
You cannot open up the paranthesis with $\exists$. Here is an example:
$P(x)=1 :\Leftrightarrow x \text{ is an even number}$, $G(x):\Leftrightarrow x \text{ is an even number}$.
Now take a look at $\exists x[P(x)\land \lnot G(x)]$. This is false. There are no numbers that are even and not even at the same time. However, $\exists x P(x)\land \exists x \lnot G(x)$ is a correct statement. For the first part we can set $x=2$ and for the second part we can set $x=1$. In other words, having $\exists x$ seperately gives us the freedom to "choose" different $x$'s. Informally speaking, what you claim is a weaker condition that you show to be fulfilled, but what you need to set to $1$ is stronger.
Hint: Can you arrange the rest of that formula such that it looks like the negation of $\exists x[P(x)\land \lnot G(x)]$?