Logic – How to Prove For-All and There-Exists Negation

boolean-algebraepsilon-deltalogicpredicate-logic

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.

Best Answer

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 ϵ$."

Related Question