Logic Behind Epsilon-Delta Proofs (Single-Variable Calculus)

Question

Most of what I am asking is based off this (fairly popular) article I've read here : https://bobobobo.wordpress.com/2008/01/20/how-to-do-epsilon-delta-proofs-1st-year-calculus/, but most lecturers, use this same process to tackle epsilon-delta proofs, so what I am asking should be pretty universal to epsilon delta proofs.

---

Epsilon-Delta Definition of a Limit

I've just referenced this here, for some added context if needed.

$$ \lim_{x \to a} f(x) = L \Leftrightarrow \forall \epsilon >0 ,\exists \delta>0 \ni \forall x \in D(0 < |x-a| < \delta \implies |f(x)-L| < \epsilon)$$

The Key Concept to $\epsilon - \delta$ Proofs

Now the key concept to epsilon-delta proofs is that you have to relate epsilon and delta. You have to show that if $0 < |x-a| < \delta$ then we can conclude that $ |f(x)-L| < \epsilon$

---

How Most People Normally Tackle $\epsilon - \delta$Proofs

When required to formally prove an arbitrary limit $$ \lim_{x \to a} f(x) = L $$

Normally what most people tend to do is start out with a statement in the form $$0 < |x-a| < \delta \implies |f(x)-L|<\epsilon$$ and they eventually work their way (as the article I linked above does) to a statement of the form $$ 0 < |x-a| < \delta \implies |x-a| < \delta$$

(This result, that they arrive is the part of the proof that I'm questioning. I don't think it to be a mathematically rigorous completion of the proof, and I'll explain why I think so further below)

They claim that this result that they've arrived at completes the proof as they have arrived at a statement that "cannot be argued against". This is a quote from the article I linked (where they've done a different example, but the underlying logic is the same) on why this is seemingly "correct" :

Wonder of wonders! It “WORKS”, because the statement has now changed from:

“IF x is within δ units of 5 . . . THEN ( 3x – 3 ) is within ε units of 12.”

To: “IF x is within ε/3 units of 5, THEN x is within ε/3 units of 5.”

Which cannot be argued against.

Remember, its not stupid. Its “rigorous”.

But I argue that what they've done is incorrect. Reaching something that is obviously true is not a proof!

---

To illustrate my point, I'm going to bring in some Propositional Logic to show why I think this way of constructing a proof fails.

$$Let \ \ \ p = 0 <|x-a| <\delta$$ $$Let \ \ \ q = |f(x)-L| <\epsilon$$

From Propositional Logic, what people have essentially done using this proof "process" is start out with a statement in the form $p \implies q$, and worked their way into a statement of the form $p \implies p$, and they state that because they've reached something that's obviously true, the implication they started out with must be true, which is WRONG!

This is wrong because if we recall from Propositional Logic that the possible truth values of statements $p$ and $q$ can be represented by a truth table.

$$ \begin{array}{cc|ccc} p&q&p&\implies&q\\\hline T&T&&\mathbf{T}&\\ T&F&&\mathbb{F}&\\ F&T&&\mathbf{T}&\\ F&F&&\mathbf{T}& \end{array} $$

As you can see in the second row of the truth table given $p = T$ and $q=F$, we can see that $(p \implies q) = F$. Now getting back to the way the above $\epsilon - \delta$ proof was handled, nothing has been done to account for this case. We have not shown $q$ to be true via this proof process, as only if we have shown $q$ to be true via this process then only is $p \implies q$ satisfied for all possible values for $p$ and $q$, i.e. we have not shown $|f(x) -L| < \epsilon$, so how could could this be a mathematically rigorous complete proof?

---

If any of you have any more intuitive/efficient or more mathematically rigorous ways of proving limits using the $\epsilon - \delta$ definition I would love to see them, as this seems to be the general "go-to" method of proving limits using $\epsilon - \delta$

Answer 1

I think you have slightly misunderstood the logical structure of this proof. This is in fact a logically correct proof, albeit I do not think this is the best way to approach a limit proof. It is simply showing that $p\to q$ is logically equivalent to $p\to p$,a tautology. So basically $p\to q$ always has the value $T$ and so we consider the statement proved. Your use of a truth table is misleading as it implies that all possible truth values are possible in our system, but as the proof has shown that is not the case.

Answer 2

See my comments, but to rephrase them:

