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.

Are the following two equivalent:

$$ \forall x \space \exists y \space [ \space A(x) \rightarrow B(y) \space ] $$

and

$$ \forall x \space [ \space A(x) \rightarrow \exists y \space B(y) \space ] $$

If so, is one preferred to the other?

Thanks!

share|improve this question

1 Answer 1

up vote 5 down vote accepted

They are equivalent. This is perhaps easiest to see intuitively by looking at their negations, $$\exists x\forall y [A(x) \land \lnot B(y)]$$ and $$\exists x [A(x) \land \forall y (\lnot B(y))]:$$ each of them fails iff there is some $x$ such that $A(x)$ holds, but $B(y)$ is false for all $y$.

Which is preferred depends on what you want to do with it. In a formal proof in predicate logic you’d have no choice. In an informal setting you’d use the one that better fits the way you want to think about the situation. The first is good when you’re thinking of $y$ more or less as a function of $x$: given an $x$, there’s a $y$ with an associated property. The second is good when you want to think of $$A(x) \to \exists y B(y)$$ as a statement about $x$ that happens to be true for all $x$.

share|improve this answer
    
What would you use in a formal proof in predicate logic? –  John Kurlak Oct 4 '11 at 3:02
    
@John: It might be either or both. A formal proof is a sequence of statements, each of which is either an axiom or a consequence of earlier statements by a formal rule of inference, you’d use whichever form was such a consequence and would be useful in deriving further statements. –  Brian M. Scott Oct 4 '11 at 3:12

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.