# How to prove validity of this formula? $\forall x [P(x)\rightarrow G(x)]\rightarrow [\exists x P(x) \rightarrow \exists x G(x)]$

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?

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)]$$?

• but it already looks like it – Elvin Aug 13 at 14:44
• seems like I have no idea solving this, could you help? – Elvin Aug 13 at 18:44
• I thinks I have a solution, could you check it please? – Elvin Aug 14 at 11:31

...and now brackets are useless :

$$\exists x [P(x) \land \neg G(x)]\lor \forall x \neg P(x) \lor \exists x G(x)$$

Hint: double negation and de Morgan's.

$$\neg\neg\big(\exists x~(P(x) \land \neg G(x))\lor \forall x~\neg P(x) \lor \exists x ~G(x)\big)\\[3ex]\neg\big(\forall x~(\neg P(x)\vee G(x))\land\exists x~P(x)\land\forall x~\neg G(x)\big)\\[2ex]\vdots$$

• updated my solution, could you check it please? – Elvin Aug 14 at 11:32
• Yes. You have it. – Graham Kemp Aug 14 at 21:33

I think the problem is that you are trying to prove this statement to be valid by showing it to be equivalent to $$1$$ (the tautology), and that you are hoping to use equivalence rules to do so. However, in predicate logic all kinds of fairly basic equivalences hold without there being an explicit equivalence principle for it.

For example, it is clear that something like $$\forall x \ P(x) \rightarrow \exists x \ P(x)$$ is a valid statement (and thus also equivalent to $$1$$), but there is really no standard equivalence principle defined for this ... or at least not that I have ever seen.

So, to show that your statement is valid, you are really going to have to rely on inference rules, rather than just equivalence principles.