# Logic of the implication in $ε$-$δ$ proofs

Im confused by why epsilon delta proofs logically work.

An example is

Proof: Given $ε>0$, choose $δ = {ε\over3}$. For all $x$, if $0<|x−2|<δ$ then $|(3x−1)−5| < ε$.

That last part if $0<|x−2|<δ$ then $|(3x−1)−5| < ε$ LOOKS A LOT LIKE $P\to Q$ because of the "if then" but yet the proof in the book solves it like as if its $Q\to P$?:

\begin{align}|(3x−1)−5| &= |3x−6|\\ &= |3(x−2)|\\ &= 3|x−2|\\ &<3δ\\ &= 3\left({ε\over3}\right) \\ &= ε\end{align}

So my question is how come it looks like a $P\to Q$ proof but yet we start with $Q$ to show $P$?

• A lot of times since you are given an $\epsilon$ to work with and need to choose a delta, books will start with the epsilon statement, do some manipulations, and eventually give you a $\delta$ in terms of epsilon, i.e work backward in a strictly logical sense. This is how we figure out $\delta$. The actual proof itself (which may seem arbitrary at first) should start with someone giving a $\delta$ (given an epsilon) and then manipulating the $\delta$ statement to make it "look like" the $\epsilon$ statement. This is all phrased quite crudely, but I hope it can clear up some confusion. Oct 8 '17 at 18:48

You wrote: $$|(3x−1)−5| = |3x−6| = |3(x−2)| = 3|x−2|<3δ < 3(ε/3) = ε.$$ First, this ought to say $$|(3x−1)−5| = |3x−6| = |3(x−2)| = 3|x−2|<3δ = 3(ε/3) = ε.$$

When you write $$A = B = C= D <E =F = G$$ then you're proving that if all of the above "equals" signs and the "less-than-or-equal-to" sign are true, then $A < G$ is true.

The most basic way to prove a statement of the form "If $P$ then $Q$" is to assume $P$ and prove $Q$.

In this case $P$ is "$0<|x-2|<\delta$", and $Q$ is $|(3x-1)-5|<\epsilon$. Earlier in the proof we defined $\delta = \epsilon/3$.

So we assume $P$: Assume that the statement $0<|x-2|<\delta$ is true, and set out to show that $Q$ holds. We accomplish this by the string of inequalities

$$|(3x−1)−5| = |3x−6| = |3(x−2)| = 3|x−2|<3δ,$$

then we use $\delta = \epsilon/3$ to continue

$$3\delta = 3(\epsilon/3) = \epsilon.$$

Therefore the first term is less than the last, which is precisely $Q$.

• Thank you, that clears it up :) Oct 8 '17 at 16:00
• Glad to hear it! Oct 8 '17 at 16:02

Let's just run through the proof.

We want to prove that, for any $\epsilon > 0$, there exists $\delta > 0$ such that for all $x$, $0 < |x-2| < \delta \implies |(3x-1)-5|<\epsilon$.

Hence, we take an arbitrary $\epsilon > 0$. We now want to prove the existence of a $\delta > 0$ such that the statement "for all $x$ (...)" holds.

Note that $|(3x−1)−5| = |3x−6| = |3(x−2)| = 3|x−2|$. Now we want to construct a $\delta > 0$ such that IF $|x-2| < \delta$, THEN $3|x-2| < \epsilon$. Hence, if we take $\delta = \frac{\epsilon}{3}$, we have reached our goal: $|x-2| < \delta = \frac{\epsilon}{3}$, hence $3|x-2| < \epsilon$.

In the proof we do not start with $Q$, namely, we don't assume that $|(3x−1)−5| < \varepsilon$. If you read the string of manipulations carefully, you see that $$|(3x−1)−5| = |3x−6| = |3(x−2)| = \color{blue}{3|x−2|<3\delta= 3(\varepsilon/3) } = \varepsilon.$$ we use the assumption that $0<|x-2|<\delta=\varepsilon/3$ in the steps coloured blue to show that $|(3x−1)−5|<\varepsilon$.

• This actually cleared it up more for me, +1. Thank You! Oct 8 '17 at 17:48

That is a VERY legitimate question.

Consider $P:=$ "$x$ is very close to $2$" and $Q:=$ "$f(x)$ is verly close to $5$"

We want to prove $P \to Q$.

The naive (but wrong) way to do this is to say. Oaky. $x$ very close to $2$ means $|x-2| < .1$ so $-.1 < x-2 < .1$ and $-.3< f(x)-5 < .3$ so $|f(x) -5|<.3$.

