Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I've been stuck on this question for the better part of the day, and I've succumbed to asking for help. I'm not sure how to go about it honestly. I've tried to do the contrapositive to prove it, but I get stuck and end up at a dead end.

The problem is as follows: $$ [(\forall y \forall z \space p(y,z)) \space \vee \space (\exists z \forall y \space q(y,z))] \space \to \space \forall y\exists z(p(y,z) \space \vee \space q(y,z)) $$

I'm supposed to to prove this is valid using interpretations. I can not replace the implies either.

share|cite|improve this question
up vote 2 down vote accepted

Could you just pull out the quantifiers from the anacedent? Since $\forall y$ is in each anacendent condition, $\forall xp(x) \vee \forall x q(x) \rightarrow \forall x (p(x) \vee q(x))$ Also, the universal quantifier implies the existential quantifier, so $[(\forall y \forall z \space p(y,z))] \rightarrow [(\forall y\exists z \space p(y,z)) ]$ Also,$(\exists z \forall y \space q(y,z))] \to (\forall y \exists z \space q(y,z))]$ Since the $z$ that makes the second form true, is the same as the $z$ from the first form (note the converse is not true). Therefore you get the series of deductions:

$[(\forall y \forall z \space p(y,z)) \space \vee \space ( \exists z\forall y \space q(y,z))] \to [(\forall y \exists z \space p(y,z)) \space \vee \space (\forall y \exists z \space q(y,z))] \to \forall y \exists z \space [p(y,z) \space \vee \space q(y,z)]$

share|cite|improve this answer
How would this work though? Aren't you completely switching the for all Y there exists a Z part in the implied half. – Requiem Nov 1 '13 at 12:31
@Requiem: Good catch...I've expanded my description to complete the derivation. – user76844 Nov 1 '13 at 12:49
@Requiem do you still need an answer to this, or was the above along the lines of what you were looking for? – user76844 Nov 5 '13 at 19:23

Your Answer


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.