Distribution of universal quantifiers over implication

Question

I want to prove that $∀x(φ(x)⟹ψ(x))$ implies $∀x(φ(x))⟹∀x(ψ(x))$. I read they are not equivalent, but I am not sure why. I tried the following:

1. $∀x(φ(x)⟹ψ(x))$
2. $⟹[φ(a)⟹ψ(a)]$ is true.
3. $⟹φ(a)$ is true.
4. $⟹∀x(φ(x))$ (by universal generalization of 3.)
5. $⟹φ(a)$ (by universal instantation of 4. and 3.)
6. $⟹ψ(a)$ (by 2.)
7. $⟹∀x(φ(x))$
8. Finally $[∀x(φ(x)⟹ψ(x))]⟹[∀x(φ(x))⟹∀x(φ(x))]$

I can't think of a counterexpample to show that they are not equivalent. Any hints would be greatly appreciated.

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.

An improper use use of Universal Generalization would be

1. $\forall x \; \phi(x)$(premise)
2. $\phi(a)$
3. $\phi(a) \implies \varphi(a)$ (assumption, begin conditional proof)
4. $\varphi(a)$
5. $\forall x \; \varphi(x)$

This is incorrect because 4. is only true because 3 is true. i.e. we should have discharged the assumption and then we could have generalized. So it would properly look like

1. $\forall x \; \phi(x)$(premise)
2. $\phi(a)$
3. $\phi(a) \implies \varphi(a)$ (assumption, begin conditional proof)
4. $\varphi(a)$
5. $(\phi(a) \implies \varphi(a))\implies \varphi(a) $
6. $\forall x \; (\phi(x) \implies \varphi(x))\implies \varphi(x))$

Now a counter example for the converse:

1. $\phi(a) \land \lnot \phi(b) \land \lnot \psi(a) \land \lnot \psi(b)$ (premise)
2. $\phi(a) \land \lnot \psi(a)$ (Simp., 2)
3. $\lnot(\psi(a) \implies \psi(a))$ (M.I./D.M., 3)
4. $\exists x\, \lnot(\psi(x) \implies \psi(x))$ (E.G. 4)
5. $\lnot \forall x \, (\psi(x) \implies \psi(x))$ (D.M. for Quantifiers, 5)
6. $\lnot \phi(b)$ (Simp., 2)
7. $\exists x \, \lnot \phi(x)$ (E.G, 7)
8. $ \lnot \forall x \, \phi(x)$ (D.M. for Quantifiers, 8)
9. $ \lnot \forall x \, \phi(x) \lor \forall x \, \psi(x)$ (Add., 9)
10. $\forall x \, \phi(x) \implies \forall x \, \psi(x)$ (M.I., 10)
11. $(\forall x \, \phi(x) \implies \forall x \, \psi(x))\land \lnot \forall x \, (\psi(x) \implies \psi(x)) $ (Conj., 11, 6)
12. $\lnot [(\forall x \, \phi(x) \implies \forall x \, \psi(x))\implies \forall x \, (\psi(x) \implies \psi(x))]$ (M.I., D.M., 12)
13. (1) is a counter example

Of course a counter example doesn't need to be shown in this way, but I'm not sure how else to show that it is in fact a counter example.

Answer 2

The argument you give is broken, for reasons stated in the comments.

Here is a hint for how to approach the problem:

Suppose we assume both $$(*)\quad\forall x(\varphi(x)\implies \psi(x))$$ and $$(**)\quad \forall x(\varphi(x)).$$ What do we know if $\forall x(\psi(x))$ happens to fail? Well, by definition this would mean $\exists x(\neg\psi(x))$. Let $a$ be such an $x$; what does $(*)$ tell us about $a$? Why does this contradict $(**)$?

Answer 3

For a counterexample to show that the two forms are not equivalent, you can let $\varphi(x)$ mean "$x$ is even" and $\psi(x)$ mean "$x$ is odd" (say, in an universe where the quantifiers range over $\mathbb N$).