# $\psi \to (\exists x)\phi(x) \Leftrightarrow (\exists x)(\psi \to \phi(x))$, etc

My textbooks states the following equivalences without proof:

$$(\psi \to (\exists x)\phi(x)) \Leftrightarrow (\exists x)(\psi \to \phi(x))$$ $$(\psi \to (\forall x)\phi(x)) \Leftrightarrow (\forall x)(\psi \to \phi(x))$$

At first blush they seem plausible, but they lead to the following additional equivalences, and these really make no sense to me:

$$((\forall x)\phi(x) \to \psi) \Leftrightarrow (\exists x)(\phi(x) \to \psi))$$ $$((\exists x)\phi(x) \to \psi) \Leftrightarrow (\forall x)(\phi(x) \to \psi))$$

I have tried to find proofs for the first two equivalences, without success.

Can someone point me to a proof of the first two equivalences?

Thanks!

Edit: Clarification: as Arturo Magidin noted, $\psi$ is such that $x$ is not free in it.

-
What are your logical axioms and inference rules? (Hilbert-style? Natural deduction? Sequent calculus? Something fourth?) – Henning Makholm Oct 10 '11 at 2:36
There is an assumption on $\psi$, right? It should not have $x$ unbound in it. – Arturo Magidin Oct 10 '11 at 2:45

The underlying idea behind several of these is that they leverage the requirement in first-order logic that the domain of discourse has to be nonempty, although this may not be obvious at first.

Consider $$\psi \to (\exists x) \phi(x)$$ where $\psi$ does not mention $x$. Assume this sentence is true in some structure. Then we can reason by cases:

• If $\psi$ is true in the structure, then $(\exists x)\phi(x)$ is also true, so there is an $x_0$ satisfying $\phi(x_0)$, and thus $(\exists x)(\psi \to \phi(x))$ is also true and witnessed by the same $x_0$.

• If $\psi$ is false in the structure, we can just take any element of the domain and call it $x_0$. Then $\psi \to \phi(x_0)$ holds, so again $(\exists x)(\psi \to \phi(x))$ holds.

Hence $$[\psi \to (\exists x) \phi(x)] \to [(\exists x)(\psi \to \phi(x))]$$ holds in every structure. The converse of this is easier to verify. Hence the two formulas in question are logically equivalent.

This sort of thing does not continue to work, in general, in free logic, where the domain of discourse is allowed to be empty. But it works fine in first-order logic, where it's a key part of putting formulas into prenex normal form.

-

Remember that an implication $p\to q$ is equivalent to $\neg p \lor q$. So $$(\forall x)\phi(x)\to \psi$$ is equivalent to $$\neg\bigl( (\forall x)\phi(x)\bigr) \lor \psi.$$ Now, what is the negation of $(\forall x)\phi(x)$? It's $(\exists x)\neg\phi(x)$. So the above is equivalent to $$\bigl( (\exists x)\neg\phi(x)\bigr) \lor \psi.$$ Since $\psi$ does not have $x$ in it, this in turn is equivalent to $$(\exists x)\bigl( \neg\phi(x)\lor \psi\bigr).$$ Now we apply the equivalence $p\to q$ and $\neg p\lor q$ again to get $$(\exists x)\bigl( \phi(x)\to \psi\bigr),$$ as claimed.

Alternatively: when will $(\forall x)\phi(x)\to \psi$ be false? It is false if and only if $\psi$ is false, but $\phi(x)$ holds for all $x$. When is $(\exists x)(\phi(x)\to\psi)$ false? It is false if and only if for every $x$, $\phi(x)\to\psi$ fails to hold; that is, if and only if for every $x$ $\phi(x)$ holds but $\psi$ is false: exactly the same condition.

I'll leave the second one to you.

-