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'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|improve this question
add comment

1 Answer

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|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. –  Eupraxis1981 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? –  Eupraxis1981 Nov 5 '13 at 19:23
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.