Prove that $\neg \forall x P(x) \leftrightarrow \exists x \neg P(x)$

Question

I am reading "How To Prove It" by Velleman, the 2nd Edition.

At page 65 Velleman presents the "Quantifier negation rules"

$$\neg \exists x P(x) \text{ is equivalent to } \forall x \neg P(x) \tag{1}$$ $$ \neg \forall x P(x) \text{ is equivalent to } \exists x \neg P(x) \tag{2}$$

justifying them with some exemples.

Then he talks about various demonstration methods and at page 128, talking about demonstration strategies involving biconditionals, he proves by contraddiction the $(1)$:

• he first proves $\forall x \neg P(x) \to \neg \exists x P(x)$: he assumes $\forall x \neg P(x)$ and $\exists x P(x)$ (i.e. the negation of $\neg \exists x P(x)$), then from $\exists x P(x)$ he derives $P(x_{0})$, that contraddicts $\forall x \neg P(x)$ beacause from this he derives $\neg P(x_{0})$;
• after he proves $\neg \exists x P(x) \to \forall x \neg P(x)$: he assumes $\neg \exists x P(x)$ and takes an arbitrary $x$ and supposes $P(x)$, from that he derives $\exists x P(x)$ that contraddicts $\neg \exists x P(x)$, from that he concludes $\neg P(x)$ and since $x$ is arbitrary he arrives at $\forall x \neg P(x)$

Velleman says that in a similar way it can be proved also $(2)$. But I am not able to do it. How can I prove $(2)$ in a similar way?

EDIT. There is a screen of pages 129-130 where Velleman proves $(1)$. I would like to $(2)$ in a similar way. https://images2.imgbox.com/05/82/VqLyVoH0_o.png

Answer 1

This seems to me to be a proof of the semantic validity of these statements (the word derivation threw me off slightly, made me think we wanted an axiomatic proof.) I will rewrite one those he's given in a way that I think is more illuminating and should help you work out the rest.

So for $¬ \exists x P(x) \to \forall x¬P(x)$

Assume we have that there is some way of putting variables (a variable assignment) into (a) $¬ \exists x P(x)$ and (b) $¬ \forall x¬P(x)$ that makes both of them true.

(a) gives us that there is no x such that $P(x)$ is true.

(b) gives us that there exists some x such that $¬P(x)$ is false (as it is not true for all x,) which means that for that x, $P(x)$ is true, giving a contradiction with a.

Therefore whenever (a) is true, (b) must be false and so we have the given implication.

I personally would have done this more directly but if he's looking at contradictions of this sort this is what you want to do.

As a general tip for proving validity, you want to assume there is some way of putting variables into the sentence that makes it false, then work through what the constituent parts to show that it leads to a contradiction in the logic of the sentence. Ted Sider has a good method in his Logic for Philosophy.

$¬ \forall xP(x) \to \exists x¬P(x)$

We take (a) $¬ \forall xP(x)$ and (b) $¬\exists x¬P(x)$ as true under some variable assignment. (a) implies that there is some x such that $¬P(x)$ (as it's not true for all x.) Then (b) implies that there is no x such that $¬P(x)$ (as there does not exist an x for which it is true,) yielding the contradiction you seek.

$\exists x¬P(x) \to ¬ \forall xP(x)$

We assume there is some variable assignment that makes $\exists x¬P(x)$ true. Then this gives us that there is some $x_0$ for which $¬P(x_0)$ is true.

(I don't like his x is arbitrary so we have $¬ \forall xP(x)$ but if you wanted to conclude that way here, then you could.) The way I would conclude this is assume $\forall xP(x)$, but you've just shown that there exists an $x_0$ for which $¬P(x_0)$ is true and so $P(x_0)$ is false, so contradiction.

Answer 2

Here is an outline of how you can give a proof of (2) that is similar to the proof you quoted of (1):

For the $\to$ direction: Assume $\neg\forall x P(x)$ and $\neg \exists x \neg P(x)$. To get a contradiction, prove $\forall x P(x)$, which will contradict your assumption $\neg\forall x P(x)$. You can do this by taking an arbitrary $x$ and proving $P(x)$. To prove $P(x)$, use proof by contradiction.

For the $\leftarrow$ direction: This direction is easier. Assume $\exists x \neg P(x)$ and $\forall x P(x)$. Since $\exists x \neg P(x)$, you can let $x_0$ be something such that $\neg P(x_0)$. You can take it from there.

However, there is another possibility that might be easier: You can use (1) to prove (2). Hint: Start by rewriting $\neg\forall x P(x)$ as $\neg \forall x \neg\neg P(x)$.