notes.tex

\documentclass[11pt,oneside]{amsbook}

\title{Introduction to real analysis}
\author{Course notes written by Samuel Coskey;\\Based on material from ``Understanding Analysis'',\\written by Stephen Abbott}

\usepackage[vscale=.8,vmarginratio=4:3]{geometry}
\usepackage{mathpazo,amssymb}
\usepackage{setspace}\onehalfspacing\raggedbottom
\renewcommand{\labelitemi}{$\circ$}
\renewcommand{\labelenumi}{(\alph{enumi})}
\renewcommand{\chaptername}{Part}
\renewcommand{\thechapter}{\Roman{chapter}}
\usepackage{remreset}
\makeatletter\@removefromreset{section}{chapter}\makeatother
\usepackage{etoolbox}
\makeatletter
\pretocmd{\@seccntformat}{\S}{}{}
\patchcmd{\tocsection}{#2.}{\S#2.}{}{}
\apptocmd{\tocsection}{\dotfill}{}{}
\patchcmd{\@maketitle}{\newpage}{}{}{}
\makeatother
\usepackage[linktoc=all,colorlinks,linkcolor=blue]{hyperref}
\usepackage{tikz}\usetikzlibrary{positioning,decorations.fractals,decorations.pathmorphing}

\newcommand{\set}[1]{\left\{\,#1\,\right\}}
\newcommand{\N}{\mathbb N}
\newcommand{\Z}{\mathbb Z}
\newcommand{\Q}{\mathbb Q}
\newcommand{\R}{\mathbb R}
\DeclareMathOperator{\dom}{dom}
\DeclareMathOperator{\rng}{rng}
\DeclareMathOperator{\cl}{cl}
\DeclareMathOperator{\inte}{int}
\DeclareMathOperator{\ext}{ext}
\renewcommand{\setminus}{\smallsetminus}

\theoremstyle{definition}
\newtheorem{exerc}{Exercise}[section]
\swapnumbers
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{example}[theorem]{Example}
\newtheorem*{reading}{Reading}
\newtheorem*{readnext}{Reading for next time}
\newtheorem*{notes}{Notes and further reading}
\numberwithin{equation}{section}
\numberwithin{figure}{section}
\renewcommand{\theequation}{\arabic{section}.e\arabic{equation}}
\renewcommand{\thefigure}{\arabic{section}.f\arabic{figure}}
\newcounter{activityitem}
\newenvironment{activity}{\begin{list}{\arabic{activityitem}.}{\usecounter{activityitem}\setlength{\itemsep}{.2in}}}{\end{list}}

\begin{document}

\maketitle

\tableofcontents

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\chapter{The theory of the real number line}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{What are rational and real numbers?}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{reading}
  Abbott \S 1.1, 1.2, start 8.6
\end{reading}

We begin the course by briefly pondering a very deep question: what are numbers and what are they for?

The natural or counting numbers $1,2,3,\ldots$ are collectively denoted $\N$ and are central to many areas of mathematical study. \emph{Combinatorics} is the study of counting finite sets. For example: how many ways are there to write the number 10 as a sum of three natural numbers? \emph{Number theory} is the study of the arithmetic operations on the natural numbers. For example: how many prime numbers are there less than 1 billion?

But in \emph{calculus}, analysis, and geometry, numbers are used for measurement. How can we measure the distance between two points on the floor? To answer this we would first need to choose a unit, such as a straight stick of random length. With this in hand, we can try count how many copies of the unit stick fit along the striaght line segment joining the two points. But what if the number of unit sticks doesn't come out whole?

In this case we can try to use \emph{ratios} to measure the distance. For example, suppose we are trying to measure the distance $d$, and three unit sticks fit perfectly inside two copies of $d$. Then we say that $d=3/2$ units. Sometimes this telescoping process takes a long time, for example if five units fit perfectly inside four copies of $d$. The set of all ratios of natural numbers (and their negatives) is called the \emph{rational numbers} and given the symbol $\Q$ (for quotient).

This leads to the \emph{big question} of the day: are rational numbers enough to measure all distances? It turns out that the answer is NO, and this fact surprised many early mathematicians (and still blows minds of new mathematicians today). Ratios are good enough for most practical purposes because in the real world we can accept approximations. But there are ideal distances (numbers) which are not rational. The simplest classical example is $d=$ the diagonal of a square.

First notice that $d$ has the property that $d^2=2$. The explanation for this is at once simple, beautiful, and clever: If we quadruplicate the square, we see that the square with sidelength $d$ is exactly half the square with sidelength $2$. Thus $d^2=2^2/2=2$.

\begin{center}
\begin{tikzpicture}
  \draw (0,0)--(1,0)--(1,1)--node[above]{$1$}(0,1)--node[left]{$1$}(0,0)--node[below right,inner sep=0]{$d$} (1,1);
\end{tikzpicture}
\quad
\begin{tikzpicture}
  \draw (0,0)--(2,0)--(2,2)--node[above]{$2$}(0,2)--node[left]{$2$}(0,0);
  \draw (1,0)--node[below right,inner sep=0]{$d$}(2,1)--(1,2)--(0,1)--(1,0);
\end{tikzpicture}
\end{center}

Armed with the knowledge that $d^2=2$, we can now show $d$ is irrational.

\begin{theorem}
  \label{thm:root-2-irrational}
  If $d^2=2$ then $d\notin\Q$.
\end{theorem}

\begin{proof}
  Suppose $d$ is rational and write $d=a/b$ where $a,b$ are natural numbers and the fraction is in lowest terms. Then $a^2=2b^2$. Notice that the right-hand side is even, and therefore so is the left-hand side. It follows that $a$ is even. Hence the left-hand side is divisible by $4$, and therefore so is the right-hand side. It follows that $b$ is even. Thus both $a$ and $b$ are even, contradicting that the fraction $a/b$ is in lowest terms.
\end{proof}

We conclude that the rational number system possesses some kind of gap at $\sqrt2$. Another way to say it is that the concept of $\sqrt2$ \emph{cuts} the rationals into two pieces, those that are less than $\sqrt2$ and those that are larger than $\sqrt{2}$. (Actually, since in our development the number $\sqrt{2}$ doesn't exist yet, it would be more appropriate to say: those that are negative or have square less than $2$, and those that are nonnegative and have square greater than $2$.)

The situation we just described is very similary to the way a rational number $q$ cuts the rationals into three pieces: those numbers that are less than $q$, $q$ itself, and those numbers that are greater than $q$. The key difference is the presence of $q$ itself in between the two halves. The concept of a cut is made formal in the following definition.

\begin{definition}
  \label{def:cut}
  A \emph{cut} in the rational number system $\Q$ consists of a triple of sets $(A,P,B)$ such that $A\cup P\cup B=\Q$ and the following properties hold:
  \begin{enumerate}
    \item $|A|=\infty$, $|P|=0$ or $1$, and $|B|=\infty$
    \item $A$ is entirely below $B$, and if $P\neq\emptyset$ then $P$ is in between $A$ and $B$
    \item $A$ has no greatest element, and $B$ has no least element
  \end{enumerate}
\end{definition}

\begin{example}
  The following is a cut:
  \begin{equation}
    \label{eq:rationalcut}
    \left(\set{q\in\Q\mid q<3/2},\set{3/2},\set{q\in\Q\mid q>3/2}\right)\text{.}
  \end{equation}
  This type of cut, with the set $P$ containing a single rational number, is called a \emph{rational cut}.

  \begin{center}
  \begin{tikzpicture}
    \draw[<-,very thick](-3,0)--node[below]{$A$}(-.05,0);
    \draw[->,very thick](.05,0)--node[below]{$B$}(3,0);
    \node[circle,fill,inner sep=1pt,label=below:$P$] at (0,0) {};
    \node at (-.08,0) {$)$};
    \node at (.08,0) {$($};
  \end{tikzpicture}
  \end{center}
\end{example}

\begin{example}
  The following is a cut:
  \begin{equation}
    \label{eq:irrationalcut}
    \left(\set{q\in\Q\mid q<0\text{ or }q^2<2},\emptyset,\set{q\in\Q\mid q\geq0\text{ and }q^2>2}\right)\text{.}
  \end{equation}
  This is the cut at $\sqrt{2}$ discussed above. We leave it until the next section to prove that $A$ really has no greatest element and $B$ has no least element. This type of cut, with $P=\emptyset$, is called an \emph{irrational cut} or a \emph{gap}.
  
  \begin{center}
  \begin{tikzpicture}
    \draw[<-,very thick](-3,0)--node[below]{$A$}(-.01,0);
    \draw[->,very thick](.01,0)--node[below]{$B$}(3,0);
    \node at (0,0) {$)\kern-2.5pt($};
  \end{tikzpicture}
  \end{center}
\end{example}

We are now prepared to define the real number system by ``filling in'' the gaps of $\Q$.

\begin{definition}
  The \emph{real number system} $\R$ consists of the rational numbers $\Q$ together with, for every irrational cut $(A,\emptyset,B)$, a new point $p$ lying between the sets $A$ and $B$.
\end{definition}

Thus there is a one-to-one correspondence between real numbers and cuts, with the rational numbers corresponding to rational cuts, and the irrational numbers corresponding to irrational cuts.

To close, let us look at the number systems we know so far, from smallest to largest. Each one has progressively more power than the last:
\begin{itemize}
  \item $\N$: supports addition and multiplication, but not subtraction or division
  \item $\Z$: supports addition, multiplication, and subtraction, but not division
  \item $\Q$: supports all four operations, but has gaps;
  \item $\R$: supports all four operations, and has no gaps.
\end{itemize}
In the next section we will prove the final claim, that $\R$ has no gaps.

% We emphasize that an irrational number is \emph{defined} from its cut. That is, we don't define $\sqrt2$ to be a positive number whose square is $2$, though it's true. That would tell you what property the number has, but not where to actually find it. Instead we define $\sqrt2$ to be a point in between $\set{q\in\Q\mid q<0\text{ or }q^2<2}$ and $\set{q\in\Q\mid q\geq0\text{ and }q^2<2}$.

\newpage
\subsection*{Activity for \S \thesection}

\begin{activity}
  \item (see Abbott, exercise 1.4.1) Complete and prove:
  \begin{enumerate}\itemsep\fill
    \item The sum of two rational numbers is\ldots
    \item The product of two rational numbers is\ldots
    \item The sum of a rational number and an irrational number is\ldots
    \item The product of a rational number and an irrational number is\ldots unless\ldots
    \item The product of two irrational numbers is\ldots? (discuss)
    \vspace{\fill}
  \end{enumerate}
  \item For each triple, either argue that it is a cut, or show that one of the conditions in the definition of cut is not satisfied.
  \begin{enumerate}\itemsep\fill
    \item $(\set{q\in\Q\mid q<2},\emptyset,\set{q\in\Q\mid q>2})$
    \item $(\set{q\in\Q\mid q\leq2},\emptyset,\set{q\in\Q\mid q>2})$
    \item $(\set{q\in\Q\mid q\leq2},\{2\},\set{q\in\Q\mid q>2})$
    \item $(\set{q\in\Q\mid q<2},\{1.5\},\set{q\in\Q\mid q>2})$
    \item $(\set{q\in\Q\mid q^2<2},\emptyset,\set{q\in\Q\mid q^2>2})$
  \end{enumerate}
\end{activity}

\vspace{\fill}
\begin{readnext}
  Abbott \S 8.6, start \S 1.3
\end{readnext}

\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Cuts and least upper bounds}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{reading}
  Abbott \S 8.6, start \S 1.3
\end{reading}

Although we introduced the real numbers as a way to measure distances, we of course know that the real numbers should carry arithmetic operations, too. In fact, it should be an \emph{ordered field}, which means it should support the four arithmetic operations as well as the comparison $\leq$, and these operations should satisfy the usual axioms of associativity, commutativity, and so forth. The rational number system has all these properties, and the real number system does too. We have yet to \emph{define} the arithmetic operations on the real numbers, but in principle it isn't difficult.

For example, we define the ordering $\leq$ on real numbers as follows. If $\alpha_1$ and $\alpha_2$ are real numbers corresponding to cuts $(A_1,P_1,B_1)$ and $(A_2,P_2,b_2)$ are cuts, then we say $\alpha_1\leq\alpha_2$ if and only if $A_1\subseteq A_2$. It is straightforward to check this definition satisfies the usual axioms of $\leq$.

Similarly, if we define $\alpha_1+\alpha_2$ as the real number corresponding to the cut $(A,P,B)$, where
\[A=\set{a_1+a_2\mid a_1\in A_1\text{ and }a_2\in A_2}
\]
and $P$ and $B$ determined using $A$. One must verify this really is a cut, and then verify the axioms of addition hold. We will omit the tedious details of defining the last three arithmetic operations, and verifying the remaining axioms.

Thus we continue with the knowledge that $\R$ is an ordered field. But $\R$ must satisfy even more properties than just this, or else we would have been happy to stick with $\Q$. It turns out that $\R$ additionally supports the \emph{least upper bound} operation, which we now define.

% In the previous section we defined the real numbers using cuts in the rational number system. Our ``triple'' notation for cuts $(A,P,B)$ is nice and symmetric, but as it happens knowing $A$ is enough to determine $P$ and $B$ too: $P\cup B$ will always be equal to the complement $\Q\setminus A$, with $P$ containing the least element of $\Q\setminus A$ if it exists. Thus from now on we drop the $P$ and the $B$ from cuts and make the following revised definition.
% 
% \begin{definition}
%   A \emph{cut} in $\Q$ is a subset $A\subset\Q$ such that the following properties hold
%   \begin{enumerate}
%   \item $A$ is infinite, and $\Q\setminus A$ is infinite;
%   \item $A$ lies entirely below $\Q\setminus A$;
%   \item $A$ has no greatest element.
%   \end{enumerate}
% \end{definition}

% Intuitively, a cut $A$ corresponds to a real number $\alpha$ which ``comes just after'' $A$. But what does it mean to come just after? To answer this, we must define an ordering on real numbers. This turns out to be easy using our new definition of cuts. If $\alpha,\alpha'$ are real numbers corresponding to cuts $A,A'$, we say that $\alpha\leq\alpha'$ if and only if $A\subseteq A'$.

\begin{definition}
  Let $S$ be a set of real numbers. An \emph{upper bound} for $S$ is a real number $\beta$ such that for all $\alpha\in S$, $\alpha\leq\beta$. If $\beta$ is an upper bound for $S$ then it is called the \emph{least upper bound} or \emph{supremum} of $S$ if it is least among all possible upper bounds of $S$.
\end{definition}

\begin{example}
  \begin{itemize}
  \item The set $(-5,5]$ has a maximum element $5$. Therefore it has least upper bound $5$.
  \item The set $(-5,5)$ has no maximum element. But it has upper bounds, for example $7$, $23.6$, and $100$. The least upper bound or supremum is $5$.
  \item The set $\set{\frac12,\frac23,\frac34,\ldots}$ has no maximum element. But it has upper bounds, and its supremum is $1$.
%   \item The set $A=\set{q\in\Q\mid q<0\text{ or }q^2<2}$ has no maximum element. But it has upper bounds, such as $1.5$, and its supremum is $\sqrt2$.
  \end{itemize}
\end{example}

% Our construction of the real numbers can now be rephrased using our new definition of cut and the concept of supremum: The real number system $\R$ consists of the rational numbers $\Q$ together with, for every cut $A\subset\Q$ which does not have a rational supremum, a newly inserted supremum $\alpha$ of $A$.

In the rational number system $\Q$, sets don't need to have a supremum (within $\Q$). Before we can prove this, we first show as promised that the cut at $\sqrt2$ is really a cut. The proof turns out to be more technical than one might expect. It will provide us with a not-so-soft example of the kind of arguments we will see later in the course.

\begin{theorem}
  \label{thm:root-2-cut}
  Let $(A,\emptyset,B)$ be the triple from Equation~\ref{eq:irrationalcut}. Then $(A,\emptyset,B)$ is a cut in $\Q$.
\end{theorem}

\begin{proof}
  The key step is to verify that $A$ has no greatest element, as the proof that $B$ has no least element is symmetric. Let $q\in A$ be given; we will show $q$ is not the greatest element of $A$. It is clear that a negative number cannot be the greatest element of $A$, so we may assume that $q\geq0$ and $q^2<2$.
  
  We wish to find a small rational number $\epsilon>0$ such that $q+\epsilon$ is in $A$ also, that is, $(q+\epsilon)^2<2$. To find what $\epsilon$ should be, we work \emph{backwards}.
  \begin{align*}
    (q+\epsilon)^2<2&\iff q^2+2q\epsilon+\epsilon^2<2\\
    &\,\Longleftarrow\,\,\, q^2+2q\epsilon+\epsilon<2\\
    &\iff \epsilon<(2-q^2)/(2q+1)
  \end{align*}
  There is a clever trick going on in the second implication (the $\Longleftarrow$ one) which we will comment on in a moment. But overall, this calculation is telling us that we will be safe if we choose $\epsilon<(2-q^2)/(2q+1)$. Note that we can do this and still have $\epsilon>0$, because $q^2<2$.

  Now, in the second implication we replaced $\epsilon^2$ with $\epsilon$ to make it easier to solve for $\epsilon$. To do this, we actually need to make the extra assumption that $\epsilon<1$, since then $\epsilon^2<\epsilon$ and the $\Longleftarrow$ implication holds true. This is acceptible because we haven't yet chosen $\epsilon$, so we just need to additionally promise to choose $\epsilon<1$.

  We now know that our proof will succeed if we choose $\epsilon$ to be any positive rational number such that $\epsilon<(2-q^2)/(2q+1)$ and $\epsilon<1$. To verify that this works, we use our preparatory work \emph{forwards} as follows.
  \begin{align*}
    \epsilon<(2-q^2)/(2q+1)\quad\&\quad\epsilon<1
    &\implies q^2+2q\epsilon+\epsilon<2\quad\&\quad\epsilon^2<\epsilon\\
    &\implies q^2+2q\epsilon+\epsilon^2<2\\
    &\implies (q+\epsilon)^2<2
  \end{align*}
  We conclude that $q+\epsilon$ is a rational number greater than $q$ satisfying $(q+\epsilon)^2<2$. This shows $q$ is \emph{not} the greatest element of $A$, as desired.
\end{proof}

We may now conclude that if $(A,\emptyset,B)$ is the cut at $\sqrt2$, then $A$ has no rational supremum. Indeed if $\beta$ were the supremum of $A$, then since $A$ has no greatest element we have $\beta\notin A$. Similarly since $B$ has no least element we have $\beta\notin B$. Thus $\beta\notin\Q$. (In the next section, we will show that in fact $\beta=\sqrt2$.)

In the real number system $\R$, on the other hand, sets do have a supremum whenever possible.

\begin{lemma}
  Let $S$ be a set of real numbers which has an upper bound. Then the supremum of $S$ exists.
\end{lemma}

\begin{proof}[Proof idea]
  By our definition of the real numbers, every $\alpha\in S$ corresponds to a cut $(A_\alpha,P_\alpha,B_\alpha)$. From these cuts we define a new cut cut $(A,P,B)$ by letting $A=\bigcup A_\alpha$, $B=\bigcap B_\alpha$, and $P=$ whatever is left. We leave it to the reader to verify that $(A,P,B)$ is really a cut. Let $\beta$ be the real number corresponding to the cut $(A,P,B)$.

  Now, since $A_\alpha\subset A$ for every $\alpha\in S$, we see that $\beta$ is an upper bound of $S$. Moreover $\beta$ is the least upper bound of $S$. Indeed, any other upper bound $\beta'$ corresponding to $(A',P',B')$ satisfies $A_\alpha\subset A'$ for every $\alpha\in S$, and therefore $A=\bigcup A_\alpha\subset A'$. In other words, $\alpha\leq\beta$, as desired.
\end{proof}

We are finally ready to prove the result, promised in the previous section, that $\R$ has no gaps.

\begin{theorem}
  The set of real numbers has no gaps. That is, if $(A,P,B)$ is such that $A\cup P\cup B=\R$ and properties (a)(b)(c) of Definition~\ref{def:cut} satisfied, then $P\neq\emptyset$.
\end{theorem}

\begin{proof}
  Let $(A,P,B)$ be such a triple. By the previous lemma, we can let $\alpha$ be the supremum of $A$. Since $A$ has no greatest element, we have $\alpha\notin A$. Since $B$ has no least element, $\alpha\notin B$. Thus we must have $\alpha\in P$, which means that $P\neq\emptyset$.
\end{proof}

\newpage
\subsection*{Activity for \S \thesection}

\begin{activity}
  \item (Abbott, ex 1.3.8) Find the supremum and infemum of each of the following sets. You do not need to give a detailed proof, but please explain your reasoning. Assume for this exercise that $\N$ exludes $0$.
  \begin{enumerate}\itemsep.5in
    \item $\set{n\in\N\mid n^2<10}$
    \item $\set{n/(m+n)\mid m,n\in\N}$
    \item $\set{n/(2n+1)\mid n\in\N}$
    \item $\set{n/m\mid m,n\in\N\text{ and }m+n\leq10}$
    \vspace{.5in}
  \end{enumerate}
  \item Suppose that $A$ and $B$ are subsets of $\R$ and that $A\subset B$.  Which of the following is correct, and why? ``any upper bound for $A$ is also an upper bound for $B$'', or; ``any upper bound of $B$ is also an upper bound for $A$.''

  Now additionally suppose that $\sup(A)$ and $\sup(B)$ exist.  Which inequality is right, and why? $\sup(A)\leq\sup(B)$, or; $\sup(B)\leq\sup(A)$.
\end{activity}

% \begin{exerc}[see also Abbott, ex 8.6.5(a)]
%   Review the three-part definition of cut. Suppose that $A$ and $B$ are cuts, and let $S$ be the so-called sum-set of the two cuts, that is, let $S=\set{a+b\mid a\in A\text{ and }b\in B}$. Prove that $S$ is a cut by proving that each of the conditions in the definition of cut is satisfied.
%
%   Why isn't the set $P=\set{ab\mid a\in A\text{ and }b\in B}$ a cut?  What kinds of things do you have to do to fix this?
% \end{exerc}

% \question Consider the sequence defined by $x_1=0$ and $x_{n+1}=\sqrt{2+x_n}$.  Prove using induction that for all $n$, $x_n<2$.  Prove using induction that for all $n$, $x_n<x_{n+1}$.

% \question Give a detailed proof from the definition of supremum that the supremum of the interval $(0,1)$ is exactly $1$.

\vspace{\fill}
\begin{readnext}
  Abbott \S 1.3, 1.4
\end{readnext}


\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{The Axiom of Completeness}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{reading}
  Abbott, \S 1.3, 1.4
\end{reading}

In the previous two sections we showed how one can construct the real number system using cuts. In this section we take a high-level approach and show how to work in the real number system using its properties alone. This will enable us to leave cuts behind for good.

\begin{definition}
  An ordered field is said to satisfy the \emph{Axiom of Completeness} if every subset which has an upper bound in fact has a supremum.
\end{definition}

In the previous section, we saw that the ordered field $\Q$ \emph{does not} satisfy the Axiom of Completeness, since the set $A=\set{q\in\Q\mid q<0\text{ or }q^2<2}$ has no supremum in $\Q$. We also saw that the ordered field $\R$ \emph{does} satisfy the Axiom of Completeness. In fact, the following is true:

\begin{theorem}
  The real number system $\R$ is an ordered field satisfying the Axiom of Completeness. Moreover, $\R$ is the unique such field up to isomorphism.
\end{theorem}

From this point on, we \emph{define} the real number system $\R$ to be the unique ordered field satisfying the Axiom of Completeness. It is therefore never necessary to speak of cuts again! In the future we may describe real numbers in many different ways: with cuts, with equations, with limits, with series, and of course with decimal expansions.

In the rest of this section, we take up the task of showing that we can use our new abstract definition of $\R$ to prove all the properties and facts we will need about the real number system. We begin with the following elementary result.

\begin{theorem}[Archimedean Principle]
  For any real number $x$, there exists a natural number $n$ such that $x<n$. That is, while there are real numbers between integers, there aren't any real numbers beyond the integers to the right.
\end{theorem}

\begin{proof}
  Suppose to the contrary that $x$ is a real number such that for all $n\in\N$ we have $n\leq x$. This says $x$ is an upper bound for $\N$, in particular it would mean $\N$ is bounded. By the Axiom of Completeness, $\N$ should have a least upper bound, call it $\alpha$.

  Now, since $\alpha$ is the \emph{least} upper bound, $\alpha-1$ is not an upper bound for $\N$. Hence there exists $n\in\N$ such that $\alpha-1<n$. It follows that $\alpha<n+1$, contradicting that $\alpha$ is an upper bound for all natural numbers.
\end{proof}

\begin{center}
  \begin{tikzpicture}
    \draw[<->] (-1,0)--(8,0);
    \node[label=above:{\small$\alpha-1$}] at (3,0) {$|$};
    \node[label=below:{\small$n$}] at (3.8,0) {$|$};
    \node[label=above:{\small$\alpha$}] at (5,0) {$)$};
    \node[label=below:{\small$n+1$}] at (5.8,0) {$|$};
  \end{tikzpicture}
\end{center}

As a consequence of this simple fact, we can now formally establish one fact we have previously stated without proof. While the rational number system is not sufficient to measure any distance, it is sufficient to \emph{approximate} any distance. In the following statement, we let $x<y$ and imagine that they are very close to one another.

\begin{theorem}[Rational density]
  For any real numbers $x,y$, if $x<y$ then there exists $q\in\Q$ such that $x<q<y$.
\end{theorem}

\begin{proof}
  Using the Archimedean Principle, we can find $n\in\N$ such that $n>1/(y-x)$. Intuitively, this guarantees that increments of size $1/n$ cannot step over the interval $(x,y)$.

  Now let $m\in\N$ be the smallest natural number such that $x<m/n$ (again use the Archimedean Principle). Note that by this minimality we have $m/n-1/n\leq x$. Putting these equations together, we have
\begin{align*}
  x&<m/n\\
   &\leq x+1/n\\
   &<x+(y-x)=y
\end{align*}
Thus the rational number $q=m/n$ lies in the interval $(x,y)$.
\end{proof}

To see that this implies we can approximate real numbers by rational numbers as closely as we like, let $x$ be a given real number and apply the rational density theorem to intervals of the form $(x-\epsilon,x+\epsilon)$ where $\epsilon$ is small.

As an application of the rational density theorem, we can finally calculate the following promised supremum.

\begin{proposition}
  Let $A=\set{q\in\Q\mid q<0\text{ or }q^2<2}$ and let $\beta=\sup(A)$. Then $\beta^2=2$, that is, $\beta=\sqrt2$.
\end{proposition}

\begin{proof}
  If $\beta^2<2$, then using the calculation from Theorem~\ref{thm:root-2-cut}, we can find $\epsilon>0$ such that $(\beta+\epsilon)^2<2$. By rational density, we can find a rational number $q$ such that $\beta<q<\beta+\epsilon$. Then $\beta<q$ and $q^2<2$, contradicting that $\beta$ is an upper bound of $A$.
  
  If $\beta^2>2$, we can reach a contradiction in a similar way. Thus we must have $\beta^2=2$, as desired.
\end{proof}

We close this section with a characterization of the supremum of a set that will be useful in the future.

\begin{lemma}
  If $A$ is a set, then $\beta$ is the supremum of $A$ if and only if the following two conditions are satisfied:
  \begin{itemize}
  \item ($\beta$ is an upper bound) for all $a\in A$ we have $a\leq\beta$, and
  \item ($\beta$ is the least such) for all $\epsilon>0$ there exists $a\in A$ such that $\beta-\epsilon\leq a$.
  \end{itemize}
\end{lemma}

You can find the proof in Lemma~1.3.8 of the text.


\newpage
\subsection*{Activity for \S\thesection}

\begin{activity}
  \item (Abbott, exercise 1.4.5) Prove the statement known as \emph{irrational density}: for every two real numbers $a$ and $b$ with $a<b$, there exists an \emph{irrational} number $r$ satisfying $a<r<b$.
  \vspace{\fill}
  \item Recall that the \emph{infemum} of a set is the greatest lower bound. Write a characterization of infemum in the style of the $\epsilon$-characterizaton of supremum.
\end{activity}

% \begin{exerc}
%   Give a detailed proof from the definition of supremum that the supremum of the interval $(0,1)$ is exactly $1$.
% \end{exerc}
%
% \begin{exerc}
%   Read the characterization of supremum described in Abbott, Lemma~1.3.8. Then, give a thorough proof that $1/2$ is the supremum of the set $\set{n/(2n+1)\mid n\in\N}$. Point out the exact moment in the proof when the Archimedean Principle is used.
% \end{exerc}
%
% \begin{exerc}
%   Consider the sequence defined by $x_1=0$ and $x_{n+1}=\sqrt{2+x_n}$. Prove using induction that for all $n$, $x_n<2$. Prove using induction that for all $n$, $x_n<x_{n+1}$.
% \end{exerc}

\vspace{\fill}
\begin{readnext}
  Abbott, \S 1.5
\end{readnext}

\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Completeness and the size of the reals}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{reading}
  Abbott, \S 1.5
