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.

Is $\forall x(P(x) \vee Q(y))$ the same as $(\forall x P(x)) \vee Q(y)$?

I understand that if I had $\forall x(P(x) \vee Q(x))$, that it is not the same as $(\forall x P(x)) \vee (\forall x Q(x))$. However the presence of a second variable is really throwing me off, and I don't understand how to think up an example to see if they are equivalent.

share|improve this question

1 Answer 1

up vote 2 down vote accepted

For a formal proof start with $$\forall x, (P(x) \lor Q(y)) \vdash (\forall x, P(x)) \lor Q(y)$$ and apply the law of excluded middle on $Q(y)$ to split that into two statements $$Q(y), [\forall x, (P(x) \lor Q(y))] \vdash (\forall x, P(x)) \lor Q(y)$$ and $$\lnot Q(y), [\forall x, (P(x) \lor Q(y))] \vdash (\forall x, P(x)) \lor Q(y),$$ the first is immediate: just introduce $x$ and take the right disjunction and you prove $Q(y)$, for the second, introduce x and eliminate the possibility of $Q(y)$ using the hypothesis to get $P(x)$ which you then generalize to get $\forall x, P(x)$. This proves $(\forall x, P(x)) \lor Q(y)$ from $\forall x, (P(x) \lor Q(y))$. Proving the converse implication is much easier.

It might be interesting to note (and part of the reason it's difficult to see why this is true) that this is not intuitionistically provable. In constructive logic it matters which of the disjunctions $\forall x, (P(x) \lor Q(y))$ are taken depending on $x$, the second formula $(\forall x, P(x)) \vee Q(y)$ does not allow such dependencies, so it's actually a much stricter formula.

share|improve this answer
1  
Your explanation looks complete. I'd like to know your idea about mine. Honestly, I think you did it completely, so maybe my answer is not necessary for the OP. Thanks +1 –  Babak S. Jan 28 '13 at 8:23
1  
@BabakSorouh, I wrote this before you deleted: I think you have in mind the same idea as me but you didn't say why the question "different values for x would affect the Q(y)?" comes from interpreting the logical formula. It's always a good idea to work out actual examples of logical formulas like you've shown though +1. –  user58512 Jan 28 '13 at 8:29
1  
Yes! I had. Not being a native person makes me not to say what I think properly as it should be. :) –  Babak S. Jan 28 '13 at 8:32

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.