Predicates and Quantifiers about Show Precedence of Quantifiers

Question

Predicates and Quantifiers Questions

for all x P(x) /\ for all x Q(x)

for all x(P(x) /\ Q(x))

why is not logically equivalent?

Answer 1

Proof in the forward direction $\forall x \; (\phi(x) \implies \psi(x)) \implies(\forall x \, \phi(x) \implies \forall x \,\psi(x))$.

1. $\forall x \; (\phi(x) \implies \psi(x))$
2. $\forall x \, \phi(x)$
3. $\phi(a)$ (U.I. 2, a\x)
4. $\phi(a) \implies \psi(a)$ (U.I. 1, a\x)
5. $\psi(a)$ (M.P. 3, 4)
6. $\forall x \, \psi(x)$ (U.G. 5)
7. $\forall x \, \phi(x) \implies \forall x \, \psi(x)$ (conditional proof, 2 - 6)
8. $\forall x \; (\phi(x) \implies \psi(x)) \implies(\forall x \, \phi(x) \implies \forall x \,\psi(x))$ (conditional proof, 1-7)

Please note that we are only able to preform step 6 because both the Universal instantation and its generalization occur within the same conditional proof.

Now a counter example for the converse: let $\phi(a)$ be true and $\phi(b)$ be false and let $\psi(a)$ and $\psi(b)$ both be false

Then $\forall x \, \phi(x)$ is false, so $\forall x \, \phi(x) \implies \forall x \, \psi(x)$ is true.

but $\lnot (\phi(a) \implies \psi(a))$, so $\forall x \; (\phi(x) \implies \psi(x))$ is false. So we have a true statement implying a false statement showing that the converse does not hold and we have a counter example

Answer 2

The first statement:

for all x : P(x) and for all x : Q(x) 

may not refer to the same domain for x so it could be written:

1. for all x in Y : P(x) and for all x in X : Q(x) where X != Y

or

2. for all x in Y : P(x) and for all x in X : Q(x) where X = Y

whereas:

for all x : P(x) and Q(x) 

refers to the same x and is equivalent to 2 above.