\end{reading}

In this section we will continue with consequences of the completeness axiom. In particular we will establish one of the most surprising and historically disruptive consequences: the fact that there are more irrational numbers than there are rational numbers! In order to make this statement precise, we need to introduce the notion of countable and uncountable sets.

\begin{definition}
  A set $A$ is \emph{countable} if it can be enumerated in a sequence $a_n$, whose items are indexed by natural numbers $n$. Intuitively, $A$ is countable if all its elements can be ordered up in an infinite shopping list:
  \begin{align*}
    1.&\quad\underline{\hspace{1in}}\\
    2.&\quad\underline{\hspace{1in}}\\
    3.&\quad\underline{\hspace{1in}}\\
    \vdots&
  \end{align*}
\end{definition}

\begin{example}
  The set of natural numbers $\N$ is countable, as is any subset of $\N$.
\end{example}

\begin{example}
  The set of integers $\Z$ is countable. To see this, one can simply alternate between positive and negative integers: $0,+1,-1,+2,-2,+3,-3,\ldots$.
\end{example}

\begin{example}
  The set of rational numbers $\Q$ is countable. To see this, let us first show that the set of positive rational numbers $\Q_+$ is countable. Although the presences of the numerator and denominator make it seem like we would need infinitely many infinite lists, we can get around that by fixing the sum of the two and then letting it increase: begin with $\frac11$, then do $\frac12,\frac21$, then $\frac13,\frac22,\frac31$, then $\frac14,\frac23,\frac32,\frac41$, and so forth. The list does have duplicates such as $\frac11$ and $\frac22$, but this is allowed, as we could in principle run through and delete them if we wanted. Finally, we can add in the negative rationals by applying the same method as we did with $\Z$.
\end{example}

The following result can be handy for showing sets are countable.

\begin{lemma}
  \begin{itemize}
  \item If $A,B$ are countable, then the union $A\cup B$ is countable.
  \item If $A_1,A_2,\ldots$ is a sequence of countable sets, then $\bigcup A_n$ is countable.
  \end{itemize}
\end{lemma}

\begin{proof}
  For the first statement, since $A$ is countable we can enumerate its elements $a_1,a_2,a_3,\ldots$ and since $B$ is countable we can enumerate its elements $b_1,b_2,b_3,\ldots$. It follows that we can enumerate the elements of $A\cup B$ in the sequence $a_1,b_1,a_2,b_2,a_3,b_3\ldots$. (Formally we are describing $c_n$ where $c_{2n}=b_n$ and $c_{2n-1}=a_n$.) Thus $A\cup B$ is countable.

  We leave the proof of the second statement as an exercise.
\end{proof}

To show how this lemma can come in handy, we can use it recast the proof that $\Z$ is countable. It is obvious that the set $\Z_+$ of nonnegative integers is countable, and ditto for the negative integers $\Z_-$. Since $\Z$ is the union of the two sets, it follows that $\Z$ is countable.

We now come to the ``surprising'' fact hinted at above.

\begin{theorem}
  \label{thm:reals-uncountable}
  The set of real numbers $\R$ is \textbf{not} countable.
\end{theorem}

In order to prove this theorem, we need the following consequence of the Axiom of Completeness for the real numbers called the \emph{nested interval property}. This is a fact which we'll also use a few more times throughout the course.

\begin{theorem}[Nested interval property]
  Suppose that $I_n$ is a sequence of closed and bounded intervals, that is, $I_n=[a_n,b_n]$. Moreover suppose that the sequence is nested, that is, $I_{n+1}\subset I_n$. Then we have $\bigcap I_n\neq\emptyset$.
\end{theorem}

\begin{proof}
  Notice that the set of left endpoints $\set{a_n\mid n\in\N}$ is bounded above, because any of the $b_n$'s is an upper bound. By the Axiom of Completeness, the set $\set{a_n\mid n\in\N}$ has a least upper bound, call it $\alpha$.

  Then given any $n$, we have $a_n\leq\alpha$, since $\alpha$ is an upper bound for the set $\set{a_n\mid n\in\N}$. On the other hand, we also have $\alpha\leq b_n$, since $\alpha$ is the \emph{least} upper bound for the set $\set{a_n\mid n\in\N}$. It follows that $\alpha$ lies in the interval $I_n=[a_n,b_n]$. Since $n$ was arbitrary, we conclude that $\alpha$ lies in $\bigcap I_n$. This completes the proof.
\end{proof}

We are now ready to prove that the set of real numbers is uncountable.

\begin{proof}[Proof of Theorem~\ref{thm:reals-uncountable}]
  Suppose towards a contradiction that $\R$ is countable. Then its elements can be enumerated in a sequence $x_n$. Now inductively construct a nested sequence of closed, bounded intervals as follows. Let $I_1$ be any closed, bounded interval not containing $x_1$. Let $I_2$ be any closed subinterval of $I_1$ not containing $x_2$. Inductively, let $I_n\subset I_{n-1}$ be any closed interval not containing $x_n$. This completes the construction.

  Now by the NIP, there exists an element $\alpha\in\R$ such that $\alpha\in\bigcap I_n$. Now for each $n$, we have both $x_n\notin I_n$ and $\alpha\in I_n$, which implies that $\alpha\neq x_n$. This contradicts the claim that every element of $\R$ was enumerated in the sequence $x_n$!
\end{proof}

\begin{corollary}
  The set of irrational numbers is uncountable.
\end{corollary}

\begin{proof}
  Suppose towards a contradiction that the set of irrational numbers is countable. Then $\R=\Q\bigcup(\R\setminus\Q)$ is countable, being the union of two countable sets. This contradicts Theorem~\ref{thm:reals-uncountable}.
\end{proof}

\newpage
\subsection*{Activity for\S \thesection}

\begin{activity}
  \item Let $A$ be the set of integer lattice points in the plane, that is, $A=\set{(x,y):x,y\in\Z}$. Draw a picture of the set $A$. Prove $A$ is countable by showing how to write all its elements in a list. (Write the first 10+ elements, explain how you would continue, and explain why the completed list would include every element.)
  \vspace\fill
  \item Find a nested sequence of nonempty bounded intervals with empty intersection.
  \vspace\fill
  \item Find a nested sequence of nonempty closed intervals with empty intersection.
\end{activity}

% \begin{exerc}
%   Show that the set of Gaussian integers is countable. Recall that the Gaussian integers is the set of all complex numbers of the form $a+bi$ where $a,b\in\Z$.
% \end{exerc}
%
% \begin{exerc}
%   Suppose that for every $n$, the set $A_n$ is countable. Show that the set $A=\bigcup A_n$ is countable. [See the hint described in Exercise~1.5.3(c).]
% \end{exerc}
%
% \begin{exerc}
%   Show that the set $\N^3$ is countable. Here $\N^3$ consists of all triples of the form $(a,b,c)$, where $a,b,c\in\N$. [Hint: use the previous two exercises.]
% \end{exerc}
%
% \begin{exerc}
%   \begin{enumerate}
%     \item Find a nested family of nonempty bounded intervals with empty intersection.
%     \item Find a nested family of nonempty closed intervals with empty intersection.
%   \end{enumerate}
% \end{exerc}

\vspace{\fill}
\begin{readnext}
  Abbott, \S 1.6
\end{readnext}

\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{More on countability and uncountability}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{reading}
  Abbott, \S 1.6
\end{reading}

In the previous section we saw that among the infinite sets, some of them are not too big (countable sets) while others are much larger (uncountable sets). Showing that a set is countable requires a direct argument---write down how to enumerate all its elements in a sequence. Showing that a set is uncountable often requires an indirect argument---assume the set is countable and find a contradiction.

We were able to show that $\R$ is uncountable using the Nested Interval Property. But that proof was very particular to the set of real numbers. How would we show that some other given set is uncountable? It turns out there is another and more systematic way to prove that $\R$ is uncountable, due the mathematician Cantor. The method is called \emph{diagonalization}, and uses the decimal digit system.

\begin{theorem}
  The unit interval $(0,1)$ is uncountable.
\end{theorem}

\begin{proof}
  Suppose towards a contradiction that $(0,1)$ is countable. Then the elements of $(0,1)$ can all be enumerated in a sequence $a_n$. We need to analyze the digits of each entry of this sequence, so let us fix some notation for them:
  \begin{align*}
    a_1&=0.a_{11}\,a_{12}\,a_{13}\cdots\\
    a_2&=0.a_{21}\,a_{22}\,a_{33}\cdots\\
    a_3&=0.a_{31}\,a_{32}\,a_{33}\cdots\\
    \vdots&
  \end{align*}
  We now define a ``diagonal'' real number $d\in(0,1)$ with a decimal expansion $d_n$ with the property that for all $n$
  \[d_n\neq a_{nn}
  \]
  We can even give an explicit definition of the digits $d_n$ that achieves this property. For instance we may let $d_n=2$ when $a_{nn}\neq2$ and let $d_n=3$ when $a_{nn}=2$. It then follows that for all $n$, we have $d\neq a_n$. Thus $d$ is an element of $(0,1)$ which does not appear in the sequence $a_n$, contradicting our assumption that every element of $(0,1)$ appears in the sequence $a_n$.
\end{proof}

In the exercises you will be asked to use diagonalization on other kinds of sets.

The dichotomy between countable and uncountable sets suggests that one should further investigate the possibilities for the size of an infinite set. Recall that for finite sets we write $|A|$ for the number of elements of $A$. However for infinite sets this definition of $|A|$ isn't a good one anymore. What is needed is the following.

\begin{definition}
  Suppose that $A,B$ are sets. Then we introduce the following notation:
  \begin{itemize}
  \item We write $|A|\leq|B|$ if there is a one-to-one function $A\to B$
  \item We write $|A|=|B|$ if there exists a one-to-one, onto function $A\to B$
  \item We write $|A|<|B|$ if we have $|A|\leq|B|$ and $|A|\neq|B|$.
  \end{itemize}
\end{definition}

This definiton is consistent with the ``number of elements'' definition of $|A|$ when $A$ is finite. However, while the terms ``number of elements'', ``more'', and ``fewer'' all lose their meaning for infinite sets, the notions of one-to-one and onto functions remain meaningful.

We call $|A|$ the \emph{cardinality} of $A$. It is important to understand that we never defined what $|A|$ actually is, only how it compares with other set cardinalities $|B|$. Using set theory we can also define what $|A|$ actually is, but it isn't necessary for this class.

Cantor's theorem can be generalized to show that for any set there is a set of even larger cardinality. Therefore there is no bound on the number of different sizes of infinity! Recall that if $A$ is any set, the \emph{power set} $\mathcal P(A)$ is the set of all subsets of $A$. Of course if $A$ is finite, then we have $|\mathcal P(A)|=2^{|A|}$ so in particular $|A|<|\mathcal P(A)|$. It turns out that this works for infinite sets too.

\begin{theorem}
  If $A$ is any set, then $|A|<|\mathcal P(A)|$.
\end{theorem}

\begin{proof}
  To show that $|A|\leq|\mathcal P(A)|$ we must exhibit a one-to-one function $A\to\mathcal P(A)$. For this, we can use the function $i(a)=\{a\}$.

  To show that $|A|\neq|\mathcal P(A)|$, we have to show that there is no one-to-one, onto function $f\colon A\to\mathcal P(A)$. For this, suppose that $f\colon A\to\mathcal P(A)$ is any function. Then we consider the ``diagonal'' set $D$:
  \[D=\set{a\in A\mid a\notin f(a)}
  \]
  We claim that $D$ is not in the range of $f$, and therefore that $f$ is not onto. To see this, suppose towards a contradiction that there exists $a_0\in A$ such that $D=f(a_0)$. Then by the definition of $D$, we have that $a_0\in D$ iff $a_0\notin f(a_0)$. And since $D=f(a_0)$ we can write this as $a_0\in D$ iff $a_0\notin D$, which is a clear contradiction.
\end{proof}

It is natural to ask to what extent cardinalities behave like ordinary finite counting numbers. For instance, is it possible to have two sets which are \emph{incomparable} in size, that is $|A|\not\leq|B|$ and $|B|\not\leq|A|$? If we assume all of the standard axioms about sets (including the axiom of choice) then this situation is impossible.

\begin{theorem}
  If $A,B$ are any sets, then exactly one of the following is true: $|A|<|B|$, $|A|=|B|$, or $|B|<|A|$.
\end{theorem}

Another natural question is whether the cardinality of $\R$ is the \emph{smallest} uncountable cardinality. Many very narrow or thin subsets of $\R$ still have the full cardinality of $\R$. Just consider $(0,1)$ or $(0,\epsilon)$ or the set of irrationals. So the question is whether for any set $A$ of real numbers, if $A$ is uncountable then is it necessarily true that $|A|=|\R|$?

This question is known as the \emph{continuum hypothesis} and has great historical significance. After remaining open for many decades, it was finally settled in a surprising way: the answer is \emph{undecidable} using the accepted axioms of mathematics! In other words, there is a universe of mathematics in which the continuum hypothesis is true, and also a universe of mathematics in which it is false.

Since this stunning resolution to the continuum hypothesis was found in 1965, the occurrence and nature of undecidable statements has remained of key interest to mathematicians.

\newpage
\subsection*{Activity for \S \thesection}

In the following, let $S_{\infty}$ be the set of all \emph{infinite} words made with the letters $a,b$. So $S_\infty$ contains elements like $aaaa\cdots$, $ababa\cdots$, $aabaabaab\cdots$, also non-repeating strings like $abaabaaabaaaab\cdots$, and even strings with no discernible pattern whatsoever.

\begin{activity}
  \item Write any ten elements of $S_{\infty}$. Include at least ten letters in each element (with the understanding that the words continue indefinitely, either according to a pattern or arbitrarily).
  \begin{align*}
    s_1   & = \underline{\hspace{3in}\cdots} \\
    s_2   & = \underline{\hspace{3in}\cdots} \\
    s_3   & = \underline{\hspace{3in}\cdots} \\
    s_4   & = \underline{\hspace{3in}\cdots} \\
    s_5   & = \underline{\hspace{3in}\cdots} \\
    s_6   & = \underline{\hspace{3in}\cdots} \\
    s_7   & = \underline{\hspace{3in}\cdots} \\
    s_8   & = \underline{\hspace{3in}\cdots} \\
    s_9   & = \underline{\hspace{3in}\cdots} \\
    s_{10}& = \underline{\hspace{3in}\cdots} \\
  \end{align*}
  \item Write the first ten letters of the \emph{diagonal} word $d$ with the property that for all $n$, $d$ disagrees with $s_n$ on the $n$th letter.
  \item Write the definition of $d$ in the abstract (not just in this example).
  \[d=\begin{cases}
    \underline{\hspace{.5in}} & \text{if }s_{nn}=\underline{\hspace{.5in}}\\
    \underline{\hspace{.5in}} & \text{if }s_{nn}=\underline{\hspace{.5in}}
  \end{cases}
  \]
  \item Write out the proof that $S_{\infty}$ is uncountable.
\end{activity}

% Prove that R and P(N) have the same cardinality.

% (See also Abbott, ex 1.5.9). Recall that a real number $\alpha$ is called \emph{algebraic} if there exists a polynomial $p$ with integer coefficients such that $p(\alpha)=0$. Is the set $A$ of all algebraic numbers countable or uncountable? Prove your assertion.

\vspace\fill
\begin{readnext}
  Abbott, \S 2.1
\end{readnext}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\chapter{Sequences and series}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Infinity and arithmetic}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\label{sec:sequences}

\begin{reading}
  Abbott, \S 2.1
\end{reading}

A sequence of real numbers consists of one real number $a_n$ for each natural number $n$. Officially a sequence is a \emph{function} from $\N$ to $\R$. However sequences are so special that we rarely use the function notation $a(n)$ and instead prefer the traditional notation $a_n$. We have already used sequences, for instance in the definition of a countable set. We will see later in the course that sequences play a huge role in analysis. In this section we give further motivation for studying sequences and the sibling concept of series.

To begin consider the simple addition problem $\pi+e$, which we write out in decimal notation as
\begin{align*}
     &3.14159265\cdots\\
  {}+&2.71828182\cdots
\end{align*}
It is unclear how to begin this problem. Our usual method of carrying would have us start at the right-most digit, but there isn't one! It is possible to handle this issue by regarding $\pi$ and $e$ as cuts. But it is even more elegant to regard each of $\pi$ and $e$ as the limit of a sequence, and perform the addition term-by-term.

Another problem with addition is the prospect of adding together infinitely many numbers at once. Sometimes this clearly isn't possible; for example the sum
\[1+1+1+1+\cdots
\]
is infinite and has no value in the real numbers. On the other hand the familiar Zeno paradox asks whether the sum
\[1+\frac12+\frac14+\frac18+\cdots
\]
has any value in the real numbers, and we usually agree that it has the value $2$. It seems that sometimes it makes sense to add together infinitely many numbers, and other times it doesn't.

But this conclusion deserves a great deal of scrutiny. To see why, consider the following simple proof that the Zeno series has a value of $2$. We first notice that
\begin{align*}
  \left(1+\frac12+\frac14+\frac18+\cdots\right)-1
  &=\frac12+\frac14+\frac18+\cdots\\                                  
  &=\frac12\left(1+\frac12+\frac14+\cdots\right)
\end{align*}
Thus we see that if $x=1+\frac12+\frac14+\frac18+\cdots$, then $x$ satisfies the equation $x-1=\frac12x$ and therefore $x=2$.

Now let us apply this proof to the series $1+2+4+8+\cdots$. Again write
\begin{align*}
  (1+2+4+8+\cdots)-1&=2+4+8+\cdots\\
                    &=2(1+2+4+\cdots)
\end{align*}
This time we conclude that if $x=1+2+4+8+\cdots$ then $x$ satisfies the equation $x-1=2x$ and therefore that $x=-1$, which is nonsense! (Or is it?)

Finally, even if we do accept some infinite sums as valid, we still should decide whether the familiar laws of associativity and commutativity of addition are applicable to the terms of infinite sums. To see the potential difficulty, consider two ways of grouping the terms of the same infinite summation:
\begin{align*}
S_1&=(1-1)+(1-1)+(1-1)+\cdots\\
S_2&=1+(-1+1)+(-1+1)+\cdots
\end{align*}
Using the first grouping, we obtain a value of $0$. Using the second grouping, we obtain a value of $1$.

Commutativity has similar issues. For example, consider two ways of summing the same series:
\begin{align*}
S_1&=1-\frac12+\frac13-\frac14+\frac15-\frac16+-\cdots\\
S_2&=1+\frac13-\frac12+\frac15+\frac17-\frac14++-\cdots
\end{align*}
In the second summation we first add two of the positive terms before then adding one of the negative terms. A quick approximation with a calculator reveals that $S_1\approx0.69$ while $S_2\approx1.03$. This time we conclude that even if infinite summations are possible, one must be very careful when applying the usual laws of arithmetic to them!

\newpage
\subsection*{Activity for \S \thesection}

\begin{activity}
  \item Consider the following infinite summation:
  \[1-\frac12+\frac13-\frac14+\frac15-+\cdots
  \]
  \begin{itemize}
    \item Try to reorder the terms to make the sum as close as possible to $0.5$. Use at least 15 terms to be sure you are actually representing your pattern.
    \item Try to reorder the terms to make the sum as close as possible to $1$.
    \item Try to reorder the terms to make the sum as close as possible to $1.5$.
  \end{itemize}
  Were you (approximately) successful in each case? If so, write down your pattern and result. If not, what barrier did you encounter?
  \vspace{2in}
  \item This time consider the following infinite summation:
  \[1-\frac12+\frac14-\frac18+\frac{1}{16}-+\cdots
  \]
  \begin{itemize}
    \item Try to reorder the terms to make the sum as close as possible to $0.5$. Use at least 15 terms to be sure you are actually representing your pattern.
    \item Try to reorder the terms to make it come as close as possible to $1$.
    \item Try to reorder the terms to make it come as close as possible to $1.5$.
  \end{itemize}
  Were you (approximately) successful in each case? If so, write down your pattern and result. If not, what barrier did you encounter?
\end{activity}

\vspace\fill
\begin{readnext}
  Abbott, \S 2.2
\end{readnext}

\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Convergence}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{reading}
  Abbott, \S 2.2
\end{reading}

Recall that a \emph{sequence} is a list of one real number $a_n$ for every natural number $n$. The most important characteristic of a sequence is whether it converges or diverges. Intuitively a sequence $a_n$ converges to a limit point $L$ if the sequence eventually comes as close to $L$ as one could ever wish.

\begin{definition}
  The sequence $a_n$ \emph{converges} to $L$ if the following holds:
  \[(\forall\epsilon>0)\;(\exists N\in\N)\;(\forall n\geq N)\;|a_n-L|<\epsilon
  \]
  In this case we write both $\lim a_n=L$ and also $a_n\to L$, and we say that $L$ is the \emph{limit} of the sequence.
\end{definition}

Since the definition is both of central importance and also somewhat subtle, we will analyze it in great detail.

\begin{itemize}
  \item The $(\forall\epsilon>0)$ clause. We think of $\epsilon$ as a very small \emph{tolerance}. Thus the definition of convergence begins by saying that for all possible tolerances, something will happen.
  \item The $(\exists N\in\N)\;(\forall n\geq N)$ clause. This means that \emph{eventually} in the timeline of the sequence, something will become true, and then continue to be true forever.
  \item The $|a_n-L|<\epsilon$ clause. This means that $a_n$ lies within a small \emph{neighborhood} of $L$. Formally, if $x$ is any real number and $\epsilon>0$, then the \emph{$\epsilon$-neighborhood} of $x$, denoted $N_\epsilon(x)$, is the open interval centered at $x$ of radius $\epsilon$. In symbols:
  \[N_\epsilon(x)=(x-\epsilon,x+\epsilon)=\set{y\in\R\mid|y-x|<\epsilon}
  \]
  Thus the conclusion of the definition of convergence says precisely that $a_n$ lies within the $\epsilon$-neighborhood of $L$.
\end{itemize}

To summarize, the statement that $a_n$ converges to $L$ says:
\begin{quotation}
 ``For all tolerances $\epsilon>0$, eventually, the terms of the sequence lie in the $\epsilon$-neighborhood of $L$.''
\end{quotation}

So how does one show that a given sequence converges to a specified limit? One way to think of verifying the three-quantifier definition holds true is to play a three-step game. Your enemy takes the first turn and gives you some (small) value of $\epsilon$. You respond by calculating a (large enough) natural number $N$. Your enemy then responds by choosing a number $n\geq N$. Finally, you win if you can show that $|a_n-L|<\epsilon$, or in other words, $L-\epsilon<a_n<L+\epsilon$.

\begin{example}
  Let us confirm from the definition that $\lim1/\sqrt{n}=0$. Suppose that $\epsilon$ is given to us. We must find a value $N$ (depending on this $\epsilon$) with the property that whenever $n\geq N$ we have $-\epsilon<1/\sqrt{n}<\epsilon$. Since $1/\sqrt{n}$ is always positive, we only have to worry about the second inequality.

  To get an idea of how this is going to work, if $\epsilon=.1$ then we would need to take $N=101$. Similarly if $\epsilon=.01$ then we would need to take $N=10,001$. In general we can figure out the needed relationship by working backwards. We want
  \begin{align*}
    1/\sqrt{n}<\epsilon &\iff \sqrt{n}>1/\epsilon\\
                        &\iff n>1/\epsilon^2
  \end{align*}
  This tells us we should choose $N>1/\epsilon^2$. Technically $N$ has to be a natural number, but we can just take $N$ to be the first natural number $N>1/\epsilon^2$.

  Finally we can write the proof forwards as follows. Given any $\epsilon>0$, we let $N$ be any natural number such that $N>1/\epsilon^2$. Then for all $n\geq N$ we have
  \begin{align*}
    n>1/\epsilon^2&\implies\sqrt{n}>1/\epsilon\\
                  &\implies1/\sqrt{n}<\epsilon
  \end{align*}
  Since we always have $-\epsilon<1/\sqrt{n}$, the proof is complete.\qed
\end{example}

\begin{example}
  Let us confirm from the definition that $n/(n+1)\to1$. So let $\epsilon$ be given; we wish to conclude that eventually $1-\epsilon<n/(n+1)<1+\epsilon$. Since $n/(n+1)$ is always less than $1$, we only have to worry about the first inequality. To see the needed value of $N$ we work backwards:
  \begin{align*}
    1-\epsilon<n/(n+1)&\iff 1-n/(n+1)<\epsilon \\
                      &\iff 1/(n+1)<\epsilon \\
                      &\iff n+1>1/\epsilon \\
                      &\iff n>1/\epsilon-1
  \end{align*}
  Thus the needed value of $N$ is $1/\epsilon-1$. To simplify the calculation, it will be good enough to take $N>1/\epsilon$.
  
  Now to write the proof forwards, let $\epsilon$ be given and let $N$ be a natural number such that $N>1/\epsilon$. Then for all $n\geq N$ we have
  \begin{align*}
    1-n/(n+1) &= 1/(n+1)\\
              &< 1/n\\
              &\leq 1/N
              &<\epsilon
  \end{align*}
  Thus $1-\epsilon < n/(n+1)$, as desired.\qed
\end{example}

So far we have discussed only convergence. What happens when a sequence $a_n$ does \emph{not} converge to $L$? Formally negating the definition of convergence, this says
\[(\exists\epsilon>0)\;(\forall N\in\N)\;(\exists n\geq N)\;|a_n-L|\geq\epsilon
\]
Intuitively this says that there is some tolerance $\epsilon$ such that the sequence frequently lies outside the $\epsilon$-neighborhood of $L$.

