# Why can negation pass through multiple quantifiers? [Chartrand P52-53, Velleman P65]

I'm mindful of the Quantifier Negation Laws and Negating a statement that ... several quantifiers.

• $\neg \; \exists \; P(x) \equiv \forall \; x \; \neg \; P(x)$
• $\neg \; \forall \; x \; P(x) \equiv \exists \; \neg \; P(x)$

How and why can negation permeate/pervade through (What's the proper term?) the quantifiers?
In other words, how does negation transform $(♦) \to (♣)$? To wit, how does negation effect $(♣)$?

For example, I negate the definition of uniform continuity :

$$\color{#FF4F00}{\neg}(\; \forall \; e > 0 \: \exists \; d > 0 \: \forall \; c \in S \: \forall \; x \in S \: {\LARGE{[}} \; |x - c|< d \implies |f(x) - f(c)| < e {\LARGE{]}} \;) \tag{♦}$$

$$\iff \exists \; e > 0 \; \color{#FF4F00}{\neg}( \; \exists \; d > 0 \: \forall \; c \in S \: \forall \; x \in S \: {\LARGE{[}} \; |x - c|< d \implies |f(x) - f(c)| < e {\LARGE{]}} \;)$$

$$\iff \exists \; e > 0 \; \exists \; d > 0 \: \color{#FF4F00}{\neg}(\; \forall \; c \in S \: \forall \; x \in S \: {\LARGE{[}} \; |x - c|< d \implies |f(x) - f(c)| < e {\LARGE{]}} \;)$$

After the negation suffuses the first four quantifiers and converts each, $(♦)$ becomes: $$\exists \; e > 0 \: \forall \; d > 0 \: \exists \; c \in S \: \exists \; x \in S \:\: \color{#FF4F00}{\neg}{\LARGE{[}} \; |x - c|< d \implies |f(x) - f(c)| < e {\LARGE{]}} \tag{♣}$$

By virtue of Intuition behind "If P then Q" = "Q or Not P ", \begin{align} \color{#FF4F00}{\neg}{\LARGE{[}} \; |x - c|< d \implies |f(x) - f(c)| < e {\LARGE{]}} &\equiv \color{#FF4F00}{\neg}{\LARGE{[}} \; \neg( \; |x - c|< d \; ) \: \vee \:|f(x) - f(c)| < e {\LARGE{]}} \\ &\equiv \color{#FF4F00}{\neg}\neg( \; |x - c|< d \; ) \: \wedge \: \color{#FF4F00}{\neg}( \;|f(x) - f(c)| < e \; ) \\ &\equiv \; |x - c|< d \; \: \wedge \: |f(x) - f(c)| \ge e \end{align}

-
The "intuition behind 'if P, then Q' is equivalent to : 'not P or Q'" is not a riddle: it can be solved in two ways, if you accept classical logic : (i) truth-tables shows you that the two are equivalent; (ii) the connective $P \rightarrow Q$ is often defined as $\lnot P \lor Q$. – Mauro ALLEGRANZA Feb 15 '14 at 8:40
If you know that there doesn't exist a pink Lamborghini, then you would also know that for any Lamborghini it isn't pink. It just make sense, to use negation in this way. Another way to look at this is via finite spaces/universes, that is, in such case $\forall x.\ P(x) \equiv \bigwedge_x P(x)$ and then use the standard De Morgan's laws. – dtldarek Feb 15 '14 at 8:48
@Taladris - in your comment there is a typo; it must be : $\lnot \forall x \equiv \exists x \lnot$. – Mauro ALLEGRANZA Feb 15 '14 at 11:47
@MauroALLEGRANZA: I just copied the OP formula withou checking it :/. Thank you for noticing. – Taladris Feb 15 '14 at 14:12
@MauroALLEGRANZA: To everyone: Thank you for the observation. I beg for your forgiveness for my typo which I've just emended. – Timere Feb 16 '14 at 7:16

I don't quite understand your question, but I'd like to note that

1) $\forall e > 0 : P(e)$ is a shorthand for $\forall e : (e > 0 \implies P(e))$

2) $\exists d > 0 : P(d)$ is a shorthand for $\exists d : (d > 0 \land P(d))$

Therefore $\forall e>0 \; \exists d > 0 : P(e, d)$ is a shorthand for

$\displaystyle \forall e : (e>0 \implies (\exists d: d>0 \land P(e,d)))$

Negating gives

\begin{align} \neg \forall e : [e>0 \implies (\exists d: d>0 \land P(e,d))] &\equiv \exists e: \neg \: [e>0 \implies (\exists d: d>0 \land P(e,d))] \\ &\equiv \exists e : \neg \: [\neg(e > 0) \lor (\exists d: d>0 \land P(e,d))] \\ &\equiv \exists e : e > 0 \land \neg \: (\exists d: d>0 \land P(e,d)) \\ &\equiv \exists e : e > 0 \land \forall d: \neg [d>0 \land P(e,d)] \\ &\equiv \exists e : e > 0 \land \forall d: [\neg (d>0) \lor \neg P(e,d)] \\ &\equiv \exists e : e > 0 \land \forall d: [d>0 \implies \neg P(e,d)] \end{align}

where the latter, using shorthand, looks like $\exists e > 0 \; \forall d > 0 \; \neg P(e, d)$

-
... and so amount to : $\lnot \forall e \exists d P(e,d)$ is equivalent to : $\exists e \forall d \lnot P(e,d)$, exactly as the OP said. – Mauro ALLEGRANZA Feb 15 '14 at 12:31
@MauroALLEGRANZA yes, I just wanted to give a "deeper" justification of that fact – dani_s Feb 15 '14 at 12:38
@dani_s: Thanks. I've enlarged on my OP. Do you apprehend my question now? Please advise. I see that you've performed the negation differently than I have? – Timere Feb 16 '14 at 7:21