Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

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

2 Answers 2

up vote 3 down vote accepted

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.