I was wondering if the below formulas are the same in a logical sense? Could I use the first one instead of the second and vice versa?
- $\forall x (P(x) \implies \exists y Q(y))$
- $\forall x \exists y (P(x) \implies Q(y))$
I was wondering if the below formulas are the same in a logical sense? Could I use the first one instead of the second and vice versa?
On
1 implies 2: Suppose 1. If $P(x)$ is false for all x then 2 is true. Otherwise $P(x)$ is true for at least one $x_0$ hence by 1 there exists $y_0$ such that $Q(y_0)$ is true. Now let $x$, the there exists $y$ (namely $y_0$) such that $P(x)$ implies $Q(y)$ therefore 2.
2 implies 1: Suppose 2. Let $x$, then there exists $y_0$ such that $P(x)$ implies $Q(y_0)$. In particular, if $P(x)$ is true then there exists $y$ (namely $y_0$) such that $Q(y)$ is true.
Hence 1 and 2 are indeed logically equivalent.
See Prenex normal form. They are equivalent