\begin{example}
  Consider the following sequence with the terms, and discuss whether it converges to $0$ or not:
  \[1,-\frac12,+\frac13,-\frac14,+\frac15,-\frac15,+\frac15,-\frac15,\ldots
  \]
  If $\epsilon$ has a given value of $.5$ it is possible to find a suitable response $N$ which satisfies the definition of convergence. The same is true if $\epsilon=.25$. But if $\epsilon=.2$ then it is \emph{not} possible, so we conclude that the sequence does not converge to $0$
\end{example}

In general, we say that a sequence \emph{diverges} if for every $L$, the sequence does not converge to $L$.

In this section we made a formal definition of limit, and used it to verify several routine instances of convergence and non-convergence. This may make it seem that the purpose of the definition is to make routine calculations. Instead the opposite is true: we make routine calculations to help affirm that the definition is a good one.

\newpage
\subsection*{Activity for \S \thesection}

\begin{activity}
  \item In each case, prove the given sequence converges to the proposed limit directly from the definition of convergence.
  \begin{enumerate}\itemsep\fill
    \item $\displaystyle\lim\frac{1}{6n^2+1}=0$
    \item $\displaystyle\lim\frac{3n-1}{2n+5}=\frac32$
    \item $\displaystyle\lim\frac{\sin(n)}{n}=0$
    \item $\displaystyle\lim2^{1/n}=1$
  \end{enumerate}
  \vspace\fill
  \item Prove the given sequence \emph{does not} converge to the proposed limit directly from the \emph{negation} of the definition of convergence.
  \begin{center}
    Sequence: $0.1,0.01,0.1,0.01,0.1,0.01,\ldots$. Proposed limit: $0$.
  \end{center}
\end{activity}

\vspace\fill
\begin{readnext}
  Abbott, \S 2.3
\end{readnext}


\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Limit calculus}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{reading}
  Abbott, \S 2.3
\end{reading}

In the previous section we gave a rigorous definition of the limit of a sequence, and checked that it corresponds with our intuition for several special examples. In this section we begin our study of \emph{calculus}, that is, the laws or rules for calculating limits, derivatives, and integrals. Of course calculus usually focuses on the derivatives and integrals, but before we can get there we must first understand limits.

Before we begin recall the \emph{triangle inequality} states that for any $x,y$ we have $||x|-|y||\leq|x-y|\leq|x|+|y|$. The triangle inequality is actually best visualized in two (or more) dimensions, where it says that if $x$ is $|x|$ units from the origin, and $y$ is $|y|$ units from the origin, then the distance between $x$ and $y$ cannot be less than $||x|-|y||$, and cannot be more than $|x|+|y|$. Since the sign of $y$ doesn't matter, we can write:
\[||x|-|y||\leq|x\pm y|\leq|x|+|y|
\]

\begin{figure}[h]
  \centering
  \begin{tikzpicture}
    \draw (0,0) circle (.8);
    \draw (0,0) circle (1.3);
    \node[circle,draw,inner sep=1] at (0,0) {};
    \node[circle,fill,draw,inner sep=1,label=left:$x$] (x) at (30:.8) {};
    \node[circle,fill,draw,inner sep=1,label=right:$y$] (y) at (30:1.3) {};
    \draw (x)--(y);
  \end{tikzpicture}
  \quad
  \begin{tikzpicture}
    \draw (0,0) circle (.8);
    \draw (0,0) circle (1.3);
    \node[circle,draw,inner sep=1] at (0,0) {};
    \node[circle,fill,draw,inner sep=1,label=right:$x$] (x) at (30:.8) {};
    \node[circle,fill,draw,inner sep=1,label=left:$y$] (y) at (30:-1.3) {};
    \draw (x)--(y);
  \end{tikzpicture}
  \caption{Intuitive justification for the triangle inequality. On the left, $x$ and $y$ are as close together as possible at $||x|-|y||$ units. On the right, $x$ and $y$ are as far apart as possible at $|x|+|y|$ units.}
\end{figure}

We can now state the limit calculus laws. The proof is long, but the method of proof is very important and worth exploring at least until it becomes familiar (and somewhat tedious).

\begin{theorem}[Limit calculus]
  Suppose that $\lim a_n=a$ and $\lim b_n=b$. Then we have
  \begin{enumerate}
    \item $\lim a_n+b_n=a+b$
    \item $\lim ka_n=ka$ for any $k\in\R$
    \item $\lim a_nb_n=ab$
    \item $\lim a_n/b_n=a/b$ provided $b_n,b\neq 0$
    \item $\lim \sqrt{a_n}=\sqrt{a}$ provided $a_n\geq0$
  \end{enumerate}
\end{theorem}

\begin{proof}
  \begin{enumerate}
  \item This is our first example of a so-called ``$\epsilon/2$-argument.'' If $\epsilon>0$ is given, we cleverly apply the convergence of $a_n$ and $b_n$ to the tolerance value $\epsilon/2$. Thus there exists an $N_1$ such that for all $n\geq N_1$ we have $|a_n-a|<\epsilon/2$, and there exsits an $N_2$ such that for all $n\geq N_2$ we have $|b_n-b|<\epsilon/2$. Thus if $n\geq\max(N_2,N_2)$, we have
    \begin{align*}
      |(a_n+b_n)-(a+b)|&=|(a_n-a)+(b_n-b)|\\
      &\leq|a_n-a|+|b_n-b|\\
      &<\epsilon/2+\epsilon/2\\
      &=\epsilon
    \end{align*}
    In other words, we use the triangle inequality to \emph{split} the distance between $a_n+b_n$ and $a+b$ into two portions, each of which we can bound.
  \item This is similar but easier; we just use an $\epsilon/|k|$ argument. Given $\epsilon$, we can find $N$ such that for all $n\geq N$ we have $|a_n-a|<\epsilon/|k|$. It follows that $|ka_n-ka|<\epsilon$, as desired.
  \item Given $\epsilon$, we wish to show that eventually we have $|a_nb_n-ab|<\epsilon$. To see what we will need, we calculate
    \begin{align*}
      |a_nb_n-ab|&\leq|a_nb_n-ab_n+ab_n-ab|\\
      &\leq|a_nb_n-ab_n|+|ab_n-ab|\\
      &=|a_n-a||b_n|+|a||b_n-b|
    \end{align*}
    Since $b_n$ converges, we can find a bound $M$ such that $|b_n|\leq M$ for all $n$ (see below). Now since $a_n$ and $b_n$ converge, we can find an $N$ large enough so that for $n\geq N$ we have both $|a_n-a|<\epsilon/2M$ and $|b_n-b|<\epsilon/2|a|$. Together with the calculation above, we thus conclude that $|a_nb_n-ab|<\epsilon$, as desired.
  \item[(d),(e)] The proof of (d) is similar to (c), and the proof of (e) is left as an exercise.
  \end{enumerate}
\end{proof}

\begin{example}
  We can now verify that $\frac{n}{n+1}\to1$ as follows:
  \begin{align*}
    \lim\frac{n}{n+1}&=\frac1{\lim\frac{n+1}{n}}\\
    &=\frac1{\lim 1+1/n}\\
    &=\frac1{1+\lim 1/n}\\
    &=1
  \end{align*}
\end{example}

Before we continue, we owe

\begin{definition}
  The sequence $a_n$ is \emph{bounded} if there exists some $M\in\R$ such that for all $n$ we have $|a_n|\leq M$.
\end{definition}

It is equivalent to say that $a_n$ is bounded if there exists an interval $[a,b]$ such that $\{a_n\}\subset[a,b]$.

\begin{proposition}
  If $a_n$ is convergent, then $a_n$ is bounded.
\end{proposition}

\begin{proof}
  Suppose $a_n\to L$, so that for all $\epsilon$ we can find $N$ such that $|a_n-L|<\epsilon$ whenever $n>N$. In particular whenever $n\geq N$ we have that $|a_n|\leq|a_n-L|+|L|<\epsilon+|L|$. Thus we may take $M_0=\epsilon+|L|$ as a bound for these terms.

  Meanwhile all that remains of the sequence is the finite initial segment $a_1,\ldots,a_N$. Letting $M_1=\max(|a_1|,\ldots,|a_N|)$, we of course have for all $n\leq N$ that $|a_n|\leq M_1$. It follows that the full sequence is bounded by the constant $M=\max(M_0,M_1)$.
\end{proof}

The converse of this Proposition is false, with a simple example being the sequence with terms $+1,-1,+1,-1,\ldots$.

The limit calculus theorem above provides a method of establishing convergence using algebraic properties of the sequence. Another key method of establishing convergence is using the order properties of sequence. The result is sometimes known as the \emph{squeeze theorem}.

\begin{theorem}[Squeeze theorem]\
  \begin{itemize}
  \item If $a_n\geq0$ and $\lim a_n$ exists then $\lim a_n\geq0$.
  \item If $a_n\leq b_n\leq c_n$ and $\lim a_n=\lim c_n=L$ then $\lim b_n$ exists and $=L$.
  \end{itemize}
\end{theorem}

\begin{proof}
  For the first statement, suppose towards a contradiction that $a=\lim a_n<0$. Then applying the definition of convergence to $\epsilon=-a$ we see that eventually $|a_n-a|<-a$. It follows that $a_n-a<-a$ and hence $a_n<0$, which is a contradiction.

  For the second statement, first note that by the limit laws $\lim(c_n-a_n)=0$. Thus given $\epsilon$ we eventually have both $c_n-a_n<\epsilon/2$ and also $|a_n-L|<\epsilon/2$. Now we calculate that
  \begin{align*}
    |b_n-L|&=|b_n-a_n+a_n-L|\\
    &\leq b_n-a_n+|a_n-L|\\
    &\leq c_n-a_n+|a_n-L|\\
    &<\epsilon
  \end{align*}
  and thus $\lim b_n=L$, as desired.
\end{proof}

\begin{example}
  We can now show that $\lim\frac{1}{n^2}e^{1/n}\to0$ by writing $0\leq\frac{1}{n^2}e^{1/n}\leq\frac{e}{n^2}$ and noting the left and right sides converge to $0$.
\end{example}

\newpage
\subsection*{Activity for \S \thesection}

\begin{activity}
  \item Use the limit calculus and/or the squeeze theorem to evaluate the limits. Carefully justify all of your steps.
  \begin{enumerate}\itemsep\fill
    \item $\lim(2+\frac1n)^2$
    \item $\lim\frac{1}{3n^2-n}$
    \item $\lim\left(\frac{2n^2-3n+2}{3n^2+4n+1}\right)^{100}$
    \item $\lim\frac{\sqrt{n^2+1}}{n-2}$
    \item $\lim\frac{\sin(n)}{n}$
    \item $\lim\frac{2n+\cos(n)}{n+2}$
    % \item $\lim\frac{\arctan(n)}{n\sqrt{n}}$
    \vspace\fill
  \end{enumerate}
\end{activity}

% \begin{exerc}
%   Prove that a sequence can have at most one limit. In other words, suppose that $a_n$ converges to $L$ \textbf{and} suppose that $a_n$ converges to $M$. Using the definition of limit directly (and not the limit laws), prove that $L=M$.
% \end{exerc}

% \begin{exerc}[Abbott, ex 2.3.5]
%   Let $a_n$ and $b_n$ be sequences, and let $c_n$ be the ``shuffled'' sequence
%   \[a_1,b_1,a_2,b_2,\ldots
%   \]
%   Show that $c_n$ is convergent if and only if $a_n$ and $b_n$ are both convergent and both have the same limit.
% \end{exerc}
%
% \begin{exerc}
%   \begin{enumerate}
%     \item Give an example of a sequence where $\lim a_n=\sup a_n$.
%     \item Give an example of a sequence where $\lim a_n=\inf a_n$.
%     \item Give an example of a sequence where $\lim a_n$ exists and is neither $\sup a_n$ nor $\inf a_n$.
%   \end{enumerate}
% \end{exerc}
%
% \begin{exerc}
%   Imitate the logical structure of the definition of convergence to give a rigorous definition for the statement ``$a_n$ converges to $\infty$''.
%
%   Use your definition to prove that the sequence $a_n=\sqrt{n}$ converges to $\infty$.
%
%   What does your definition say about the sequence:
%   \[1,0,2,0,3,0,4,0,5,0,\ldots
%   \]
% \end{exerc}

\begin{readnext}
  Abbott, \S 2.4
\end{readnext}


\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Convergence and summations}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{reading}
  Abbott, \S 2.4
\end{reading}

In this section we begin to look at convergence in the context of series summations. We will define what it means for an infinite series to converge, and give a first look into the so-called convergence tests. We will return to convergence tests later on.

\begin{definition}
  If $a_n$ is any sequence then the \emph{sequence of partial sums} of the $a_n$ is the sequence $S_N$ with terms
  \[S_n=a_1+\cdots+a_n=\sum_1^na_k
  \]
  We say that the series $\sum a_n$ \emph{converges} and equals $L$ if the sequence of partial sums $S_n$ converges to $L$ in the ordinary sense.
\end{definition}

This definition answers the question of how the terms of an infinite sum are supposed to be grouped. When we write $\sum a_n$, we mean $\cdots(((a_1+a_2)+a_3)+a_4)+\cdots$

It is important to remark that the sequence of terms $a_n$ and the sequence of partial sums $S_n$ are both just ordinary sequences. The precise relation ship between the two is given by the two equations:
\begin{align*}
  S_n&=a_1+\cdots+a_n\\
  a_n&=S_n-S_{n-1}
\end{align*}

It is natural to ask about the relationship between convergence of $a_n$ and convergence of $S_n$. We will see later on that if $S_n$ converges then $a_n$ converges too. On the other hand the converse is false, that is, $a_n$ may converge while $S_n$ diverges. For a simple example, if $a_n$ is the sequence $1,1,1,\ldots$ then $S_n$ is the sequences $1,2,3,\ldots$, and this clearly diverges.

The definition of $S_n$ as a sum of a variable number of terms frequently makes it difficult to compute its values exactly. Still, sometimes one can find tricks to do so, such as with the following ``geometric'' sequence.

\begin{example}
  \label{ex:geometric}
  The series with terms $a_n=1/2^n$, beginning at $n=1$, has partial sums $S_1=1/2$, $S_2=3/4$, $S_3=7/8$, $S_4=15/16$, etc. It is easy to prove by induction that
  \[S_n=\frac{2^n-1}{2^n}
  \]
  This calculates to $S_n=1-1/2^n$ which makes it clear that $S_n\to1$. In series notation, we write $\sum1/2^n=1$.
\end{example}

It is not usually so easy to calculate the exact value of $S_n$ and of $\sum a_n$. Thus when given a series, we usually begin with the simpler question of whether it converges at all, or whether it diverges.

\begin{example}
  \label{ex:1/n^2}
  The series $\sum1/n^2$ converges. In fact the value is $\pi^2/6$, but this fact rests on some serious calculus! Rather than calculate the partial sums exactly, we will show only that the sequence $S_n$ of partial sums is bounded as follows. 
  \begin{align*}
    S_{2^n}&=1+\left(\frac14+\frac19\right)
             +\left(\frac1{16}+\frac1{25}+\frac1{36}+\frac1{49}\right)
             +\cdots
             +\frac1{(2^n)^2}\\
           &\leq1+2\left(\frac14\right)+4\left(\frac1{16}\right)
             +\cdots+2^{n-1}\left(\frac1{(2^{n-1})^2}\right)+\frac1{(2^n)^2}\\
           &\leq1+\sum\frac1{2^n}=2
  \end{align*}
  This shows that $S_{2^n}$ is bounded by $2$, and since the sequence $S_n$ is increasing, clearly the whole sequence $S_n$ is bounded by $2$. The next result implies that we can conclude $\sum1/n^2$ converges even without knowing its value.
\end{example}

\begin{theorem}[Monotone convergence theorem]
  Suppose that $b_n$ is a monotone increasing sequence, that is, for all $n$ we have $b_n\leq b_{n+1}$. Suppose further that $b_n$ is bounded. Then $b_n$ converges to the limit $L=\sup(b_n)$.
\end{theorem}

\begin{proof}
  Let $\epsilon>0$ be given. Since $L$ is an upper bound for the $b_n$, we have $b_n\leq L$ for all $n$. Since $L$ is the least upper bound for the $b_n$, we can find a particular element $b_N$ of the sequence such that $b_N>L-\epsilon$. Since the sequence is monotone increasing, $n>N\implies b_n>L-\epsilon$ as well. Thus for all $n>N$ we have $L-\epsilon<b_n<L+\epsilon$, and the convergence is established.
\end{proof}

To complete Example~\ref{ex:1/n^2}, we know that the sequence of partial sums $S_n$ is increasing and bounded above by $2$, therefore it is convergent. Hence the series $\sum1/n^2$ converges to some unknown value $\leq2$.

We conclude our examples with a divergent series.

\begin{example}
  The series $\sum 1/n$ looks similar to the previous one, but in fact it diverges. To prove this, we show that the sequence of partial sums is unbounded using a similar grouping trick.
\begin{align*}
  S_{2^n} &= 1+\frac12+\frac13+\frac14+\frac15+\frac16+\frac17+\frac18+
            \cdots+\frac1{2^n}\\
          &\geq 1+\frac12+\left(\frac14+\frac14\right)
            +\left(\frac18+\frac18+\frac18+\frac18\right)
            +\cdots+2^{n-1}\frac1{2^n}\\
          &=1+n\left(\frac12\right)
\end{align*}
It follows that the sequence of partial sums $S_n$ is unbounded and therefore divergent.
\end{example}

The method of this last two examples can be used in a wide variety of situations. We can package this method of proof in the following convergence test.

\begin{theorem}[Condensation test]
  If $a_n$ is a positive, decreasing sequence, then $\sum a_n$ converges if and only if $\sum2^ka_{2^k}$ converges.
\end{theorem}

% Can omit the proof...

\begin{proof}
  First suppose that $\sum2^ka_{2^k}$ converges and let $S_n$ denote the partial sums of the sequence $a_n$. Then
  \begin{align*}
    S_{2^n}&=a_1+(a_2+a_3)+\cdots+(a_{2^{n-1}}+\cdots+a_{2^n-1})+a_{2^n}\\
           &\leq a_1+2a_2+\cdots+2^{n-1}a_{2^{n-1}}+2^na_{2^n}\\
           &\leq\sum2^ka_{2^k}
  \end{align*}
  Thus the monotone convergence theorem implies that $S_n$ converges, in other words that $\sum a_n$ converges.

  Conversely suppose that $\sum a_n$ converges and let $T_k$ be the partial sums of the sequence $2^ka_{2^k}$. Then
  \begin{align*}
    T_k&=a_1+2a_2+4a_4+\cdots+2^ka_{2^k}\\
       &\leq 2a_1+2a_2+2(a_3+a_4)+\cdots+2(a_{2^{k-1}+1}+\cdots+a_{2^k})\\
       &\leq 2\sum a_n
  \end{align*}
  Thus again the monotone convergence theorem implies that $T_k$ converges, in other words that $\sum2^ka_{2^k}$ converges.
\end{proof}

The condensation test may be applied to our earlier examples as follows.
\begin{itemize}
\item To test whether $\sum1/n^2$ converges, we may instead test $\sum2^k/(2^k)^2=\sum1/2^k$. This latter series converges by Example~\ref{ex:geometric}, so $\sum1/n^2$ converges as well.
\item To test whether $\sum1/n$ converges, we may instead test $\sum2^k/2^k=\sum1$. This latter series clearly diverges, so $\sum1/n$ diverges as well.
\end{itemize}

% Another consequence of the monotone convergence theorem is the following.

% \begin{example}
%   The series $\sum1/n(n+1)$ converges and its value can be calculated using another clever trick. Specifically, we compute the values of the partial sums $Sn$ using the method of ``telescoping.''
%   \begin{align*}
%     S_n&=\frac12+\frac16+\frac1{12}+\cdots+\frac1{n(n-1)}\\
%        &=\frac12+\left(\frac12-\frac13\right)+\left(\frac13-\frac14\right)
%          +\cdots+\left(\frac1{n-1}-\frac1n\right)\\
%        &=\frac12+\frac12-\frac1n
%   \end{align*}
%   It is now clear that $S_n$ converges to $1$.
% \end{example}

% \begin{corollary}[Comparison test]
%   If $a_n$ and $b_n$ are nonnegative sequences with $a_n\leq b_n$ for all $n$, and if $\sum b_n$ is known to converge, then $\sum a_n$ converges too.
% \end{corollary}

\newpage
\subsection*{Activity for \S \thesection}

\begin{activity}
  \item Use the condensation test to determine whether the series converge.
  \begin{enumerate}
    \item $\sum\frac{1}{\ln(n)}$\vspace\fill
    \item $\sum\frac{1}{n\ln(n)}$\vspace\fill
    \item $\sum\frac{1}{n(\ln n)^2}$\vspace\fill
  \end{enumerate}
  % MCT ??
\end{activity}

\begin{readnext}
  Abbott, \S 2.5
\end{readnext}


\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Subsequences}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{reading}
  Abbott, \S 2.5
\end{reading}

Given a sequence $a_n$, a \emph{subsequence} of $a_n$ is a selection of infinitely many terms of $a_n$. More formally, if $n_1<n_2<n_3<\ldots$ is a properly increasing sequence of indices, then the corresponding subsequence $a_{n_k}$ consists of the temrs $a_{n_1},a_{n_2},a_{n_3},\ldots$.

\begin{example}
  Starting with the sequence $a_n=1/n$, let's make some subsequences:
  \begin{align*}
    a_{2k}&: \frac12, \frac14, \frac16, \frac18, \ldots\\
    a_{k^2}&: 1, \frac14, \frac19, \frac1{16}, \ldots
  \end{align*}
  One could also have a selection of terms with no apparent pattern whatsoever:
  \[a_{n_k}:\frac14, \frac{1}{15}, \frac{1}{37},\ldots
  \]
\end{example}

One must be careful to point out that it is not allowed to reorder or repeat the terms. Thus in the example of $a_n=1/n$ the terms $1,\frac13,\frac12,\frac14,\ldots$ cannot be part of a subsequence of $a_n$, and neither can the terms $1,\frac12,\frac12,\frac13,\ldots$.

Not surprisingly, if a sequence converges, so do its subsequences.

\begin{proposition}
  \label{prop:subsequence}
  If $a_n$ is a sequence which converges to $L$, and $a_{n_k}$ is a subsequence of $a_n$, then $a_{n_k}$ converges to $L$ too.
\end{proposition}

\begin{proof}
  Since $a_n\to L$, if $\epsilon>0$ is given we can find $N$ such that $n>N$ implies $|a_n-L|<\epsilon$. Since the $n_k$ are strictly increasing, we always have $n_k\geq k$. Hence if $k\geq N$ then we have $n_k\geq k\geq N$ and therefore $|a_{n_k}-L|<\epsilon$ too.
\end{proof}

Of course the converse is false; for a simple example the sequence $1,-1,+1,-1,\ldots$ has the convergent subsequence $1,1,1,1,\ldots$.

Although it is very simple, Proposition~\ref{prop:subsequence} has several useful applications. The first application gives a method of determining that a sequence is divergent. In the past, we have checked that a given sequence fails to converge to a proposed limit. The following result lets you check that a sequence fails to converge to any/every limit.

\begin{corollary}
  \label{cor:divergence}
  Let $a_n$ be a sequence, and suppose the subsequences $a_{n_k}$ and $a_{n_l}$ both converge but to different limits. Then $a_n$ does not converge.
\end{corollary}

For example if $a_n=(-1)^n(1+1/n)$, then $a_n$ has terms
\[-2,\frac32,-\frac{4}{3},\frac54,-\frac{6}{5},\ldots
\]
The subsequence $a_{2n}=1+1/(2n)$ converges to $1$, and the subsequence $a_{2n+1}=-1-1/(2n+1)$ converges to $-1$. Therefore the original sequence $a_n$ diverges.

A second application of Proposition~\ref{prop:subsequence} allows us to settle the question posed about the associative law for series way back in Section~\ref{sec:sequences}.

\begin{corollary}
  The associative law holds for convergent series. That is, if $\sum a_n$ converges then any association of its terms converges.
\end{corollary}

So for example if $\sum a_n$ converges then the following series converges:
\[(a_1+a_2+a_3)+(a_4+a_5+a_6)+\cdots
\]
The proof is simple: the partial sums of the re-associated series form a subsequence of the partial sums of the original series. Therefore the re-associated series converges by Proposition~\ref{prop:subsequence}.

We conclude this section with a key theorem about subsequences. Recall that we saw every convergent sequence is bounded, but not every bounded sequence is convergent. The following theorem gives a consolation prize instead: even if a bounded sequence doesn't converge, at least it has a convergent subsequence.

\begin{theorem}[Bolzano--Weierstra\ss]
  If $a_n$ is a bounded sequence, then $a_n$ has a convergent subsequence.
\end{theorem}

\begin{proof}
  Since $a_n$ is bounded we may assume it is a subset of some large interval $[-M,M]$. We go in search of the limit by iteratively subdividing the interval. To begin, at least one of $[-M,0]$ or $[0,M]$ must contain infinitely many terms of the sequence. Whichever of these intervals it is, call it $I_1$, and let $a_{n_1}$ be a term of the sequence lying in $I_1$.

  Next, one of the two halves of $I_1$ must contain infinitely many terms of the sequence $a_n$, call it $I_2$, and let $a_{n_2}$ be a term of the sequence lying in $I_2$. (Let us also ensure that $n_1<n_2$.)

  Continuing in this manner, we find intervals $I_k\subset I_{k-1}$ with length $M/2^{k-1}$, and terms of the sequence $a_{n_k}\in I_k$. By the NIP there exists a real number $L\in\bigcap I_k$. We claim $a_{n_k}$ is convergent and has limit $L$.

  For this, let $\epsilon>0$ be given. Choose $K$ large enough so that $M/2^{K-1}<\epsilon$. Then for all $k\geq K$ we have $a_{n_k}\in I_k\subset I_K$ and therefore $|a_{n_k}-L|<\epsilon$, as desired.
\end{proof}

The Bolzano--Weierstra\ss\ theorem has numerous theoretical applications, some of which we will see later in the course. To give one small example, we can establish the following partial converse to Corollary~\ref{cor:divergence}.

\begin{proposition}
  Let $a_n$ be a bounded sequence. If $a_n$ does not converge, then it has subsequences $a_{n_k}$ and $a_{n_l}$ which both converge but to different limits.
\end{proposition}

\begin{proof}
  By the Bolzano--Weierstra\ss\ theorem, there is a convergent subsequence $a_{n_k}\to L$. Since $a_n$ itself does not converge to $L$, there exists $\epsilon$ such that infinitely many terms $a_n$ of the sequence satisfy $|a_n-L|\geq\epsilon$. Enumerate these terms in a subsequence $a_{n_l}$. Again by the Bolzano--Weierstra\ss\ theorem, this subsequence $a_{n_l}$ has a further subsequence $a_{n_{l_m}}$ which converges to a limit $M$. Then we have $|M-L|\geq\epsilon$, in particular $M\neq L$.
\end{proof}

\newpage
\subsection*{Activity for \S \thesection}