We want to be able to find (as in the article linked to) for every given positive number $\epsilon > 0$ (statement $q_{\epsilon}$) at least one positive number $\delta >0$, such that for all positive numbers $\le \delta$ (statements $p_\delta$), the condition involving the given $\epsilon$ is satisfied (i.e. for all such $\delta$, $p_{\delta} \implies q_{\epsilon}$).

The method of the proof of the article you linked to is not general, inasmuch as it is calculating the limit of a linear function, for which different manipulations are allowed compared to, say, a quadratic. Specifically I am referencing the pulling out of multiplicative constants from the absolute value bars. ($|3x-r| < 5 \epsilon \iff |x - \frac{r}{3}| < \frac{5}{3}\epsilon$, but what do we do if $|x\Gamma(x)| < \epsilon^2$ ?)

The point of the method though is that for any positive number, say 27, we can find another positive number, in the case of the article $\delta=\epsilon /3 = 9$, such that "$p_9$ True $\implies$ $q_{27}$ True".

(But note that we also could have taken $\delta$ = 0.000000001 or $\pi$ or 6.66, not just 9. However, there are infinitely many possible $\epsilon>0$, so that if we ever want to prove the statement for all $\epsilon$, we better come up with a way for any given $\epsilon$ to relate $\delta$ to $\epsilon$ in some pre-determined fashion, i.e. some statement that gives a possible value for a $\delta$ for any given $\epsilon$. In the case of the article $\delta = \epsilon/3$ works, but again so would $\delta =\frac{\epsilon}{ 70000}$.)

The article simplifies too much, exploiting the linearity of the function $f$ and the resulting simple condition $\delta=\epsilon/3$ to write the condition $p_\delta$ in terms of $\epsilon$, even though such an explicit rewriting is in general not possible.

The fact that the article says that "this cannot be argued against" without actually clearly explaining what is being argued for evinces, in my opinion, poor writing.

Hope this helps.

Answer 3

Your statement about proof is incorrect. What you state proof isn't is exactly what proof is. What they are doing is showing that the original formula is logically equivalent to a tautology, i.e. to truth. Equivalently, it is enough to show that it is logically implied by a tautology, as then it immediately follows that it is logically equivalent to a tautology. I would recommend, for (at least) the purposes of this, to not use a semantical argument (i.e. truth tables) to make this deduction.

Let's choose something simpler. Let's say you want to prove $(P\land Q) \to (P \lor Q)$, here's a proof: $$\begin{align} (P \land Q) \to(P \lor Q) & \impliedby (P \land Q) \to P \\ & \impliedby P \to P \\ & \impliedby \top \end{align}$$ The first step uses the one of the defining rules of $\lor$, $P \to (P \lor Q)$. The second, one of the defining rules of $\land$, $(P \land Q) \to P$. And the main driver is (an instance of) modus ponens (aka as "cut"), $$(P \to Q)\text{ and }(Q \to R) \implies (P \to R)$$ To state it explicitly, a formal proof is a sequence of applications of given rules that ultimately begins with a formula that is declared provable by fiat. More precisely (and a bit more generally), the relationship "$P$ is provable" is inductively defined and the base cases of the induction are the trivially provable formulae.

To be clear, the structure of their proof is more like: $$\begin{align} x+2x = 3x & \iff (1+2)x = 3x \\ & \iff 3x = 3x \end{align}$$ In other words they have a chain of "if and only ifs" that allows them to move either way. Or even more closely, it's "show $Q \iff P$ in context $P$ from which follows $(P \to Q) \iff (P \to P)$." Actually, to be even more precise, instantiating the existential quantifier, that is "choosing $\delta = \epsilon / 3$", is an $\impliedby$. At this point you can probably spell out the complete logical structure of their proof.

Epsilons and deltas don't change the above picture (while it does impact semantics, or rather quantifiers do). While you could certainly use more precise syntax, the general shape of their argument is fine. I agree with William Krinsman that indexing $\delta$ by $\epsilon$ is a crucial detail that is lost by typical syntax. Via (partially) Skolemizing, you can think of $\delta$ as a (Skolem) function of $\epsilon$. As William suggests, this is a stronger statement (although not in ZFC), but that's no problem if you find a proof. Personally, I'm a constructivist, so to me the statement is already asking for a function. Practically, the fastest way to do epsilon-delta proofs is to not do them by showing a broad class of functions is continuous, then just showing that the function is (locally) in that class. For coursework, you more or less are going to have to directly prove the the statement. I can pretty much guarantee that any example you come across in coursework that isn't refutable will reduce to picking a function of epsilon for delta.