1

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.

1 Answers1

1

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)]$

  • How would this work though? Aren't you completely switching the for all Y there exists a Z part in the implied half. –  Nov 01 '13 at 12:31
  • @Requiem: Good catch...I've expanded my description to complete the derivation. –  Nov 01 '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? –  Nov 05 '13 at 19:23