\begin{activity}
  \item (Abbott, exercise 2.5.3) Give an example of each of the following, or prove that no such example exists.
  \begin{enumerate}\itemsep\fill
    \item A sequence that does not have $0$ or $1$ as a term, but has a subsequence which converges to $0$ and a susequence which converges to $1$
    \item A bounded divergent sequence with a convergent subsequence
    \item An unbounded sequence with a convergent subsequence
    \item An unbounded monotone sequence with a convergent subsequence
    \item A sequence that has subsequences which converge to each of the following: $1,\frac12,\frac13,\frac14,\ldots$
    \item A sequence that has a subsequence that is bounded, but no subsequence that converges
    \vspace\fill
  \end{enumerate}
\end{activity}

% \begin{exerc}
%   Prove the following characterization: $a_n$ has a subsequence converging to $L$ if and only if for all $\epsilon>0$, for all $N$, there exists $n>N$ such that $|a_n-L|<\epsilon$.
% \end{exerc}
%
% \begin{exerc}
%   Prove or give a counterexample: If $a_n$ has a subsequence converging to $a$ and $b_n$ has a subsequence converging to $b$ then $a_n+b_n$ has a subsequence converging to $a+b$.
% \end{exerc}
%
% \begin{exerc}
%   Consider the sequence $a_n=$ the reciprocal of the least prime factor of $n$. Write out the first 20 terms of the sequence. Find two subsequences of $a_n$ that converge but to different limits.
% \end{exerc}
%
% didn't port this one:
% \begin{exerc}
%   Suppose that $a_n$ has the property that every subsequence $a_{n_k}$ has a \emph{further} subsequence $a_{n_{k_\ell}}$ which converges to $L$.  Show that $a_n$ converges to $L$.  (Hint: try contradiction!)
% \end{exerc}

\begin{readnext}
  Abbott, \S 2.6
\end{readnext}


\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{More about completeness}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{reading}
  Abbott, \S 2.6
\end{reading}

Recall that the the real number system satisfies the Axiom of Completeness, which says that every bounded set has a supremum. We have said that this axiom should be interpreted as saying that the real number system does not have any gaps. But this leads to the question of what it means for other spaces, besides the real numbers, to be complete. For example, it is intuitively clear that the plane $\R^2$ and the sphere $\mathbb S^2$ do not have any gaps, but they do not have any ``supremum'' operation. To continue with analysis beyond the real numbers, one needs a more general way to define completeness.

\begin{definition}
  The sequence $a_n$ is \emph{Cauchy} if for all $\epsilon>0$ there exists $N\in\N$ such that for all $m,n\geq N$ we have $|a_n-a_m|<\epsilon$.
\end{definition}

The Cauchy sequences are the ones which really, really want to converge, but don't know what their limit should be!

\begin{example}
  The sequence $a_n=1/n$ is Cauchy. As scratch work, we seek $N$ large enuogh that whenever $n,m\geq N$ we have $|1/n-1/m|<\epsilon$. Using the triangle inequality, this will be true so long as $1/n+1/m<\epsilon$. We therefore try to make both $1/n$ and $1/m$ be $<\epsilon/2$. Solving $1/n<\epsilon/2$ yields $n>2/\epsilon$, and solving $1/m<\epsilon/2$ yields $m>2/\epsilon$. 
  
  To complete the proof, let $N>2/\epsilon$, and let $m,n\geq N$ be given. Then $1/n+1/m\leq1/N+1/N=2/N<\epsilon$. Hence $|1/n-1/m|\leq1/n+1/m<\epsilon$, as desired.
\end{example}

The proof that the above sequence is Cauchy is not too different than the proof that it is convergent. In fact the notions of Cauchy and convergent sequences turn out to be exactly the same.

\begin{theorem}[Cauchy criterion]
  A sequence of real numbers is Cauchy if and only if it is convergent.
\end{theorem}

\begin{proof}
  Let us first suppose that $a_n$ is convergent with limit $L$ and show that it is Cauchy. Given $\epsilon$ we can choose $N$ large enough that $n>N$ implies $|a_n-L|<\epsilon/2$. Then if $m,n>N$ we have
  \begin{align*}
    |a_n-a_m|&= |a_n-L+L-a_m|\\
             &\leq |a_n-L|+|L-a_m|\\
             &<\epsilon
  \end{align*}
  and hence $a_n$ is Cauchy.
  
  Conversely suppose that $a_n$ is Cauchy. Before showing it is convergent, we will first show it is bounded. For this, we can choose $N$ large enough that $m,n\geq N$ implies $|a_n-a_m|<1$. This shows that a tail of the sequence is bounded, and since finite sets are always bounded, the whole sequence must be bounded too.

  Now since $a_n$ is bounded, it follows from the Bolzano--Weierstra\ss\ theorem that $a_n$ has a convergent subsequence $a_{n_k}$ with limit $L$. We claim that the whole sequence $a_n$ converges to $L$ as well. Indeed given $\epsilon$ we can choose $N$ large enough that $m,n\geq N$ implies $|a_n-a_m|<\epsilon/2$. Moreover we can find $k$ large enough that $n_k\geq N$ and $|a_{n_k}-L|<\epsilon/2$. Therefore
  \begin{align*}
    |a_n-L|&\leq|a_n-a_{n_k}|+|a_{n_k}-L|<\epsilon
  \end{align*}
  and so $a_n$ converges to $L$, as desired.
\end{proof}

The above theorem says that in the real number system, every sequence that wants to converge (beacuse it is Cauchy) really does converge. This statement is false if you consider the rational number system only. Instead, the statement can be regarded as another way of saying that the real number system is complete. In general, we say that a space is \emph{Cauchy complete} if all of its Cauchy sequences converge. The spaces $\R$, $\R^2$, $\mathbb S^2$ are all Cauchy complete.

It turns out that many of the theorems we have investigated so far can be regarded as statements of completeness. Just now we proved the Cauchy criterion (CC) using the Bolzano--Weierstra\ss\ theorem (BWT). Earlier we proved the Bolzano--Weierstra\ss\ theorem using the NIP. And we proved the NIP using our original Axiom of Completeness (bounded sets have a least upper bound). We therefore see that:
\[AOC\implies NIP\implies BWT\implies CC
\]
The following result states that in fact all four of these statements are equivalent to one another!

\begin{theorem}
  All of the statements AOC, NIP, BWT, CC are equivalent.
\end{theorem}

\begin{proof}[Proof outline]
  It remains only to show that CC implies AOC. Suppose we know Cauchy sequences converge and let $A$ be a bounded subset of $\R$. Then $A$ is contained in some interval $[a,b]$. For each $n$, divide $[a,b]$ into cells of width $(b-a)/2^n$ and let $a_n$ be the right endpoint of the right-most cell meeting $A$. Then for any $N$, the sequence $a_n$ eventually lies in an interval of with $(b-a)/2^N$ and hence $a_n$ is Cauchy.

  Since Cauchy sequences converge we may let $L$ be the limit of $a_n$. We claim that $L$ is the least upper bound for $A$. Indeed since for all $n$ we have that $a_n$ is an upper bound for $A$, it is clear that $L$ is an upper bound for $A$. Moreover given any $n$ we can find $a\in A$ such that $a\geq a_n-1/2^n$. Since the latter is $\geq L-1/2^n$, this implies $L=\sup(A)$. Thus AOC holds, as desired.
\end{proof}

It is also the case that the monotone convergence theorem (MCT) is equivalent to AOC, a fact we leave as an exercise.

\newpage
\subsection*{Activity for \S \thesection}

\begin{activity}
  \item Show directly from the definition that the sequence $x_n=\frac{n}{n+1}$ is Cauchy.\vspace\fill
  \item (Abbott, ex 2.6.2) Give an example of each of the following, or prove that no such example exists.
  \begin{enumerate}\itemsep.8in
    \item A Cauchy sequence that is not monotone
    \item A monotone sequence that is not Cauchy
    \item A Cauchy sequence with a divergent subsequence
    \item An unbounded sequence containing a subsequence that is Cauchy\vspace{.5in}
  \end{enumerate}
\end{activity}

% \begin{exerc}
%   Find an example of a divergent sequence $a_n$ which satisfies $\lim(a_{n+1}-a_n)=0$.
% \end{exerc}
%
% \begin{exerc}
%   The MCT (monotone convergence theorem) is yet another equivalent of completness. To establish this, complete the following proof that MCT implies BWT. To begin, say that a term $a_n$ of a sequence is a \emph{peak} if for all $n'>n$ we have $a_n'\leq a_n$.
%   \begin{enumerate}
%     \item Assume the sequence $a_n$ has infinitely many peaks. Conclude that $a_n$ has a monotone decreasing subsequence.
%     \item Assume the sequence $a_n$ has a last peak. Conclude that $a_n$ has a monotone increasing subsequence.
%     \item Use parts (a) and (b) together with the MCT to prove the BWT.
%   \end{enumerate}
% \end{exerc}

\begin{readnext}
  Abbott, \S 2.7
\end{readnext}


\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Series convergence tests}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{reading}
  Abbott, \S 2.7
\end{reading}

In this section we return to series and the so-called tests for series convergence. First, we note that just as limits obey calculus laws, series obey certain rules as well.

\begin{theorem}[Series calculus]
  Suppose $\sum a_n$ and $\sum b_n$ both converge. Then $\sum ca_n=c\sum a_n$ and $\sum(a_n+b_n)=\sum a_n+\sum b_n$.
\end{theorem}

\begin{proof}
  This follows almost directly from the limit calculus. For example, to show that $\sum a_n+b_n=\sum a_n+\sum b_n$, we let $S_n$ denote the sequence of partial sums of the $a_n$ and $T_n$ the sequence of partial sums of $b_n$.
  \begin{align*}
    \sum(a_n+b_n)&=\lim\sum_1^N(a_n+b_n)\\
                &=\lim (S_N+T_N)\\
                &=\lim S_N+\lim T_N\\
                &=\sum a_n+\sum b_n
  \end{align*}
  Here, the third equality is an instance of the limit summation law.
\end{proof}

Before proceeding to the convergence tests, we state formally one simple test for divergence which should be kept in mind when considering practical examples.

\begin{theorem}[Divergence criterion]
  If $\sum a_n$ is a series such that the terms $a_n$ do not converge to zero, then $\sum a_n$ diverges.
\end{theorem}

\begin{proof}
  We use the contrapositive. Suppose that $\sum a_n=S$. Then the sequence partial sums $S_n$ converges to $S$. It follows from the addition law for limits that the terms $a_n=S_n-S_{n-1}$ converge to $S-S=0$.
\end{proof}

\begin{example}
  Consider the series $\sum(-1)^n\frac{3n^2+1}{2n^2-5}$. The terms are alternating in sign and one might think they could conceivably cancel with one another to yield a finite summation. However we know from the limit calculus that the subsequence of positive terms converges to $3/2$ and the subsequence of negative terms to $-3/2$. Hence the terms of the series do not converge to $0$, so the series diverges.
\end{example}

The next two tests summarize some familiar series, and help give us a library of known series convergence and divergence for future use.

\begin{proposition}[Series library]
  \begin{itemize}
    \item $\sum r^n$ converges if and only if $|r|<1$
    \item $\sum\frac{1}{n^p}$ converges if and only if $p>1$
  \end{itemize}
\end{proposition}

The geometric series test is standard in calculus and can be proved with a calculation similar to that of Example~\ref{ex:geometric}. The $p$-series test was proved in an earlier exercise as an application of the condensation test.

\begin{example}
  Consider the series $\sum 9^{-n+2}4^{n+1}$. We can rewrite it as $4\cdot81\sum(4/9)^n$. Since $4/9<1$ the series converges and the summation is $4\cdot81/(1-4/9)$.
\end{example}

\begin{theorem}[Comparison test]
  Let $a_n$ and $b_n$ be nonnegative sequences of terms, and suppose $\sum b_n$ converges. If for all $n$ we have $a_n\leq b_n$, then $\sum a_n$ converges too.
\end{theorem}

\begin{proof}
  Let $S_n$ denote the partial sums of $a_n$ and let $T_n$ denote the partial sums of $b_n$. By assumption we have that $T_n$ converges to some value, let's call it $T$. Meanwhile since $a_n\leq b_n$ we clearly have $S_n\leq T_n\leq T$. Thus we have shown $S_n$ is monotone and bounded above, and it follows from the MCT that the sequence $S_n$ converges. This means by definition that the series $\sum a_n$ converges.
\end{proof}

\begin{example}
  Consider the series $\sum\frac{n^2-3n-1}{n^4+2n^3+3}$. Intuitively this series isn't very different than the simpler series $\sum\frac{1}{n^2}$, but it would be a mess to apply the condensation test to this one directly. Instead, we can easily calculate
  \[\frac{n^2-3n-1}{n^4+2n^3+3}\leq\frac{n^2}{n^4}=\frac{1}{n^2}
  \]
  Since $\sum\frac{1}{n^2}$ converges by the $p$-series test, the comparison test implies that $\sum\frac{n^2-3n-1}{n^4+2n^3+3}$ converges too.
\end{example}

\begin{example}
  The comparison test may also be applied in contrapositive as follows. Consider the series $\sum\frac{n^2+2n+1}{n^3-2n-1}$. Intuitively this series isn't very different than the simpler series $\sum\frac1n$, and we can again bear this out:
  \[\frac{n^2+2n+1}{n^3-2n-1}\geq\frac{n^2}{n^3}=\frac1n
  \]
  Since $\sum\frac1n$ diverges, the comparison test implies that $\sum\frac{n^2+2n+1}{n^3-2n-1}$ diverges too.
\end{example}

Although the comparison test is very simple, it may be leveraged to yield several more powerful tests. Perhaps the most famous applications of the comparison test are the ratio and root tests.

\begin{theorem}[Root and ratio test]
  Let $a_n$ be a nonnegative sequence of terms.
  \begin{itemize}
  \item If the sequence $(a_n)^{1/n}$ converges to a limit $r<1$, then the series $\sum a_n$ converges.
  \item If the sequence $a_{n+1}/a_n$ converges to a limit $r<1$, then the series $\sum a_n$ converges.
  \end{itemize}
\end{theorem}

\begin{proof}
  We prove only the root test. Let $r'$ be any number such that $r<r'<1$. Then there exists $N$ such that $n>N$ implies $a_n^{1/n}<r'$. Since we can ignore initial segments for the purposes of series convergence, we can suppose without loss of generality that $a_n^{1/n}<r'$ for all $n$. It follows that $a_n<(r')^n$, and since we know $\sum(r')^n$ converges, the comparison test implies that $\sum a_n$ converges too.
\end{proof}

\begin{example}
  Consider the series $\sum(1/2+1/n)^n$. Intuitively it is similar to the series $\sum1/2^n$, but it is hard to apply either the geometric series test or the comparison test directly. Instead, we calculate
  \[\lim[(1/2+1/n)^n]^{1/n}=\lim(1/2+1/n)=1/2
  \]
  Since this value is less than $1$, the root test implies the series converges.
\end{example}

\newpage
\subsection*{Activity for \S \thesection}

\begin{activity}
  \item Decide whether the given series converge or diverge. Prove your answers using the series tests we have discussed in class so far.
  \begin{enumerate}\itemsep\fill
    \item $\displaystyle\sum\frac{1}{n^2+n+2}$
    \item $\displaystyle\sum\frac{1}{n^2-n+2}$
    \item $\displaystyle\sum\frac{1}{3n-2}$
    \item $\displaystyle\sum\frac{1}{3n+2}$
    \item $\displaystyle\sum\frac{(n+1)^{2n}}{(2n^2+n+1)^n}$
    \item $\displaystyle\sum\frac{n!}{n^n}$
    \vspace\fill
  \end{enumerate}
\end{activity}

% \begin{exerc}
%   Suppose that $a_n,b_n\geq0$ and that $\sum a_n$ and $\sum b_n$ both converge. Prove that $\sum a_nb_n$ converges.
% \end{exerc}
%
% \begin{exerc}[Abbott, ex 2.7.4(a)]
%   Give an example of two divergent series $\sum a_n$ and $\sum b_n$ such that $\sum a_nb_n$ converges.
% \end{exerc}

% prove the ratio test?

% prove the limit comparison test?


\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Conditional convergence}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

The convergence tests we studied in the previous section were mainly applicable to series with nonnegative terms. But many series have mixed signs, and as we saw earlier that such series can exhibit some of the most confusing behavior (such as a lack of commutativity).

Of course, if $\sum a_n$ is a series with mixed signs, one can always take absolute values of the terms and study $\sum|a_n|$ instead. All of the tests in the previous section apply to $\sum|a_n|$. But this leads to the question of what is the relationship between convergence of $\sum a_n$ and convergence of $\sum|a_n|$.

\begin{theorem}
  \label{thm:absolute}
  If $\sum|a_n|$ is convergent, then $\sum a_n$ is convergent.
\end{theorem}

\begin{proof}
  Consider the new series $\sum(a_n+|a_n|)$ and note that the terms $a_n+|a_n|$ are nonnegative. Since $a_n+|a_n|\leq2|a_n|$, the comparison test implies that $\sum(a_n+|a_n|)$ converges. Now the series calculus implies that $\sum a_n=\sum(a_n+|a_n|)-\sum|a_n|$, and in particular $\sum a_n$ converges.
\end{proof}

The converse of the Theorem~\ref{thm:absolute} is false, as we will see shortly in the examples.

\begin{definition}
  A series $\sum a_n$ is said to be \emph{absolutely convergent} if it is convergent, and moreover $\sum|a_n|$ is convergent.

  A series $\sum a_n$ is said to be \emph{conditionally convergent} if it is convergent, and $\sum|a_n|$ is divergent.
\end{definition}

\begin{example}
  The series $\sum\sin(n)/n^2$ is absolutely convergent. Indeed, the series $\sum|\sin(n)|/n^2$ may be compared with $\sum 1/n^2$, which we know to be convergent. Therefore by Theorem~\ref{thm:absolute}, $\sum\sin(n)/n^2$ is convergent too.
\end{example}

