4
$\begingroup$

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!

1 Answers 1

5

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$.

  • 0
    @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.2011-10-04