How to understand proof of a limit of a function?

Given the following function:

$$f(x)=\left\{ \begin{array} {cc} 0, & x \text{ irrational, } 0<x<1 \\ \frac{1}{q}, & x=\frac{p}{q} \text{ in lowest terms, } 0<x<1 \end{array} \right.$$

Spivak (Calculus, 4th Ediiton, page 99) proved that for any number $a$, with $0<a<1$, the function $f$ approaches $0$ at $a$ as follows:

To prove this, consider any number $\epsilon > 0$. Let $n$ be a natural number so large that $\frac{1}{n} \leq \epsilon$. Notice that the only numbers $x$ for which $|f(x)-0|\leq \epsilon$ could be false are: $$\frac{1}{2}; \frac{1}{3}, \frac{2}{3}; \frac{1}{4}, \frac{3}{4}; \frac{1}{5}, \frac{2}{5}, \frac{3}{5}, \frac{4}{5}; \dots ; \frac{1}{n}, \dots , \frac{n-1}{n}.$$

(If $a$ is rational, then $a$ might be one of these numbers.) However many of these numbers there may be, there are at any rate, only finitely many. Therefore, of all these numbers, one is closest to $a$; that is, $|\frac{p}{q}-a|$ is smallest for one $\frac{p}{q}$ among these numbers. (If $a$ happens to be one of these numbers, then consider only the values $|\frac{p}{q}-a|$ for $\frac{p}{q} \neq a$.) This closest distance may be chosen as the $\delta$. For if $0<|x-a|< \delta$, then $x$ is not one of $$\frac{1}{2}, \dots , \frac{n-1}{n}$$ and therefore $|f(x)-0| < \epsilon$. This completes the proof.

My questions are:

1. How do people follow this proof? I am lost starting at the second paragraph ("However many of these...") I have gone through and understand (I think) the definition of a limit but still I can't follow what the author is trying to say and do (I do know the end product he wants to arrive at, which is to prove $f$ approaches $0$ at any $a$, where $0<a<1$. Can someone please explain what he is trying to say?

2. Are there any tips on how to follow the arguments presented in proof? I am sure there are people who understood a proof only after multiple readings. What did you do to improve your understanding?

3. After further study, I am now stuck at "For if $0<|x-a|< \delta$,...". I am not convinced that after finding $\delta$, all $x$ that meets the condition $0<|x-a|<\delta$ will make $f(x)<\epsilon$. I tried walking through the proof with a few numbers and it seem to work but I wonder why will it always be true i.e. what does the algebra look like?

Thank you in advance for any help provided.

• Just pointing out the language aspect: the sentence "However many of these numbers there may be, there are at any rate, only finitely many" means "No matter how many of these numbers there are, there are only finitely many". In other words "There are only finitely many of these numbers (without caring exactly how many there are)". – ShreevatsaR Jul 23 '13 at 10:16
• @ShreevatsaR Thanks. Now I am wondering how can we be sure that all the $x$ that meet $0 < |x-a| < \delta$ will always exclude those numbers that will make $|f(x)-0|\leq \epsilon$ false? – mauna Jul 24 '13 at 2:42

Firstly, don't be disheartened: one's first encounter with analysis is generally hard the way you're finding it. See for instance Herbert Wilf's piece Epsilon sandwiches, where he describes how this course is:

The one where students and epsilons meet, eyeball to eyeball, and it isn't the epsilons that blink. The one where students decide that they really wanted to be doctors and lawyers after all.

This course is famous for being our rite of passage. Our hazing ceremony. If you want to join the club, then here is the hurdle that you have to jump over.

And so on.

Secondly, the best way to understand a proof is to first try and prove the theorem yourself. Then when you read the proof, you'll have a better idea of what it's trying to do: you'll know which parts are just scaffolding, similar to what you'd have done yourself, and which parts are the new ideas, the real essence or new insight or trick that you should take away from the proof. This helps with all areas of mathematics — see Thurston's comment here:

"When listening to a lecture, I can't possibly attend to every word: so many words blank out my thoughts. My attention repeatedly dives inward to my own thoughts and my own mental models, asking 'what are they really saying?' or 'where is this going?'. I try to shortcut through my own understanding, then emerge to see if I'm still with the lecture. It's the only way for me, and it often works."

— but especially in analysis it's crucial because otherwise the $2\epsilon/3M$ and so on of slick proofs can appear to be pulled out of a hat.

Finally, to this particular question. You have a function $f$ that is $0$ at irrational points, and $\frac1q$ at rational points $\frac{p}q$. You want to prove that for any number $a$, the function approaches $0$ at $a$. Before reading the proof, you should try to prove it by yourself, so let's try.

We start with definitions: what does it mean to say that $f$ approaches $0$ at the point $a$? If you've internalized the definitions well, you should be able to say (and if not, this is a sign that you should go back and do that) what we want to prove: that $f(x)$ is sufficently close to $0$ for $x$ sufficiently close to $a$, or in formal words, for any $\epsilon > 0$, there exists $\delta$ such that if $|x-a| < \delta$‌ then $|f(x) - 0| < \epsilon$. And indeed, if you peek now at the proof, you'll see that it is of the form

To prove this, consider any number $\epsilon > 0$. [...]
if $0<|x-a|< \delta$, then [..] and therefore $|f(x)-0| < \epsilon$. This completes the proof.

so you've got the "skeleton" of the proof right.

Next, we worry about strategy: how are we going to prove that $|f(x) - 0| < \epsilon|$? We try to use what we know about $f$: that $f$ takes values either $0$ or of the form $\frac1q$. At points $x$ where $f(x) = 0$, we have $|f(x) - 0| = |0-0| = 0$, so it's certainly less than $\epsilon$ (as $\epsilon > 0$). So we only need to worry about $x$ where $f(x) = \frac1q$ for some $q$. In that case, $|f(x) - 0| = |\frac1q - 0| = \frac1q$. We'd like this to be less than $\epsilon$. (Now if we peek at the proof, we see that the second sentence is something about taking $n$ such that $\frac1n \le \epsilon$, so it's probably related to this, and we're on the right track.) Indeed, for any fixed $\epsilon$, as $q$ becomes larger $\frac1q$ becomes smaller and eventually becomes smaller than $\epsilon$.

So: to prove that $|f(x) - 0| < \epsilon$ for $x$ sufficiently near $a$, we do something akin to proof by contradiction: we look at when it's not true: $|f(x) - 0| \ge \epsilon$ when $f(x)$ is of the form $\frac1q$ for some $q$ such that $\frac1q \ge \epsilon$, and there are only finitely many such $q$. That is, if we take some fixed $n$ large enough so that $\frac1n \le \epsilon$, then the only $x$ for which $|f(x) - 0| < \epsilon|$ are those for which $f(x) = \frac1q$ for some $q \le n$, and $f(x) = \frac1q$ in turn means that $x = \frac{p}q$ for some such $q$, which gives the set of numbers in the proof.

So there are only these finitely many points $x$ at which the desired conclusion $|f(x) - 0| \le \epsilon$ might not hold. To avoid all of them, we must take $x$ very close to $a$ (note that to prove the desired conclusion, the only thing we can control about $x$ is its distance $\delta$ to $a$). That is, to make sure that $x$ is not any of these "bad points", we'll insist that $x$ must be closer to‌ $a$ than any of these "bad points" are, i.e. we'll take $\delta$ smaller than the smallest of the distances of these "bad points" from $a$.
Then $x$ is surely not any of the "bad points" at which the desired conclusion $|f(x) - 0| \le \epsilon$ might not hold, which means that the conclusion holds. That's the rest of the proof, which I hope you'll be able to understand now.

• In the second last paragraph, if $\frac{1}{n} \lt \epsilon$ shouldn't $q \geq n$ so that $|f(x)-0| \lt \epsilon$? – mauna Jul 24 '13 at 18:19
• @mauna:‌ You are correct that when $q > n$, we have $|f(x)-0|<\epsilon$. In that particular paragraph, we were trying to find when $|f(x)-0|<\epsilon$ is not true (just to rule out such‌ bad $x$): so for that to happen it needs the opposite, i.e $q \le n$. – ShreevatsaR Jul 24 '13 at 18:33
• Noted. Thank you so much for your time and patience. – mauna Jul 24 '13 at 18:41

My strategy is to just try to understand each sentence one by one. And if that doesn't work, each word one by one. :) With each sentence ask "1. Why is that true? 2. Why did the author mention that? 3. How is he using the hypotheses here? 4. Why would this statement not be true in another situation?"

Certainly my ability to understand proofs has improved with practice. After a while you start to understand what are the key ideas, and you mostly disregard the details, knowing that you could reproduce them if necessary.

I wonder: are you reading Spivak's book having not had the regular calculus series (Calc 1, calc 2, calc 3)? Often such classes provide an intuition for calculus ideas, which softens the ground for an understanding of rigorous proofs.

• @ Eric Auld I've learned Calculus as part of additional mathematics in high school but only to the extent of applying theorems to solve problems, not understanding why they work. That's why I've decided to study Spivak during my school break. I am not sure what Calc 1, Calc 2, Calc 3 covers as I study under the Singapore school syllabus. – mauna Jul 23 '13 at 9:23
• Calc 1 and 2 is typically applying differentiation and integration to solve problems in a single variable; Calc 3 is doing so in several variables (including things like integration over regions and Stokes' theorem). But you sound like you're ready to do this work, if you find that you want to. Good luck! One tip that is relevant to this proof: always keep in your mind which variables we're fixing for the moment, and which we're allowing to vary. – Eric Auld Jul 23 '13 at 10:12
1. Here's what Spivak is doing: To prove that the limit at $a$ is equal to 0, what needs to be shown is that for every given $\epsilon>0$, there exists a $\delta >0$ such that:

if $x$ is within $\delta$ of $a$, then $f(x)$ is within $\epsilon$ of 0, i.e. $$0< |x - a | < \delta \ \implies |f(x) - 0 | < \epsilon$$

So he starts by choosing some $\epsilon >0$: the goal is to find $\delta$ so that the above implication holds. Then he analyzes the bad points: the set of $x$'s for which $|f(x) - 0| \geq \epsilon$, and violate the condition. As he works out, these bad points are the finite set that he lists, and so as long as $x$ is not one of the bad points, then $|f(x) |$ will be less than $\epsilon$.

The last step is to find a $\delta$ so that the condition $$0 < |x - a| < \delta$$ excludes these bad points, which he explains starting from "Therefore, of all these numbers..."

This is an example of a very useful strategy: you want to formulate a condition ( e.g. $0<|x-a|<\delta$) so that a desired conclusion holds (e.g. $|f(x)| < \epsilon$). One way to do this is to find exactly where your desired conclusion fails to hold, and formulate your condition to exclude those points.

2. Practice and patience. This material is hard, and is not supposed to be clear after one reading.

• Does this mean that the numbers $x$ that will meet $0<|x-a|<\delta$ will lie outside the sequence $\frac{1}{n}, \dots, \frac{n-1}{n}$ for all $n$? – mauna Jul 24 '13 at 2:37