Is $.3$ "very close" or not? And how do we generalize this?

So the next reasonable thing would be:

If $|x-2|< \delta$ which can be as small as we like then prove that $|f(x)-5|<\epsilon$ and prove that we can make $\epsilon$ as small as we like.

And we can prove that we can have if $|x-2| < \delta$ then $|f(x) -5| < 3\epsilon$ (it was simple in this case). But we can't make $*\epsilon*$ as small as we want! If we made $\epsilon$ smaller than $3\delta$, the statement would no longer be true. The size of $\epsilon$ has limits determined by the size of $\delta$.

Now, you might argue: But we can make $*\delta*$ smaller to get a smaller $\epsilon$. And you'd be correct. But now we are trying to find a $\delta$ to match our $\epsilon$; not the other way around.

Which makes sense. Of course we can get $x$ as close to $2$ as we like and we can select $\delta$ to be anything. The trick is showing the if we want to get $f(x)$ close to (within some epsilon of) $5$ then there is some $\delta$ that will let us prove it.

So we want to prove: "We can get $|f(x) - 5|< .000000001$. Question. How do we do that? Answer: By taking $|x - 2|< .0000000003333333333......$".

Or: "We can get $|f(x)-5|< \epsilon$. But how? What $\delta$ do we need?"

... or to put it another way....

Let $C(variable, constant, \gamma) = \{|variable - constant| < \gamma \}=$ "$variable$ is $\gamma$ close to $constant$".

We know that for any $c$ and $\delta$ we can always find an interval where $C(x, c, \delta)$ is true. We just take $x \in (c-\delta, c+\delta)$. We do not know that $C(f(x), k, \epsilon)$ is necessarily true.

What we want to prove is we can always find $\delta$s and $\epsilon$s where $C(x,c,\delta)$ and $C(f(x),k, \epsilon)$ are both true. And furthermore we can find these $\epsilon$s and $\delta$s so that they are as small as we want.

Well, we know $C(x,c,\delta)$ can always be made true. So we need to prove that $C(x,k,\epsilon)$ can be made true for any $\epsilon$ and that in doing so, there will be a $\delta$ where $C(x,c,\delta)$ will make that true.

So what we want to prove: $\forall \epsilon > 0| \exists \delta >0: C(x, c, \delta) \to C(f(x), k, \epsilon)$.

Or $\forall \epsilon > 0|\exist \delta > 0: P=C(x,c,\delta) \to Q= C(f(x), k , \epsilon)$.

The thing to realize is that $\epsilon, \delta$ are quantifiers, not statements.

Say we want to "do" $\epsilon \to \delta$ is not saying we want to do $Q\to P$. It is saying we want to do $\epsilon \to \delta$ in order to get the values that will allow us to prove $P\to Q$.

A lot of the answers here are focusing on the "if-then" part of the statement and proof -- that is certainly essential, but I think the more common misunderstandings about epsilon-delta proofs come from how you deal with the quantifiers. Drawing out the quantifiers in the epsilon-delta definition of a limit: for all $\epsilon>0$ there is a $\delta>0$ so that for any $x$, if $0<|x-c|<\delta$ then $|f(x)-L|<\epsilon$. I like to think about the quantifiers in terms of a game (classically, the "Ehrenfeucht-Fraisse game"): You have two players, epsilon and delta. Epsilon plays first, and has the easy task: just state a number, any number $\epsilon>0$. The delta player has the hard job: to respond with a value of $\delta>0$ so that for arbitrary $x$ satisfying $0<|x-c|<\delta$, i.e. $x\in(c-\delta, c)\cup(c, c+\delta)$ on the $x$-axis, it is also the case that $|f(x)-L|<\epsilon$, i.e. $f(x)\in(L-\epsilon, L+\epsilon)$ on the $y$-axis, with the value of $\epsilon$ that the epsilon player picked. What the delta player really needs is a strategy, a procedure, or better still a formula, for finding a response value of $\delta$ just by plugging the given value of $\epsilon$ into the formula. (The formula will typically be different for different limits.) What you actually see in a typical epsilon-delta proof of a limit is verifying that a formula for $\delta$ works as needed. That is what leads to the focus on the "if-then" part of the proof. In my opinion, if you work out how the quantifiers work in this kind of proof, the "if-then" part will be a lot easier to grasp as well.

• Note that ϵ gets chosen first and that the person doing the proof must show the existence of a suitable δ. It's a bit like a game with the adversary choosing first.
– ttw
Oct 9 '17 at 1:24