\begin{example}
  The series $\sum(-1)^{n+1}/n$ is conditionally convergent. Recall from Section~\ref{sec:sequences} we estimated its value at $0.69$ (we will prove it's convergent later). On the other hand, if we take the absolute values of the terms we get $\sum 1/n$, which we know to be divergent.
\end{example}

We can organize the possibilities for convergence in a table, see Figure~\ref{fig:convergence}.

\begin{figure}[h]
  \begin{tabular}{l|cc}
                     & $\sum a_n$ conv & $\sum a_n$ div\\\hline
    $\sum|a_n|$ conv & AC & X\\
    $\sum|a_n|$ div & CC & Div
  \end{tabular}
  \caption{AC denotes Absolutely Convergent, CC denotes Conditionally Convergent, Div denotes divergent, and X denotes an impossible situation\label{fig:convergence}.}
\end{figure}

If $\sum a_n$ is a nonnegative series, then convergence and absolute convergence are the same. If $\sum a_n$ has mixed signs, then we can test for absolute convergence by considering $\sum|a_n|$ and using any test from the previous sections. Testing for conditional convergence is more subtle, but there are some tests such as the following.

\begin{theorem}[Alternating series test]
  Assume that $a_n$ is monotone decreasing and $\lim a_n=0$. Then the series $\sum(-1)^na_n$ converges.
\end{theorem}

\begin{proof}
  Let $S_n$ be the sequence of partial sums, and consider the two subsequences $S_{2k}$ and $S_{2k+1}$. Then since $a_n$ is decreasing, we have $S_{2k+2}-S_{2k}=a_{2k+2}-a_{2k+1}<0$ and that $S_{2k+3}-S_{2k+1}=-a_{2k+3}+a_{2k+2}>0$. It follows that $S_{2k}$ is decreasing and $S_{2k+1}$ is increasing. Moreover $S_{2k}$ is bounded below by $-a_1$ and $S_{2k+1}$ is bounded above by $-a_1+a_2$.

  By the MCT, both $S_{2k}$ and $S_{2k+1}$ converge, say to $S$ and $T$ respectively. Now it follows that $S_{2k+1}-S_{2k}\to S-T$. But we also have $S_{2k+1}-S_{2n}=a_{2k+1}\to0$. Therefore $S=T$ and this implies $S_n\to S$. In particular $\sum a_n$ converges.
\end{proof}

\begin{example}
  The series $\sum(-1)^n\frac{n^2}{n^3+9}$ is conditionally convergent. To show it is convergent, we apply the alternating series test. The only tricky thing to check is that $n^2/(n^3+9)$ is (eventually) decreasing. For this one can simply check that the derivative of $x^2/(x^3+9)$ is (eventually) negative. To see that it is not absolutely convergent one may compare $\sum\frac{n^2}{n^3+9}$ against $\sum 1/2n$. 
\end{example}

We close our discussion of series by answering our initial question about commutativity in infinite summations. Recall that we calculated two different values for series with terms $1,-1/2,+1/3,-1/4,\ldots$. As we shall now see, this phenomenon occurs precisely when a series is conditionally convergent.

\begin{theorem}
  \begin{itemize}
  \item If $\sum a_n$ is absolutely convergent then any rearrangement of its terms converges to the same limit.
  \item If $\sum a_n$ is conditionally convergent then any value can be obtained as the sum of a rearrangement of its terms.
  \end{itemize}
\end{theorem}

\begin{proof}[Proof sketch]
  Beginning with the first statement, suppose that $\sum a_n$ is absolutely convergent and that $\sum a_n=A$. Let $\sum b_n$ be a given rearrangement of $\sum a_n$. Since $\sum a_n$ is absolutely convergent, given $\epsilon$ we can find $N$ so large that $\sum_N^\infty|a_n|<\epsilon/2$. Next choose $N'$ large enough that all of the terms $a_1,\ldots,a_N$ appear in the list $b_1,\ldots,b_{N'}$. Then
  \begin{align*}
    \left|\sum_1^{N'}b_n-A\right|
    &\leq\left|\sum_1^{N'}b_n-\sum_1^Na_n\right|+\left|\sum_1^Na_n-A\right|\\
    &\leq\sum_{N+1}^\infty|a_n|+\left|\sum_{N+1}^\infty a_n\right|\\
    &\leq2\sum_{N+1}^\infty|a_n|\\
    &<\epsilon
  \end{align*}
  This shows that the partial sums of the $b_n$ converge to $A$, as desired.
  
  For the second statement, note that the sum of just the positive terms must be divergent, and the sum of just the negative terms must also be divergent. Thus given a target summation $S$, we can add together enough positive terms until we just overshoot $S$. We can then add together enough negative terms until we just undershoot $S$. Continuing in like fashion, we straddle $S$ infinitely many times. Since the terms $a_n\to0$, these attempts get arbitrarily close to the value $S$.
\end{proof}

\newpage
\subsection*{Activity for \S \thesection}

\begin{activity}
  \item Decide whether the given series converge absolutely, converge conditionally, or diverge.
  \begin{enumerate}\itemsep\fill
    \item $\displaystyle\sum\frac{(-2)^n}{3^n}$
    \item $\displaystyle\sum\frac{(-3)^n}{2^n}$
    \item $\displaystyle\sum\frac{(-1)^n\ln n}{n}$
    \item $\displaystyle\sum\frac{(-1)^n}{\sqrt[3]{n^2+7}}$
    \vspace\fill
  \end{enumerate}
\end{activity}

% \begin{exerc}
%   Give an example of two convergent series $\sum a_n$ and $\sum b_n$ such that $\sum a_nb_n$ diverges. (Compare with the previous homework.)
% \end{exerc}
%
% \begin{exerc}
%   Suppose that $\sum a_n$ converges absolutely and that the sequence $b_n$ is bounded.  Prove that $\sum a_nb_n$ converges absolutely.
% \end{exerc}

% Show that if a series is CC then its positive and negative terms are Div

\begin{readnext}
  Abbott, \S 3.1
\end{readnext}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\chapter{Topology}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{The Cantor set}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{reading}
  Abbott, \S 3.1
\end{reading}

In this chapter we study subsets of the real line using \emph{topology}, which is a notion of abstract shape. In the context of our class, topology will let us explore the shape of subsets of $\R$. Before commencing with the appropriate definitions, we wish to give a small taste of just how complicated subsets of $\R$ can be.

To motivate our discussion, let us begin with the notoriously difficult problem of measuring the \emph{size} of a subset. We have already introduced the notion of \emph{cardinality}, which gives us some idea of the size of a set (countable vs uncountable). But this notion is very course since it has just two outcomes. In this section we will discuss two more notions: the \emph{length} and the \emph{dimension} of a set.

We will now introduce the \emph{Cantor set}, which will help us challenge our ideas about what cardinality, length, and dimension mean, and how they interact with one another. The Cantor set set has many unusual properties not seen in our familiar examples of sets, that is, the intervals, cuts, sequences, and so forth.

The Cantor set is constructed as follows. Begin with the unit interval $[0,1]$, and remove its open middle third to obtain the set $C_1=[0,\frac13]\cup[2/3,1]$. Next remove the open middle third of each of these intervals to obtain the set $C_2=[0,\frac19]\cup[\frac29,\frac13] \cup[\frac23,\frac79]\cup[\frac89,1]$. Continuing in like fashion, we obtain a decreasing sequence of closed sets $C_n$, each of which is the union of several disjoint closed intervals. The Cantor set $C$ is then defined to be $\bigcap C_n$.

\begin{figure}[h]
\begin{center}
  \begin{tikzpicture}
    \draw[|-|] (0,0) -- (10,0) node[anchor=west] {\ \ $C_0$};
    \draw[|-|] (0,-.5) -- (10/3,-.5);
    \draw[|-|] (20/3,-.5) -- (10,-.5) node[anchor=west] {\ \ $C_1$};
    \draw[|-|] (0,-1) -- (10/9,-1);
    \draw[|-|] (20/9,-1) -- (30/9,-1);
    \draw[|-|] (60/9,-1) -- (70/9,-1);
    \draw[|-|] (80/9,-1) -- (10,-1) node[anchor=west] {\ \ $C_2$};
    \node[anchor=west] at (10,-1.4) {\ \ \ $\vdots$};
    \draw[decoration=Cantor set,very thick]
    decorate{ decorate{ decorate{ decorate{ decorate{ decorate{
                (0,-2) -- (10,-2) }}}}}} node[anchor=west] {\ \ $C$};
  \end{tikzpicture}
\end{center}
\caption{The first few steps in the construction of the Cantor set, and a rough image of the Cantor set itself.\label{fig:cantor-set}}
\end{figure}

Initially it is hard to see whether $C$ has any elements at all. But it does, for example both $0$ and $1$ lie in $C$. In fact $C$ is infinite because the endpoints of every interval making up $C_n$ lie in $C$ (for example $\frac13$, $\frac19$, etc). The following result states that the Cantor set is in fact very large.

\begin{proposition}
  The Cantor set is uncountable.
\end{proposition}

\begin{proof}
  Let $S$ denote the set of infinite binary sequences. We have already seen using a diagonalization argument that $S$ is uncountable. Thus it suffices to find a one-to-one function from $S$ to the Cantor set. Indeed, given any element $s\in S$ we define a sequence of intervals $I_n$ from $C_n$ as follows. If $s(1)=0$ we let $I_1=$ the left interval of $C_1$ and if $s(1)=1$ we let $I_1=$ the right such. Similarly if $s(2)=0$ we let $I_2=$ the left interval of $C_2$ contained in $I_1$, and if $s(2)=1$ we let $I_2=$ the right such.

  Continuing in this fashion, $s$ determines a nested sequence of closed intervals $I_n$. By the NIP there exists a point $x_s$ lying in $\bigcap I_n$. Moreover the function $x\mapsto x_s$ is one-to-one. Indeed, if $s\neq s'$ then there is some first index $n$ such that $s(n)\neq s(n')$. Then the interval $I_n$ determined by $s$ and the interval $I'_n$ determined by $s'$ are disjoint, and this implies $x_s\neq x_{s'}$.
\end{proof}

We next consider the \emph{length} of the Cantor set. Although we do not give the definition of length in full generality, we need only keep in mind the following very simple properties. First, the length of an interval $[a,b]$ or $(a,b)$ is equal to $b-a$. Second, the length of a finite or countable union of disjoint sets is equal to the sum of the lengths of the sets.

\begin{proposition}
  The Cantor set has zero length.
\end{proposition}

\begin{proof}
  Going from $C_0$ to $C_1$ we remove one interval of length $1/3$. Going from $C_1$ to $C_2$ we remove two intervals of length $1/9$. Going from $C_2$ to $C_3$ we remove four intervals of length $1/27$. In general, going from stage $n-1$ to stage $n$ we remove a total length of $2^n/3^{n+1}$. Therefore in the whole construction we remove a total of
  \begin{align*}
    \sum\frac{2^n}{3^{n+1}}&=\frac13\sum\left(\frac23\right)^n\\
                           &=\frac13\cdot\frac{1}{1-2/3}\\
                           &=1
  \end{align*}
  We therefore conclude that the total length remaining in the Cantor set is $0$.
\end{proof}

We close with a brief discussion of the \emph{dimension} of the Cantor set. Although we do not give a precise definition of dimension, we motivate it by observing the following property. When you dilate a square by a factor of two, the result contains $4=2^2$ copies of the original square. When you dilate a cube by a factor of two, the result contains $8=2^3$ copies of the original cube. In each case the number appearing in the exponent matches our intuitive idea of the dimension of the object. This leads to the following formula, which is used whenever it is applicable:
\[\text{number of copies}=\text{(scaling factor)}^\text{dimension}
\]
The most general definitions of dimension are somewhat complicated to describe, but all of them reduce to the above formula when it applies.

\begin{proposition}
  The Cantor set has dimension strictly between $0$ and $1$.
\end{proposition}

\begin{proof}
  The trick is to dilate the Cantor set by a factor of $3$. Looking at the result applied to the first step $C_1$, we see it becomes two unit intervals. Thus if the construction is completed on the dilated copy, we will obtain two full copies of the Cantor set. The dimension formula therefore yields:
\[2=3^{\text{dimension}}
\]
Hence the dimension of $C$ is equal to $\log(2)/\log(3)\approx0.63$.
\end{proof}

The three propositions taken together yield an interesting conclusion: the Cantor set is large from the point of view of cardinality, small from the point of view of length, and intermediate from the point of view of dimension!

\newpage
\subsection*{Activity for \S \thesection}

For $0<\alpha<1$, the \emph{modified Cantor set} $C^\alpha$ is constructed by starting with $B_0=[0,1]$ and recursively letting $B_{n+1}$ be the set obtained by removing the middle $\alpha$ fraction of each interval of $B_n$. Thus $C^{1/3}$ is precisely the original Cantor set $C$.

For a new example, we construct the modified Cantor set $C^{1/4}$ as follows. First $B_1$ is obtained by removing the middle $1/4$ of $[0,1]$. Next $B_2$ is obtained by removing the middle $1/4$ of each interval of $B_1$, for a total removal of \underline{\hspace{1in}}.

\begin{center}
  \begin{tikzpicture}
    \draw[|-|] (0,0) -- node[above]{$1$} (10,0) node[anchor=west] {$B_0$};
    \draw[|-|] (0,-1)--(30/8,-1);
    \node at (5,-1) {$(1/4)$};
    \draw[|-|] (50/8,-1)--(10,-1) node[anchor=west] {$B_1$};
    \draw[|-|] (0,-2)--(90/64,-2);
    \node at (15/8,-2) {$(?)$};
    \draw[|-|] (30/8-90/64,-2)--(30/8,-2);
    \node at (10-15/8,-2) {$(?)$};
    \draw[|-|] (50/8,-2)--(50/8+90/64,-2);
    \draw[|-|] (10-90/64,-2)--(10,-2) node[anchor=west] {$B_2$};
  \end{tikzpicture}
\end{center}

\begin{activity}
  \item In the construction of $C^{1/4}$ shown above, for each $n$ find the total amount removed when going from $B_n$ to $B_{n+1}$.
  \vspace{\fill}
  \item Find the sum of all the lengths removed, that is, the sum of the amounts calculated in part~(a). Then take $1$ minus this sum to find the length of the modified Cantor set $C^{1/4}$.
  \vspace{\fill}
  \item Find the fractal dimension of $C^{1/4}$. \textbf{Hint:} use a scaling factor that grows both intervals in $B_1$ to a length of $1$.
  \vspace{\fill}
  \item Does the length of $C^\alpha$ depend on $\alpha$? Does the fractal dimension of $C^\alpha$ depend on $\alpha$?
\end{activity}

\begin{readnext}
  Abbott, \S 3.2
\end{readnext}


\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{The boundary of a set}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{reading}
  Abbott, \S 3.2
\end{reading}

We can think of a subset $A$ of some universe set $X$ as a black-and-white division: every point is either in $A$ or in its complement $A^c$. However this division is purely set-theoretic in that it doesn't take into account the relative placement of the points. If one the other hand we have some idea about the location or ordering of the points of $X$, then we can imagine there is a grey area consisting of points that are ``on the boundary'' of $A$.

Before we formally define the boundary of a set, recall the neighborhood notation that we introduced alongside the definition of convergence. The \emph{$\epsilon$-neighborhood of $x$} consists of all points that are less than $\epsilon$ away from $x$. In symbols:
\[N_\epsilon(x)=\set{y\in\R\mid|y-x|<\epsilon}
\]

In other words, $N_\epsilon(x)$ is an interval centered at $x$, that is, $(x-\epsilon,x+\epsilon)$. Note that if we were working in $X=\R^2$ we would define $N_\epsilon(x)$ to be a disk centered at $x$, in $X=\R^3$ we would define $N_\epsilon(x)$ to be a ball centered at $x$, and so on.

\begin{definition}
  Let $A$ be a subset of $\R$. A point $x$ is said to be a \emph{boundary point} of $A$ if for every $\epsilon>0$, we have that $N_\epsilon(x)\cap A\neq\emptyset$ and $N_\epsilon(x)\cap A^c\neq\emptyset$.
  
  The set of all boundary points of $A$ is denoted $\partial A$.
\end{definition}

Intuitively, if we think of points of $A$ as colored black and points of $A^c$ as colored white, the boundary of $A$ consists of those points such that no matter how far you zoom in on them, you still see both the colors black and white.

\begin{example}
  If $A$ is the closed interval $[0,1]$ then the boundary of $A$ is the set $\{0,1\}$. Similarly, if $A$ is the open interval $(0,1)$ then the boundary is once again the set $\{0,1\}$.
\end{example}

Notice that the boundary points of a set $A$ may be in either $A$ or $A^c$. In fact following the example above, it is easy to see that a closed interval will always contain its boundary, while an open interval will always omit its boundary. This observation leads us to make the following general definition of closed and open sets.

\begin{definition}
  \begin{itemize}
    \item The set $A$ is \emph{open} if $\partial A\cap A=\emptyset$.
    \item The set $A\subset\R$ is \emph{closed} if $\partial A\subset A$.
  \end{itemize}
\end{definition}

\begin{example}
  \begin{itemize}
  \item Open intervals are open, and so are unions of open intervals such as $(0,1)\cup(2,3)$.
  \item Closed intervals are closed, and so are unions of (finitely many) closed intervals such as $[0,1]\cup[2,3]$.
  \item Single points $\{x\}$ are closed, as is the set $\Z$.
  \item The set $\set{1/n\mid n\in\N}$ is neither open nor closed: $1$ is a boundary point which lies in the set, and $0$ is a boundary point which does not lie in the set.
  \item The empty set $\emptyset$ is both open and closed.
  \end{itemize}
\end{example}

As we have just seen, open and closed sets are not opposites, since it is possible for a set to be both or neither. The following fundamental result states rather that the two notions are complementary.

\begin{theorem}
  $A$ is open if and only if $A^c$ is closed.
\end{theorem}

\begin{proof}
  By the symmetry of the definition of boundary point, it is clear that $\partial A=\partial(A^c)$. Hence $A$ omits its boundary if and only if $A^c$ contains its boundary.
\end{proof}

% It is now time to introduce some more terminology that will help us understand boundary and open and closed sets.
%
% \begin{definition}
%   Let $A$ be a subset of $\R$.
%   \begin{itemize}
%     \item The \emph{interior} of $A$ is $\inte(A)=A\setminus\partial A$.
%     \item The \emph{closure} of $A$ is $\cl(A)=A\cup\partial A$.
%   \end{itemize}
% \end{definition}
%
% Thus we have $\inte(A)\subset A\subset\cl(A)$. It is not hard to believe that $\inte(A)$ is open and $\cl(A)$ is closed.
%
% In order to prove this, we need the following more basic fact.
% \begin{proposition}
%   \label{prop:closure}
%   Let $A$ be a subset of $\R$.
%   \begin{itemize}
%     \item $\inte(\inte(A))=\inte(A)$.
%     \item $\cl(\cl(A))=\cl(A)$.
%   \end{itemize}
% \end{proposition}
%
% The proof of the proposition is requested in the exercises.
%
% \begin{theorem}
%   For any set $A$ we have that $\inte(A)$ is open and $\cl(A)$ is closed.
% \end{theorem}
%
% \begin{proof}
%   Let us prove first that $\cl(A)$ is closed. For any set $B$ we have $\partial B\subset \cl(B)$. Hence we have $\partial(\cl(A))\subset\cl(\cl(A))$, and by the above we have $\cl(\cl(A))=\cl(A)$. Hence we have $\partial(\cl(A))\subset\cl(A)$ and so $\cl(A)$ is closed.
%
%   To see that $\inte(A)$ is open, note that $\inte(A)=\cl(A^c)^c$, and hence $\inte(A)$ is the complement of a closed set.
% \end{proof}

% In order to proceed, we need to establish a characterization of open sets in terms of the interior of the set.

% \begin{proposition}
%   A set $A$ is open if and only if for every point $x\in A$, there exists a neighborhood $N_\epsilon(x)$ such that $N_\epsilon(x)\subset A$.
% \end{proposition}
%
% \begin{proof}
%   First let $A$ be an open set and let $x\in A$. Since $x\notin\partial A$, there must exist a neighborhood $N_\epsilon(x)$ such that $N_\epsilon(x)\subset A$ or $N_\epsilon(x)\subset A^c$. Since $x\in A$ the latter option is impossible.
%
%   Conversely let $A$ be a set which is not open. Then there exists a point $x\in A$ such that $x\in\partial A$. By definition of $\partial A$, any neighborhood $N_\epsilon(x)$ satisfies $N_\epsilon(x)\cap A^c\neq\emptyset$, meaning that $N_\epsilon(x)\not\subset A$.
% \end{proof}

% As a matter of terminology, we say that $x\in A$ is an \emph{interior point} of $A$ if there exists a neighborhood $N_\epsilon(x)$ such that $N_\epsilon(x)\subset A$. We write $\inte(A)$ for the set of interior points of $A$.

We next investigate the relationship between the boolean operations of union and intersection, and the concepts of open and closed sets.

\begin{theorem}
  The union of any collection of open sets is open. The intersection of finitely many open sets is open.
\end{theorem}

\begin{proof}
  For the first statement let $\set{A_\alpha}$ be a collection of open sets; we use the index $\alpha$ to allow the collection to be finite, countable, or even uncountable. Let $S=\bigcup_\alpha A_\alpha$ and let $x\in S$ be given. We wish to show that $x$ is not in the boundary of $S$. Since $x\in S$ there exists an index $\alpha$ such that $x\in A_\alpha$. Since $A_\alpha$ is open, $x$ is not in the boundary of $A_\alpha$. Hence there exists a neighborhood $N_\epsilon(x)\subset A_\alpha$. It follows that also $N_\epsilon(x)\subset S$, which means $x$ is not in the boundary of $S$.

  For the second statement let $A_1,\ldots,A_n$ be open sets, let $T=A_1\cap\cdots\cap A_n$, and let $x\in T$ be given. Again we wish to show that $x$ is not in the boundary of $T$. Since $A_i$ are open for each $i\leq n$, we can find $\epsilon_i$ such that $N_{\epsilon_i}(x)\subset A_i$. Letting $\epsilon=\min(\epsilon_1,\ldots,\epsilon_n)$ we clearly have that $N_\epsilon(x)\subset T$. Thus $x$ is not in the boundary of $T$, as desired.
\end{proof}

We also have an analogous statement regarding closed sets. It follows directly from the previous theorem using complements.

\begin{theorem}
  The intersection of any collection of closed sets is closed. The union of finitely many closed sets is closed.
\end{theorem}

\begin{example}
  The Cantor set is closed. Indeed, all of the sets removed in the construction of the Cantor set are open. This includes the initial removal of $(-\infty,0)$ and $(1,\infty)$, and then all the open middle thirds. Thus the complement of the Cantor set is a union of open sets and hence open. Hence the Cantor set is closed.
\end{example}

We conclude this section with a justification for the term ``closed''. The next result says that closed sets are closed under the operation of taking limits of sequences.

\begin{theorem}
  Suppose $a_n$ is a sequence of $A$ and $a_n\to x$. If $A$ is closed then $x\in A$.
\end{theorem}

\begin{proof}
  Using contraposition, suppose $x\notin A$. Since $a_n\to x$, for every $\epsilon$ there exists $n$ such that $a_n\in N_\epsilon(x)$. Thus $N_\epsilon(x)$ meets $A$ (at $a_n$) and meets $A^c$ (at $x$). This means by definition that $x\in\partial A$. Thus $x$ is a boundary point of $A$ that is not in $A$, so $A$ is not closed.
\end{proof}

% Closure of a set?

% We conclude this section with a second very natural method of forming the closure of a set. Intuitively, if one begins with a set $A$ and takes limits of all convergent sequences in $A$, then one should end up with the closure of $A$.
%
% \begin{definition}
%   Let $A$ be a subset of $\R$.
%   \begin{itemize}
%   \item A point $x$ is said to be a \emph{limit point} of $A$ if every neighborhood $N_\epsilon(x)$ meets $A$ in some point other than $x$ itself. The set of limit points of $A$ is denoted $A'$.
%   \item A point $x$ is said to be a \emph{isolated point} of $A$ if $x\in A$ and there exists a neighborhood $N_\epsilon(x)$ which meets $A$ in no points other than $x$ itself. In other words the set of isolated points of $A$ is equal to $A\setminus A'$.
%   \end{itemize}
% \end{definition}
%
% The terminology ``limit point'' is justified by the fact that in $\R$, if $x$ is a limit point of $A$ then there is some sequence of elements of $A$ which converges to $x$. The following result explains the ``closure'' terminology: the closure of a set can be thought of as the closure under the limit operation.
%
% \begin{proposition}
%   \label{prop:closure-equiv}
%   The closure $\bar A$ is equal to both $A\cup\partial A$ and $A\cup A'$.
% \end{proposition}
%
% \begin{proof}
%   We first show that $A\cup\partial A\subset A\cup A'$. Suppose that $x\in A\cup\partial A$. If $x\in A$ we are done, so suppose $x\notin A$. Then $x\in \partial A$, so every neighborhood $N_\epsilon(x)$ meets $A$. Since $x\notin A$ this meeting must be in a point other than $x$ itself, and so $x\in A'$.
%
%   Converesly we show that $A\cup A'\subset A\cup\partial A$. Suppose that $x\in A\cup A'$. If $x\in A$ we are again done, so suppose $x\notin A$. Then $x\in A'$, so every neighborhood $N_\epsilon(x)$ meets $A$. Since $x\notin A$, every neighborhood $N_\epsilon(x)$ also meets $A^c$, and so $x\in\partial A$, as desired.
% \end{proof}

% venn diagram of different types of points?

\newpage
\subsection*{Activity for \S \thesection}

\begin{activity}
  \item For each of the following sets $A$, find the boundary $\partial A$. Then decide whether the set is open, closed, both, or neither.
  \begin{enumerate}\itemsep\fill
    \item $A=\set{0,1,\ldots,10}$
    \item $A=\set{1/n\mid n\in\N}\cup\{0\}$
    \item $A=(-1,1)\cup\{2\}$
    \item $A=[-1,1]\cup\{2\}$
    \item $A=\Q$
    \item $A=\set{x\mid (\exists n\in\N)\,\frac1{n+1}<x<\frac1n}$
    \vspace\fill
  \end{enumerate}
\end{activity}

% \begin{exerc}
%   Give an example of a sequence of open sets $A_n$ such that $\bigcap A_n$ is \emph{not} open. Give an example of a sequence of closed sets $B_n$ such that $\bigcup B_n$ is \emph{not} closed.
% \end{exerc}

%\question Suppose that $A$ is an open set, that $x\in A$, and that $x_n\to x$. Show that the sequence $x_n$ eventually lies in $A$.

%\question Show that the previous exercise fails if $A$ is not assumed to be open. In other words, give an example of a set $A$, an element $x\in A$, and a sequence $x_n\to x$ such that the sequence $x_n$ does \emph{not} eventually lie in $A$.

% \begin{exerc}
%   Show that $A$ is clopen (both open and closed) if and only if $\partial A=\emptyset$.
% \end{exerc}

% For the next two exercises, we say that $x\in A$ is an \emph{interior point} of $A$ if there exists a neighborhood $N_\epsilon(x)$ such that $N_\epsilon(x)\subset A$. We write $\inte(A)$ for the set of interior points of $A$.
%
% \begin{exerc}
%   Prove that $\inte(\inte(A))=\inte(A)$.
% \end{exerc}
%
% \begin{exerc}
%   Show that $\inte(A)$ contains all open subsets of $A$.
% \end{exerc}

% show a boundary is always closed

% show that closure A = A union dA is closed

\begin{readnext}
  Abbott, \S 3.3
\end{readnext}


\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Compact sets}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{reading}
  Abbott, \S 3.3
\end{reading}

Recall the Nested Interval Property, which states that the intersection of a family of nested closed intervals $I_n$ is nonempty. We have seen that this theorem may fail if the intervals are not assumed to be closed, or not assumed to be bounded. However, a version of the NIP does hold even if the intervals are replaced by arbitrary sets which are both closed and bounded.

For subsets of $\R$, being both closed and bounded is very strong. To understand why, notice that if $A$ is bounded then by the Bolzano--Weierstra\ss\ theorem every sequence of elements of $A$ has a convergent subsequence, and if $A$ is also closed then the limit of the subsequence lies in $A$. Sets with this compound property are given a special name.

\begin{definition}
  A subset $A\subset\R$ is called \emph{compact} if every sequence from $A$ has a convergent subsequence whose limit lies in $A$.
\end{definition}

\begin{example}
  Any set which is closed and bounded is an example of a compact set. Thus the interval $[0,1]$ is an example, as is the Cantor set $C$. The open interval $(0,1)$ is not compact, since the sequence $a_n=1/n$ has no subsequence that converges to a point in $(0,1)$. The unbounded interval $[0,\infty)$ is not compact, since the sequence $a_n=n$ has no subsequence which converges at all.
\end{example}

The following result gives what one might call the ``nested compact sets property.''

\begin{theorem}
  Let $A_n$ be a sequence of nonempty compact sets such that $A_{n+1}\subset A_n$ for all $n$. Then $\bigcap A_n\neq\emptyset$.
\end{theorem}

\begin{proof}
  For each $n$ choose any element $a_n\in A_n$. In particular the entire sequence lies in $A_1$, and since $A_1$ is compact, $a_n$ has a convergent subsequence $a_{n_k}$ with some limit $L\in A_1$. Moreover, since the $A_n$ are nested, for every $n$ some tail of the subsequence $a_{n_k}$ lies entirely within $A_n$. Since $A_n$ is compact, $a_{n_k}$ has a subsequence whose limit is in $A_n$. Since $a_{n_k}$ converges to $L$, this limit must be $L$ and therefore $L\in A_n$. Thus we have shown that $L\in\bigcap A_n$.
\end{proof}

Compact sets play a role in almost every area of mathematics. As just a small example consider the extreme value theorem from calculus. The way it is usually stated, the EVT says that a continuous function on a closed, bounded interval attains its minimum and maximum value. It turns out that the domain of the function can be taken to be any compact set. Since we have not yet introduced continuous functions, we give a sketch of the proof that will be made more formal in the future.

\begin{theorem}[Extreme Value Theorem]
  Any continuous function with a compact domain attains a minimum and maximum value.
\end{theorem}

\begin{proof}[Proof sketch]
  Let $A$ be a compact set and let $f\colon A\to\R$ be a continuous function. Let $R=\{f(x)\mid x\in A\}$ be the range of $f$, and let $\alpha=\sup(R)$. We wish to show there is some $x\in A$ such that $f(x)=\alpha$. Since $\alpha=\sup(R)$ there exists a sequence $y_n$ contained within $R$ such that $y_n\to\alpha$. For each $n$ we may then let $x_n\in A$ be such that $f(x_n)=y_n$. Since $A$ is compact, there exists a convergent subsequence $x_{n_k}$ with some limit $x$. Then since $f$ is continuous $f(x)=f(\lim x_{n_k})=\lim f(x_{n_k})=\lim y_{n_k}=\alpha$, which means $f$ attains a maximum value. [It remains for us to justify why we can pass the limit from the inside to the outside of the function $f$.]
\end{proof}

As we have outlined above, any closed and bounded subset of $\R$ is compact. In fact for subsets of $\R$ (or even $\R^n$), this turns out to be an equivalence.

\begin{theorem}[Heine--Borel]
  If $A\subset\R$ then $A$ is compact if and only if $A$ is closed and bounded.
\end{theorem}

\begin{proof}
  We have already seen that the Bolzano--Weierstra\ss\ theorem implies that every set which is closed and bounded is compact. For the converse we will show that if $A$ is either not closed or unbounded, then $A$ is not compact.

  First suppose that $A$ is unbounded. Then for all $n$ there exists some point $a_n\in A$ such that $|a_n|>n$. It follows that every subsequence of $a_n$ does not converge at all, and therefore that $A$ is not compact.

  Next suppose that $A$ is not closed. Then by there exists some $a\in\partial A\setminus A$. That is, $a$ is in the boundary of $A$ but not in $A$. From the definition of boundary, it is not difficult to verify there exists a sequence $a_n$ of elements of $A$ such that $a_n\to a$. Then $a_n$ has the property that none of its subsequences converges to a point of $A$, and so $A$ is again not compact.
\end{proof}

The equivalence in the last theorem turns out to be something of a coincidence. Indeed when one studies the topology of more general types of spaces, the equivalence can fail. For example, if one studies topology on $\R$ with the usual distance $|x-y|$ replaced by the function $d(x,y)=|x-y|/(1+|x-y|)$, then the entire space $\R$ is closed and bounded, and fails to be compact. In general topology one doesn't use a distance function at all, so ``bounded'' doesn't make sense. In this setting, even the subsequence definiton of compactness fails to be adequate.

\newpage
\subsection*{Activity for \S \thesection}

\begin{activity}
  \item (See Abbott, ex 3.3.5) Decide whether each of the following sets $A$ is compact. If it is not compact, give an example of a sequence in $A$ with no subsequential limit in $A$.
  \begin{enumerate}\itemsep\fill
    \item $A=\set{0,1,\ldots,10}$
    \item $A=\Z$
    \item $A=\set{1/n\mid n\in\N}\cup\{0\}$
    \item $A=\set{q\in\Q\mid0\leq q\leq2}$
    \item $A=\set{x\mid (\exists n\in\N)\,\frac1{2n+1}\leq x\leq\frac1{2n}}$
    \vspace\fill
  \end{enumerate}
\end{activity}

% \begin{exerc}
%   Prove, using the ``subsequential limit'' definition of compactness, that if $A$ and $B$ are both compact then $A\cup B$ is compact.
% \end{exerc}
%
% \begin{exerc}
%   Prove, using the ``subsequential limit'' definition of compactness, that if $A$ is a closed subset of a compact set $B$, then $A$ is compact. Conclude that the boundary of any compact set is compact.
% \end{exerc}
%
% \begin{exerc}
%   \begin{enumerate}
%     \item Suppose that $A$ is a closed subset of $\R$ which is bounded above. Show that $\sup(A)\in A$.
%     \item Suppose that $A$ is an open subset of $\R$ which is bounded above. Show that $\sup(A)\notin A$.
%   \end{enumerate}
% \end{exerc}

\begin{readnext}
  Abbott, \S 3.4
\end{readnext}


\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Connected sets}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{reading}
  Abbott, \S 3.4
\end{reading}

Thinking about sets in the plane, it is easy to visualize the idea that some sets come all in one blob, while others are split up into multiple blobs. But if a set is just a shapeless collection of points, it is impossible to make this idea precise. It is tempting to say that $(0,1)\cup[1,2)$ has two componenents, but it is actually equal to $(0,2)$ which seems to have just one component.

We will need to bring topology into the picture. If the two components are open, then this idea works. For example, the set $(0,1)\cup(1,2)$ consists of two nonempty disjoint open components, and so we say it is \emph{disconnected}. But we will need to be more general, because a set like $[0,1]\cup[2,3]$ is also disconnected but its components aren't open.

To resolve this mess, we observe that the two components of the set $[0,1]\cup[2,3]$ are \emph{contained in} disjoint open sets. That is, $[0,1]\subset(-0.1,1.1)$ and $[2,3]\subset(1.9,3.1)$. The following correct definition is the end result of this line of reasoning.

% Suggestion for streamlined definition of connected.

% Motivation: Consider the ways intervals can abut.
% [0,1]u[1,2]. The sets overlap. The result is connected.
% [0,1]u(1,2]. The sets are disjoint. But the boundaries meet. Even stronger, the boundary of one set meets the other set. The result is connected.
% [0,1)u(1,2]. The boundaries meet. But at least the boundary of each set doesn't meet the other set. The result is disconnected.

% A is connected if for any partition of A into nonempty sets BuC, either dB meets C or dC meets B.
% A is disconnected if you can partition it into nonempty sets BuC, such that dB,C are disjoint and B,dC are disjoint.

\begin{definition}
  A subset $A\subset\R^n$ is said to be \emph{disconnected} if there exist disjoint open sets $V,V'$, both meeting $A$, and such that $A\subset V\cup V'$. A subset $A\subset\R^n$ is said to be \emph{connected} if it is not disconnected.
\end{definition}

Observe that it was easier to define disconnectedness first, and connectedness as its opposite. Thus we begin with examples of disconnected sets.

\begin{example}
  The union $(0,1)\cup(3,4)$ is clearly disconnected. The Cantor set is disconnected, being contained in $(-1,\frac12)\cup(\frac12,2)$. The set $\Q$ is disconnected, being contained in $(-\infty,\sqrt2)\cup(\sqrt2,\infty)$.
\end{example}

In fact, as the next proposition shows, any subset of $\R$ which is not an interval must be disconnected. In the past we have mentioned open and closed intervals, but when we say just \emph{interval}, we mean an interval of any type. Thus the sets $(a,b)$, $(a,b]$, $[a,b)$, and $[a,b]$ are all intervals, where $a,b$ may be real numbers or even $\pm\infty$ when it makes sense. It is easy to see that a subset $A\subset\R$ is an interval if and only if whenever $a,b\in A$ and $a<c<b$ we have $c\in A$ too.

