Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
I would suggest trying out some examples to see how this works. –  AMPerrine Nov 1 '11 at 21:05
2  
@Sasha, really? –  The Chaz 2.0 Nov 1 '11 at 21:08
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. –  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
add comment

2 Answers

up vote 4 down vote accepted

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?

share|improve this answer
    
@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
show 3 more comments

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

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.