2
$\begingroup$

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.

  • 0
    Let $P(x)$ be $x$ is even and let $Q(x)$ be $x$ is odd.2011-11-01

2 Answers 2

4

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?

  • 0
    oh, I guess I had misunderstood then! I thought that when you wrote $\forall x\,P(x)$, it just couldn't be false. I thought it was a statement, saying, you have to pick a$P(x)$that always returns true for a given set. Thanks for the explanation!2011-11-02
3

$\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$.

  • 0
    And rewriting $\{0,1\}$ as $\{0 \mod 2, 1 \mod 2\}$, we have another "solution"!2011-11-01