\begin{proposition}
  If $A$ is a subset of $\R$ and $A$ is connected, then $A$ is an interval.
\end{proposition}

\begin{proof}
  Let $a,b\in A$ and $a<c<b$; we wish to show that $c\in A$ too. Indeed if $c\notin A$, then the sets $V=(-\infty,c)$ and $V'=(c,\infty)$ would witness that $A$ is disconnected, which is contrary to our hypothesis.
\end{proof}

At this point we should stress that for subsets of $\R^2$ or higher, the situation is much more complex. In fact, in these higher dimensions there are connected figures of any shape you can imagine.

So far we have not given any examples of connected sets. Intuitively speaking all intervals should be connected, that is, the converse to the above proposition should be true. Thus if our definition of connectedness is a good one, it will allow us to verify that intervals are connected. Because the definition was so complex, this verification turns out to be slightly tricky.

\begin{theorem}
  If $A$ is a subset of $\R$, then $A$ is connected if and only if $A$ is an interval.
\end{theorem}

\begin{proof}
  We have already shown that connected subsets of $\R$ must be intervals. Conversely, let $I$ be an interval, and suppose towards a contradiction that $I\subset V\cup V'$ where $V,V'$ are disjoint open sets meeting $I$. Let us also choose specific elements $a_1\in I\cap V$ and $b_1\in I\cap V'$, and assume without loss of generality that $a_1<b_1$.

  In the next part of the proof, we will use $a_1,b_1$ as the basis for sequences $a_n$ and $b_n$. The sequence $a_n$ will be monotone increasing and lie in $V$, while the sequence $b_n$ will be monotone decreasing and lie in $V'$. Moreover the two sequences will be getting closer and closer to one another, that is, $a_n-b_n\to0$.

  Assuming this has been done, we can complete the proof as follows. By the monotone convergence theorem $a_n$ and $b_n$ both converge, and since $a_n-b_n\to0$ they both converge to the same limit $L$. Since $I$ is an interval and $a_1\leq L\leq b_1$, we clearly have $L\in I$. Since $I\subset V\cup V'$, we have either $L\in V$ or $V'$. But $L$ cannot be in $V$ since $V$ is open and $L$ is a limit of points outside $V$. Similarly, $L$ cannot be in $V'$, resulting in a contradiction.

  To construct the sequences $a_n$ and $b_n$, assume the terms $a_n,b_n$ have been defined and define $a_{n+1},b_{n+1}$ as follows. Let $c$ be the midpoint of $a_n,b_n$. Since $I$ is an interval, $c$ lies in $I$ too. Since $I\subset V\cup V'$, we either have $c\in V$ or $V'$. If $c$ lies in $V$ then let $a_{n+1}=c$ and $b_{n+1}=b_n$; if $c$ lies in $V'$ then let $a_{n+1}=a_n$ and $b_{n+1}=c$. In either case we have everything we want: $a_{n+1}\in V$, $b_{n+1}\in V'$, $a_n\leq a_{n+1}<b_{n+1}\leq b_n$ and the distance between $a_{n+1},b_{n+1}$ has decreased by half.
\end{proof}

Recall that the compact sets will play a key role in the Extreme Value Theorem from calculus. Similarly, the connected sets will play a key role in the Intermediate Value Theorem from calculus. Once again, we provide only a preview.

\begin{theorem}[Intermediate Value Theorem]
  If $f$ is a continuous function with a connected domain, then $f(a)<0<f(b)$ implies there exists $c$ such that $f(c)=0$.
\end{theorem}

\begin{proof}[Sketch of proof]
  If there was no such $c$, then the sets $V=\{x\mid f(x)<0\}$ and $V'=\{x\mid f(x)>0\}$ would witness that the domain of $f$ is disconnected, a contradiction. [It remains to justify why $V$ and $V'$ are open.]
\end{proof}

Athough it took some work to show the intervals are connected, this fact can be leveraged to show that a variety of subsets of $\R^n$ are connected. For this we will need to see how one can piece together several connected sets to make a larger one.

\begin{proposition}
  If $\mathcal F$ is a family of connected sets which overlap pairwise, then $S=\bigcup\mathcal F$ is connected.
\end{proposition}

\begin{proof}
  Suppose, towards a contradiction, that there exist disjoint open sets $V,V'$ meeting $S$ such that $S\subset V\cup V'$. Since each set $A\in\mathcal F$ is connected, it must be contained in either $V$ or $V'$. Indeed, otherwise $V,V'$ would witness that $A$ is disconnected. Since both $V,V'$ meet $S$, we can find $A,B\in\mathcal F$ such that $A\subset V$ and $B\subset V'$. But we are assuming that $A,B$ overlap, while $V,V'$ are disjoint, a contradiction.
\end{proof}

As a simple application, this result can be used to show that disks in $\R^2$ are connected.

\begin{corollary}
  Let $D$ be a disk in $\R^2$, possibly containing some or all of its boundary. Then $D$ is connected.
\end{corollary}

\begin{proof}
  $D$ can be written as a union of straight line segments from $\mathbf{0}$ to the boundary of $D$. The proof that intervals are connected may also be used to show that line segments are connected. Since these line segments all overlap at $\mathbf{0}$, the previous proposition implies that $D$ is connected.
\end{proof}

\newpage
\subsection*{Activity for \S \thesection}

\begin{activity}
  \item Decide whether each of the following sets $A$ is connected. If it is not connected, give an example of disjoint open sets $V,V'$ meeting $A$ such that $A\subset V\cup V'$.
  \begin{enumerate}\itemsep\fill
    \item $A=\set{x\mid x^2<5}$
    \item $A=\set{x\mid 2<x^2<5}$
    \item $A=\set{x\mid x^3-3x^2+x=0}$
    \item $A=\set{x\mid x^3+x^2+x=0}$
    \item $A=$ any countable infinite subset of $\R$
    \vspace\fill
  \end{enumerate}
  \item How many different kinds of interval are there?
  \vspace\fill
%   \item Explain why $A$ is an interval if and only if whenever $a,b\in A$ and $a<c<b$ we have $c\in A$ too.
%   \vspace\fill
\end{activity}
  
%\question Suppose $A$ and $B$ are open intervals. Under what circumstances will $A\cup B$ be connected? Under what circumstances  will $A\cap B$ be connected?

% \begin{exerc}
%   If $A,B$ are connected subsets of $\R$, show that $A\cap B$ is connected. Is this true for connected subsets $A,B$ of $\R^2$?
% \end{exerc}

% \begin{exerc}
%   Let $A$ be a subset of $\R^n$.
%   \begin{enumerate}
%     \item Show that any open set which meets $\cl(A)$ also meets $A$. [Recall that $\cl(A)=A\cup\partial A$.]
%     \item Show that if $A$ is connected then $\cl(A)$ is connected.
%   \end{enumerate}
% \end{exerc}

% Replace with \partial(A)?

\begin{readnext}
  Abbott, \S 8.2
\end{readnext}

\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Metric space}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{reading}
  Abbott, \S 8.2
\end{reading}

So far we have studied the topology of the real line $\R$ and to some extent the Euclidean spaces $\R^n$. Almost everything we have said about these spaces applies in a vastly more general context.

\begin{definition}
  A \emph{metric space} consists of a set of points $X$ together with a distance function $d\colon X\times X\to\R$ satisfying the following properties for all $x,y,z\in X$:
  \begin{enumerate}
  \item $d(x,y)\geq0$, with $d(x,y)=0$ iff $x=y$;
  \item $d(x,y)=d(y,x)$; and
  \item $d(x,z)\leq d(x,y)+d(y,z)$.
  \end{enumerate}
\end{definition}

Parts~(a) and (b) of the definition should seem quite natural. Part~(c) is motivated by the triangle inequality for real numbers, which we have often used in the form $|x-z|\leq|x-y|+|y-z|$.

\begin{example}
  The real line $\R$ and Euclidean spaces $\R^n$ are the quintessential examples of metric spaces. The usual distance function on $\R$ is $d(x,y)=|x-y|$ and the usual distance function on $\R^n$ is $d(x,y)=\|x-y\|$.
\end{example}

\begin{example}
  Any subset $A$ of a given metric space $X$ can be thought of as a metric space in its own right. The restriction of the metric $d$ to $A\times A$ still satisfies properties (a)--(c). Thus for examlpe the Cantor set is a metric space.
\end{example}

\begin{example}
  The space $C[0,1]$ consists of all continuous functions $f\colon[0,1]\to\R$. (Recall that we will discuss continuity more rigorously in the next chapter.) The distance function is the \emph{uniform distance} $d(f,g)=\sup_{t\in[0,1]}|f(t)-g(t)|$.
\end{example}

To do topology in metric space, we first have to have neighborhoods. Recall that in $\R$ the neighborhood notation $N_\epsilon(x)$ denotes the interval $(x-\epsilon,x+\epsilon)$. In $\R^2$ the neighborhood notation $N_\epsilon(\mathbf{x})$ denotes the disk centered at $x$ of radius $\epsilon$, and so forth. By analogy, if $X$ is a metric space with distance function $d$, we can define the neighborhoods $N_\epsilon(x)=\{y\in X\mid d(x,y)<\epsilon\}$.

We can use these neighborhoods to repeat the definitions of all the basic topological concepts.

\begin{definition}
  Let $X$ be a metric space with distance function $d$ and let $A\subset X$.
  \begin{itemize}
  \item A point $x\in X$ is on the boundary of $A$ if every neighborhood $N_\epsilon(x)$ meets both $A$ and $X\setminus A$
  \item $A$ is open if it omits its boundary, $A$ is closed if it contains its boundary
  \item $x_n$ converges to $x$ if $(\forall\epsilon>0)(\exists N\in\N)(\forall n>N)\,d(x_n,x)<\epsilon$
  \item $x_n$ is Cauchy if $(\forall\epsilon>0)(\exists N\in\N)(\forall m,n>N)\,d(x_m,x_n)<\epsilon$
  \item $A$ is compact if every sequence of $A$ has a subsequence converging to a limit in $A$
  \item $A$ is connected if one cannot find disjoint open sets $V,V'$ meeting $A$ such that $A\subset V\cup V'$.
  \end{itemize}
\end{definition}

% It is easy to fill in the omitted definitions of interior, exterior, and several others.

Since we have defined convergent and Cauchy sequences, it is natural to ask whether the Cauchy criterion is true in metric spaces. The answer is not in general! For example, if $X$ is the space $(0,1)$, then the sequence $1/n$ is a Cauchy sequence in $X$ with no limit in $X$. This means we need a name for the situation when the Cauchy criterion is true in $X$.

\begin{definition}
  A metric space $X$ is \emph{complete} if every Cauchy sequence is convergent.
\end{definition}

In this terminology, $\R$ is complete (by the actual Cauchy criterion), and the spaces $\R^n$ are complete too. On the other hand, the space $X=(0,1)$ is not complete.

\begin{proposition}
  A subspace $A\subset\R$ is complete if and only if $A$ is closed.
\end{proposition}

\begin{proof}
  First suppose that $A$ is closed and let $a_n$ be a sequence of $A$. By the Cauchy criterion, $a_n$ has a limit $a$, and since $A$ is closed, $a\in A$. 

  Conversely, suppose that $A$ is complete and let $a$ be a limit point of $A$. Then there exists a sequence $a_n$ of $A$ with limit $a$. Since $a_n$ is convergent, it is Cauchy and therefore has a subsequence with limit in $A$. Since subsequences of a convergent sequence converge to the same limit, it follows that $a\in A$ and therefore that $A$ is closed.
\end{proof}

\begin{theorem}
  The space $C[0,1]$ is complete.
\end{theorem}

\begin{proof}
  Let $f_n$ be a sequence of functions which is Cauchy in the metric of $C[0,1]$. This means that for all $\epsilon$ there exists $N$ such that $n>N$ implies $\sup_{t\in[0,1]}|f_n(t)-f_m(t)|<\epsilon$. We seek to find a function $f$ which is the limit of the sequence. To define the function $f$, first note that since $f_n$ is Cauchy, it follows that for each $t\in[0,1]$ the sequence $f_n(t)$ is a Cauchy sequence of real numbers. Now by the Cauchy criterion, for each $t$ the sequence $f_n(t)$ has a limit. Thus we can define a function $f(t)=\lim f_n(t)$.

  While it may seem like we are done, we actually have to verify two things. First we have to check that $f$ really lies in $C[0,1]$, in other words, that $f$ is a continuous function. We will leave out this check for now, and revisit it when we have introduced continuous functions more formally. Second we have to check that $f_n\to f$ in the uniform metric (at the moment we only know $f_n\to f$ pointwise).

  To see that $f_n\to f$ in the uniform metric, let $\epsilon>0$ be given and choose $N$ large enough such that $m,n>N$ implies $\sup_{t\in[0,1]}|f_m(t)-f_n(t)|<\epsilon/2$. Fixing $n>N$ and $t\in[0,1]$, find $m>N$ large enough that $|f_m(t)-f(t)|<\epsilon/2$. Now we have
\[|f_n(t)-f(t)|\leq|f_n(t)-f_m(t)|+|f_m(t)-f(t)|<\epsilon/2+\epsilon/2=\epsilon\;.
\]
Since $t$ was arbitrary, we have $\sup_{t\in[0,1]}|f_n(t)-f(t)|\leq\epsilon$, which shows that $f_n\to f$ in the uniform metric.
\end{proof}

When $f_n\to f$ in the uniform metric, we say that the sequence $f_n$ \emph{converges uniformly} to $f$. In the future we will address the missing component in the above proof by showing that whenever a sequence of continuous functions converges uniformly to a limit, the limit must be continuous.

\newpage
\subsection*{Activity for \S \thesection}

\begin{activity}
  \item For each of the distance functions below, verify that it is a metric on $\R^2$. Then plot the set of points in the plane that are exactly one unit away from the origin.
  \begin{enumerate}
    \item $\displaystyle d(\mathbf{x},\mathbf{y})=\max\set{|x_1-y_1|,|x_2-y_2|}$
    \vspace\fill
    \item $\displaystyle d(\mathbf{x},\mathbf{y})=|x_1-y_1|+|x_2-y_2|$
    \vspace\fill
    \item $\displaystyle d(\mathbf{x},\mathbf{y})=\begin{cases}1&x\neq y\\0&x=y\end{cases}$
    \vspace\fill
  \end{enumerate}
  \item Give an informal explanation why the following is a metric on $C[0,1]$. What does it mean for a function $f$ to be in $N_\epsilon(0)$?
  \[d(f,g)=\int_0^1|f-g|
  \]
  \vspace\fill
\end{activity}

\begin{readnext}
  Abbott, \S 4.1, 4.2
\end{readnext}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\chapter{Continuity and calculus}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Functions and limits}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{reading}
  Abbott, \S 4.1, 4.2
\end{reading}

So far in this course we have investigated real numbers and sets of real numbers. In this part we will study functions because they are fundamental to applications such as modeling. Many of the most important functions turn out to be continuous. For example if you go for a jog, the distance you travel varies continuously over time. Moreover many common expressions such as $x^2$, $\ln(x)$, or $3\sin(x)-2e^x$ define continuous functions. However it is important to note that not all natural functions are continuous. For example the charge for a phone call does not vary continuously over time because it jumps at each minute.

What exactly is a continuous function? We often say intuitively that a continuous function has no breaks in its graph. But how can we make ``no breaks'' more formal? A simple example of a discontinuous function is one with a jump:
\begin{center}
\begin{tikzpicture}[domain=0:4]
\draw (-0.2,0) -- (4.2,0);
\draw (0,-0.2) -- (0,2.2);
\draw plot (\x,{1+sin(\x r)});
\draw[fill=white] (3,{1+sin(3r)}) circle (.07);
\draw[fill=black] (3,{1.5+sin(3r)}) circle (.07);
\draw (3,.05)--(3,-.05);
\node[below] at (3,0) {$a$};
\end{tikzpicture}
\end{center}
What makes this function discontinuous is that the value $f(a)$ (the filled dot) is nowhere near the limit of $f(x)$ as $x$ approaches $a$ (the unfilled dot). In order to follow through on this idea, we need to give a formal definition for ``the limit of $f(x)$ as $x$ approaches $a$.''

% Roughly speaking, we will define that $f$ is continuous at $a$ if whenever the values of $x$ approach $a$, the values of $f(x)$ approach $f(a)$:
% \[f(a)=\lim_{x\to a}f(x)
% \]
% In the past we have seen limits with $n\to\infty$, we have to make a new definition for $x\to a$.

% In convergence for ordinary limits, as the index $n$ gets larger the values $x_n$ get closer to the limit $L$. Thus the definition began ``for all $\epsilon$ there exists an $N$.'' In convergence for functional limits, as the variable $x$ gets closer to $a$ the values $f(x)$ get closer to $L$. Thus the definition will begin ``for all $\epsilon$ there exists a $\delta$'', where $\delta$ is another small quantity.

\begin{definition}
  We say that $\lim_{x\to a}f(x)=L$ if for all $\epsilon>0$ there exists $\delta>0$ such that $0<|x-a|<\delta$ implies $|f(x)-L|<\epsilon$.
\end{definition}

Visualizing the definition on the graph of $f$, it means that whenever we draw a band of radius $\epsilon$ around the line $y=L$, there exists a small enough $\delta$ such that on $N_\delta(a)$ the function lies entirely within the band.
\begin{center}
\begin{tikzpicture}
\draw (-0.2,0) -- (4.2,0);
\draw (0,-0.2) -- (0,2.2);
\draw[domain=0:4] plot (\x,{1+sin(\x r)});
\draw[domain=2.8:3.2,samples=100,very thick] plot (\x,{1+sin(\x r)});
\draw[fill=white] (3,{1+sin(3r)}) circle (.07);
\draw[dashed] (0,{1+sin(3r)+.3}) -- (4,{1+sin(3r)+.3}) node[right] {$L+\epsilon$};
\draw[dashed] (0,{1+sin(3r)-.3}) -- (4,{1+sin(3r)-.3}) node[right] {$L-\epsilon$};
\node[below] at (3,0) {$N_\delta(a)$};
\draw (2.8,.05)--(2.8,-.05);
\draw (3.2,.05)--(3.2,-.05);
\draw[very thick] (2.8,0)--(3.2,0);
\end{tikzpicture}
\end{center}

\begin{example}
  We can verify by hand that $\lim_{x\to2}(5x+3)=13$. As scratch work, let $\epsilon$ be given and let us work backwards as follows:
  \begin{align*}
    |5x+3-13|<\epsilon&\iff|5x-10|<\epsilon\\
                      &\iff5|x-2|<\epsilon\\
                      &\iff|x-2|<\epsilon/5
  \end{align*}
  This calculation suggests we should let $\delta=\epsilon/5$. To write the proof forwards, we do indeed let $\delta=\epsilon/5$ and then observe that the calculation above shows that $|x-2|<\delta\implies|5x+3-13|<\epsilon$, as desired.
\end{example}

The linear example above was perhaps a little too simple; the following quadratic example gives one an idea of the kinds of manipulations that can arise generally.

\begin{example}
  Let us verify by hand that $\lim_{x\to2}x^2=4$. As scratch work, we once again work backwards from the desired conclusion:
  \begin{align*}
    |x^2-4|<\epsilon&\iff |x-2|\cdot|x+2|<\epsilon\\
                    &\iff |x-2|<\epsilon/|x+2|
  \end{align*}
  Now unfurtunately this last quantity is not a constant so it does not tell us directly what number to choose for $\delta$. However for values of $x$ near $2$ we will certainly have $|x+2|<10$. Thus we choose $\delta=\epsilon/10$, promise ourselves to consider values of $x$ near $2$, and write the proof forwards as follows:
  \begin{align*}
    |x-2|<\delta &\implies |x-2|<\epsilon/10\\
                 &\implies |x-2|<\epsilon/|x+2|\\
                 &\implies |x^2-4|<\epsilon
  \end{align*}
  which concludes this example.
\end{example}

It is also possible to use sequential limits to describe functional limits, as the next result shows.

\begin{theorem}
  The following are equivalent.
  \begin{itemize}
  \item for all $\epsilon>0$ there exists $\delta>0$ such that $0<|x-a|<\delta$ implies $|f(x)-L|<\epsilon$;
  \item for all sequences $x_n\neq a$ if $x_n\to a$ then $f(x_n)\to L$.
  \end{itemize}
\end{theorem}

\begin{proof}
  We first assume the $\epsilon,\delta$ statement holds. Letting $x_n$ be a given sequence such that $x_n\neq a$ and $x_n\to a$, we wish to show that $f(x_n)\to L$. To this end let $\epsilon$ be arbitrary, and choose $\delta$ as in the the hypothesis. Since $x_n\to a$ we can find $N$ such that $n>N$ implies $|x_n-a|<\delta$. The hypothesis now gives that $|f(x_n)-L|<\epsilon$, and therefore that $f(x_n)\to L$.

  For the converse, we proceed by contrapositive. Assume that the negation of the $\epsilon,\delta$ statement holds, that is, there exists $\epsilon$ such that for al $\delta$ there exists $x\neq a$ such that $|x-a|<\delta$ but $|f(x)-L|\geq\epsilon$. Fix this special value of $\epsilon$, and apply the statement repeatedly to $\delta$-values $1/n$. We thus obtain a sequence of $x_n\neq a$ such that $|x_n-a|<1/n$ but $f|(x_n)-L|\geq\epsilon$. It follows that $x_n\to a$, but $f(x_n)$ does not converge to $L$. This establishes the negation of the latter statement, as desired.
\end{proof}  

This theorem is nice to have because the two equivalent clauses have complementary uses. The sequential definition is really handy for refuting functional limit equalities, since one can use a single sequence as a counterexample. On the other hand, the definition is cumbersome for establishing functional limit equalities because of the ``for all sequences'' quantifier. The $\epsilon,\delta$ definition is often one's only resort for establishing a functional limit equality.

We close this section with the analog of the limit calculus for functional limits.

\begin{theorem}[Functional limit calculus]
  Suppose that $\lim_{x\to a}f(x)=L$ and $\lim_{x\to a}g(x)=M$. Then we have
  \begin{enumerate}
    \item $\displaystyle\lim_{x\to a}[f(x)+g(x)]=L+M$
    \item $\displaystyle\lim_{x\to a}kf(x)=kM$ for any $k\in\R$
    \item $\displaystyle\lim_{x\to a}f(x)g(x)=LM$
    \item $\displaystyle\lim_{x\to a}f(x)/g(x)=L/M$ provided $M\neq 0$
    \item $\displaystyle\lim_{x\to a}\sqrt{f(x)}=\sqrt{L}$ provided $f(x)\geq 0$
  \end{enumerate}
\end{theorem}

\begin{proof}
  Each of these statements can be proved using the corresponding statement in the ordinary limit calculus. For example let us prove part~(a). For this let $x_n$ be an arbitrary sequence such that $x_n\to a$. Then $\lim[f(x_n)+g(x_n)]=\lim f(x_n)+\lim g(x_n)$ by the limit calculus. By our hypothesis and the limit characterization of functional limits, this latter quantity equals $L+M$. Since $x_n$ was arbitrary, we can conclude that $\lim_{x\to a}[f(x)+g(x)]=L+M$.
\end{proof}
% of course the last statement actually requires some care

\begin{theorem}[Functional squeeze theorem]\
  \begin{itemize}
  \item If $f(x)\geq0$ in a neighborhood of $a$ and $\lim_{x\to a}f(x)$ exists then $\lim_{x\to a}f(x)\geq0$.
  \item If $f(x)\leq g(x)\leq h(x)$ and $\lim_{x\to a}f(x)=\lim_{x\to a}h(x)=L$ then $\lim_{x\to a}g(x)$ exists and $=L$.
  \end{itemize}
\end{theorem}

The proof is left as an exercise.

\newpage
\subsection*{Activity for \S \thesection}

\begin{activity}
  \item Prove the following using the $\epsilon,\delta$-definition of functional limits.
  \begin{enumerate}
    \item $\displaystyle\lim_{x\to3}x^2=9$
    \vspace\fill
    \item $\displaystyle\lim_{x\to4}\sqrt{x}=2$
    \vspace\fill
  \end{enumerate}
  \item Evaluate the following using the limit laws.
  \begin{enumerate}
    \item $\displaystyle\lim_{x\to0}\frac{x^3+2x^2+3x+1}{x^5+x+2}$
    \vspace\fill
    \item $\displaystyle\lim_{x\to-2}\frac{x^2-x-6}{3x^2+5x-2}$
    \vspace\fill
  \end{enumerate}
\end{activity}

% \begin{exerc}
%   Read \S4.1 of the text and write a one-paragraph response. You may use the following questions as a writing prompt. What definition of function does the text give? How do the examples of ``wild'' functions given in the text challenge your intuitive idea of what a function is? What implications does this have on the difficulty of the task of investigating continuity? Did you have any other comments or questions while reading the section?
% \end{exerc}

% \begin{exerc}
%   Let $f(x)$ be the Dirichlet function, defined by
%   \[f(x)=\begin{cases}1&x\in\Q\\0&x\notin\Q\end{cases}
%   \]
%   Prove that for every real number $a$, $f$ is discontinuous at $a$.
% \end{exerc}

% \begin{exerc}[Abbott, ex 4.2.6(a)]
%   Suppose $\delta>0$ has been constructed as a suitable response to a particular $\epsilon$ challenge. Which is correct and why: any larger $\delta$ will also suffice, or; any smaller $\delta$ will also suffice.
% \end{exerc}

% \begin{exerc}
%   Prove using the $\epsilon,\delta$ definition that if $\lim_{x\to a}f(x)=L$ and $\lim_{x\to a}g(x)=M$ then $\lim_{x\to a}\left[f(x)+g(x)\right]=L+M$.
% \end{exerc}

% \begin{exerc}[Abbott, ex 4.2.11]
%   Prove the squeeze theorem for functional limits: if $f(x)\leq g(x)\leq h(x)$ and $\lim_{x\to a}f(x)=\lim_{x\to a}h(x)=L$ then $\lim_{x\to a}g(x)$ exists and $=L$. You may use either definition of functional limit.
% \end{exerc}

\begin{readnext}
  Abbott, \S 4.3
\end{readnext}


\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Continuous functions}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{reading}
  Abbott, \S 4.3
\end{reading}

Recall that intuitively speaking, we said that $f$ is continuous at $a$ if the value of the function at $a$ is near the values $f(x)$ as $x$ approaches $a$. Thanks to our rigorous treatment of functional limits, we are now ready to state this formally as follows.

\begin{definition}
  Let $f$ be a real-valued function defined on an interval of $\R$. We say $f$ is \emph{continuous} at a point $a$ in its domain if $\lim_{x\to a}f(x)$ exists and equals $f(a)$. We say that $f$ is \emph{continuous} if it is continuous at every point of its domain.
\end{definition}

Our theorems regarding functional limits are now ready to bear fruit. First of all, since functional limits admit both an $\epsilon,\delta$ and a sequential characterization, so too does continuity.

\begin{proposition}
  The function $f$ is continuous at $a$ if and only if either of the two following conditions holds:
  \begin{enumerate}
  \item for all $\epsilon$ there exists a $\delta$ such that for all $x$, $|x-a|<\delta$ implies $|f(x)-f(a)|<\epsilon$; or
  \item for all sequences $x_n$, if $x_n\to a$ then $f(x_n)\to f(a)$
  \end{enumerate}
