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.

  • 1
    I would suggest trying out some examples to see how this works.2011-11-01
  • 3
    @Sasha, really?2011-11-01
  • 1
    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.2011-11-01
  • 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
    @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!2011-11-01
  • 0
    Another question, $\forall x : P(x) \lor \forall x : Q(x)$, is this the same x for both equations?2011-11-01
  • 0
    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.2011-11-01
  • 0
    $\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.2011-11-01
  • 0
    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!2011-11-01
  • 0
    If you pick $P(x)$ as "$x$ is even", then certainly it is not the case that $\forall x\,P(x)$ is false, and $\forall y\,P(y)$ is also false, but how does that make you think the example isn't "valid"? It just means that $\forall x\,P(x)\lor \forall x\,Q(x)$ evaluates to false. So what about that? It's a perfectly good truth value, and we can compare it to the truth value $\forall x\,(P(x)\lor Q(x))$ evaluates to, to see whether they are the same. If they aren't, then the entire $\Leftrightarrow$ will evaluate to false ...2011-11-01
  • 0
    [OOPS! The "certainly it is not" above should not have the "not". Please pretend it isn't there!] ... and to prove $\text{blah}\Leftrightarrow\text{blah}$ means to convince ourselves and the reader that _no matter how we pick $P$ and $Q$_, the $\Leftrightarrow$ will evaluate to true. Finding even one $P$ and $Q$ where it evaluates to false means that we have a _counterexample_, i.e. what we're being asked to prove does not actually hold. Thus, there'd better not be any proof of it, and it would be foolish to try to find one.2011-11-01
  • 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