# Proof of for-all / there-exists “negation”?

I was recently playing around with delta-epsilon proofs for limits, which, when true, have the following form:

$$\forall \epsilon > 0, \exists \delta>0 , p \implies q$$

Where $p = (\text{for all$x$, }0 < |x-a| < \delta)$ and $q = (|f(x) - L| < \epsilon)$ (this isn't directly relevant to my question, just showing what these... events? Statements? Propositions? I don't know the word -- what they look like).

I didn't include the actual thing being shown true above about $f(x)$ (I don't know where it'd go), but the more informal statement is "The limit of $f(x)$ as $x$ approaches $a$ is equal to $L$ if for all $\epsilon > 0$ there exists a $\delta>0$ such that for all $x$, $0 < |x-a| < \delta$ implies $|f(x)-L|<\epsilon$."

I wanted to prove a scenario where the limit was knowingly false ahead of time, and it took me some time to notice that this was the new statement to show in order to prove a limit false:

$$\exists \epsilon > 0, \forall \delta>0 , p \not\implies q$$

Now it's something more like, "The limit of $f(x)$ as $x$ approaches $a$ is not equal to $L$ if there exists an $\epsilon > 0$ such that for all $\delta>0$, for all $x$ $0 < |x-a| < \delta$ does not imply $|f(x)-L|<\epsilon$."

My questions:

1. Is there a formal proof or understanding as to why negation changes for-alls into there-exists and vice-versa?

2. I'm a little unsure why De Morgan's laws don't seem to apply between the "statements" (apologies for my imprecision, I don't know what any of these things are called). For instance could we not think of it as $(\forall \epsilon > 0) \land (\exists \delta>0) \land (p \implies q)$ as in, all of these things must be true -- the epsilon condition must be true AND the delta condition must be true AND $p$ must imply $q$. Then if we negate it, why doesn't it become something like $(\exists \epsilon > 0) \lor (\forall \delta>0) \lor (p \not\implies q)$ as in, the epsilon condition must be true OR the delta condition must be true OR $p$ must not imply $q$. I know intuitively this isn't the case but I don't know why, since the original statement makes sense to me as a chain of ANDs but the negation... still feels like it should be a chain of ANDs whereas De Morgan's laws normally have you invert them to ORs.

• Not answering the questions you asked - but upvoting for your accurate rendering of these statements in English prose. That's way more important than being able to manipulate the logical symbols. – Ethan Bolker Mar 1 '18 at 14:54

Is there a formal proof or understanding as to why negation changes for-alls into there-exists and vice-versa?

Yes; the rules are very simple:

$\lnot \forall x$ is equivalent to $\exists x \lnot$

and

$\lnot \exists x$ is equivalent to $\forall x \lnot$.

Finally: $\forall x$ is equivalent to $\lnot \exists x \lnot$ and vice versa.

The formal proof needs a formal system: predicate logic.

An informal proof is quite easy: if not all the balls in the box are black, this means that there is some ball in the box that is not black.

In the same way: if all the balls in the box are black, this means that there are no balls in the box that are not black.

Having managed the quantificational part, we have to consider also the propositional part.

In negating the statement, you have correctly "moved inside" the negation sign, starting from $\lnot ∀ϵ>0,∃δ>0, ∀x \ \ldots$ and ending with: $∃ϵ>0,∀δ>0, ∃x \ \lnot \ldots$

The last step needs the tautological equivalence between:

$\lnot (p \to q)$ and $(p \land \lnot q)$.

So, in conclusion, we have:

"The limit of $f(x)$ as $x$ approaches $a$ is not equal to $L$ if there exists an $ϵ>0$ such that for all $δ>0$ there is an $x$ such that: $0<|x−a|<δ$ and $|f(x)−L| \ge ϵ$."

• What does it mean when the not symbol is off to the right of the first symbol? (whatever these are called) "If not all are x, then there exists something that is not x" and "if there doesn't exist x, then all are not x"? – user536260 Mar 1 '18 at 14:57
• I understand that $\lnot(p \land \lnot q)$ is the same as $(p \land \lnot q)$, but what I don't understand is what the commas in between the (statements?) represent. I would have normally interpreted them as "informal" ANDs that would negate with De Morgan's laws but this doesn't appear to be the case? – user536260 Mar 1 '18 at 15:01
• @user536260 - Not clear... the negation sign applies to formulas (sentences) and not to terms (predicates or variables). Thus, when we say "$x$ is not Black", we have to translate it as $\lnot (\text {Black}(x))$ and not as $(\text {not-Black}(x))$. – Mauro ALLEGRANZA Mar 1 '18 at 15:06
• I probably made a typo in my comment (I meant to use the OR symbol in the first one), what I meant was (p implies q) is the same as (not p OR q), and its negation is (p AND not q). (However this particular point isn't related to my question). – user536260 Mar 1 '18 at 15:09
• @user536260 - Yes; comma are unnecessary. They can improve readibility, but in the formal version is better to use parentheses: $\forall \epsilon > 0 \ \exists \delta > 0 \ \forall x \ [(0<|x−a|<δ) \to (|f(x)−L| < ϵ)]$. – Mauro ALLEGRANZA Mar 1 '18 at 15:15