\end{proposition}  

\begin{proof}
  The equivalence of continuity with (a) is clear from the $\epsilon,\delta$ definition of functional limit. The equivalence of continuity with (b) is clear from the sequential characterization of functional limit.
\end{proof}

\begin{theorem}[Continuity calculus]
  Suppose that $f,g$ are continuous functions with the same domain. Then we have:
  \begin{enumerate}
    \item $f+g$ is continuous
    \item $kf$ is continuous for any $k\in\R$
    \item $fg$ is continuous
    \item $f/g$ is continuous, provided $g(x)\neq 0$
    \item $\sqrt{f}$ is continuous, provided $f\geq0$
  \end{enumerate}
\end{theorem}

These properties follow trivially from the functional limit calculus, together with the definition of continuity. To this list of laws we can add one additional operation, namely composition of functions.

\begin{theorem}
  If $f,g$ are continuous and $\rng(f)\subset\dom(g)$ then the composition $g\circ f$ is continuous.
\end{theorem}

\begin{proof}
  This follows trivially from the sequential characterization of continuity. Let $a$ be a point of $\dom(g\circ f)=\dom(f)$ and let $x_n\to a$. Then since $f$ is continuous $f(x_n)\to f(a)$, and since $g$ is continuous $g\circ f(x_n)\to g\circ f(a)$. This shows $g\circ f$ is continuous at $a$.
\end{proof}

The continuity calculus allows us to establish that a variety of functions are continuous.

\begin{example}
  Since it is clear that the identity function $f(x)=x$ is continuous, we can use the arithmetic laws to conclude that polynomial functions such as $3x^5-17x^2+12$ are continuous. We can also conclude that rational functions such as $(3x^3+17x)/(2x^2-13)$ are continuous whenever the denominator is not zero.
\end{example}

% \begin{example}
%   The function $f(x)=\sqrt{x}$ is continuous on its domain. First let $a>0$ and given $\epsilon$ let $\delta=\epsilon\sqrt{a}$. Then if $|x-a|<\delta$ we have
%   \begin{align*}
%     |\sqrt{x}-\sqrt{a}|&=|x-a|/(\sqrt{x}+\sqrt{a})\\
%                        &<|x-a|/\sqrt{a}\\
%                        &<(\epsilon\sqrt{a})/\sqrt{a}=\epsilon
%   \end{align*}
%   One must check separately that $\sqrt{x}$ is continuous at $a=0$.
% \end{example}

\begin{example}
  The function $\sqrt{x^2+17\sin(1/x)}$ is continuous where it is defined. Here we are using the composition law two times.
\end{example}

\begin{example}
  The function $f(x)=\sin(x)$ is continuous. Since the continuity calculus doesn't apply, we must check this directly from the definition. Without going into details, it is not difficult to see geometrically that we always have $|\sin(x)-\sin(a)|\leq|x-a|$, so we may take $\delta=\epsilon$ in the proof.
\end{example}

We close with a beautiful characterization which expresses continuity in purely topological terms. First we need to define forward and inverse images of a set with respect to a function.

\begin{definition}
  Let $f\colon X\to Y$ be any function. If $A$ is a subset of $X$ then the \emph{forward image} of $A$ with respect to $f$ is the set $f(A)=\set{f(a)\mid a\in A}$. And if $B$ is a subset of $Y$ then the \emph{inverse image} of $B$ with respect to $f$ is $f^{-1}(B)=\set{x\in X\mid f(x)\in B}$.
\end{definition}

Notice that if $f$ is a continuous function and $V$ is an open set, it is not necessarily the case that $f(V)$ is open too. For example if $f(x)=x^2$ and $V=(-1,1)$, then $f[V]=[0,1)$ which is not open. On the other hand, the following result states that the continuous functions are precisely those which preserve the open sets under inverse images. %]

\begin{theorem}
  Let $f\colon\R\to\R$. Then $f$ is continuous everywhere if and only if for every open set $V$ we have $f^{-1}(V)$ is open too.
\end{theorem}

\begin{proof}
  First suppose $f$ is continuous, and let $V$ be open and $a\in f^{-1}(V)$. Since $V$ is open, $f(a)$ has a neighborhood $N_\epsilon(f(a))\subset V$. Since $f$ is continuous at $a$ there exists $\delta$ such that $|x-a|<\delta$ implies $|f(x)-f(a)|<\epsilon$. This is equivalent to the set containment $F(N_\delta(a))\subset N_\epsilon(f(a))$. It follows that $N_\delta(a)\subset f^{-1}(V)$, so $f^{-1}(V)$ is open.
  
  Conversely, suppose $V$ open implies $f^{-1}(V)$ is open. Given $a$ and $\epsilon$ we apply this to the open set $N_\epsilon(f(a))$ to conclude $f^{-1}(N_\epsilon(a))$ is open. This implies there exists $\delta$ such that $f(N_\delta(a))\subset N_\epsilon(f(a))$. This means precisely that $|x-a|<\delta$ implies $|f(x)-f(a)|<\epsilon$, that is, $f$ is continuous at $a$.
\end{proof}

We remark that this characterization is true in the world of metric spaces too: if $f\colon X\to Y$ then $f$ is continuous (preserves limits) if and only if for every open set $V$ in $Y$ we have $f^{-1}(V)$ is open in $X$.

% In the general topology world, where one is only told which sets are open and which are not, this characterization becomes a definition.

\newpage
\subsection*{Activity for \S \thesection}

\begin{activity}
  % \item Write an expression for a function $f$ with the given property.
  % \begin{enumerate}
  %   \item $f$ is defined and continuous everywhere except $x=1$
  %   \item $f$ is defined and continuous everywhere except $x=1,2$
  %   \item $f$ is defined and continuous everywhere except the integers
  %   \item $f$ is defined and continuous everywhere except $(-1,1)$
  % \end{enumerate}
  \item Let $f(x)=\frac{3}{1+x^2}$.
  \begin{enumerate}
    \item Let $V=(1,2)$ and find $f^{-1}(V)$ (a graph may help). Is it open?
    \vspace\fill
    \item Let $W=(-1,1)$ and find $f^{-1}(V)$. Is it open?
    \vspace\fill
    \item Let $V=(1,2)$ and find $f(V)$. Is it open?
    \vspace\fill
    \item Let $W=(-1,1)$ and find $f(W)$. Is it open?
    \vspace\fill
  \end{enumerate}
  % \item Give an example of a discontinuous function $f$ such that $|f|$ is continuous.
%   \item (Abbott, ex 4.3.9) Let $f$ be a continuous function and let $Z=\set{x\mid f(x)=0}$ (the zeroes or roots of the function). Prove that $Z$ is closed.
\end{activity}
  
% \begin{exerc}
%   \begin{enumerate}
%     \item Give an example of a discontinuous function $f$ such that $|f|$ is continuous.
%     \item Give an example of a pair of discontinuous functions $f$ and $g$ such that $f+g$ is continuous.
%   \end{enumerate}
% \end{exerc}

% \begin{exerc}
%   Suppose that $f$ is continuous and $f(c)>0$. Show that there exists a neighborhood of $c$ on which $f$ is positive.
% \end{exerc}
%
% \begin{exerc}[Abbott, ex 4.3.1]
%   Let $f(x)=\sqrt[3]{x}$.
%   \begin{enumerate}
%     \item Prove that $f(x)$ is continuous at $a=0$.
%     \item Prove that $f(x)$ is continuous at $a\neq0$. [Hint: you will need the algebraic identity $A^3-B^3=(A-B)(A^2+AB+B^2)$.]
%   \end{enumerate}
% \end{exerc}

\begin{readnext}
  Abbott, \S 4.4, 4.5
\end{readnext}


\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Continuity and preservation}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{reading}
  Abbott, \S 4.4, 4.5
\end{reading}

In the previous section we concluded that continuous functions preserve open sets under inverse images but not necessarily under forward images. In this section we address the same questions for closed, compact, and connected sets. In doing so we will finally be able to explain two major theorems from calculus: the extreme value theorem and the intermediate value theorem.

Before beginning our investigation, we should point out some further properties of forward and inverse images. It is not hard to check that for any function $f$, the inverse image mapping $f^{-1}$ preserves unions, intersections, and differences. That is, we have
\begin{itemize}
\item $f^{-1}(A\cup B)=f^{-1}(A)\cup f^{-1}(B)$
\item $f^{-1}(A\cap B)=f^{-1}(A)\cap f^{-1}(B)$
\item $f^{-1}(A\setminus B)=f^{-1}(A)\setminus f^{-1}(B)$
\end{itemize}
The forward image mapping $f(\cdot)$ also preserves unions, but fails to preserve intersections or differences. For counterexamples, one can often use the function $f(x)=x^2$.

\begin{proposition}
  If $f$ is continuous and $C$ is closed, then $f^{-1}(C)$ is closed.
\end{proposition}

\begin{proof}
  We have shown that if $f$ is continuous and $V$ is open, then $f^{-1}(V)$ is open. Since $C$ is closed, its complement $\R\setminus C$ is open. It follows from the pervious discussion that $f^{-1}(\R)\setminus f^{-1}(C)$ is open since it is equal to $f^{-1}(\R\setminus C)$. We therefore conclude that $f^{-1}(C)$ is closed.
\end{proof}

Just as continuous functions need not preserve open sets under forward images, neither must they preserve closed sets under forward images. For example if $f(x)=1/(1+x^2)$ and $A=\R$ then $f(A)=(0,1]$. Observe that for this counterexample we chose to go with an unbounded set $A$. The following result implies that it was necessary to do so.

\begin{theorem}
  If $f$ is continuous and $K$ is compact, then $f(K)$ is compact.
\end{theorem}

\begin{proof}
  Let $y_n$ be a seqence of $f(K)$, and let $x_n$ be such that $y_n=f(x_n)$ for all $n$. Since $K$ is compact, $x_n$ has a convergent subsequence $x_{n_k}$ with limit $x\in K$. Since $f$ is continuous we have that $y_{n_k}=f(x_{n_k})$ converges to the limit $f(x)$ which is in $f(K)$. Thus $f(K)$ is compact.
\end{proof}

We have mentioned the extreme value theorem before as an important property of compact sets. At the time we did not have the framework to give a formal proof, but now we do.

\begin{corollary}[Extreme Value Theorem]
  \label{cor:evt}
  If $K$ is compact and $f\colon K\to\R$ is continuous, then $f$ achieves a minimum and maximum value on $K$.
\end{corollary}

\begin{proof}
  By the theorem, $f(K)$ is a compact subset of $\R$. Since compact sets are bounded, $f(K)$ has an infemum $\alpha$ and a supremum $\beta$. Since compact sets are closed, and we have seen that $\alpha,\beta$ lie on the boundary of $f(K)$, it follows that $\alpha,\beta\in f(K)$. Thus there exist $a,b\in K$ such that $f(a)=\alpha$ and $f(b)=\beta$, as claimed.
\end{proof}

The extreme value theorem is the key to any kind of optimization. If one is seeking an optimum value (usually an infemum or supremum), the exterem value theorem gives conditions under which one can be assured that such a value exists.

Finally we turn to preservation of connected sets. To motivate this, observe intuitively that if $f$ is a continuous real-valued function defined on an interval, then the range of $f$ had better be an interval too. That's because if there were a gap in the range then $f$ would have to have some kind of jump, which means a discontinutiy. 

\begin{theorem}
  If $f$ is continuous and $A$ is connected then $f(A)$ is connected.
\end{theorem}

\begin{proof}
  Let us prove the contrapositive, that if $f(A)$ is disconnected then $A$ is disconnected. So suppose that there exist disjoint open sets $V,V'$ both meeting $f(A)$ and such that $f(A)\subset V\cup V'$. Observe that the inverse image mapping $f^{-1}$ preserves open sets, disjointness, and unions. It follows that $f^{-1}(V),f^{-1}(V')$ are disjoint open sets, both meeting $A$, and such that $A\subset f^{-1}(V)\cup f^{-1}(V')$. This means that $A$ is disconnected, as desired.
\end{proof}

Once again, this simple preservation property has an important consequence in calculus.

\begin{corollary}[Intermediate Value Theorem]
  If $A$ is connected and $f\colon A\to\R$ is continuous, then $f(a)<L<f(b)$ implies there exists $c\in A$ such that $f(c)=L$.
\end{corollary}

\begin{proof}
  By the previous theorem we have that $f(A)$ is connected. We have shown that connected subsets of $\R$ are intervals, so $f(A)$ is an interval. Recall our characterization that $I$ is an interval iff $x,y\in I$ and $x<z<y$ implies $z\in I$. We currently have $f(a),f(b)\in f(A)$ and $f(a)<L<f(b)$. Thus $L\in f(A)$, which means there exists $c\in A$ such that $f(c)=L$.
\end{proof}

The intermediate value theorem has many practical consequences, just one of which is the following.

\begin{corollary}
  If $f\colon[0,1]\to[0,1]$ is a continuous function, then $f$ has a fixed point (a point where $f(c)=c$).
\end{corollary}

\begin{proof}
  Consider the function $g(x)=x-f(x)$; we are looking for some point $c$ such that $g(c)=0$. If either $g(0)$ or $g(1)=0$ then we would be done. Otherwise, we clearly have that $g(0)<0<g(1)$. By the intermediate value theorem it follows that there exists $c$ such that $g(c)=0$, as desired.
\end{proof}

\newpage
\subsection*{Activity for \S \thesection}

\begin{activity}
  \item Give an example of each of the following, or argue that no such example exists.
  \begin{enumerate}\itemsep\fill
    \item A continuous function $f$ and a compact set $K$ such that $f^{-1}(K)$ is not compact.
    \item A continuous function $f$ and a connected set $C$ such that $f^{-1}(C)$ is disconnected.
    \item A continuous function $f$, whose domain is a bounded interval, and a set $A$ such that $f(A)$ is not bounded.
    \item A continuous function $f$, whose domain is all of $\R$, and a bounded set $A$ such that $f(A)$ is not bounded.
    \item a continuous function $f$ and a bounded set $B$ such that $f^{-1}(B)$ is not bounded.
    % \item A continuous function $f$ on the interval $(0,1)$ and a convergent sequence $x_n\in(0,1)$ with limit in $(0,1)$ such that $f(x_n)$ is not a convergent sequence.
    % \item A continuous function $f$ on the interval $(0,1)$ and a Cauchy sequence $x_n\in(0,1)$ such that $f(x_n)$ is not a Cauchy sequence.
    % \item A continuous function $f$ on the interval $[0,1]$ and a Cauchy sequence $x_n\in[0,1]$ such that $f(x_n)$ is not a Cauchy sequence.
    % \item A continuous function $f$ on the interval $[1,\infty)$ and a Cauchy sequence $x_n\in[1,\infty)$ such that $f(x_n)$ is not a Cauchy sequence.
    % \item A continuous and bounded function $f$ on the interval $(0,1)$ that attains a maximum value on this interval but not a minimum value.
    \vspace\fill
  \end{enumerate}
\end{activity}
  
%\question Suppose that $f$ is continuous on $[a,b]$ and that for every $n\in\N$ there exists $x\in[a,b]$ such that $\abs{f(x)}\leq\frac1n$. Show that there exists $x\in[a,b]$ such that $f(x)=0$.

% \begin{exerc}[Abbott, ex 4.4.4(a)]
%   Suppose that $f$ is continuous on the interval $[a,b]$ and that $f(x)>0$ for all $x\in[a,b]$.  Show that the reciprocal function $1/f$ is bounded on $[a,b]$.
% \end{exerc}
%
% \begin{exerc}
%   Show that the equation $2^x+3^x=4^x$ has a positive solution, using the intermediate value theorem on an appropriate interval. (You may assume exponential functions are continuous.)
% \end{exerc}
%
% \begin{exerc}
%   A function $f$ is said to be monotone if either it is increasing ($x<x'\Rightarrow f(x)\leq f(x')$) or else it is decreasing ($x<x'\Rightarrow f(x)\geq f(x')$).
%
%   Suppose that $f(x)$ is continuous and one-to-one on the interval $[a,b]$. Show that $f$ is monotone.
% \end{exerc}

% sphere temperature thing

% ham sandwich thing

\begin{readnext}
  Abbott, \S 5.2
\end{readnext}

\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Continuity and derivatives}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{reading}
  Abbott, \S 5.2
\end{reading}

The derivative is one of the most important developments of modern mathematics because it captures the intuitive notion of instantaneous rate of change. As simple as a ``rate of change'' may seem, one must be careful with the ``instantaneous'' part since it isn't always well defined. Our study of continuous functions and limits leaves us prepared to explore the concept rigorously.

\begin{definition}
If $f$ is a real-valued function defined on an interval and $x$ is in the domain of $f$, then $f$ is said to be \emph{differentiable} at $x$ if the limit exists:
\[\lim_{h\to0}\frac{f(x+h)-f(x)}{h}
\]
In this case the value of the limit is called the \emph{derivative} of $f$ at $x$ and denoted $f'(x)$.
\end{definition}

As one often observes in a calculus class, the derivative is a limit of slopes between $(x,f(x))$ and nearby points $(x+h,f(x+h))$. This means that $f'(x)$ represents the slope of the line tangent to $f$ at $x$. If a function is differentiable on its domain, we sometimes say that it is ``locally linear''.

\begin{example}
  The function $f(x)=x^2$ is differentiable at every point and we can use the functional limit calculus to find $f'(x)$ as follows:
  \[f'(x)=\lim_{h\to0}\frac{(x+h)^2-x^2}{h}
  =\lim_{h\to0}\frac{x^2+2xh+h^2-x^2}{h}=\lim_{h\to0}2x+h=2x
  \]
\end{example}

\begin{example}
  Any function with a corner or pointy cusp is not differentiable at that point. For example $f(x)=|x|$ is not differentiable at $x=0$ because $\lim_{h\to0}|h|/h$ does not exist.
\end{example}

The primary development of differential calculus now proceeds in two pieces. First, one uses the definition of the derivative to calculate a library of \emph{formulas} for the derivatives of common functions. Second, one uses the definition of the derivative to prove the algebraic \emph{laws} of the derivative operation itself.

\begin{theorem}[Derivative formulas]\
  \begin{itemize}
    \item The derivative of $x^\alpha$ is $\alpha x^{\alpha-1}$
    \item The derivative of $e^x$ is $e^x$
    \item The derivative of $\ln(x)$ is $1/x$
    \item The derivative of $\sin(x)$ is $\cos(x)$
    \item The derivative of $\cos(x)$ is $-\sin(x)$
  \end{itemize}
\end{theorem}

\begin{theorem}[Derivative calculus]
  Asusme $f,g$ are differentiable functions with appropriate domains. Then we have:
  \begin{itemize}
    \item $(f+g)'=f'+g'$
    \item $(kf)'=kf'$
    \item $(fg)'=f'g+fg'$
    \item $(f/g)'=(f'g-g'f)/g^2$
    \item chain rule: $(g\circ f)'=(g'\circ f)f'$
    \item inverse rule: $(f^{-1})'=1/(f'\circ f^{-1})$ if $f$ is invertible
  \end{itemize}
\end{theorem}

We leave the proofs of these theorems to your old calculus textbook.

In the rest of the section, we investigate the subtle relationship between continuity and differentiability. Our first result in this direction implies that differentiability is stronger than continuity. Phrased another way, any function which is discontinuous will also be non-differentiable.

\begin{proposition}
  If $f$ is differentiable at a point $a$ then $f$ is continuous at $a$.
\end{proposition}

\begin{proof}
  We begin by calculating:
  \[\lim_{h\to 0}(f(a+h)-f(a))=\lim_{h\to 0}\frac{(f(a+h)-f(a))h}{h}
    =f'(a)\lim_{h\to 0}h=0\text{.}
  \]
  Substituting $x=a+h$ into this limit, we have $\lim_{x\to a}(f(x)-f(a))=0$. This implies $\lim_{x\to a}f(x)=f(a)$, which means by definition that $f$ is continuous at $a$.
\end{proof}

Now we know that every differentiable function is continuous, but not every continuous function is differentiable. It is natural to ask whether $f$ being differentiable implies $f'$ is differentiable too. It turns out that the answer is ``no'', and in fact $f'$ doesen't even have to be continuous.

\begin{example}
  Let $f(x)=x^2\sin(1/x)$ and $f(0)=0$. The function is clearly differentiable at any point $x\neq0$, and it is actually differentiable at $x=0$ too. To see this, observe that
\[f'(0)=\lim_{h\to0}\frac{h^2\sin(1/h)-0}{h}=\lim_{h\to0}h\sin(1/h)
\]
Since $\sin(1/h)$ is bounded and $h\to 0$, it follows that $f'(0)=0$.

Next, the derivative of $f$ is $f'(x)=2x\sin(1/x)-\sin(1/x)$ and $f'(0)=0$. It is easy to see that the first term $x\sin(1/x)$ is continuous, but the second term $\sin(1/x)$ is not continuous at $x=0$. It follows that $f'(x)$ is not continuous at $x=0$.
\end{example}
% don't think we still have this homework problem about sin(1/x)

In fact there is a whole ``hierarchy of differentiability''. We say that a function $f$ is in the class $C^0$ if $f$ is continuous, in the class $C^1$ if $f$ is differentiable $f'$ is continuous, in the class $C^2$ if $f'$ is differentiable and $f''$ is continuous, and so forth. We say that $f$ is in the class $C^\infty$ or \emph{smooth} if it is differentiable infinitely many times. Functions such as polynomials and $\sin(x)$ are all smooth. But the function $x^n\sin(1/x)$ lies in the class $C^{n-2}$.

Recall that we have already seen that continuous functions and compact sets are important in optimization because of the Extreme Value Theorem. You surely recall that derivatives are also important in optimization, and that is due to the following result.

\begin{lemma}[Interior Extremum Theorem, or, Critical Point Lemma]
  \label{thm:iet}
  If $f$ is differentiable on the interval $(a,b)$ and $f$ attains a maximum or minimum value at $c\in(a,b)$, then $f'(c)=0$.
\end{lemma}

\begin{proof}
  Let us treat the case when $f$ attains a maximum value at $c$. Then for any $h$ we have $f(c+h)-f(c)\leq0$. It follows that for $h>0$ we have $(f(c+h)-f(c))/h\leq0$, which implies that $f'(c)\leq0$. Similarly for $h<0$ we have $(f(c+h)-f(c))/h\geq0$, which implies that $f'(c)\geq0$. This leaves only the possibility that $f'(c)=0$.
\end{proof}

To conclude the section, we revisit the example of the differentiable function $f(x)=x^2\sin(x)$ with a discontinuous derivative. It didn't have a simple jump discontinuity, but something much uglier. In our final result of the section, we will show that this ugliness can't be avoided. The reason is that derivatives have to satisfy the \emph{conclusion} of the IVT, so while they don't have to be continuous, their discontinuities cannot be simple jumps.

