# Proof, is $\forall x : (P(x) \lor Q(x)) \Leftrightarrow \forall x : P(x) \lor \forall x : Q(x)$?

I have to prove if the following statement is true or false $$\forall x : (P(x) \lor Q(x)) \Leftrightarrow \forall x : P(x) \lor \forall x : Q(x)$$

I understand the first statement as, for every $x$, at least one of the functions $P$, $Q$ is true. For the second statement, at least one of the functions $P$, $Q$ is true for every $x$. Is this correct? When yes, how could I prove this? Using the distributive law will clearly render me the wrong result.

-
I would suggest trying out some examples to see how this works. – AMPerrine Nov 1 '11 at 21:05
@Sasha, really? – The Chaz 2.0 Nov 1 '11 at 21:08
Read again what you wrote here - there is the answer to your question. If you understand what is going on, creating a counterexample will be a piece of cake. – savick01 Nov 1 '11 at 21:09
Let $P(x)$ be $x$ is even and let $Q(x)$ be $x$ is odd. – The Chaz 2.0 Nov 1 '11 at 21:09

In think your understanding is right, except that "at least one of the functions $P$, $Q$ is true for every $x$" is somewhat ambiguous in ordinary English. It could mean either the left-hand side of your goal or the right-hand side of your goal.

Before you start figuring out how to prove the statement, you should give some thought to whether you would expect it to be true at all. If it's not true, searching for a proof will be futile. Is there some easy counterexample to find, perhaps?

For example, for every natural number it is true that it is even or that it is odd. What does your formula claim when applied to that fact?

-
@AMPerrine Guys, I think I found my problem. The problem is the way I read it. When I see $\forall x : P(x)$, I think, P(x) is true for every x, which means, this always returns true. $\forall x : Q(x)$, Q(X) is true for every x, this means this always returns true. Until here everything is perfectly fine. Here comes my mistake: I then think, so, I guess true $\lor$ true, is always true, right? Wrong! – Clash Nov 1 '11 at 21:40
Another question, $\forall x : P(x) \lor \forall x : Q(x)$, is this the same x for both equations? – Clash Nov 1 '11 at 21:40
true $\lor$ true is always true. I think your problem is that you're somehow ignoring the quantifiers. Can you repeat your argument with all of the "this"es unfolded? I think something might be buried there. – Henning Makholm Nov 1 '11 at 21:43
$\forall x : P(x) \lor \forall x : Q(x)$ is the same as $\forall s : P(x) \lor \forall t : Q(t)$ is the same as $\forall b : P(b) \lor \forall w : Q(w)$. The scope of each variable bound by $\forall$ is only the formula immediately after it. – Henning Makholm Nov 1 '11 at 21:45
I don't really get it then... $\forall x : P(x)$ means, P(x) is true for every x and $\forall y : Q(y)$ also means, Q(y) is true for every y. Then the whole thing has to be always true. If I pick P(x) as "x is even" and Q(y) as "y is odd", then it isn't a valid example for the integer numbers set, because P(x) is not true for every x. Where did I go wrong? Thanks! – Clash Nov 1 '11 at 21:49

$\forall x \in \{0,1\}$ either $x = 0$ or $x = 1$ but it isn't true that $\forall x \in \{0,1\}$, $x = 0 \$ or $\forall x \in \{0,1\}$, $x = 1$.

-
And rewriting $\{0,1\}$ as $\{0 \mod 2, 1 \mod 2\}$, we have another "solution"! – The Chaz 2.0 Nov 1 '11 at 21:13