# Formula so that $(\forall x \ \phi \rightarrow \forall x \ \psi) \rightarrow \forall x (\phi \rightarrow \psi)$ is not valid

I am looking for an example of a formula of the form in the title of this post which is not valid.

I am very much looking forward to your replies!

Essentially anything you try will work! For example, the following formula is not valid, when $$P$$ and $$Q$$ are unary relation symbols: $$(\forall x\, P(x) \rightarrow \forall x\, Q(x))\rightarrow \forall x\, (P(x)\rightarrow Q(x))$$

For a countermodel, let $$M = \{a,b\}$$, with $$P^M = \{a\}$$ and $$Q^M = \emptyset$$.

• Thanks, but I'm not sure if I really get what you mean. Is $\forall x P(x)$ false because it's not true for the assignment x=b, therefore we can conclude that $\forall x Q(x)$ is true (although it's false), so the left side of the implication is true.(?) But the right side is false since $P(a)$(which equals $\{a\}$) and $P(b)$(which equals $\{a\}$) don't imply $Q(a)$ (which equals $\emptyset$) and $Q(b)$(which equals $\emptyset$) respectively? – Studentu Nov 2 '18 at 22:13
• $P(b)$ is false, so $\forall x P(x)$ is false, so $\forall x P(x) \rightarrow \forall x Q(x)$ is true. The point is that if $A$ is false, then $A\rightarrow B$ is true, regardless of the truth value of $B$. – Alex Kruckman Nov 2 '18 at 22:18
• On the other hand, $P(a)\rightarrow Q(a)$ is false, so $\forall x(P(x)\rightarrow Q(x))$ is false. – Alex Kruckman Nov 2 '18 at 22:21
• In total, the big implication is false, since the first part is true and the second part is false. – Alex Kruckman Nov 2 '18 at 22:22
• Yeah, then I got you right. Thank you! – Studentu Nov 3 '18 at 2:51

Consider $$(\forall x(x\in\{\varnothing\})\Rightarrow\forall x(x\in\varnothing))\Rightarrow\forall x(x\in\{\varnothing\}\Rightarrow x\in\varnothing)\tag 1$$ $$\forall x(x\in\{\varnothing\})$$ is false, hence $$\forall x(x\in\{\varnothing\})\Rightarrow\forall x(x\in\varnothing)$$ is true. On the other hand, $$\forall x(x\in\{\varnothing\}\Rightarrow x\in\varnothing)$$ is false, hence $$(1)$$ is false.

• Thank you very much, that did help me a lot! – Studentu Nov 2 '18 at 22:14

Rather than approaching it in an ad hoc way, just negate the formula:

$$\lnot\bigg((\forall x \ \phi \rightarrow \forall x \ \psi) \rightarrow \forall x (\phi \rightarrow \psi)\bigg)$$

$$(\forall x \ \phi \rightarrow \forall x \ \psi) \land \lnot\bigg(\forall x (\phi \rightarrow \psi)\bigg)$$

$$(\lnot \forall x \ \phi \lor \forall x \ \psi) \land \exists x \lnot\bigg(\phi \rightarrow \psi\bigg)$$

$$(\exists x \ \lnot \phi \lor \forall x \ \psi) \land \exists x (\phi \land \lnot \psi)$$

$$\exists x \ \lnot \psi$$ contradicts $$\forall x \ \psi$$, so the left hand side can be simplified

$$(\exists x \ \lnot \phi) \land \exists x (\phi \land \lnot \psi)$$

So you just need an example where $$\phi$$ is sometimes false, sometimes true, and somewhere it is true that $$\psi$$ is false.

So $$\phi ~:~ \text{x is even}$$ is sometimes true and sometimes false. Pick a point where it is true, $$x=4$$, and make $$\psi$$ false there, $$\psi(x) \equiv (x \ne 4)$$.

• Clever approach, thank you! – Studentu Nov 3 '18 at 16:11