\begin{theorem}[Darboux's Theorem, or, IVT for derivatives]
  If $f$ is differentiable on $[a,b]$ and $f'(a)<L<f'(b)$, then there exists $c\in(a,b)$ such that $f'(c)=L$.
\end{theorem}

\begin{proof}
  We may assume without loss of generality that $L=0$. Since $[a,b]$ is compact, the Extreme Value Thorem implies that $f$ attains its minimum value at some point $c\in[a,b]$. We claim that $c$ is not equal to $a$ or $b$. Admitting the claim for the moment, this implies $f$ attains its minimum at a point $c\in(a,b)$. Thus the Interior Extremum Theorem implies that $f'(c)=0$, as desired.

  To see that $f$ doesn't attain its minimum value at $a$ or $b$, first note that since $f'(a)<0$ we have $\lim_{h\to0}(f(a+h)-f(a))/h<0$. It follows that there exists $h>0$ such that $f(a+h)<f(a)$, that is, $f$ cannot attain its minimum value at $a$. Similarly since $f'(b)>0$ we have $\lim_{h\to0}(f(b+h)-f(b))/h>0$. It follows that there exists $h<0$ such that $f(b+h)<f(b)$, so once eagain $f$ cannot attain its minimum value at $b$ either.
\end{proof}

\newpage
\subsection*{Activity for \S \thesection}

\begin{activity}
  \item Find the derivative of each function directly from the definition.
  \begin{enumerate}
    \item $\displaystyle f(x)=x^3$
    \vspace\fill
    \item $\displaystyle f(x)=1/x$
    \vspace\fill
    \item $\displaystyle f(x)=\frac{1}{\sqrt{x}}$
    \vspace\fill
  \end{enumerate}
  \item Decide, with justification, whether each of the following functions is differentiable at $x=0$.
  \begin{enumerate}
    \item $\displaystyle f(x)=x+|x|$
    \vspace\fill
    \item $\displaystyle f(x)=x\,|x|$
    \vspace\fill
    % \item $\displaystyle f(x)=|\sin(x)|$
    % \vspace\fill
  \end{enumerate}
\end{activity}
  
% \begin{exerc}[Abbott, ex 5.2.3]
%   \begin{enumerate}
%     \item Use the definition of derivative to find the derivative of $f(x)=1/x$.
%     \item Give a proof of the quotient rule using part (a) together with the product and chain rules.
%   \end{enumerate}
% \end{exerc}

% \begin{exerc}
%   Prove \emph{Rolle's thoerem}, which states that if $f$ is a differential function, $a<c$, and $f(a)=f(b)$, then there exists $c$ such that $a<c<b$ and $f'(c)=0$.
% \end{exerc}

% \begin{exerc}[Abbott, ex 5.2.5]
%   Let $f(x)$ be the function:
%   \[f(x)=\begin{cases}x^a&x\geq0\\0&x<0\end{cases}\]
%   \begin{enumerate}
%     \item For which values of $a$ is $f$ continuous at $0$?
%     \item For which values of $a$ is $f'(0)$ defined?
%     \item For which values of $a$ is $f''(0)$ defined?
%   \end{enumerate}
% \end{exerc}

\begin{readnext}
  Abbott, \S 7.2, 7.4
\end{readnext}

\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Continuity and integrals}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{reading}
  Abbott, \S 7.2, 7.4
\end{reading}

Along with the derivative, the integral is one of the highlights of modern mathematics because it helps capture the concept of area. Just as the idea of ``slope of a function'' is intuitively simple but required rigorous definition, the idea of ``area under a curve'' is easy to visualize but must be defined carefully. Once again, our knowledge of functions, infemums, and supremums leaves us prepared to define and explore integrals.

\begin{definition}
  Let $f$ be a bounded function defined on an interval $[a,b]$. Given a finite sequence $P$ of endpoints $a=x_0<x_1<\cdots<x_n=b$, we let $m_i=\inf f([x_{i-1},x_i])$ and $M_i=\sup f([x_{i-1},x_i])$, and:
  \begin{align*}
    L(f,P)&=\sum_{i=1}^n m_i(x_i-x_{i-1})\\
    U(f,P)&=\sum_{i=1}^n M_i(x_i-x_{i-1})
  \end{align*}
  We then define the \emph{lower integral} of $f$ as $L(f)=\sup_P\{L(f,P)\}$ and the \emph{upper integral} of $f$ as $U(f)=\inf_P\{U(f,P)\}$. One can verify that we always have $L(f)\leq U(f)$. If in fact $L(f)=U(f)$, then we say $f$ is \emph{integrable} and write
  \[\int_a^bf\,dx=\text{the common value of }L(f)\text{ and }U(f)
  \]
\end{definition}

\begin{example}
  The function $f(x)=x^2$ on the interval $[0,b]$ is integrable. To see why, given any $n$ we define the regularly-spaced partition $P_n$ by $x_i=bi/n$. Since $f$ is a monotone increasing function, maximum values occur at right endpoints, which means we always have $M_i=(bi/n)^2$. Now we can calculate:
  \begin{align*}
    U(f,P_n)&=\sum_{i=1}^n\left(\frac{bi}{n}\right)^2\left(\frac{b}{n}\right)\\
    &=\frac{b^3}{n^3}\sum_{i=1}^n i^2\\
    &=\frac{b^3}{n^3}\frac{n(n+1)(2n+1)}{6}
  \end{align*}
  Here we are using a classic formula for the sum of the first $n$ squares. It is easy to calculate that $\lim U(f,P_n)=b^3/3$, and since $U(f)$ is the infemum over all possible $U(f,P)$, we conclude that $U(f)\leq b^3/3$.
  
  Similarly the minimum falues occur at left endpoints, which means we always have $m_i=(b(i-1)/n)^2$. We thus obtain:
  \begin{equation}
    L(f,P_n)=\frac{b^3}{n^3}\frac{(n-1)n(2n-1)}{6}
  \end{equation}
  Using the same logic as above, it follows that $L(f)\geq b^3/3$, and we conclude from these inequalities that $\int_0^bf\,dx$ exists and equals $b^3/3$.
\end{example}

\begin{example}
  Let $f$ be the Dirichlet function on $[0,1]$, which is defined by
  \[f(x)=\begin{cases}1&x\in[0,1]\cap\Q\\0&x\in[0,1]\setminus\Q\end{cases}
  \]
  Then $f$ is not integrable. In fact using rational and irrational density, for any $P$ we have $L(f,P)=0$ and $U(f,P)=1$.
\end{example}

As was the case with limits and derivatives, the integral operation obeys some useful laws.

\begin{theorem}[Integral calculus]
  Assume $f,g$ are integrable functions on $[a,b]$.
  \begin{enumerate}
    \item $\int_a^b(f(x)+g(x))\,dx=\int_a^bf(x)\,dx+\int_a^bg(x)\,dx$
    \item $\int_a^bkf(x)\,dx=k\int_a^bf(x)\,dx$
    \item If $f\leq g$ then $\int_a^bf(x)\,dx\leq\int_a^bg(x)\,dx$
    \item If $a<c<b$ then $\int_a^cf(x)\,dx+\int_c^bf(x)\,dx=\int_a^bf(x)\,dx$
  \end{enumerate}
\end{theorem}

\begin{proof}
  As these results are standard facts of calculus, we prove only (c). For this let $h(x)=g(x)-f(x)$, so that we have $h\geq0$. Now using parts~(a) and~(b), $h$ is integrable and our desired conclusion is equivalent to $\int_a^bh(x)\,dx\geq0$. Since $h\geq0$ we have that for any $P$, all values of $m_i\geq0$ and thus $L(f,p)\geq0$. It follows that $L(f)\geq0$ too, and hence that $\int_a^bh(x)\,dx\geq0$.
\end{proof}

We note that in calculations it is sometimes useful to define $\int_a^a f=0$, and if $a<b$ we define $\int_b^a f=-\int_a^b f$.

We close this section by establishing the first link between continuity and integration. We show that any continuous function is integrable. Since we have seen that every differentiable function is continuous and not every continuous function is differentiable, we can conclude that the integral operation is properly \emph{more general} than the derivative operation!

\begin{theorem}
  If $f$ is a continuous function on $[a,b]$ then $f$ is integrable. If $f$ has finitely many discontinuities on $[a,b]$ then $f$ is integrable.
\end{theorem}

\begin{proof}
  We will use Abbott, Theorem~4.4.7 as a black box. It states that if $f$ is a continuous function on a compact domain, then it satisfies the following strong form of continuity:
  \[(\forall\epsilon>0)(\exists\delta>0)(\forall x,y)\;
  |x-y|<\delta\implies|f(x)-f(y)|<\epsilon
  \]
  (The difference is only that $\delta$ does not depend on $x$.) Now given any $\epsilon>0$, we create a partition $P$ such that $x_i-x_{i-1}<\delta$ for all $i$. This implies that for all $i$, we have $M_i-m_i\leq\epsilon$. Thus
  \[U(f,P)-L(f,P)=\sum_{i=1}^n(M_i-m_i)(x_i-x_{i-1})\leq\sum_{i=1}^n\epsilon(x_i-x_{i-1})
  =\epsilon(b-a)
  \]
  Since $\epsilon$ was arbitrary, we conclude that $U(f,P)-L(f,P)=0$.
  
  The second statement follows from this together with law~(d).
\end{proof}

\newpage
\subsection*{Activity for \S \thesection}

\begin{activity}
  \item Use the definition of integral to calculate the value of the integral:
  \[\int_0^bx^3\,dx
  \]
  Hint: You will need the sum of cubes formula:
  \[\sum_1^ni^3=\frac{n^2(n+1)^2}{4}
  \]
  \vspace\fill
\end{activity}

% \begin{exerc}[See Abbott, ex 7.2.2]
%   Consider the function $f(x)=1/x$ on the interval $[1,4]$. Find a partition $P$ such that $U(f,P)$ and $L(f,P)$ are less than $0.3$ units apart.
% \end{exerc}

% \begin{exerc}[Abbott, ex 7.3.1]
%   Let $h(x)$ be the function on $[0,1]$ defined by
%   \[h(x)\begin{cases}1&x<1\\2&x=1\end{cases}
%   \]
%   \begin{enumerate}
%     \item For any $P$, what is the value of $L(f,P)$?
%     \item Can you find a $P$ such that $U(f,P)$ is within $1/10$ of $L(f,P)$?
%     \item Show that $h$ is integrable.
%   \end{enumerate}
% \end{exerc}

\begin{readnext}
  Abbott, \S 7.5
\end{readnext}

\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Derivatives and integrals}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{reading}
  Abbott, \S 7.5
\end{reading}

We have introduced derivatives as slopes or rates of change, and integrals as areas or accumulations. How are the two concepts related? Since we have already calculated that $\int_0^b x^2\,dx=b^3/3$ and $\int_0^b x^3\,dx=b^4/4$, it is not difficult to guess that the integral of a function is related to its \emph{antiderivative}. Intuitively, it is also not hard to accept that the rate of change of an accumulation of some quantity should at least be related to the size of the original quantity. This is all confirmed in surprisingly great generality by the Fundamental Theorem of Calculus, which says in brief that derivatives and integrals are inverse operations.

Before stating and proving the FTC, we need to visit the Mean Value Theorem, a cornerstone result about derivatives that is closely related to the FTC.

\begin{theorem}[Mean Value Theorem]
  Let $f$ be differentiable on $[a,b]$. Then there exists $c\in[a,b]$ such that
  \[\frac{f(b)-f(a)}{b-a}=f'(c)
  \]
\end{theorem}

\begin{proof}
  We can add a linear term to $f$ to assume without loss of generality that $f(a)=f(b)$. (Note that passing from $f(x)$ to $f(x)+mx+b$ has the effect of adding an $m$ to both sides of the desired equation.) This reduces the statement to Rolle's theorem, which uses the Extreme Value Thoerem together with the Interior Extremum Theorem to conclude that there must exist $c\in[a,b]$ such that $f'(c)=0$.
\end{proof}

The MVT says that the ``average rate of change'' of a function over an interval is equal to the instantaneous rate of change at some point in the interval. On the other hand, the conclusion of the MVT can also be written as follows:
\[f(b)-f(a)=f'(c)(b-a)
\]
This version foreshadows the FTC because the left side involves a change in $f$, and the right side involves a derivative times a change in $x$.

The MVT has a number of important applications. For example, it can be used to show that antiderivatives are unique up to an additive constant.

\begin{corollary}
  Suppose that $f'(x)=g'(x)$. Then $f-g$ is a constant function.
\end{corollary}

\begin{proof}
  Let $h=f-g$ and suppose $h$ is not a constant function. Then there exist $a,b$ in the domain of $h$ such that $(h(b)-h(a))/(b-a)\neq0$. It follows from the MVT that there exists $c$ such that $h'(c)\neq0$. Thus $f'(c)\neq g'(c)$, contradicting our hypothesis.
\end{proof}

We are now ready to dive into the FTC, which we recall says that derivatives and integrals are inverse operations. This is actually two separate statements: the integral of a derivative is (related to) the original function, and the derivative of an integral is the original function. We begin with the first version, sometimes called the net change theorem.

\begin{theorem}[FTC, net change theorem]
  Let $f$ be differentiable on $[a,b]$ and $f'$ be integrable on $[a,b]$. Then
  \[f(b)-f(a)=\int_a^b f'(x)\,dx
  \]
\end{theorem}

\begin{proof}
  Let $P$ be a partition of $[a,b]$ consisting of endpoints $0=x_0<x_1<\cdots<x_n=b$. Then for each $i$, the MVT gives us $c_i\in[x_{i-1},x_i]$ such that
  \[f(x_i)-f(x_{i-1})=f'(c_i)(x_i-x_{i-1})
  \]
  Summing both sides over $i\leq n$, the left-hand side telescopes and becomes $f(b)-f(a)$. Therefore we have
  \[f(b)-f(a)=\sum_{i=1}^n f'(c_i)(x_i-x_{i-1})
  \]
  Since we clearly have $m_i\leq f'(c_i)\leq M_i$, we obtain
  \[L(f',P)\leq f(b)-f(a)\leq U(f',P)
  \]
  Since the partition $P$ was arbitrary, we conclude that $L(f')\leq f(b)-f(a)\leq U(f')$. Since we are assuming $L(f')=U(f')=\int_a^bf'(x)\,dx$, we have $f(b)-f(a)=\int_a^bf'(x)\,dx$ as desired.
\end{proof}

Dividing both sides of the net change theorem by $b-a$, we obtain a statement which says that the ``average rate of change'' of a function over an interval is equal to the average of its instantaneous rates of change over the interval.
\[\frac{f(b)-f(a)}{b-a}=\frac{1}{b-a}\int_a^b f'(x)\,dx
\]

We now continue with the second part of the FTC. First, given any integrable function $f$ we define its \emph{accumulation function} (or \emph{area function}) as $\int_0^xf(t)\,dt$. The second part of the FTC concerns the derivative of the accumulation function. To understand the statement intuitively, imagine extending a $0.5\times x$ rectangle in the $x$ direction. The area grows at a rate of $0.5$. In a similar way, if we extend the region under $f$ in the $x$ direction the area should grow at a rate of $f(x)$. Said another way, the derivative of the accumulation of $f$ is $f$, or, the accumulation of $f$ is an antiderivative of $f$.

\begin{theorem}[FTC, accumulation-is-antiderivative theorem]
  Let $f(x)$ be a continuous function and let $F(x)=\int_a^x f(t)\,dt$. Then $F$ is differentiable, and
  \[F'(x)=f(x)
  \]
\end{theorem}

\begin{proof}
  Substituting the definition of $F$ into the difference quotient for $F$, we have:
  \[F'(x)=\lim_{h\to0}\frac{1}{h}\int_x^{x+h} f(t)\,dt
  \]
  By the continuity of $f$, given $\epsilon>0$ we can find $\delta>0$ such that $|t-x|<\delta$ implies $|f(t)-f(x)|<\epsilon$. Letting $h<\delta$, it follows that
  \[h(f(x)-\epsilon)\leq\int_x^{x+h} f(t)\,dt\leq h(f(x)+\epsilon)
  \]
  Dividing all sides by $h$ and taking the limit, we have:
  \[f(x)-\epsilon\leq F'(x)\leq f(x)+\epsilon
  \]
  Since $\epsilon$ was arbitrary, we conclude that $F'(x)=f(x)$.
\end{proof}

Recall that when we introduced the derivative calculus we had both formulas for specific derivatives as well as laws for the derivative operation. On the other hand for the integral calculus we have only introduced laws, which means we have yet to deliver the formulas. The accumulation-is-antiderivative theorem implies that every derivative formula can be reversed to give an integral formula, and therefore completes our basic picture of calculus.

\begin{theorem}[Integral calculus formulas]
  For each function $f(x)$, we have $\int_a^bf(t)\,dt=F(b)-F(a)$ where $F$ is the function shown.
  \begin{enumerate}
    \item If $f(x)=x^\alpha$ then $F(x)=\frac{1}{\alpha+1}x^{\alpha+1}+C$, for $\alpha\neq-1$
    \item If $f(x)=e^x$ then $F(x)=e^x+C$
    \item If $f(x)=1/x$ then $F(x)=\ln(x)+C$
    \item If $f(x)=\sin(x)$ then $F(x)=-\cos(x)+C$
    \item If $f(x)=\cos(x)$ then $F(x)=sin(x)+C$
  \end{enumerate}
\end{theorem}

\newpage
\subsection*{Activity for \S \thesection}

\begin{activity}
  \item Find the derivative of the function:
  \begin{enumerate}
    \item $F(x)=\int_0^x \cos(3t)\,dt$\vspace\fill
    \item $F(x)=\int_0^{\ln(x)}\cos(3t)\,dt$\vspace\fill
    \item $F(x)=\int_0^x \cos(t^2)\,dt$\vspace\fill
    \item $F(x)=\int_0^{\ln(x)} \cos(t^2)\,dt$\vspace\fill
  \end{enumerate}
  \item Suppose you know $f(2)=5$ and $-.5\leq f'(x)\leq.5$ for all $x$. What is the biggest $f(10)$ can be? What is the smallest? How do you prove it?
  \vspace\fill
\end{activity}

\begin{readnext}
  That's it!
\end{readnext}


\iffalse
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\chapter{Additional material}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Wild functions}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

So far in this course we have investigated real numbers and their arithmetic, and sets of real numbers. In this part we will study functions, especially those that arise naturally in models and applications.

Many of the most important functions in terms of theory, models, and applications turn out to be continuous. For example if you go for a jog, the distance you have traveled varies continuously over time. Moreover many common expressions such as $x^2$, $\ln(x)$, or $3\sin(x)-2e^x$ define continuous functions. However it is important to note that not all natural functions are continuous. For example the charge for a phone call does not vary continuous over time, but rather jumps at each minute.

What exactly is a continuous function? We often say intuitively that a continuous function has no breaks in its graph. But what does this mean in terms of formal definitions? A simple example of a discontinuous function is one with a jump:
\begin{center}
\begin{tikzpicture}[domain=0:4]
\draw (-0.2,0) -- (4.2,0);
\draw (0,-0.2) -- (0,2.2);
\draw plot (\x,{1+sin(\x r)});
\draw[fill=white] (3,{1+sin(3r)}) circle (.07);
\draw[fill=black] (3,{1.5+sin(3r)}) circle (.07);
\draw (3,.05)--(3,-.05);
\node[below] at (3,0) {$a$};
\end{tikzpicture}
\end{center}
What makes this function discontinuous is that the value $f(a)$ is nowhere near the values of $f(x)$ for $x$ very near to $a$.

At this point one may guess that the concept of a limit should be useful here. In fact, roughly speaking, we will define that $f$ is continuous at $a$ if whenever the values of $x$ approach $a$, the values of $f(x)$ approach $f(a)$:
\[f(a)=\lim_{x\to a}f(x)
\]
Unfortunately, in the past we have only worked with limits as the integer value $n$ approaches $\infty$, never as a continuous variable $x$ approaches $a$. In the rest of this section we will begin to explore what should be meant by this limit expression.

To reduce the question to one of sequential limits, one might replace the continuous variable $x$ by a sequence $x_n$ converging to $a$. For example, if $f(x)=x^3+5x+2$ then we can compute $\lim_{x\to0}f(x)$ as follows. First replace $x$ with the sequence $1/n$, since this has limit $0$. Next note that $\lim f(x_n)=\lim \frac{1}{n^3}+5\frac{1}{n}+2=2$.

On problem with this approach is the possibility that the function doesn't just have a jump iscontinuity, but actually has a break.
\begin{center}
\begin{tikzpicture}
\draw (-0.2,0) -- (4.2,0);
\draw (0,-0.2) -- (0,2.2);
\draw[domain=0:3] plot (\x,{1+sin(\x r)});
\draw[domain=3:4] plot (\x,{1.5+sin(\x r)});
\draw[fill=white] (3,{1+sin(3r)}) circle (.07);
\draw[fill=black] (3,{1.5+sin(3r)}) circle (.07);
\draw (3,.05)--(3,-.05);
\node[below] at (3,0) {$a$};
\end{tikzpicture}
\end{center}
When we used the sequence $1/n$ we only considered values of $x$ to the right of $a$, and none to the left. Thus this method would mistakenly conclude that the function depicted above is continuous.

For example, if $f$ is the function
\[f(x)=\begin{cases}x-1&x\leq0\\x+1&x>0\end{cases}
\]
then $\lim f(1/n)=1$, while $\lim f(-1/n)=-1$. Since we cannot say that either value has a greater claim to being the true limit, we correctly conclude that $\lim_{x\to0}f(x)$ does not exist.

At this point one may be tempted to define $\lim_{x\to a}f(x)$ as the value of $\lim f(a+1/n)$ and $\lim f(a-1/n)$ provided these values exist and agree. However, this would again be mistaken! To see this consider the \emph{Dirichlet function} defined by
\[f(x)=\begin{cases}1&x\in\Q\\0&x\notin\Q\end{cases}
\]
This function is so ugly that our definitions should definitely imply it is discontinuous. In fact our definitions should imply that none of its functional limits exist. But since we have $\lim f(1/n)=\lim f(-1/n)=1$, the above method would incorrectly conclude that $\lim_{x\to0}f(x)=1$. It is thanks to this strange example that we settle on the following very strong definition.

\begin{definition}
  We say that $\lim_{x\to a}f(x)=L$ if for every sequence $x_n$ such that $x_n\to a$ and $x_n\neq a$, we have $\lim f(x_n)=f(a)$.
\end{definition}

For example, if $f(x)=x^2$, then we can calculate $\lim_{x\to2}f(x)$ as follows. Let $x_n$ be an arbitrary sequence such that $x_n\to2$. Then $\lim f(x_n)=\lim(x_n)^2=(\lim x_n)^2=2^2=4$. Since $x_n$ was arbitrary, we can conclude that the functional limit $\lim_{x\to2}f(x)=4$ too.

\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Baire's theorem and sets of discontinuity}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Baire's theorem, also called Baire's category theorem, is one of the most important results of analysis and topology This theorem is not hard to prove, in fact the proof is essentially the same as our first proof of the NIP. But the theorem has a profound impact on the development of analysis. In this section and the next we will elaborate on just two consequences of the theorem.

Before stating the theorem, recall that a subset $A$ of a metric space is called \emph{dense} if $A$ meets every open subset of $X$.

\begin{theorem}[Baire's theorem]
  If $X$ is a complete metric space then the following hold:
  \begin{enumerate}
  \item The intersection of countably many dense open subsets of $X$ is nonempty.
  \item The union of countably many closed sets with empty interior is not all of $X$.
  \end{enumerate}
\end{theorem}

\begin{proof}
  We will prove the first statement, since the second follows by taking complements. Given a sequence $O_n$ dense open sets we will inductively construct a nested sequence of neighborhoods $N_{\epsilon_n}(x_n)$ such that $N_{\epsilon_n}(x_n)\subset O_n$. To begin choose $N_{\epsilon_1}(x_1)\subset O_1$ arbitrarily. Assuming $N_{\epsilon_n}(x_n)$ has been constructed, since $O_n$ is dense open we haev that $N_{\epsilon_n}(x_n)\cap O_{n+1}$ is a nonempty open set. Hence we can find a neighborhood $N_{\epsilon_{n+1}}(x_{n+1})\subset N_{\epsilon_n}(x_n)\cap O_{n+1}$.

  By choosing the $\epsilon_n$ small enough in the above construction, we can ensure that $\epsilon_n\to0$ and that $\overline{N_{\epsilon_{n+1}}(x_{n+1})}\subset N_{\epsilon_n}(x_n)$. It follows that the sequence $x_n$ is Cauchy, and since $X$ is complete, that $x_n$ converges to a limit $x$. Then this limit $x$ lies in every neighborhood $N_{\epsilon_n}(x_n)$ and hence in every set $O_n$, which implies that $\bigcap O_n\neq\emptyset$, as desired.
\end{proof}

Our first application of Baire's theorem will be to address the question: if $f$ is a discontinuous function, what does its set of discontinuities look like? Recall that we have seen examples of functions that are discontinuous at a single point, discontinuous at a few points, and discontinuous everywhere.

\begin{definition}
  If $f\colon\R\to\R$ then the \emph{set of discontinuities} of $f$ is the set $D_f=\set{x\in\R\mid\text{$f$ is discontinuous at $x$}}$.
\end{definition}

It is possible to produce examples of functions $f$ with interesting discontinuity sets $D_f$.

\begin{example}
  Let $f(x)=$ the greatest integer less than or equal to $x$ (the floor of $x$). Then the set $D_f$ is exactly $\mathbb Z$.
\end{example}

\begin{example}
  Let $f(x)=1/n$ if $x=m/n$ is a rational number and $m/n$ is its reduced representation. Let $f(x)=0$ if $x$ is irrational. This function $f$ is called Thomae's function, and it has the remarkable property that $D_f$ is exactly $\Q$. To see this, one should check that if $x$ is any number and $a_n/b_n$ is any nonconstant sequence of reduced rational numbers such that $a_n/b_n\to x$, then the sequence $1/b_n\to0$.
\end{example}

% play around with other sets: [0,1], (0,1), 1/n, 1/n\cup0, etc

The example of Thomae's function naturally leads to the question: If we can find a function $f$ such that $D_f$ is the set of rational numbers, can we also find a function $f$ such that $D_f$ is the set of irrational numbers? With all our ingenuity to create bizarre functions, it may surprise you that the answer is ``no''. To help us reach this conclusion, we need the following partial characterization of the sets $D_f$.

\begin{theorem}
  \label{thm:df-closed}
  If $f\colon\R\to\R$, then $D_f$ can be written as a union of countably many closed sets.
\end{theorem}

\begin{proof}
  Define a function $f$ to be \emph{$\epsilon$-continuous} at $a$ if there exists $\delta$ such that for all $x,y\in N_\delta(a)$ we have $|f(x)-f(y)|<\epsilon$. Accordingly, we let $D_{f,\epsilon}$ be the set of points $a$ such that $f$ is \emph{not} $\epsilon$-continuous at $a$. We make the following two claims:
  \begin{enumerate}
  \item $f$ is continuous at $a$ if and only if for all $\epsilon>0$, $f$ is $\epsilon$-continuous at $a$. Thus $D_f=\bigcup D_{f,\epsilon}$.
  \item Each set $D_{f,\epsilon}$ is closed.
  \end{enumerate}
  Admitting these for the moment, the result follows since then $D_f$ is the countable union of closed sets $D_f=\bigcup_nD_{f,1/n}$

  For claim (a), the backwards implication is immediate. For the forwards implication, suppose that $f$ is continuous at $a$. Then given $\epsilon>0$ we can find a $\delta>0$ such that $|x-a|<\delta$ implies $|f(x)-f(a)|<\epsilon/2$. Then if $x,y\in N_\epsilon(a)$ we have
  \[|f(x)-f(y)|\leq|f(x)-f(a)|+|f(a)-f(y)|<\epsilon/2+\epsilon/2=\epsilon
  \]
  as desired.

  For claim (b), we will show that if $a_n\in D_{f,\epsilon}$ and $a_n\to a$ then $a\in D_{f,\epsilon}$. Observe here that $a\in D_{f,\epsilon}$ means for all $\delta$ there exist $x,y\in N_\delta(a)$ such that $|f(x)-f(y)|<\epsilon$. Now let $\delta>0$ be given, and choose $n$ large enough that $|a_n-a|<\delta/2$. Since $a_n\in D_{f,\epsilon}$ we can find $x,y\in N_{\delta/2}(a_n)$ such that $|f(x)-f(y)|\geq\epsilon$. Then by our choice of $a_n$ we have that $N_{\delta/2}(a_n)\subset N_\delta(a)$. Thus $x,y$ also lie in $N_\delta(a)$, which implies that $a\in D_{f,\epsilon}$ too.
\end{proof}

\begin{remark}
  The converse to Theorem~\ref{thm:df-closed} is also true. If $A$ is an set which is a union of closed sets, then there exists a function $f$ such that $D_f$ is exactly equal to $A$.
\end{remark}
% exercise: do it for a closed set? ... uh how?

Now we are ready to give a negative answer to the question of whether there is a function $f$ such that $D_f$ is exactly the set of irrational numbers.

\begin{theorem}
  \label{thm:df-irrationals}
  The set of irrational numbers cannot be written as a countable union of closed sets. Hence there is no function $f$ such that $D_f=$ the set of irrational numbers.
\end{theorem}

\begin{proof}
  Suppose towards a contradiction that the set $\mathbb I$ of irrational numbers can be written as a union $\mathbb I=\bigcup F_n$, where each $F_n$ is closed. Since any open set contains rational numbers, it must be the case that each set $F_n$ has empty interior. Let $\Q=\mathbb{q_n}$ be an enumeration of the rational numbers. Then $\R=\bigcup F_n\cup\bigcup\{q_n\}$ is a union of a countable family of closed subsets with empty interior, contradicting Baire's theorem.
\end{proof}

\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Most functions are not differentiable}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

We have seen many examples of continuous functions which fail to be differentiable at one or more points. Our second application of Baire's theorem will be to answer the quesiton: how rare is it for a function to be differentiable? In order to proceed, we need a measure of size for subsets of the space $C[0,1]$ of continuous functions. Cardinality isn't useful here, since there are uncountably many differentiable functions and uncountably many non-differentiable functions. We have also discussed the notions of length and dimension for subsets of $\R^n$, but again these will not help here. In this section we introduce a notion of size which stems from Baire's theorem.

\begin{definition}
  A subset $A\subset X$ is said to be \emph{meager} if it is contained in a countable union of closed sets with empty interior.
\end{definition}

The Baire category can be rephrased to say that any complete metric space is comeager and not meager. A consequence is that the subsets of a complete metric space can be divided into three possible ``categories'':
\begin{itemize}
\item meager (small)
\item comeager (large)
\item neither meager nor comeager (intermediate)
\end{itemize}
For this reason, Baire's theorem is traditionally called the \emph{Baire category theorem}.
% exercise: check no set is meager and comeager, and there exist sets which are neither meager nor comeager

Recall that the space $C[0,1]$ of continuous functions is a complete metric space. Letting $D[0,1]\subset C[0,1]$ denote the subset of differentiable functions, it makes sense to ask which size $D$ has.

\begin{theorem}
  The set $D[0,1]$ of differentiable functions on $[0,1]$ is a meager subset of $C[0,1]$.
\end{theorem}

\begin{proof}
  To witness that $D[0,1]$ is meager, we will show it is the union of closed sets without interior:
  \[A_{M,\epsilon}=\set{f\in C[0,1]:\text{for some $x\in[0,1]$, for all $|h|<\epsilon$, we have }\left|\frac{f(x+h)-f(x)}{h}\right|\leq M}
  \]
  \ldots
\end{proof}
\fi

\end{document}