\documentclass[12pt]{article} \title{Math 521 -- Spring 2010} \author{521} \usepackage{amsthm,amsfonts,amsmath,amscd,amssymb,latexsym,epsfig} %\usepackage{endnotes} \usepackage{hyperref} %http://arxiv.org/hypertex/ \usepackage[all]{xy} %\usepackage{showkeys} \usepackage{makeidx} \makeindex % % \newcommand{\N}{\mathbb{N}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\R}{\mathbb{R}} \newcommand{\C}{\mathbb{C}} %\newcommand{\K}{\mathbf{K}} \newcommand{\eps}{\varepsilon} \newcommand{\p}{\partial} \newcommand{\ds}{\displaystyle} \newcommand{\id}{\mathrm{id}} %\newcommand{\nt}{\mathrm{int}} %\newcommand{\ext}{\mathrm{ext}} %\newcommand{\bdry}{\mathrm{bdry}} \newcommand{\note}[1]{#1} \newcommand{\jdef}[1]{{\bf #1\index{#1}}} \newtheorem{PARA}{}[section] \newtheorem{theorem}[PARA]{Theorem} \newtheorem{corollary}[PARA]{Corollary} \newtheorem{lemma}[PARA]{Lemma} \newtheorem{proposition}[PARA]{Proposition} \newtheorem{definition}[PARA]{Definition} \newtheorem{remark}[PARA]{Remark} \newtheorem{example}[PARA]{Example} \newtheorem{exercise}[PARA]{Exercise} \newtheorem{problem}[PARA]{Problem} % \newcommand{\para}{\begin{PARA}\rm} \newcommand{\arap}{\end{PARA}\rm} \newcommand{\dfn}{\begin{definition}\rm} \newcommand{\nfd}{\end{definition}\rm} \newcommand{\rmk}{\begin{remark}\rm} \newcommand{\kmr}{\end{remark}\rm} \newcommand{\xmpl}{\begin{example}\rm} \newcommand{\lpmx}{\end{example}\rm} \newcommand{\xrcs}{\begin{exercise}\rm} \newcommand{\scrx}{\end{exercise}\rm} \newcommand{\prob}{\begin{problem}\rm} \newcommand{\borp}{\end{problem}\rm} % \newcommand{\medskipnoindent}{\par\medskip\par\noindent} % \newcommand{\inner}[2]{\langle#1,#2\rangle} % \begin{document} \maketitle \tableofcontents \bigskip %\part{Preliminaries} \section{Pep Talk} \begin{quote}\em \hfill What does not kill me, makes me stronger. \hfill Friedrich Nietzsche (1844 - 1900) \hfill in The Twilight of the Idols (1899) \end{quote} It is generally acknowledged in the math department that the two hardest undergraduate courses we teach are~222 and~521. The former is hard because for many students it is their first college math course, and although they did well in high school, they are unprepared for what is expected in college. The latter is hard for many reasons. For many students it is the first course where they are expected to understand and write proofs. (See~\ref{proofs}.) There are a lot of hard words like `if', 'for all', 'there exists', (see Chapter~\ref{sec:logic}) and the order in which they appear is crucial (see~\ref{def:pointwise_and_uniform_contnuity}). Inequalities (see~\ref{ax:order}) play a crucial role. The language of set theory (see Chapter~\ref{sec:sets}) is used heavily and some students have a hard time visualizing what set is. On top of all this there is some strange lingo like 'connected', 'compact, 'open cover', etc. The first time you think you understand and discover that I disagree you may well decide that it is easier to get hit by a truck. The subject {\em is} hard. Calculus was invented by Leibniz and Newton in the seventeenth century, but the ideas presented in these notes were not fully developed until the early twentieth century. Some of the best mathematical minds in human history contributed to the subject. But you have one advantage over these luminaries: a teacher who understands the subject and wants to help you understand. Given the task before you, why should you make the effort? The above quote of Nietzsche may inspire you. The ability to reason carefully will serve you well in any future endeavor. You may be driven (like I am) to understand the patterns in mathematical reasoning. These patterns help us see the similarities between apparently different problems and enable us to use our understanding of one problem to solve the others. Finally, you may actually need to use the material someday. Many mathematical problems have no explicit solution: we must prove that there is a solution and use that proof both to guide us to an approximate solution and to estimate the accuracy of that solution. If we get to the end of these notes in this course you will get a glimpse of how this works when we solve the heat equation in problem~\ref{prob:HeatEquation}. Here are some tips: \begin{enumerate} \item Read. It is a bad idea to try to learn just from lectures. A really good lecturer can make the material look easy, but just listening is rarely enough to lead to true understanding. \item Focus on definitions. It is impossible to understand why a compact set is closed and bounded if you don't know what the words mean. Use the index and cross references in these notes or the text you are reading to recall definitions and previous theorems. If you are reading these notes on a computer and have a sufficiently recent version of Adobe Acrobat Reader or some other pdf viewer, you will notice that this document contains embedded hypertext links. Some viewers even allow text searches and links to URLs. (If you are online try clicking on the link to the official description below.) This makes the task of jumping around the text much easier. \item Be active not passive. As you read or listen, make up examples to test your understanding. When you see a definition make up an example of something which satisfies it and something which doesn't. \item Ask questions. If you can formulate a question when you are confused, you may discover that you become unconfused and don't need to ask the question. But don't hesitate to ask me questions in class or office hours. \item Be concise when you write. Excess verbiage is hard to follow and may conceal confusion. \item Don't fall behind. If you postpone understanding till the night before the exam, you may find that you are still lost. For each lecture there will be a short prequiz on \texttt{Moodle} (see below) designed to get you to read the material before I lecture on it. In addition there will be a short post quiz almost every day (I hope). \end{enumerate} We will use an online course management system called \texttt{Moodle}. To use it go to \url{https://www.math.wisc.edu/moodle} and click on Math~521. You will be prompted to authenticate. Use your net id and net password the same as if you were logging on the MyUW or WiscMail. If you are not enrolled in the course (according to the registrar) you will not be allowed in. \medskip The text references in these notes are to the following texts: \begin{description} \item[(Buck)] R.Creighton Buck, {\em Advanced Calculus}, 3rd edition, Waveland Press. \item[(Lang)] Serge Lang, {\em Undergraduate Analysis}, 2nd edition, Springer Undergraduate Texts in Mathematics. \item[(Morgan)] Frank Morgan, {\em Real Analysis}, American Mathematical Society \item[(Rudin)] Walter Rudin, {\em Principles of Mathematical Analysis}, McGraw Hill. \end{description} There are three sections of~521 this semester and each has chosen one of the first three. The instructor I am replacing chose Buck. I used this book the last time I taught~521. The terminology, content, even the title is are somewhat dated. (The math department will soon change the name of~521 from {\em Advanced Calculus} to {\em Real Analysis I}.) Lang is good but somewhat ponderous. It contains more material than can be comfortably treated in a two semester course. My favorite is from the first three is Morgan. It is student friendly and contains almost exactly the material I hope to cover. (See the official description of~521 at \url{http://www.math.wisc.edu/521-advanced-calculus}.) It is also the least expensive. The Rudin text is the best for someone who already thinks like a mathematician, but is difficult for the apprentice. I have arranged these notes so you can use them with any of these texts -- there are remarks and footnotes which explain slight differences in terminology -- but the notes are designed with the Morgan text in mind. Possibly you won't even need to buy a text: all three texts are on reserve in the Math Library. The prequizzes will only require you to read the course notes. \section{Notation} The following standard notations are used:\footnote{ Morgan uses $\N$ denote the positive integers while Lang uses $\N$ to denote the nonnegative integers. } \medskip \begin{center} \begin{tabular}{lcl} $\Z^+$ && the set of positive integers (\jdef{natural numbers}).\\ $\N$ && the set of nonnegative integers.\\ $\Z$ && the set of integers.\\ $\Q$ && the set of rational numbers.\\ $\R$ && the set of real numbers.\\ $\C$ && the set of complex numbers. %\\ $\R^+$ && the set of positive real numbers. \end{tabular} \end{center} \medskipnoindent The usual \jdef{interval notation} is used, e.g. $$ [a,b):=\{x\in\R: a\le x0$ or else $x<5$}' (true) not exclusive as in `{\em soup or salad?}' (not both). \arap \para \label{if_P_then_Q} The following are synonymous:%\footnote{ See Morgan Pages~5 and~6.} \begin{itemize} \item P $\implies$ Q. \item P implies Q. \item If P, then Q. \item If not Q, the not P. \item Q, if P. \item P only if Q. \end{itemize} Do not confuse the statement {\em `if Q, then P'} with its \jdef{converse} {\em `if P, then Q'}: it can happen that one is true and the other is not as in $x=2\implies x^2=4$. The statement {\em `If not Q, the not P'} is called the \jdef{contrapositive} of the statement {\em `if P, then Q'}. A statement and its contrapositive are equivalent. This provides the justification for \jdef{proof by contradiction}. \arap \para\label{proofs} One of the principal aims of this course is to teach you how to read and write proofs. A \jdef{proof} is an argument intended to convince the reader that a general principle is true in all situations. The amount of detail that an author supplies in a proof should depend on the audience. Too little detail leaves the reader in doubt; too much detail may leave the reader unable to see the forest for the trees. As a general principle, the author of a proof should be able to supply the reader with additional detail on demand. When a student writes a proof for a teacher, the aim is usually not to convince the teacher of the truth of some general principle (the teacher already knows that), but to convince the teacher that the student understands the proof and can write it clearly. The ``theorems'' below show the proper format for writing a proof. In each of them you are supposed to imagine that the theorem to be proved has the indicated form. Notice how the key words {\it choose, assume, let,} and {\it therefore} are used in the proof. In these sample formats, the phrase ``Blah Blah Blah'' indicates a sequence of steps, each one justified by earlier steps. \medskip {\samepage \noindent {\bf Theorem} {\it If P, then Q.} \begin{proof} Assume P. Blah Blah Blah. Therefore Q. \end{proof} } \medskip {\samepage \noindent {\bf Theorem} {\it P if and only if Q.} \begin{proof} Assume P. Blah Blah Blah. Therefore Q. Conversely, assume Q. Blah Blah Blah. Therefore P. \end{proof} } \medskip {\samepage \noindent {\bf Theorem} {\it P($x$) for all $x$.} \begin{proof} Choose $x$. Blah Blah Blah. Therefore P($x$). \end{proof} } \medskip {\samepage \noindent {\bf Theorem} {\it There is an $x$ such that P($x$).} \begin{proof} Let $x= \ldots$. Blah Blah Blah. Therefore P($x$). \end{proof} } \arap \section{Sets}\label{sec:sets} \para A set $A$ divides the mathematical universe into two parts: those objects $x$ that {\em belong} to $A$ and those that don't. The notation $x\in A$ means $x$ belongs to $A$. The notation $x\notin A$ means that $x$ does not belong to $A$. The objects that belong to $A$ are sometimes called the {\em elements} of $A$ but we will often call them {\em points} or {\em numbers}. Other words roughly synonymous with the word {\em set} are {\em class}, {\em collection}, and {\em aggregate}. These longer words are generally used to avoid using the word {\em set} twice in one sentence. The situation typically arises when an author wants to talk about sets whose elements are themselves sets. One might write ``the collection of all finite sets of integers'', rather than ``the set of all finite sets of integers''. \arap \para For two sets $A$ and $B$, the notation $A\subseteq B$ means that $A$ is a \jdef{subset} of $B$, i.e. for all $x$ we have $x\in A\implies x\in B$. By definition, two sets are \jdef{equal} if each is a subset of the other: $$ A=B\iff A\subseteq B\mbox{ and } B\subseteq A. $$ The notation $\{x:P(x)\}$ denotes the set of all $x$ for which the property $P(x)$ is true. The notation $\{x\in A:P(x)\}$ denotes the set of all $x\in A$ for which the property $P(x)$ is true. Finite sets may be defined by enumerating their elements as in $$ x\in\{a_1,a_2,\ldots,a_n\}\iff x=a_1 \mbox{ or } x=a_2 \mbox{ or } \cdots \mbox{ or } x=a_n $$ and often infinite sets as well as in $$ \N=\{0,1,2,\ldots\}, \qquad \Z=\{\ldots,-2, -1,0,1,2,\ldots\},\qquad \Z^+=\{1,2,3,\ldots,\}. $$ \arap \para If $A$ and $B$ are sets, then the sets $$ A\cup B:=\{x: x\in A\mbox{ or } x\in B\},\qquad A\cap B:=\{x: x\in A\mbox{ and } x\in B\}, $$ are called respectively the \jdef{union} and \jdef{intersection} of $A$ and $B$. The \jdef{empty set} is denoted $\emptyset$: For all $x$ it is true that $$ x\notin\emptyset. $$ Two sets are \jdef{disjoint} iff they have no elements in common, i.e iff $A\cap B=\emptyset$. The set $$ X\setminus A:=\{x\in X: x\notin A\} $$ is called the \jdef{complement} of $A$ in $X$.\footnote{ Morgan uses the notation $A^\complement $ for $\R^n\setminus A$ (when $A$ is a subset of $\R^n$). } The set $$ A\times B:=\{(x,y): x\in A\mbox{ and } y\in B\} $$ of all ordered pairs $(x,y)$ with $x\in A$ and $y\in B$ is called the \jdef{Cartesian product} of $A$ and $B$. The term \jdef{direct product} is a synonym. We also use the notation $$ A^n:= \underbrace{A\times A\times \cdots\times A}_n $$ In particular, $$ \R^n :=\{(x_1,x_2,\ldots,x_n): x_i\in\R\} $$ denotes the vector space of all $n$tuples of real numbers, so $\R^1=\R$, $\R^2=\R\times\R$, $\R^3=\R\times\R\times\R$, etc.\footnote{ Buck uses the term \jdef{$n$ space} as a synonym for $\R^n$.} \arap \rmk Do not confuse an \jdef{$n$tuple} (finite sequence of length $n$) with a finite set. For the former order is important: $\{3,7\}=\{7,3\}$ but $(3,7)\ne(7,3)$; for the latter repetitions don't matter: $\{2,2,3\}=\{2,3\}$ but $(2,2,3)\ne(2,3)$. \kmr \para An \jdef{indexed family of sets} is a function which assigns a set $A_i$ to each element $i$ of a set $I$. The set $I$ is called the \jdef{index set} of the family and the family is usually denoted $(A_i)_{i\in I}$. The \jdef{union} and \jdef{intersection} of the indexed family are defined by \begin{eqnarray*} x\in \bigcup_{i\in I} A_i &\iff& \exists i\in I\;\mbox{such that}\; x\in A_i.\\ x\in \bigcap_{i\in I} A_i &\iff& \forall i\in I\;\mbox{we have}\; x\in A_i. \end{eqnarray*} The notation $\exists i\in I$ is an abbreviation for ``there exists $i\in I$'', and the notation $\forall i\in I$ is an abbreviation for ``for all $i\in I$''. In these definitions the set $I$ can be infinite. For finite sets $I$ we recover the earlier definitions, e.g. for $I=\{1,2\}$ we have $$ \bigcup_{i\in\{1,2\}} A_i=A_1\cup A_2 ,\qquad \bigcap_{i\in\{1,2\}} A_i=A_1\cap A_2. $$ This illustrates the logical principle that $\exists$ is like an ``infinite or'' and $\forall$ is like an ``infinite and''. \arap \rmk\label{rmk:truth_table} Set theory is simply a way of formalizing logic. Simple set theoretic identities may be proved by \jdef{truth tables}. For example, consider the following ``distributive law'' $$ (A\cup B)\cap C = (A\cap C)\cup(B\cap C). $$ To show that $x\in(A\cup B)\cap C \iff x\in(A\cap C)\cup(B\cap C)$ we can simply consider all the possibilities: $$ \begin{array}{ccc|cc} A&B&C& (A\cup B)\cap C & (A\cap C)\cup (B\cup C)\\ \hline T&T&T& T & T\\ T&T&F& F & F\\ T&F&T& T & T\\ T&F&F& F & F\\ F&T&T& T & T\\ F&T&F& F & F\\ F&F&T& F & F\\ F&F&F& F & F \end{array} $$ It is usually not necessary to show so much detail in your written work, but it will be hard for you to decide just how much detail {\em is} appropriate. A good rule of thumb is that you should be prepared to supply more detail if challenged. \kmr \para\label{demorgan_and_distributive} From logic we know that $$ \mathrm{not }\;\exists \iff \forall\;\mathrm{ not}, \qquad \mbox{ and } \qquad \mathrm{not }\;\forall \iff \exists\; \mathrm{ not}, $$ so for any set $X$ and any indexed family $(A_i)_{i\in I}$ we have $$ X\setminus \bigcup_{i\in I} A_i = \bigcap_{i\in I} (X\setminus A_i), \qquad X\setminus \bigcap_{i\in I} A_i = \bigcup_{i\in I} (X\setminus A_i). $$ Logicians call these \jdef{De Morgan's Laws}. In particular, for $I=\{1,2\}$ we have $$ \begin{aligned} & X\setminus(A_1\cup A_2)= (X\setminus A_1)\cap(X\setminus A_2), \\ & X \setminus(A_1\cap A_2)= (X \setminus A_1)\cup(X \setminus A_2). \end{aligned} $$ Also by logic we have set theoretic distributive laws $$ X\cap \bigcup_{i\in I} A_i = \bigcup_{i\in I} (X\cap A_i), \qquad X\cup\bigcap_{i\in I} A_i = \bigcap_{i\in I} (X\cup A_i). $$ In particular, for $I=\{1,2\}$ we have $$ \begin{aligned} &X\cup(A_1\cap A_2)= (X\cup A_1)\cap(X\cup A_2), \\ &X\cap(A_1\cup A_2)= (X\cap A_1)\cup(X\cap A_2). \end{aligned} $$ The latter was proved above in Remark~\ref{rmk:truth_table}. \arap \section{Functions and Maps} \para A \jdef{function} is a rule which assigns a value $f(x)$ to every point $x$ from a set called the \jdef{domain} of the function. The set $$ \mathrm{graph}(f):=\{(x,y): y=f(x)\} $$ of all pairs $(x,y)$ such that $y=f(x)$ is called the \jdef{graph} of the function $f$. Two functions are equal iff they have the same graph. \arap \para \index{equality of sets} Let $X$ and $Y$ be sets. We say that $f$ is a \jdef{map} from $X$ to $Y$ and write $f:X\to Y$ when $f$ is a function which assigns a point $y=f(x)\in Y$ to each point $x\in X$. Two maps $f:X\to Y$ and $f':X'\to Y'$ are said to be \jdef{equal} when $X=X'$, $Y=Y'$, and $f(x)=f'(x)$ for all $x\in X$. Thus if $f$ and $f'$ equal maps, then $\mathrm{graph}(f)=\mathrm{graph}(f')$ but not conversely (because $Y=Y'$ is part of the definition of equality for maps). However most authors would say that two functions are equal iff they have the same graph. \arap \rmk Some authors use the notation $x\mapsto f(x)$ to define a map. This allows them to avoid introducing a name for the map. Thus instead of writing \begin{quote}\em Consider the map $f:\R\to\R$ defined by $f(x)=x^5+x$. \end{quote} they may write \begin{quote}\em Consider the map $\R\to\R:x\mapsto x^5+x$. \end{quote} \kmr \para When $A\subseteq X$, $B\subseteq Y$, and $f:X\to Y$, the sets $$ \begin{aligned} & f(A):=\{y\in Y: \exists x\in A \mbox{ such that }y=f(x)\}, \\ & f^{-1}(B):=\{x\in X: f(x)\in B\}, \end{aligned} $$ are called respectively the \jdef{image} of $A$ by $f$ and \jdef{inverse image} of $B$ by $f$. \arap \rmk\label{rmk:source_target} The sets $X$ and $Y$ are sometimes called the \jdef{source} and \jdef{target} of a map $f:X\to Y$. The image $f(X)$ of the source is what is called the \jdef{range} of the function $f$ in calculus. Thus the domain of a map is the same as its source while the range is a subset of its target. \kmr \rmk There are slight variations in terminology among authors. Morgan avoids the word {\em map} and Lang sometimes uses the word {\em mapping}. Buck uses the term the \jdef{preimage} instead of {\em inverse image}. Lang (page~4) uses the $\mapsto$ notation but the other authors apparently avoid it. For Lang a function is a map whose target is $\R$. In precalculus courses a function is usually defined by an expression and the domain is implicitly taken to be the largest set of numbers for which the expression is meaningful, but in advanced mathematics authors usually make the domain explicit. Examples~\ref{xmpl:four_maps} below shows why the distinction is important. \kmr \prob\label{prob:cap_cup_map} Let $f:X\to Y$, $(A_i)_{i\in I}$ be a family of subsets of $X$, and $(B_i)_{i\in I}$ be a family of subsets of $Y$. Which of the following are (always) true? Hint: When there is a counterexample, there is a counterexample with the index set $I=\{1,2\}$. $$\renewcommand{\arraystretch}{2.5} \begin{array}{llll} \ds f^{-1}\left(\bigcup_{i\in I} B_i\right)\subseteq\bigcup_{i\in I} f^{-1}(B_i)? && \ds \bigcup_{i\in I} f^{-1}(B_i)\subseteq f^{-1}\left(\bigcup_{i\in I} B_i\right)? \\ \ds f^{-1}\left(\bigcap_{i\in I} B_i\right)\subseteq\bigcap_{i\in I} f^{-1}(B_i)? && \ds \bigcap_{i\in I} f^{-1}(B_i)\subseteq f^{-1}\left(\bigcap_{i\in I} B_i\right)? \\ \ds f\left(\bigcup_{i\in I} A_i\right)\subseteq\bigcup_{i\in I} f(A_i)? && \ds \bigcup_{i\in I} f(A_i)\subseteq f\left(\bigcup_{i\in I} A_i\right)? \\ \ds f\left(\bigcap_{i\in I} A_i\right)\subseteq\bigcap_{i\in I} f(A_i)? && \ds \bigcap_{i\in I} f(A_i)\subseteq f\left(\bigcap_{i\in I} A_i\right)?\\ \end{array} $$ \borp \prob\label{prob:setminus_map} Proof or counterexample: \begin{description} \item[(1)] If $f:X\to Y$ and $A_1,A_2\subseteq X$, then $f(A_1\setminus A_2)\subseteq f(A_1)\setminus f(A_2)$? \item[(2)] If $f:X\to Y$ and $A_1,A_2\subseteq X$, then $f(A_1)\setminus f(A_2)\subseteq f(A_1\setminus A_2)$? \item[(3)] If $f:X\to Y$ and $B_1,B_2\subseteq Y$, then $f^{-1}(B_1\setminus B_2)\subseteq f^{-1}(B_1)\setminus f^{-1}(B_2)$? \item[(4)] If $f:X\to Y$ and $B_1,B_2\subseteq Y$, then $f^{-1}(B_1)\setminus f^{-1}(B_2)\subseteq f^{-1}(B_1\setminus B_2)$? \end{description} \borp \prob\label{prob:f_of_f_inverse} Proof or counterexample: \begin{description} \item[(1)] If $f:X\to Y$ and $A\subseteq X$, then $f^{-1}(f(A))\subseteq A$? \item[(2)] If $f:X\to Y$ and $A\subseteq X$, then $A\subseteq f^{-1}(f(A))$? \item[(3)] If $f:X\to Y$ and $B\subseteq Y$, then $f(f^{-1}(B))\subseteq B$? \item[(4)] If $f:X\to Y$ and $B\subseteq Y$, then $B \subseteq f(f^{-1}(B))$? \end{description} \borp \section{Composition and Inverse} \para If $f:X\to Y$ and $g:Y\to Z$, then the \jdef{composition} of $f$ and $g$ is the map $g\circ f:X\to Z$ defined by $$ (g\circ f)(x)=g(f(x)) $$ for $x\in X$. For any set $X$ the \jdef{identity map} of $X$ is the map $\mathrm{id}_X:X\to X$ defined by $$ \id_X(x)=x $$ for $x\in X$. Clearly $$ \id_Y\circ f = f \mbox{ and } f\circ\id_X=f $$ for $f:X\to Y$. \arap \para A map $g:Y\to X$ is said to be a \jdef{left inverse} for the map $f:X\to Y$ iff $g\circ f=\id_X$, i.e. iff $g(f(x))=x$ for all $x\in X$. A map $g:Y\to X$ is said to be a \jdef{right inverse} for the map $f:X\to Y$ iff $f\circ g=\id_Y$, i.e. iff $f(g(y))=y$ for all $y\in Y$. A map $g:Y\to X$ is said to be a (two sided) \jdef{inverse} to the map $f:X\to Y$ iff it is both a left inverse and a right inverse to $f$. If $g$ is a left inverse to $f$ and $g'$ is a right inverse to $f$ then $g=g'$. (Proof: $g=g\circ \id_X=g\circ f\circ g'=\id_Y\circ g'=g'$.) In this case there is a unique inverse and it is denoted $f^{-1}$. So if $f:X\to Y$ has an inverse $f^{-1}:Y\to X$, then $$ y=f(x)\iff x=f^{-1}(y) $$ for $x\in X$ and $y\in Y$. \arap \dfn\label{dfn:jective} A map $f:X\to Y$ is said to be \jdef{injective} iff $$ \forall x_1,x_2\in X\;[f(x_1)=f(x_2)\implies x_1=x_2] $$ and it is said to be \jdef{surjective} iff $Y=f(X)$, i.e. $$ \forall y\in Y\;\exists x\in X\; y=f(x). $$ A map is \jdef{bijective} iff it is both injective and surjective. Thus \begin{description} \item[(1)] A map is injective if and only if it has a left inverse; \item[(2)] A map is surjective if and only if it has a right inverse; \item[(3)] A map is bijective if and only if it has a (two-sided) inverse. \end{description} In the lingo used in Remark~\ref{rmk:source_target}, a map is surjective if and only if its range equals its target. \nfd \rmk Both Lang and Morgan use the more modern terms injective, surjective, bijective, but Buck and Rudin use the older terminology \jdef{one-one} instead of injective, \jdef{onto} instead of {\em surjective}, and \jdef{one-one onto} instead of bijective. The older terminology is used in teaching calculus. \kmr \rmk\label{rmk:axiom_of_choice} The 'only if' part of item~(2) is called the \jdef{Axiom of Choice}. It was once controversial because one can imagine a situation where one can prove that a map $f$ is surjective but where one cannot give an explicit formula for a right inverse. \kmr \xmpl\label{xmpl:discontinuous_bijection} The assertions (1-3) in Definition~\ref{dfn:jective} are false if continuity (defined later) is required: There is a continuous bijective map whose inverse is not continuous (and hence continuous injective map which does not have a continuous left inverse, and a continuous surjective map which does not have a continuous right inverse). Let $S:=\{(x,y)\in\R^2: x^2+y^2=1\}$ denote the unit circle in $\R^2$ and define $f:[0,2\pi)\to S$ by $f(\theta)=(\cos\theta,\sin\theta)$. Then $f$ bijective and continuous but $f^{-1}$ is not continuous. In Theorem~\ref{thm:continuous_bijection} below we will see that the inverse if a continuous bijective map is continuous if its domain is compact (defined later), but $[0,2\pi)$ is not compact. \lpmx \xmpl \label{xmpl:four_maps} Consider the four maps $$ f_1:\R\to\R,\quad f_2:[0,\infty)\to\R, \quad f_3:\R\to[0,\infty), \quad f_4:[0,\infty)\to [0,\infty) $$ defined by $f_i(x)=x^2$. Then $f_1$ is not injective and not bijective, $f_2$ is injective but not surjective, $f_3$ is surjective but not injective, and $f_4$ is bijective. Any map $g_2:\R\to[0,\infty)$ such that $g_2(y)=\sqrt{y}$ for $y\ge 0$ is a left inverse to $f_2$, and any map $g_3:[0,\infty)\to\R$ such that $g_3(y)=\pm\sqrt{y}$ (the $\pm$ can depend on $y$) is a right inverse to $f_3$ The inverse map to $f_4$ is $f_4^{-1}(y)=\sqrt{y}$. \lpmx \prob Which (if any) of the false formulas in problem~\ref{prob:cap_cup_map} become true if we assume that the map $f$ is injective? surjective? (Proof or counter example.) \borp \section{Mathematical Induction} \para\label{induction} The principle of \jdef{mathematical induction} is the following axiom. \begin{quote}\em Let $S\subseteq\N$ be a set of nonnegative integers. Assume that $0\in S$ and that $n\in S \implies n+1\in S$. Then $S=\N$. \end{quote} It is usually taught in College Algebra as a means of proving identities like $$ \sum_{k=0}^n k= \frac{n(n+1)}{2} \qquad\mbox{and}\qquad \sum_{k=0}^n k^2= \frac{n(n+1)(2n+1)}{6} . $$ For example to prove the first identity let $S$ denote the set of all $n\in\N$ for which the statement is true. Then $0\in S$ and if $n\in S$ then $$ \sum_{k=0}^{n+1} k = \left(\sum_{k=0}^n k\right)+(n+1) = \frac{n(n+1)}{2} +(n+1) =\frac{(n+1)(n+2)}{2} $$ so $n+1\in S$. Hence by the principle of mathematical induction, $S=\N$, i.e. the identity is true for all $n\in\N$. \arap \para \label{inductive_definitions} We will often use \jdef{inductive definitions} where a sequence is defined by specifying the first few values and then giving a ``recurrence relation'' for determining the remaining values from the earlier ones. For example, the \jdef{Fibonacci numbers} are defined by $$ F_0=0,\qquad F_1=1,\qquad F_n=F_{n-1}+F_{n-2}. $$ Thus $F_2=1$, $F_3=3$, $F_4=5$, $F_5=8$, $F_9=55$ etc. \arap \prob Prove the sum of squares formula in~\ref{induction} \borp \section{Infinite Sets} \dfn A set $S$ is said to be \begin{itemize} \item \jdef{infinite} iff there is a injective map $f:\N\to S$, \item \jdef{finite} iff it is not infinite, \item \jdef{countable} iff there is a bijective map $J\to S$ for some $J\subseteq\N$, and \item \jdef{uncountable} iff it is not countable.\footnote{This this the terminology used by Morgan. For Buck and Rudin {\em countable} means {\em countable and infinite} which is equivalent to saying that there is a bijective map $\N\to S$. Lang uses the terms \jdef{denumerable} and \jdef{nondenumerable} for {\em countable and infinite} and {\em uncountable}. } \end{itemize} \nfd \begin{proposition} If there is a bijective map $\{1,2,\ldots,m\}\to\{1,2,\ldots,n\}$, then $m=n$. Hence if $S$ is finite, there is a unique $n$ (called the \jdef{cardinality} of $S$) such that there is a bijective map $\{1,2,\ldots,n\}\to S$. \end{proposition} \prob Suppose that $S$ and $T$ are finite sets of cardinality $s$ and $t$ respectively? What is the cardinality of $S\times T$? Of the set $T^S$ of maps from $S$ to $T$? Of the set $2^S$ of subsets of $S$? Of $S\cup T$ (assuming that $S\cap T=\emptyset$)? \borp The following four propositions are proved in Chapter~2 of Morgan. See also Lang pages~12-15. The main value of these propositions is to give the student experience in constructing maps. The constructions are not needed in the rest of the course, but learning them will give you some confidence. \begin{proposition} A subset of a countable set is countable. \end{proposition} \begin{proof} A subset of a finite set is finite so it is enough to consider a subset $S\subset\N$ of the nonnegative integers. Define $s_n$ inductively (see~\ref{inductive_definitions}) by $s_{n+1}=$ the least element of $S\setminus\{s_1,\ldots,s_n\}$. If for some $n$ the set $S\setminus\{s_1,\ldots,s_n\}$ is empty then the induction stops and the set $S$ is finite of cardinality $n$. Otherwise, the map $\N\to S:n\mapsto s_n$ is injective. But it is also surjective: if $k\in S$ then $k=s_n$ for some $n\le k$. \end{proof} \begin{proposition} \label{prop:product_of_countable} If $S$ and $T$ are countable, so is $S\times T$. \end{proposition} \begin{proof} It is enough to prove that $\N\times\N$ is countable. Consider the following enumeration of $\N\times\N$: $$\small \begin{array}{cccccc} f(0)=(0,0) &f(2)=(0,1) &f(5)=(0,2)&f(9)=(0,3)&f(14)=(0,4)& \cdots\\ f(1)=(1,0) &f(4)=(1,1) &f(8)=(1,2)&f(13)=(1,3)& \cdot& \cdots\\ f(3)=(2,0) &f(7)=(2,1) &f(12)=(2,2)& \cdot& \cdot& \cdots\\ f(6)=(3,0) &f(11)=(3,1)&\cdot&\cdot& \cdot& \cdots\\ f(10)=(4,0)&\cdot&\cdot&\cdot& \cdot& \cdots\\ \vdots &\vdots& \vdots & \vdots &\vdots&\ddots \end{array} $$ This defines a bijection $f:\N\to\N\times\N$. (Compare with Morgan page~10.) On each diagonal the sum of the coordinates is constant and the input $n$ to the function $f(n)$ increases as you go from left to right up the diagonal. \end{proof} \prob For $f$ as in Proposition~\ref{prop:product_of_countable}, find $f(1307)$ and $f^{-1}(58,19)$. Hint: The formula for the sum of the first $n$ natural numbers from~\ref{induction} will be helpful. \borp \begin{proposition} The set $\Q$ of rational numbers is countable. \end{proposition} \begin{proposition} The set $\R$ of real numbers is uncountable. \end{proposition} \begin{theorem} The set $2^\N$ of all subsets of $\N$ is uncountable. \end{theorem} \begin{proof} Suppose not. Then there is a bijective map $\N\to 2^\N:n\mapsto A_n$. Let $B=\{n\in\N: b\notin A_n\}$ Then $B=A_k$ for some $k$. Either $k\in A_k$ or $k\notin A_k$. If the former, then $k\notin B$ so $A_k\ne B$. If the latter, $k\in B$, so again $A_k\ne B$. Either way we have a contradiction to the assumption that the map $n\mapsto A_n$ is bijective. \end{proof} \begin{theorem}[Dedekind] A set $S$ is infinite if and only if there is an injective map from $S$ to itself which is not surjective. \end{theorem} \begin{theorem}[Cantor Schroeder Bernstein] If there is an injective map from $S$ to $T$ and there is an injective map from $T$ to $S$, then there is a bijective map from $S$ to $T$. \end{theorem} \begin{proof} Buck page~552. \end{proof} \section{Axioms for the Real Numbers} We state here the axioms for the real number system $\R$. We shall accept these axioms without proof but it can proved (from more general axioms) that there is an essentially unique structure satisfying them. \para\jdef{Algebraic Axioms}. \label{ax:algebraic} The set $\R$ of \jdef{real numbers} is equipped with two operations $$ \R\times\R\to\R:(a,b)\mapsto a+b,\qquad\R\times\R\to\R:(a,b)\mapsto a\cdot b $$ such that the usual laws of grade school arithmetic hold: \begin{description} \item[(Commutative Laws)] $a+b=b+a$ and $a\cdot b=b\cdot a$. \item[(Associative Laws)] $(a+b)+c=a+(b+c)$ and $(a\cdot b)\cdot c= a\cdot (b\cdot c)$. \item[(Distributive Law)] $(a+b)\cdot c= (a\cdot c)+(b\cdot c)$. \item[(Zero,One)] There are (necessarily unique) distinct elements $0,1\in\R$ such that $a+0=a$ and $a\cdot 1=a$ for all $a\in\R$. \item[(Inverses)] For every $a\in\R$ there is a (necessarily unique) element $-a$ such that $a+(-a)=0$. For every $a\in\R\setminus\{0\}$ there is a (necessarily unique) element $a^{-1}$ such that $a\cdot a^{-1}=1$. \end{description} The standard notations from high school algebra are used: in particular, $ab:=a\cdot b$, $a-b:=a+(-b)$, and $a/b=a\cdot b^{-1}$. \arap \para\jdef{Order Axioms}. \label{ax:order} The set $\R$ has an order relation denoted $aa$ and $a\le b\iff b\ge a\iff$ either $a0$ if $a>0$? Explain. \borp \dfn \label{def:glb} A set $S$ of real numbers is said to be \jdef{bounded above} iff there is a number $b\in\R$ such that $x\le b $ for all $x\in S$; the number $b$ is then called an \jdef{upper bound} for $S$. A number $b\in\R$ is called a \jdef{least upper bound} for $S$ iff it is an upper bound for $S$ and $b\le b'$ for every other upper bound $b'$ for $S$. Similarly the set $S$ is said to be \jdef{bounded below} iff there is an number $a\in\R$ such that $a\le x$ for all $x\in S$; the element $b$ is then called a \jdef{lower bound} for $S$. An element $a\in\R$ is called a \jdef{greatest lower bound} iff it is an lower bound for $S$ and $a'\le a$ for every other lower bound $a'$ for $S$. The words \jdef{infimum} and {\em greatest lower bound} are synonymous as are the words \jdef{supremum} and {\em least upper bound}. The least upperbound of the set $S$ will be denoted $\sup(S)$ and the greatest lower bound of the set $S$ will be denoted $\inf(S)$. We write $\sup(S)=\infty$ when $S$ is not bounded above and $\inf(S)=-\infty$ when $S$ is not bounded below. \nfd \para\jdef{Completeness Axiom}. \label{completeness_axiom} Every set $S$ of real numbers which is bounded above has a least upper bound, i.e. \begin{quote} if $x\le b$ for all $x\in S$, then $x\le \sup(S)\le b$ for all $x\in S$. \end{quote} Because multiplication by $-1$ reverses the order it is the same to say that every set which is bounded below has a greatest lower bound. Thus \begin{quote} if $a\le x$ for all $x\in S$, then $a\le \inf(S)\le x$ for all $x\in S$. \end{quote} \arap \rmk \label{rmk:decimal_expansion_and_addition} For Morgan the completeness axiom is a theorem (see page~44 of his book) but most authors of undergraduate texts don't prove it. Of course it can't be proved until we give a precise construction (definition) of the real numbers. Morgan takes the view that a real number is a number with a decimal expansion, but avoids certain subtle issues connected with this view. %(For example $1.0=0.99\ldots$ has two decimal expansions.) Actually making his definition precise would involve defining how to do the arithmetic operations with decimal expansions and would be a bit tedious. To see why, imagine that $a+b=c$ and that $$ a=\sum_{n=1}^\infty a_n10^{-n},\qquad b=\sum_{n=1}^\infty b_n10^{-n},\qquad c=\sum_{n=1}^\infty c_n10^{-n}, $$ where the coefficients, $a_n,b_n,c_n$ are integers between $0$ and $9$ and try to express $c_n$ in terms the $a_n$'s and the $b_n$'s. In an appendix to his book, Buck sketches a construction the real numbers by something called \jdef{Dedekind cuts} but leaves out many details. Rudin explains cuts in an appendix to his chapter~1. (The book {\em Foundations of Analysis} by Edmund Landau gives all the details.) The completeness axiom is an easy consequence of this construction. One can also define the real numbers using `equivalence classes of Cauchy sequences' (see~\ref{dfn:cauchy}) and again the completeness axiom is a consequence; if we get to the topic of completion of metric spaces, I'll explain it then. The crucial point is the uniqueness `up to isomorphism' which we will prove in Appendix~\ref{app:uniqueness_of_R}. It means that if we start from the axioms, it doesn't matter what definition of the real numbers we use. We will not use the completeness axiom until the proof of Theorem~\ref{thm:monotone_sequence} and the exposition is arranged in such a way that it will be clear that the reasoning is not circular. The following exercises will help you understand some of the issues. \kmr \prob \label{prob:archimedes} Prove the following \jdef{Archimedean Property} of the real numbers: There is neither an infinite real number nor an infinitesimal real number. More precisely, \begin{description} \item[(1)] There is no real number which is larger than every integer. \item[(2)] For every positive real number $\eps>0$ there is a positive integer $n$ such that $1/n<\eps$. \end{description} Hint: If $\omega>n$ for every integer $n$ what about $\omega-1$? The proof will use the completeness axiom. \borp \prob\label{prob:calR} Let $\mathcal{R}$ denote the set of real valued rational functions, i.e. $f\in\mathcal{R}$ iff $f(x)=p(x)/q(x)$ where $p(x)$ and $q(x)$ are polynomials with real coefficients (and $q(x)$ is not the zero polynomial). For $f,g\in\mathcal{R}$ define an order relation by the condition that $f>g$ iff there exists an $M$ such that $f(x)>g(x)$ for all $x>M$. Then the set $\mathcal{R}$ satisfies the algebraic axioms and order axioms given above. View $\R$ (and hence $\Z$) as a subset of $\mathcal{R}$ by identifying the real number $c$ with the constant function whose value is always $c$. Exhibit (in the lingo of Problem~\ref{prob:archimedes}) an infinite element $f\in\mathcal{R}$ and an infinitesimal element $g\in\mathcal{R}$. Hint: What is $\lim_{x\to\infty}\frac{p(x)}{q(x)}$? \borp \prob \label{prob:Q_dense} Prove that there is a rational number in every nonempty open interval $(a,b)\subset\R$. \borp %\iffalse \iftrue \noindent{\bf Solution:} By the Archimedean property from Problem~\ref{prob:archimedes} there are integers $m$ and $n$ with $mn$ so to be sure that the strict inequality holds we should take $n=8$. For the second part we have $$ |(a+b)-(A+B)| \le |a-A|+|b-B|\le 2\cdot 10^{-8} $$ by the first part and the triangle inequality. Since $2\cdot 10^{-8}<10^{-7}$ we have that $n=8$ works here as well. Note: The point of this problem is to convince you that it is awkward to work with decimal expansion if you want to be super careful. Also the wording of the problem (``How large must $n$ be to ensure that'') suggests that I want the smallest possible $n$ that works. Usually I don't care about that. I could have replaced the phrase `How large must $n$ be to ensure that'' by ``Find $N$ so that for $n\ge N$ we have''. In that case the answer $n=13472$ would be correct (but overkill). \fi \section{Distance} \para The \jdef{distance} $d(p,q)$ between two points $p=(x_1,x_2,\ldots,x_n)$ and $q=(y_1,y_2,\ldots,y_n)$ in $\R^n$ is defined by\footnote{ In Chapters I-V Buck writes $|p-q|$ instead of $d(p,q)$ but uses the notation $d(p,q)$ starting in Chapter~VI (page~304) in a more general setting.} $$ d(p,q)=\sqrt{(x_1-y_1)^2+(x_2-y_2)^2+\cdots+(x_n-y_n)^2}. $$ The distance $d(v,0)$ from a vector $v\in\R^n$ to the origin is called the \jdef{norm} of $v$ denoted by $|v|$ so $$ d(p,q):=|p-q|. $$ The norm satisfies the following laws for $v,w\in\R^n$: \begin{description} \item[(zero norm)] $|v|=0\iff v=0$, \item[(homogeneity)] $|av|=a\,|v|$ if $a>0$, \item[(symmetry)] $|-v|=|v|$, \item[(triangle inequality)] $|v+w| \le |v|+|w|$. \end{description} The zero norm law holds because a sum of squares vanishes only if each summand vanishes and the triangle inequality is proved in problem~\ref{prob:triangle_inequality} below.\footnote{ See also the Corollary on page~14 of Buck or Theorem~2.1 on page~134 of Lang.} The laws for the norm imply that the distance function satisfies the following: \begin{description} \item[(zero distance)] $d(p,q)=0\iff p=q$, \item[(symmetry)] $d(p,q)=d(q,p)$, \item[(triangle inequality)] $d(p,r)\le d(p,q)+d(q,r)$. \end{description} These are proved by reading $v=p-q$ and $w=q-r$ in the corresponding law for the norm. \arap \para Define the \jdef{inner product} of two vectors in $\R^n$ by $$ \inner{u}{v}=u_1v_1+u_2v_2+\cdots+u_nv_n $$ for $u=(u_1,u_2,\ldots,u_n)$, $v=(v_1,v_2,\ldots,v_n)$. In freshman calculus you called this the \jdef{dot product} and learned that the angle $\theta$ between the two vectors $u$ and $v$ satisfies $$ \inner{u}{v}=\cos\theta\,|u|\,|v|. $$ Since the cosine takes values between -1 and +1, it follows that $$ |\inner{u}{v}| \le |u|\,|v|. $$ This inequality is called the \jdef{Schwarz inequality}. \arap \prob\label{prob:triangle_inequality} In this problem you will prove the triangle inequality without using trigonometry in two steps. \begin{enumerate} \item Prove the Schwarz inequality. (Hint: The quadratic polynomial $f(t)=|u+tv|^2=At^2+Bt+C$ is always nonnegative so its discriminant $B^2-4AC$ is nonpositive.) \item Derive the triangle inequality as a corollary. (Hint: Compare $|u\pm v|^2$ and $(|u|+|v|)^2$.) \end{enumerate} \borp \dfn\label{def:open_ball} For $p\in\R^n$ and $\delta>0$ the set $$ B(p,\delta):=\{q\in\R^n:d(p,q)<\delta\} $$ is called the \jdef{open ball} centered at $p$ with radius $\delta$. When $X\subseteq\R^n$ we often use the abbreviation $$ B_X(p,\delta):=B(p,\delta)\cap X:=\{q\in X: d(p,q)<\delta\} $$ \nfd \rmk When $n=1$ the open ball is an open interval: $$ \begin{aligned} B(a,\delta)&=\{x\in\R: |x-a|<\delta\}\\ &=\{x\in\R: a-\delta0$ such that $|p|0$ define $\delta_n>0$ and $p_n\in S$ inductively (see~\ref{inductive_definitions}) by $\delta_n=\min(|p_n-p|,1/n)$ and $p_{n+1}\in B(p,\delta_n)\cap S$. The map $n\mapsto p_n$ is injective as $|p_n-p|<|p_m-p|$ for $n>m$. Choose $\delta>0$ so that $B(p,\delta)\subset U$ (by the definition of neighborhood). Then $\delta_n<\delta$ for $1/n<\delta$ so $p_n\in B(p,\delta)\cap S\subseteq U\cap S$. Hence $U$ contains the infinite set $\{p_n:n>1/\delta\}$. \end{proof} \para\label{limit} Let $p_0$ be a accumulation point of a set $S$ and $F$ be a function defined on $S$ (but possibly not at $p_0$). The notation $$ \lim_{p\to p_0}F(p) = L $$ means that for every neighborhood $V$ of $L$ of there is a punctured neighborhood $U\setminus\{p\}$ of $L$ such that $f(S\cap U\setminus\{p\})\subset V$. When $p_0\in S$ and $p_0$ is a accumulation point of $S$ we have that a function $f$ defined on $S$ is continuous at $p_0$ (see Definition~\ref{def:continuous} below) if and only if $$ \lim_{p\to p_0}f(p) =f(p_0) $$ (and the function is trivially continuous at a point $p_0\in S$ which is not an accumulation point of $S$). However, the limit notation is usually used in situations where ($p_0$ is a accumulation point of $S$ but) $p_0\notin S$. For example, the \jdef{derivative} of a real valued function $f:I\to\R$ defined on an open interval $I\subseteq\R$ is defined by $$ f'(x_0):=\lim_{x\to x_0}\frac{f(x)-f(x_0)}{x-x_0}. $$ The ratio in the limit is undefined when $x=x_0$ but is defined for nearby values of $x$. \arap \para \label{extended_reals} For a real valued function $f$ defined on a subset of $\R$ we can extend the definition of the notation $\lim_{x\to a}F(x)=L$ to include the cases where $a=\pm\infty$ and/or $L=\pm\infty$ as follows. Let $$ \hat\R:=\{-\infty\}\cup\R\cup\{\infty\} $$ consist of the set of real numbers together with two additional points which we think of as located at infinity. The set $\hat\R$ is sometimes called the set of \jdef{extended real numbers}. Extend the usual order relation on $\R$ to $\hat\R$ in the obvious way. For $a\in\hat\R$, a set $U\subseteq\hat\R$ is called \jdef{neighborhood} of $a$ iff \begin{description} \item[] either $a\in\R$ and $U$ contains an open interval $(a-\delta,a+\delta)$ for some $\delta>0$, \item[] or else $a=\infty$ and $U$ contains an interval $(M,\infty]$ for some $M>0$, \item or else $a=-\infty$ and $U$ contains an interval $[-\infty,-M)$ for some $M>0$. \end{description} Because $B(a,\delta)=(a-\delta,a+\delta)$ this definition agrees with the definition in~\ref{limit} for $a\in\R$. A point $a\in\hat\R$ is called a \jdef{accumulation point} of a subset $S\subseteq\R$ iff every punctured neighborhood of $a$ intersects $S$. If $f:S\to\R$ and $a$ is a accumulation point of $S$, then the notation $$ \lim_{x\to a} F(x)=L $$ means that for every neighborhood $V$ of $L$ there is a punctured neighborhood $U$ of $a$ such that $f(U\cap S)\subseteq V$. \arap \rmk Unraveling the above definitions we see that for $a,L\in\R$ we have that $\lim_{x\to a} F(x)=L$ iff $\forall \eps>0\,\exists \delta>0$ such that $\forall x\in S$ we have that $0<|x-a|<\delta\implies |F(x)-L|<\eps$. Also $\lim_{x\to\infty} F(x)=L$ iff $\forall \eps>0\,\exists M>0$ such that $\forall x\in S$ we have that $M0\}$ of positive integers or the set $\N:=\{n\in\Z:n\ge0\}$ of nonnegative inregers. ) It is customary to denote the value of a sequence at an integer $n$ with a subscript rather than with parentheses and to denote a sequence with a notation like $(p_n)_n$ or $(p_n)_{n\in\Z^+}$. \arap \dfn\label{def:converge} The sequence $(p_n)_n$ of points of $\R^m$ is said to \jdef{converge} to the point $p\in\R^m$ iff $$ \lim_{n\to\infty} p_n=p $$ This is sometimes abbreviated as $p_n\to p$ as $n\to\infty$. We say a sequence \jdef{converges} or is \jdef{convergent} iff it converges to $p$ for some $p\in\R^m$. A sequence is said to \jdef{diverge} when it does not converge. (A sequence in $\R$ whose limit is infinite is also said to diverge.) \nfd \rmk Using the lingo introduced in~\ref{extended_reals} this may be stated as $ \lim_{n\to\infty} p_n=p $ iff for every $\eps>0$ there exists $N=N(\eps)>0$ such that $n\ge N\implies |p_n-p|<\eps$. \kmr \begin{theorem}\label{sum_product_quotient_sequences} Assume that $(a_n)_n$ and $(b_n)_n$ are convergent sequences of real numbers: $$ \lim_{n\to\infty} a_n = a, \qquad \lim_{n\to\infty} b_n=b. $$ Then $$ \lim_{n\to\infty} a_n+b_n = a+b, \qquad \lim_{n\to\infty} a_nb_n = ab. $$ Moreover, if $b\ne 0$ then $b_n\ne 0$ for sufficiently large $n$ and $$ \lim_{n\to\infty} \frac{a_n}{b_n} = \frac{a}{b}. $$ \end{theorem} \begin{proof} %\iftrue \iffalse Exercise. \else \noindent {\bf (I)} We prove $\lim_{n\to\infty} a_n+b_n = a+b$. Choose $\eps>0$. By hypothesis there exists $N_1$ and $N_2$ such that $$ n>N_1\implies |a_n-a|<\frac{\eps}{2},\qquad n>N_2\implies |b_n-b|<\frac{\eps}{2}. $$ Let $N=\max(N_1,N_2)$. Then for $n>N$ we have $$ \begin{aligned} |(a_n+b_n)-(a+b)| &=|(a_n-a)+(b_n-b)|\\ &\le |a_n-a|+|b_n-n|\\ &<\frac{\eps}{2}+\frac{\eps}{2}=\eps \end{aligned} $$ as required. \noindent {\bf (II)} We prove $\lim_{n\to\infty} a_nb_n = ab$. Choose $\eps>0$. By hypothesis there exists $N_0$,$N_1$,$N_2$ such that $$ \begin{aligned} n>N_0&\implies |a_n-a|<1,\\ n>N_1&\implies |b_n-b|<\frac{\eps}{2(|a|+1)},\\ n>N_2&\implies |a_n-a|<\frac{\eps}{2|b|}. \end{aligned} $$ Let $N=\max(N_0,N_1,N_2)$. Then for $n>N$ we have $$ \begin{aligned} |a_nb_n-ab|&=|a_n(b_n-b)+(a_n-a)b|\\ &\le |a_n|\,|b_n-b|+|a_n-a|\,|b|\\ &<(|a|+1)|b_n-b|+|a_n-a|\,|b|\\ &< (|a|+1)\frac{\eps}{2(|a|+1)}+\frac{\eps}{2|b|}|b|\\ &=\frac{\eps}{2}+\frac{\eps}{2}=\eps. \end{aligned} $$ \noindent {\bf (III)} We prove $\lim_{n\to\infty} 1/b_n = 1/b$ if $b\ne 0$. Choose $\eps>0$. By hypothesis there exists $N_1$ such that for $n>N_1$ we have that $|b_n-b|<\tfrac12|b|$ (and hence that $\tfrac12|b|<|b_n|$) and there exists $N_2$ such that $|b_n-b|< \eps\tfrac12|b|^2$. Then for $n>\max(N_1,N_2)$ we have $$ \left|\frac1{b_n}-\frac1{b}\right|=\frac{|b_n-b|}{|bb_n|}<\frac{|b_n-b|}{\tfrac12|b|^2}<\eps. $$ \noindent {\bf (IV)} That $\lim_{n\to\infty} a_n/b_n = a/b$ follows immediately from~(II) and~(III) by substituting $1/b_n$ for $b_n$ and $1/b$ for $b$ \fi \end{proof} \dfn\label{dfn:monotonic} A real valued function $f$ defined on a subset of the real numbers $\R$ is called \begin{description} \item[] \jdef{increasing} iff $x_1 < x_2\implies f(x_1)< f(x_2)$, \item[] \jdef{decreasing} iff $x_1 > x_2\implies f(x_1)> f(x_2)$ , \item[] \jdef{monotonic} iff it is either increasing or decreasing. \end{description} \nfd \rmk If $<$ is replaced by $\le$ in this definition, the meaning changes: a constant function satisfies the modified definition. When we want to use the weaker form we use the term \jdef{nondecreasing} instead of {\em increasing}, the term \jdef{nonincreasing} instead of {\em decreasing}, and the term \jdef{weakly monotonic} instead of {\em monotonic}. Thus in freshman calculus it is correct to say that {\em a differentiable function is nondecreasing if and only if its derivative is everywhere nonnegative} but incorrect to say that {\em a differentiable function is increasing if and only if its derivative is everywhere positive}. (If $f(x)=x^3$, then $f$ is increasing but $f'(0)=0$.) To avoid this confusion some authors insert the word \jdef{strictly} in~\ref{dfn:monotonic}. \kmr \begin{theorem} \label{thm:monotone_sequence} A bounded weakly monotonic sequence is convergent. In fact $$ \lim_{n\to\infty}a_n=\sup_n a_n $$ if the sequence $(a_n)_n$ is nondecreasing, and $$ \lim_{n\to\infty}a_n=\inf_n a_n $$ if the sequence $\{a_n\}$ is nonincreasing. (See~\ref{def:glb}.) \end{theorem} \begin{proof} (Compare Buck page~47 or Lang page~35 or Morgan page~38.) In this proof we use the completeness axiom~\ref{completeness_axiom} for the first time. Assume that the sequence $(a_n)_n$ is nondecreasing and let $a=\sup\{a_n:n\in\N\}$. Then $a_n\le a$ for all $n$ as $a$ is an upperbound for the set $\{a_n:n\in\N\}$. Choose $\eps>0$. Then $a-\epsN$ we have $a_N\le a_n$ as the sequence $(a_n)_n$ is nondecreasing so $$ a-\epsN$ as required. The nonincreasing case is proved by an analogous argument, or alternatively by applying the nondecreasing case to the seqeunce $(-a_n)_n$. \end{proof} \para We introduce some handy notation. For any sequence $(a_k)_k$ of real numbers we have $ \{a_k:k\ge n\}\subseteq\{a_k:k\ge m\}$ for $mN(\eps)$ then in particular we have $|p_{n_k}-p|<\eps$ for $k>N(\eps)$. \kmr \begin{theorem}[\jdef{Bolzano-Weierstrass}]\label{thm:BolzanoWeierstrass} Every bounded sequence in $\R^m$ has a convergent subsequence. \end{theorem} \begin{proof} Compare Buck Theorem~22 page~62 or Lang page~38-39 or Morgan~page~38. We first do the case $m=1$. Let $(a_n)_n$ be a bounded sequence of real numbers. Then there is a number $M$ such that $-m\le a_n\le M$ for all $M$. For each $n$ define $$ A_n:=\{a_{n+1},a_{n+2},\ldots,\}, \qquad b_n:=\inf A_n. $$ Since $A_n\subset A_{n+1}$ we have that $b_n\le b_{n+1}$ so the sequence $(b_n)_n$ converges to its supremum $b:=\sup\{b_n\}:=\liminf_n a_n$. We will show that a subsequence of the sequence $(a_n)_n$ also converges to $b$. For $n\in\N$ we have that $b_n0$ there is an $N=N(\eps)$ such that $|b_n-b|<\eps/2$ for $n>N(\eps)$. Hence for $n>\max(2/\eps,N(\eps)$ we have that $ |c_n-b|\le |c_n-b_n|+|b+n-b| n_k$ as required. (The further subsequence still converges by Remark~\ref{rmk:subsequence}. Now we prove the theorem for a sequence of points in $\R^m$ by induction on $m$. Assume the theorem holds for $\R^m$ and choose a bounded sequence $(p_n)_n$ of points in $\R^{m+1}$. Then $p_n=(q_n,a_n)$ where $q_n\in\R^m$ and $a_n\in\R$. That the sequence $(p_n)_n$ is bounded means that there is an $M$ such that $|p_n|\le M$ for all $n$, As $|p_n|^2=|q_n|^2+a_n^2$ it follows that $|q_n|\le M$ and $|a_n|\le M$ for all $n$, i.e. the sequence $(q_n)_n$ and $(a_n)_n$ are also bounded. By the inductive hypothesis the sequence $(q_n)_n$ has a subsequence $(q_{n_k})_k$ converging to $q$. By replacing the sequence $(p_n)_n$ by the sequence $(p_{n_k})_k$ we may assume that the sequence $(q_n)_n$ converges. (Remark~\ref{rmk:subsequence}.) Now by the case $m=1$ (already proved) the sequence $(a_n)_n$ contains a convergent subsequence $(a_{n_k})_k$. Hence $$ \lim_{k\to\infty} q_{n_k}=q, \qquad \lim_{k\to\infty} a_{n_l}=a. $$ By the triangle inequality $|(q',a')-(q,a)|\le|q'-a|+|a'-a|$ so $$ \lim_{k\to\infty}p_{n_k}=\lim_{k\to\infty}(q_{n_k},a_{n_k})= (q,a) $$ as required. \end{proof} \begin{corollary}\label{cor:sequentially_compact} For a subset $S\subseteq\R^m$ the following conditions are equivalent. \begin{description} \item[(1)] For every sequence $(p_n)_n$ of points of $S$ there is a subsequence $(p_{n_k})_k$ which converges to $p\in S$. \item[(2)] The set $S$ closed and bounded. \end{description} \end{corollary} \begin{proof} Assume~(1). The certainly every convergent sequence $p_n\in S$ has limit in $S$ so $S$ is closed by Theorem~\ref{thm:sequentially_closed}. Also $S$ is bounded as otherwise for every $n$ there would be a point $p_n\in S$ with $|p_n|>n$ and this sequence cannot have a convergent subsequence. Conversely assume~(2) and let $(p_n)_n$ be a sequence of points in $S$. As $S$ is bounded there is a convergent subsequence (by Theorem~\ref{thm:BolzanoWeierstrass}) and as $S$ is closed the limit of this subsequence is a point of $S$ (by Theorem~\ref{thm:sequentially_closed}). \end{proof} \begin{corollary} \label{cor:BolzanoWeierstrass} Every bounded infinite subset of $\R^m$ has an accumulation point. \end{corollary} \begin{proof} By Theorem~\ref{thm:BolzanoWeierstrass} and Proposition~\ref{prop:accumulation_infinitely_many}. \end{proof} \rmk The image\footnote{ Buck calls the set $S$ the \jdef{trace} of the sequence, but that terminology is uncommon. } of the sequence $(p_n)_{n\in\N}$ (when viewed as a map $n\mapsto p_n$) is the set $$ S=\{p_n:n\in\N\}. $$ The set $S$ can be finite. For example for the sequence $p_n=(-1)^n$, the set $S$ is the two element set $S=\{-1,1\}$. If the image of a sequence is finite then there must be at least one constant subsequence and a constant subsequence is trivially convergent. By definition only an infinite set can have an accumulation point. \kmr \dfn \label{dfn:cauchy} A sequence $\{p_n\}$ is called \jdef{Cauchy} iff $$ \lim_{m,n\to\infty} |p_n-p_m|=0 $$ i.e. iff for every $\eps>0$ there exists $N>0$ such that $|p_n-p_m|<\eps$ for $n,m\ge N$. \nfd \begin{theorem}[\jdef{Cauchy Convergence Criterion}] \label{thm:Cauchy-sequence} A sequence in $\R^n$ converges if and only if it is a Cauchy sequence. \end{theorem} \begin{proof} \note{(Buck Theorem~23 and its corollary on pages~62-63.)} \end{proof} \section{Continuity} Throughout this chapter $f:X\to Y$ where $X\subseteq\R^n$ and $Y\subseteq\R^m$. \dfn \label{def:continuous} The map $f$ is said to be \jdef{continuous} at a point $p\in X$ iff for every $\eps>0$ there exists $\delta>0$ such that $f(B_X(p,\delta))\subseteq B(f(p),\eps)$. \nfd \begin{theorem}\label{thm:seq-cont} The map $f$ is continuous at $p\in X$ if and only if for every sequence $\{p_n\}$ of points in $X$ we have %% \begin{equation}\label{eq:limpif} \lim_{n\to\infty}p_n=p\implies \lim_{n\to\infty}f(p_n)=f(p). \end{equation} \end{theorem} \begin{proof} {\em We prove `only if'.} Assume $f$ is continuous at $p$. Choose sequence $\{p_n\}$ of points in $X$. Assume % \begin{equation}\label{eq:limp} \lim_{n\to\infty}p_n=p. \end{equation} % Choose $\eps>0$. Because $f$ is assumed to be continuous at $p$ there is a $\delta>0$ such that for all $q\in X$ % \begin{equation}\label{eq:imp} |q-p|<\delta\implies |f(q)-f(p)|<\eps. \end{equation} % By~(\ref{eq:limp}) there is an $N$ such that $|p_n-p|<\delta$ for $n>N$. Hence by~(\ref{eq:imp}) $|f(p_n)-f(q)|<\eps$ for $n>N$. This proves %% \begin{equation}\label{eq:limf} \lim_{n\to\infty} f(p_n)=f(p). \end{equation} as required. {\em We prove `if'.} Assume that $f$ is not continuous at $p\in X$. Then there is an $\eps>0$ such that for every $\delta>0$ there is a $q\in X$ such that $$ |q-p|<\delta\mbox{ but } |f(q)-f(p)|\ge\eps. $$ In particular, for each $n\in\Z^+$ there is a $q_n$ such that $$ |q_n-p|<\frac1n \mbox{ but } |f(q_n)-f(p)|\ge\eps. $$ But then~(\ref{eq:limp}) holds but~(\ref{eq:limf}) fails. This proves that~(\ref{eq:limpif}) is false as required. \end{proof} \dfn\label{def:pointwise_and_uniform_contnuity} The map $f$ is said to be \jdef{continuous} iff it is continuous at every point of $X$, i.e. iff $$ \forall p\in X\;\forall \eps>0\;\exists\delta>0 \mbox{ such that } f(B(p,\delta))\subseteq B(f(p),\eps). $$ The map $f$ is said to be \jdef{uniformly continuous} iff $$ \forall \eps>0\;\exists\delta>0\; \mbox{ such that } \forall p\in X \mbox{ we have } f(B(p,\delta))\subseteq B(f(p),\eps). $$ (For continuity $\delta=\delta(p,\eps)$; for uniform continuity $\delta=\delta(\eps)$.) \nfd \begin{proposition} If $f:X\to Y$ and $g:Y\to Z$ are both continuous, then so is the composition $g\circ f:X\to Z$. \end{proposition} \begin{proof} Choose $p_0\in X$ and $\eps>0$. As $g$ is continuous there exists $\eta>0$ such that $|g(q)-g(f(p_0))|<\eps$ whenever $q\in Y$ and $|q-f(p_0)|<\eta$. As $f$ is continuous, there exists $\delta>0$ such that $|f(p)-f(p_0)|<\eta$ whenever $p\in X$ and $|p-p_0|<\delta$. For $p\in X$ we have $q=f(p)\in Y$ so $$ |p-p_0|<\delta\implies |f(p)=f(p_0)|<\eta\implies |(g\circ f)(p)-(g\circ f)(p_0)|<\eps $$ as required. \end{proof} \para The map $f$ is said to be \jdef{Lipschitz} iff there is a constant $M$ such that $$ |f(p)-f(q)|\le M|p-q| $$ for all $p,q\in X$. A Lipschitz function is uniformly continuous. (Proof: $\delta=\eps/M$.) \arap \prob Let $f(x)=x^p$. Show that $f$ is Lipschitz on every closed interval $[a,b]\subseteq(0,\infty)$. For which values of $p$ is $f$ uniformly continuous on $(0,\infty)$? Hint: Use the Mean Value Theorem from calculus. (See Theorem~\ref{thm:MVT} below.) Theorem~\ref{thm:compact-uniform} below may also help. \borp %\part{Topology} \section{Open Sets and Closed Sets} In all the following definitions the term {\em set} means {\em subset of}\, $\R^m$. \dfn \label{def:open} A set $U$ is \jdef{open} iff for every $p\in U$ there exists a $\delta>0$ such that $B(p,\delta)\subseteq U$. \nfd \prob\label{prob:ball_open} Prove that the ball $B(p,\delta)$ is open. Hint: You must choose an arbitrary $q\in B(p,\delta)$ and then find an $\eta>0$ so that $B(q,\eta)\subseteq B(p,\delta)$. Use the triangle inequality. \borp \begin{theorem}\label{thm:open} The collection of all open sets in $\R^m$ satisfies the following conditions: \begin{description} \item[(i)] The set $\R^m$ and the empty set $\emptyset$ are both open. \item[(ii)] The intersection of a finite collection of open sets is open. \item[(ii)] The union of an arbitrary collection of open sets is open. \end{description} \end{theorem} \begin{proof} The set $\R^m$ is open because $B(p,1)\subseteq\R^m$ for $p\in\R^m$. The empty set is open because for every $p\in\emptyset$ satisfies the required condition -- or any other condition -- since {\em `false $implies$ anything' is true}. See~\ref{if_P_then_Q}). To prove~(ii) assume $U$ is open. Then for every point $p\in U$ there is a $\delta=\delta_p$ such that $B(p,\delta_p)\subseteq U$.\footnote{ This is actually an example of an application of the Axiom of Choice. See Remark~\ref{rmk:axiom_of_choice}. } It follows that $$ U=\bigcup_{p\in U} B(p,\delta_p), \eqno(*) $$ i.e. that $U$ is an union of balls. A union of unions is a union: $$ \bigcup_{i\in I}\bigcup_{j\in I_j} B_{ij}=\bigcup_{(i,j)\in K} B_{ij}, \qquad K:=\{(i,j): i\in I,\; j\in I_j\} $$ so~(ii) follows. To prove~(iii) assume that $U_1,U_2,\ldots U_m$ are open and choose an arbitrary point $p\in\bigcap_{i=1}^m U_i$. Then $p\in U_i$ so there is a $\delta_i>0$ with $B(p,\delta_i)\subseteq U_i$. Let $\delta=\min(\delta_1,\ldots,\delta_m)$. Then $$ B(p,\delta)\subseteq \bigcap_{i=1}^m B(p,\delta_i)\subseteq \bigcap_{i=1}^m U_i $$ as required. \end{proof} \dfn A set $W\subseteq X$ is called \jdef{relatively open} in $X$ iff for every $p\in W$ there exists a $\delta>0$ such that $B_X(p,\delta)\subseteq W$. (See~\ref{def:open_ball}.) \nfd \rmk\label{rmk:relative} A set $U\subseteq\R^m$ is open if and only if it is relatively open in $\R^m$. For this reason many theorems can be generalized by systematically replacing $\R^m$ by $X$, $B(p,\delta)$ by $B_X(p,\delta)$, and the word {\em open} by the phrase {\em relatively open in $X$}. In Math~551 you will learn to generalize further by replacing $\R^n$ by something called a {\em topological space}. \kmr \begin{corollary} A set $W$ is relatively open in $X$ if and only if $W=X\cap U$ for some open set $U\subset \R^n$. \end{corollary} \begin{proof} Equation~$(*)$ in the last proof and the distributive law from~\ref{demorgan_and_distributive}. %and in the proof of Theorem~\ref{thm:open}. \end{proof} \begin{proposition} A map $f:X\to $Y is continuous if and only if the inverse image $f^{-1}(V)$ of every relatively open subset $V$ of $Y$ is a relatively open subset of $X$. \end{proposition} \begin{proof} Exercise. \end{proof} \begin{corollary} Assume that $f:X\to Y$ and $g:Y\to Z$ are continuous. Then $g\circ f:X\to Z$ is continuous. \end{corollary} \begin{proof} Exercise. Hint: Prove that $(g\circ f)^{-1}(W)=f^{-1}\bigl( g^{-1}(W)\bigr)$. \end{proof} \dfn A set $X$ is \jdef{closed} iff its complement $\R^n\setminus X$ is open. \nfd \begin{corollary}\label{cor:closed} The collection of all closed sets in $\R^n$ satisfies the following conditions: \begin{description} \item[(i)] The set $\R^n$ and the empty set $\emptyset$ of both closed. \item[(ii)] The intersection of an arbitrary collection of closed sets is closed. \item[(iii)] The union of a finite collection of closed sets is closed. \end{description} \end{corollary} \begin{proof} Apply the De Morgan laws from~\ref{demorgan_and_distributive} to Theorem~\ref{thm:open}. \end{proof} \begin{theorem}\label{thm:sequentially_closed} A set $S$ is closed if and only if it is closed under limits of sequences, i.e. whenever $\lim_{n\to\infty} p_n=p$ and each $p_n\in S$ we have $p\in S$. \end{theorem} \begin{proof} \note{(See Buck Theorem~5 page~40.)} To prove {\em only if} assume that $S$ is closed, that $\lim_{n\to\infty} p_n=p$, and that each $p_n\in S$. If $p\notin S$ then $p\in\R^m\setminus S$. As this set is open there is a $\delta>0$ such that $B(p,\delta)\subset \R^m\setminus S$. As the sequence converges to $p$ there is an $N$ such that $p_n\in B(p,\delta)$ for $n>N$ contradicting the hypothesis that $p_n\in S$. To prove {\em if} assume that $S$ is not closed. Then $\R^m\setminus S$ is not open so there is a point $p\in\R^m\setminus S$ such that $B(p,\delta)\not\subseteq \R^m\setminus S$ for every $\delta>0$. In particular for $\delta=1/n$ there is a point $p_n\in B(p,1/n)$ (i.e. $|p_n-p|<1/n$) such that $p_n\notin \R^m\setminus S$, i.e. $p_n\in S$. Thus $\lim_{n\to\infty}p_n=p$ and $p\notin S$ as desired. \end{proof} \para Let $S\subseteq\R^n$. For any point $p\in\R^n$ exactly one of the following alternatives holds: \begin{description} \item[(i)] $B(p,\delta)\subseteq S$ for some $\delta>0$. \item[(ii)] $B(p,\delta)\subseteq \R^n\setminus S$ for some $\delta>0$. \item[(iii)] $B(p,\delta)\cap S\ne\emptyset$ and $B(p,\delta)\cap (\R^n\setminus S)\ne\emptyset$ for all $\delta>0$. \end{description} The \jdef{interior} of $S$ is the set $\mathrm{int}(S)$ of all points $p$ where~(i) holds, the \jdef{exterior} of $S$ is the set $\mathrm{ext}(S)$ of all points $p$ where~(ii) holds, and the \jdef{boundary} of a set $S$ is the set $\mathrm{bdry}(S)$ of all points $p$ where~(ii) holds. The ambient space $\R^n$ may be written as the pairwise disjoint union $$ \R^n=\mathrm{int}(S)\cup\mathrm{ext}(S)\cup\mathrm{bdry}(S). $$ The notations $$ \stackrel{\circ}{S}\;:=\mathrm{int}(S),\qquad \partial S := \mathrm{bdry}(S) $$ are commonly used. \arap \xmpl For the half open interval $S=[a,b)\subseteq\R$ we have $$ \mathrm{int}(S)=(a,b),\qquad \mathrm{ext}(S)=(-\infty,a)\cup (b,\infty),\qquad \mathrm{bdry}(S)=\{a,b\}. $$ \lpmx \dfn A set $S\subseteq\R^n$ is \jdef{closed} iff its complement $\R^n\setminus S$ is open. The \jdef{closure} of the set $S$ is the set $$ \mathrm{cl}(S):=\bar{S}:=S\cup\mathrm{bdry}(S). $$ \nfd \begin{proposition} The interior $\mathrm{int}(S)$ of $S$ is the largest open set contained in $S$ and closure $\bar{S}$ of $S$ is the smallest closed set containing $S$. \end{proposition} \begin{proof} Exercise. Hint: You must show %\begin{description} %\item[(i)] (1a)~$\mathrm{int}(S)$ is open, (1b)~$\bar{S}$ is closed, %\item[(ii)] (2a)~$\mathrm{int}(S)\subseteq S$, (2b)~$S\subseteq\bar{S}$, %\item[(iii)] (3a)~if $U$ is open and $U\subseteq S$ then $U\subseteq \mathrm{int}(S)$, and (3b)~if $T$ is closed and $S\subseteq T$ then $\bar{S}\subseteq T$. %\end{description} \end{proof} \prob \label{prob:Q^m_dense} Prove that if $U\subseteq\R^m$ is an open set and $p\in U$, then there is a point $q$ with rational coordinates and a positive rational number $\delta$ such that $p\in B(q,\delta)\subseteq U$. \borp %\iffalse \iftrue \noindent{\bf Solution.} As $U$ is open there is an $r>0$ such that $B(p,r)\subseteq U$. Let $p_i$ denote the $i$th coordinate of $p$ so that $p=(p_1,p_2,\ldots,p_m)$. By Problem~\ref{prob:Q_dense} there are rational numbers $q_1,q_2,\ldots,q_m$ such that $$ p_i-\frac{r}{2m}0$ with $(a-\eps,a+\eps)\subseteq U$. Making $\eps$ smaller we also have $a+\eps0$ with $(b-\eps,b+\eps)\subseteq V$. Making $\eps$ smaller we also have $a0$ with $a0$ with $a0,\\ 0 & \mbox{ if } x\le 0. \end{array}\right. $$ This function is not continuous as follows. Let $x_n=(2n\pi+\pi/2)^{-1}$. Then $f(x_n)=1$, $\lim_{n\to\infty}x_n=0$, but $\lim_{n\to\infty} f(x_n)=1\ne 0=f(0)$. However, the graph of $f$ is connected. To see this suppose $U$ and $V$ are open subsets of $\R^2$ and $\mathrm{graph}(f)\subseteq U\cup V$ with $U\cup V=\emptyset$. Suppose that $(0,0)\in U$. Then $(x,f(x))\in U$ for $x\le 0$ as $f$ is continuous on $(-\infty,0]$ and $(x,f(x))\in U$ in $U$ for $x>0$ as $f$ is continuous on $(0,\infty)$. But then $\mathrm{graph}(f)\subset U$ so $\mathrm{graph}(f)\cap V=\emptyset$. \lpmx \section{Compact Sets} \dfn An \jdef{open cover} of a set $S$ is a collection $(U_\alpha)_{\alpha\in A}$ of open sets such that $S\subseteq \bigcup_{\alpha\in A} U_\alpha$. The subset $S$ is \jdef{compact} iff every open cover $(U_\alpha)_{\alpha\in A}$ of $S$ has finite subcover, i.e. there are indices $\alpha_1,\alpha_2,\ldots,\alpha_n\in A$ such that $S\subseteq U_{\alpha_1}\cup U_{\alpha_2}\cup\cdots \cup U_{\alpha_n}$. \nfd \begin{theorem}[\jdef{Heine Borel}]\label{thm:HeineBorel} The following are equivalent conditions on a set $S\subseteq\R^m$: \begin{description} \item[(1)] For every sequence $(p_n)_n$ of points of $S$ there is a subsequence $(p_{n_k})_k$ which converges to $p\in S$. \item[(2)] The set $S$ closed and bounded. \item[(3)] The set $S$ is compact. \end{description} \end{theorem} \begin{proof} \note{(This is Theorem~9.2 on page~41 of Morgan. See also Buck Theorem~25 page~65.)} The equivalence of~(1) and~(2) is Corollary~\ref{cor:sequentially_compact}. {\em We prove (3)$\implies$(2).} Assume that~(2) is false. Then either $S$ is not closed or $S$ is not bounded. In the former case by Theorem~\ref{thm:sequentially_closed} there is a convergent sequence of points $p_n\in S$ whose limit $p:=\lim_{n\to\infty}p_n$ is not in $S$. This implies $S\subseteq \R^m\setminus\{p\}=\bigcup_{k=1}^\infty U_k$ where $U_k:=\{q\in\R^m: |q-p|>1/k\}$. The sets $U_k$ are open but we cannot have $S\subseteq U_\cup U_2\cup\cdots \cup U_N$ as as $U_1\subseteq U_2\subseteq\cdots\subseteq U_N$ and $p_n\notin U_N$ for $n>N$ so we have an open cover of $S$ with no finite subcover so $S$ is not compact. In the latter case the open balls $V_n:=B(0,n):=\{q\in\R^m: |q|0 \mbox{ and } B(q,\delta)\subseteq U_\alpha\mbox{ for some }\alpha\in A\} $$ of open balls with rational center and rational radius which are contained in some element of the open cover. For every point $p\in S$ there is an $\alpha\in A$ with $p\in U_\alpha$ (because the sets $U_\alpha$ cover $S$), and so by Problem~\ref{prob:Q^m_dense} there is a point $q\in\Q^m$ so that $p\in B(q,\delta)\subseteq U_\alpha$. In other words there is a point $(q,\delta)\in I$ with $p\in B(q,\delta)$. We have proved that $$ S\subseteq\bigcup_{(q,\delta)\in I} B(q,\delta). $$ The set $I$ is countable because $I$ is a subset of the countable set $\Q^m\times\Q$. Let $V_1,V_2,V_3,\ldots$ be an enumeration of the sets $(B(q,\delta))_{(q,\delta)\in I}$. By construction each $V_i$ is a subset of some $U_\alpha$. Hence if finitely many of the sets $V_i$ cover $S$ so do finitely many of the sets $U_\alpha$ from the original cover. But~(1) implies that finitely many of the sets $V_i$ cover $S$. If not, we have $S\not\subseteq V_1\cup V_2\cup\cdots\cup V_n$ for all $n$ so for each $n$ there is a point $p_n\in S\setminus(V_1\cup V_2\cup\cdots\cup V_n)$. By condition~(1) the sequence $(p_n)_n$ contains a subsequence $(p_{n_k})_k$ converging to a point $p\in S$. The point $p$ lies in some set $V_i$ and this set must contain $p_{n_k}$ for sufficiently large $k$ which is a contradiction if $n_k>i$. \end{proof} \begin{corollary} The closed interval $[a,b]$ is compact. \note{(Buck Theorem~24 page~65.)} \end{corollary} \begin{theorem}\label{thm:compact-uniform} Assume that $X$ is compact and $f$ is continuous. Then $f$ is uniformly continuous. \end{theorem} \begin{proof} Choose $\eps>0$. Then, because $f$ is continuous, for every $p\in X$ there is a $\delta=\delta(p)>0$ such that $$ |q-p|<\delta(p)\implies |f(q)-f(p)|<\frac\eps2. $$ Let $U_p:=B(p,\delta(p)/2)$. The sets $U_p$ cover $X$ (since $p\in U_p$), i.e. $X\subseteq\bigcup_p U_p$. As $X$ is compact, finitely many of these sets cover $X$, i.e. %% \begin{equation}\label{eq:cover} X\subseteq U_{p_1}\cup U_{p_2}\cup\cdots\cup U_{p_n}. \end{equation} %% Define $$ \delta:=\tfrac12\min\{\delta(p_1),\delta(p_2),\ldots, \delta(p_n)\}. $$ Choose $p,q\in X$. Assume $|q-p|<\delta$. By~(\ref{eq:cover}) we have that $p\in U_{p_k}$ for some $k$. Hence %% \begin{equation}\label{eq:ppk} |p-p_k|<\delta(p_k)/2. \end{equation} %% But $\delta\le\delta(p_k)/2$ by its definition so %% \begin{equation}\label{eq:qpk} |q-p_k|\le |q-p|+|p-p_k|\le \delta+\frac{\delta(p_k)}{2} \le \frac{\delta(p_k)}{2}+\frac{\delta(p_k)}{2}=\delta(p_k). \end{equation} %% Hence, by the definition of $\delta(\cdot)$ and Equations~(\ref{eq:ppk}) and~(\ref{eq:qpk}) we have $$ |f(p)-f(q)|\le |f(p)-f(p_k)|+|f(q)-f(p_k)|<\frac\eps2+\frac\eps2=\eps $$ as required. \end{proof} \rmk A proof using the Bolzano-Weierstrass theorem instead on the Heine-Borel theorem is given in Buck page~85. The proof given here is like the proof sketched in Exercises~11 and~12 in Buck page~89. \kmr \begin{theorem}\label{thm:cont-cpct} The continuous image of a compact set is compact: If $f:X\to\R^m$ is continuous and $X$ is compact, then $f(X)$ is compact. \end{theorem} \begin{proof} See Buck Theorem~13 on page~93 or \end{proof} \begin{corollary} The continuous image of compact set is bounded. \end{corollary} \begin{proof} See Buck Theorem~10 on page~90 or \end{proof} \begin{theorem} If $f:X\to\R$ is continuous and $X$ is compact, then $f$ assumes its maximum on $X$, i.e. there exists $p\in X$ such that $f(q)\le f(p)$ for all $q\in X$. Similarly for the minimum. \end{theorem} \begin{proof} See Buck Theorem~11 page~91 or \end{proof} \begin{theorem}\label{thm:continuous_bijection} Let $f:X\to Y$ be bijective and continuous, and assume $X$ (and hence by Theorem~\ref{thm:cont-cpct} also $Y$) is compact. Then $f^{-1}:Y\to X$ is continuous. \end{theorem} \begin{proof} Choose a convergent sequence $(q_n)_n$ in $E$ and a let $$ q:=\lim_{n\to\infty}q_n $$ be its limit. We will show that $$ f^{-1}(q)=\lim_{n\to \infty} f^{-1}(q_n);\eqno(\#) $$ the theorem will then follow by Theorem~\ref{thm:seq-cont}. By Bolzano Weierstrass and Heine Borel there is a convergent subsequence $(f^{-1}(q_{n_k}))_k$. Let $$ p:=\lim_{k\to\infty}f^{-1}(q_{n_k}) $$ be its limit. Now $f$ is assumed to be continuous so $$ f(p)=f\left(\lim_{k\to\infty}f^{-1}(q_{n_k})\right) =\lim_{k\to\infty}f(f^{-1}((q_{n_k})) = \lim_{k\to\infty}q_{n_k} = q. $$ But $f(p)=q\implies p=f^{-1}(q)$ so $f^{-1}(q)=\lim_{k\to\infty}f^{-1}((q_{n_k})$. If~$(\#)$ fails, then there is a neighborhood $U$ of $f^{-1}(q)$ such that for every $N$ there exists $n>N$ with $f^{-1}(q_n)\notin U$, i.e. there is a subsequence $f^{-1}(q_{m_j})$ with $f^{-1}(q_{m_j})\notin U$. As before choose a further subsequence (again denoted $f^{-1}(q_{m_j})$ which converges and let $$ p':=\lim_{j\to\infty}f^{-1}(q_{m_j}) $$ denote the limit. Then $p'\notin U$ (else we would have $f^{-1}(q_{m_j})\in U$ for sufficiently large $j$) so $p'\ne p$. But as before $$ f(p')=f\left(\lim_{j\to\infty}f^{-1}(q_{m_j})\right) =\lim_{j\to\infty}f(f^{-1}(q_{m_j})) = \lim_{j\to\infty}q_{m_j} = q. $$ But now $f(p)=q=f(p')$ which contradicts the fact that $f$ is injective. \end{proof} \begin{theorem}\label{thm:extend} Let $S\subseteq\R^n$ be and $f:S\to\R^m$ be uniformly continuous.Then the function $f$ can be continuously extended to the closure $\bar{S}$ of $S$. i.e. there is a continuous function $F:\bar{S}\to \R^m$ such that $F(p)=f(p)$ for $p\in S$. \end{theorem} \begin{proof} \note{(Buck Theorem~25 on page~109.)} \end{proof} \xmpl The function $f:(0,1]\to\R$ defined by $f(x)=\sin(1/x)$ cannot be extended to a continuous function on the closure $[0,1]$ of $(0,1]$. \lpmx \section{Derivatives} \dfn The function $f:I\to\R$ is said to be \jdef{differentiable} at the point $x_0\in I$ iff the limit $$ f'(x_0):= \lim_{x\to x_0}\frac{f(x)-f(x_0)}{x-x_0} $$ exists; we say that $f$ is differentiable on a set iff it is differentiable at each point $x_0$ in the set. The function $f'$ is called the \jdef{derivative} of $f$. \nfd \begin{theorem} A differentiable function is continuous. \end{theorem} \begin{theorem} If $I$ is an open interval, $f:I\to\R$ is differentiale on $I$, and $f$ assumes its maximum (or minimum) at $c\in I$ then $f'(c)=0$. \end{theorem} \begin{theorem}[\jdef{Mean Value Theorem}]\label{thm:MVT} Suppose that $f$ is differentiable of $(a,b)$ and continuous on $[a,b]$. The there exists $c\in(a,b)$ such that $$ f'(c)=\frac{f(b)-f(a)}{b-a}. $$ \end{theorem} \begin{corollary} Assume that $f$ is differentiable on $I$. Then the derivative $f'$ vanishes identically on $I$ if and only if $f$ is constant on $I$. \end{corollary} \prob{\em The Intermediate Value Theorem for Derivatives.} Assume that $f$ is differentiable on an open interval $I$, that $a,b\in I$ with $a0$ there is a $\delta>0$ such that for every partition $P$ whose mesh is less than $\delta$ we have} $$ \overline{S}(f,P)<\underline{S}(f,P)+\eps. $$ To see this choose $\eps>0$. By Theorem~\ref{thm:compact-uniform} there is a $\delta>0$ such that $|f(x)-f(x')|<\eps/(b-a)$ whenever $|x-x'|<\delta$. If the partition $P$ has mesh less than $\delta$ it follows that $\overline{y}_k\le\underline{y}_k +\eps/(b-a)$ for $k=1,2,\ldots,n$. The desired inequality follows by multiplying by $x_k-x_{k-1}$ and summing on $k$. (Use the collapsing sum from Step~1.) \medskipnoindent{\bf Step 4.} {\em Given any two partitions of the interval $[a,b]$ there is a third partition which refines both of them.} To construct this third partition we simply take the union of the underlying sets of the two partitions and list the elements of this union in increasing order. \medskipnoindent{\bf Step 6.} {\em $\underline{S}(f,P')\le\overline{S}(f,P'')$ for {\em any} two partitions $P'$ and $P''$ of the interval $[a,b]$.} This is because by Step~4 the partitions $P'$ and $P''$ have a common refinement $P$ so Step~2 we have $$ \underline{S}(f,P')\le \underline{S}(f,P)\le\overline{S}(f,P)\le\overline{S}(f,P''). $$ \medskipnoindent{\bf Step~7.} $\sup_P\underline{S}(f,P)\le\inf_P\overline{S}(f,P)$. To see this take the supremum over $P'$ is Step~4 to get $\sup_P\underline{S}(f,P)\le\overline{S}(f,P'')$ for every $P''$. Then take the infimum over $P''$. \medskipnoindent{\bf Step 8.} {\em $\inf_P\overline{S}(f,P)\le\sup_P\underline{S}(f,P')$}. To see this choose $\eps>0$ and let $\delta>0$ be given as in Step~3. There certainly are partitions with mesh less than $\delta$, for example the partition $P_n=(x_k)_k$ with $x_k=a+k(b-a)/n$ where $n$ is so large that $(b-a)/n<\delta$. From Step~3 we conclude that $$ \inf_P\overline{S}(f,P)\le \overline{S}(f,P_n) \le \underline{S}(f,P_n)+\eps\le \sup_P\underline{S}(f,P)+\eps. $$ Step~7 follows since this inequality is true for any $\eps>0$. \medskip By Steps~6 and~7 we have that $ \sup_P\underline{S}(f,P)=\inf_P\overline{S}(f,P)$ This common value satisfies the conclusion of the theorem and is the definite integral $\int_a^bf$. \end{proof} \rmk\label{rmk:Riemann_Sum} A \jdef{Riemann sum} for a partition $P=(x_k)_k$ of the interval $[a,b]$ is a sum of form $$ S=\sum_{k=1}^n f(c_k)(x_k-x_{k-1}) $$ where $c_k\in[x_{k-1},x_k]$. Since $\underline{f}_k\le f(c_k)\le\overline{f}_k$ it follows that $$ \underline{S}(f,P)\le S\le \overline{S}(f,P) $$ for any Riemann sum for the partition $P$. It follows from the proof of Theorem~\ref{thm:darboux} that the definite integral is the limit of the Riemann sums $S$ as the mesh of the partition $P$ tends to zero, i.e. for every $\eps>0$ there exists a $\delta>0$ such that $\left|S-\int_a^bf\right|<\eps$ whenever the mesh of $P$ is less than $\delta$. In Math~221 the definite integral is usually defined as the limit of Riemann sums in this sense. \kmr \begin{theorem}\label{thm:axioms_for_the_integral} The definite integral of a continuous function satisfies the following properties. \begin{description} \item[(1)] (Normalization). $\ds\int_a^b1=b-a$. \item[(2)] (Linearity). $\ds \int_a^b (f+g)=\int_a^bf+\int_a^bg$ \item[(3)] (Linearity). $\ds\int_a^bcf=c\int_a^bf$ for $c\in\R$. \item[(4)] (Additivity). $\ds\int_a^bf+\int_b^cf=\int_a^cf$. \item[(5)] (Order). If $f(x)\le g(x)$ for all $x\in[a,b]$, then $\ds\int_a^bf\le\int_a^bg$. \item[(6)] (Triangle Inequality). $\ds\left|\int_a^bf\right|\le \int_a^b|f|$. \end{description} In~(3) $c$ is any real number, and in~(4) $a,b,c\in I$ satisfy $a\le b\le c$.\footnote{It is customary to define $\int_a^bf=-\int_b^af$ if $b0$ there is a $\delta>0$ such that $$ -\eps < \frac{F(x+h)-F(x)}{h}-f(x) < \eps $$ whenever $0<|h|<\delta$. We will only use the properties in Theorem~\ref{thm:axioms_for_the_integral} to prove this. Assume $h>0$ (the case $h<0$ is similar). Then $$ F(x+h)-F(x)= \int_a^{x+h}f-\int_a^xf=\int_x^{x+h}f $$ by property~(4). Choose $\eps>0$. By Theorem~\ref{thm:compact-uniform} $f$ is uniformly continuous so there is a $\delta>0$ such that $0a$. (The case $x1$ there will be a different value of $c$ for each component of $f$. \kmr \section{Series} \para A sequence determines a series and a series determines a sequence. More precisely, a sequence $(a_k)_k$ determines a \jdef{series} whose \jdef{partial sums} are $$ S_n=\sum_{k=1}^n a_k:=a_1+a_2+\cdots + a_n, $$ and the \jdef{terms} of the series may be recovered from the sequence of partial sums via the formula $$ a_n= S_n-S_{n-1}, \qquad a_1=S_1. $$ Convergence of the series is synonymous with convergence of the sequence of partial sums: $$ \sum_{k=1}^\infty a_k:=\lim_{n\to\infty}\sum_{k=1}^na_k. $$ Since the limit of a difference is the difference of the limits and the limit of a constant is the constant we have the useful formula $$ \sum_{k=1}^\infty a_k-\sum_{k=1}^n a_k= \sum_{k=n+1}^\infty a_k. $$ Here the notation on the right has the obvious definition, namely $$ \sum_{k=n+1}^\infty a_k:=\lim_{m\to\infty} \sum_{k=n+1}^m a_k. $$ \arap \para The notation $$ \sum_{k=1}^\infty a_k=\infty $$ means that for every $M>0$ there exists an integer $N>0$ such that $\sum_{k=1}^n a_k>M$ for $n>N$. If $a_k\ge 0$ for all $k$ then the sequence of partial sums is monotonic increasing so by Theorem~\ref{thm:monotone_sequence} either the limit $\sum_{k=1}^na_k$ exists (i.e. the sequence of partial sums is bounded) or $\sum_{k=1}^\infty=\infty$ (i.e. the sequence of partial sums is unbounded). \arap \xmpl\label{xmpl:geometric_series} The $n$th partial sum $$ \sum_{k=0}^nx^k=1+x+x^2+\cdots+x^n $$ of the \jdef{geometric series} is easy to compute: $$ (1-x)\sum_{k=0}^nx^k=\sum_{k=0}^n(x^k-x^{k+1})=1-x^{n+1} $$ (as the sum telescopes) so dividing by $(1-x)$ gives $$ \sum_{k=0}^nx^k=\frac{\;1-x^{n+1}}{\!\!\!1-x} $$ Hence if $|x|<1$ we have the formula $$ \sum_{k=0}^\infty x^k=\frac{1}{1-x} $$ for the infinite sum. \lpmx \begin{theorem}[\jdef{$n$th Term Test}] \label{thm:nth-term} If the series $\sum_ka_k$ converges, then the $n$th term converges to zero. \end{theorem} \begin{proof} (See Buck Theorem~2 page~230.) Let $S_n=\sum_{k=0}^na_k$ be the $n$th partial sum so $a_n=S_n-S_{n-1}$. If the series converges then $\lim_{n\to\infty}S_n=\lim_{n\to\infty}S_{n-1}$ so $\lim_{n\to\infty} a_n= \lim_{n\to\infty}S_n-\lim_{n\to\infty}S_{n-1}=0$. \end{proof} \xmpl (\jdef{Harmonic series}) \label{xmpl:harmonic_series} Since $$ \sum_{k=1}^\infty\frac{1}{k}= 1+\left(\frac12+\cdots\frac1{10}\right) +\left(\frac1{11}+\cdots\frac1{100}\right)+\cdots $$ and each sum in parentheses is $\ge 9/10$ we see that $\sum_{k=1}^\infty\frac{1}{k}=\infty$. But $\lim_{n\to\infty}1/n =0$ so the converse to Theorem~\ref{thm:nth-term} is false. \lpmx \begin{theorem}[\jdef{Cauchy Convergence Criterion for Series}] \label{thm:Cauchy-series} A series $\sum_k a_k$ converges if and only if $$ \lim_{m,n\to\infty}\sum_{k=m+1}^n a_k=0, $$ i.e. for every $\eps>0$ there exists $N=N(\eps)$ such that $\left|\sum_{k=m+1}^n a_k\right|<\eps$ for $n>m>N$. \end{theorem} \begin{proof} This follows immediately from the formulas $$ \sum_{k=m+1}^n a_k=S_n-S_m,\qquad S_n:= \sum_{k=1}^n a_k,\qquad \sum_{k=m+1}^n a_k:=a_{m+1}+\cdots+a_n. $$ and the Cauchy Convergence Criterion for Sequences (Theorem~\ref{thm:Cauchy-sequence}). \end{proof} \dfn The series $\sum_k a_k$ is said to \jdef{converge absolutely} iff $$ \sum_{k=1}^\infty|a_k|<\infty. $$ A series which converges but does not converge absolutely is said to \jdef{converge conditionally}. \nfd \begin{theorem} If a series converges absolutely, then it converges. \end{theorem} \begin{proof} This is an immediate consequence of the inequality $$ \left|\sum_{k=m+1}^n a_k\right|\le\sum_{k=m+1}^n|a_k| $$ and Theorem~\ref{thm:Cauchy-series}. \end{proof} \rmk Of course, if $a_k\ge 0$ then $|a_k|=a_k$ so convergence and absolute convergence coincide in this case. When $a_k\ge 0$ the sequence of partial sums is monotonic increasing so either the series converges or diverges to infinity. \kmr \begin{corollary}\label{cor:alternating_series} Assume that $a_0\ge a_1\ge a_2\cdots\ge 0$. Then the series $\sum_k(-1)^ka_k$ converges if and only if $\lim_{n\to\infty}a_n=0$. (A series like this whose terms alternate sign is called an \jdef{alternating series}.) \end{corollary} \begin{proof} ``Only if'' follows by the $n$th Term Test (Theorem~\ref{thm:nth-term}). For ``if'' assume that $\lim_{n\to\infty}a_n=0$ and let $$ S_n:= \sum_{k=0}^n (-1)^ka_k $$ denote the $n$th partial sum. Then the sequence $$ S_{2m+1} = \sum_{k=0}^m (a_{2k}-a_{2k+1}) $$ is monotonic non decreasing (since ($a_{2k}-a_{2k+1}\ge 0$) so it either converges or tends to infinity. But the latter cannot happen as $$ S_{2m+1} = a_0 -\sum_{k=0}^{m-1} (a_{2k+1}-a_{2k+2}) -a_{2m+1} \le a_0-a_{2m+1} $$ and the sequence $(a_{2m+1})_m$ is bounded (as it converges to zero). Hence the sequence $(S_{2m+1})_m$ converges by Theorem~\ref{thm:monotone_sequence}. But the sequence $(S_{2m})_m$ converges to the same limit as $S_{2m+1}=S_{2m}+a_{2m+1}$ and we have assumed that $\lim_{n\to\infty} a_n=0$. Hence the sequence $(S_n)_n$ converges as claimed. \end{proof} \xmpl (\jdef{Alternating harmonic series}) \label{xmpl:alternating_harmonic_series} We will see later (see Remark~\ref{rmk:boundary_of_interval_of_convergence}) that $$ -\ln2=\sum_{k=1}^\infty \frac{(-1)^k}{k}. $$ The convergence is conditional but (by~Example~\ref{xmpl:harmonic_series}) not absolute. \lpmx \begin{theorem}[\jdef{Comparison Test}] \label{thm:comparison_test} If $0\le a_k\le b_k$ for sufficiently large $k$ and the series $\sum_kb_k$ converges, then the series $\sum_ka_k$ does. \end{theorem} \begin{proof} (Buck Theorem~5 page~231.) The partial sums satisfy the inequality $$ 0\le \sum_{k=m+1}^na_k\le \sum_{k=m+1}^nb_k. $$ Because the $\sum_kb_k$ is assumed to converge we have $\lim_{m,n\to\infty}\sum_{k=m+1}^nb_k=0$. Hence $\lim_{m,n\to\infty}\sum_{k=m+1}^na_k=0$ so the series $\sum_ka_k$ converges by Theorem~\ref{thm:Cauchy-sequence} \end{proof} \begin{theorem}[\jdef{Integral Test}]\label{thm:integral_test} Assume that $a_k=f(k)$ where $f:[1,\infty)\to[0,\infty)$ is monotonic decreasing. Then the improper integral $\int_1^\infty f(x)\,dx<\infty$ converges if and only if the sum $\sum_{k=1}^\infty a_k<\infty$ does. \end{theorem} \begin{proof} (Buck Theorem~10 page~233.) We have $a_{k+1}=f(k+1)\le f(x)\le f(k)=a_k$ for $k\le x\le k+1$ so $$ \sum_{k=2}^{n+1}a_k \le \int_1^nf(x)\,dx\le \sum_{k=1}^na_k. $$ This inequality shows that the infinite sum is finite if and only if the integral is finite. \end{proof} \begin{theorem}[\jdef{Root Test}] \label{thm:root_test} Let $$ R=\lim\sup_{k\to\infty}|a_k|^{1/k} $$ Then the series $\sum_ka_k$ converges absolutely if $ R<1$ and diverges (does not converge) if $R>1$. \end{theorem} \begin{proof} (Buck Theorem~9 page~232.) Let $S_n=\left\{|a_k|^{1/k}: k=n,n+1,\ldots\right\}$, $s_n=\sup S_n$ so $S_{n+1}\subseteq S_n$ and hence $s_{n+1}\le s_n$. (We are using the convention that $\sup S\infty$ if $S$ is not bounded above.) Either $s_n=\infty$ for all $n$ (this falls under the case $R>1$) or else $(s_n)_n$ is a monotonic sequence decreasing (i.e non-increasing) converging to $R$. If $R<1$ then $RN$ and hence $|a_k|^{1/k}\le s_n N$. From this we deduce that $|a_k|\le r^k$ and hence $$ \sum_{k=N+1}^\infty |a_k|\le \sum_{k=N+1}^\infty r^k $$ so the series convergence by the Comparison Test (Theorem~\ref{thm:comparison_test}, see also) and the fact that the geometric series converges for $r<1$. %As $\lim_{N\to\infty} r^{N+1}/(1-r)=0$ this shows that the series converges absolutely. Conversely if $R>1$ then $s_n\ge R>1$ for all $n$ so for every $n$ there exists a $k\ge n$ with $|a_k|=\bigl(|a_k|^{1/k}\bigr)^k\ge 1$. This means that it is {\em not} the case that $\lim_{n\to\infty} a_n =0$ so the series diverges by the $n$th term test (Theorem~\ref{thm:nth-term}). \end{proof} \rmk Theorem~\ref{thm:root_test} gives no information when $R=1$. If $a_k=1/k$, then $R=1$ but $\sum_ka_k=\infty$. If $a_k=1/k^2$, then $R=1$ and $\sum_ka_k<\infty$. \kmr \rmk The proofs the convergence tests tell us how to estimate the error, i.e. the difference between a partial sum and the infinite sum. For example, by the Integral Test, the series $\sum_k1/k^2$ converges and $$ \left| \sum_{k=1}^\infty\frac1{k^2}- \sum_{k=1}^n\frac1{k^2}\right|= \left| \sum_{k=n+1}^\infty\frac1{k^2}\right|\le \int_n^\infty\frac{dx}{x^2} = \frac1{n}. $$ Similarly if $R<1$ in the Root Test and $RN$ and hence $$ \left| \sum_{k=1}^\infty a_k- \sum_{k=1}^na_k\right|= \sum_{k=n+1}^\infty|a_k| \le \sum_{k=n+1}^\infty r^k = \frac{r^{n+1}}{1-r}\le\frac{r^N}{1-r} $$ for $n>N$. \kmr \prob \label{prob:p-series} Show that for $p>1$ the series $\sum_{k=1}^\infty k^{-p}$ converges and that the estimate $$ \left|\sum_{k=1}^\infty k^{-p} -\sum_{k=1}^n k^{-p}\right|\le \frac{(n+1)^{1-p}}{p-1} $$ holds for the difference (error) between the $n$th partial sum and the limit. \borp \dfn A series $\sum_{k=1}^\infty b_k$ is said to be a \jdef{rearrangement} of the series $\sum_{k=1}^\infty a_k$ iff there is a permutation\footnote{ A \jdef{permutation} is bijective map from a set itself. This terminology is most often used for finite sets, but here it is used for a infinite set.} $\sigma:\Z^+\to\Z^+$ such that $b_k=a_{\sigma(k)}$. \nfd \begin{theorem} \begin{description} \item [(1)] Any rearrangement of an absolutely convergent series converges absolutely to the same limit. \item[(2)] Assume that the series $\sum_{k=1}^na_k$ converges conditionally and $L\in\hat\R$ (see~\ref{extended_reals}). Then there is a rearrangement $\sum_{k=1}^\infty b_k$ of the series $\sum_{k=1}^na_k$ such that $$ \sum_{k=1}^\infty b_k = L. $$ \end{description} \end{theorem} \begin{proof} Part~(1) is Theorem~13 page 239 of Buck. Part~(2) is proved on pages~238-9 of Buck in the special case where $a_n=(-1)^n/n$ and $L=10$; the general argument is much the same but uses Theorem~\ref{thm:nth-term}. \end{proof} \section{Uniform Convergence} \dfn A sequence $(f_n)_n$ of functions with common domain $X$ said to \jdef{converge pointwise} to the function $f:X\to\R$ iff $$ \lim_{n\to\infty}f_n(p)=f(p) $$ for all $p\in X$, i.e. iff $$ \forall p\in X\, \forall\eps>0\,\exists N\,\forall n\; \bigr[n>N\implies |f_n(p)-f(p)|<\eps \bigr]. $$ The sequence is said to \jdef{converge uniformly} to the function $f$ iff $$ \lim_{n\to\infty}\sup_{p\in U}|f_n(p)-f(p)|=0, $$ i.e. iff $$ \forall\eps>0\,\exists N\,\forall p\in U\,\forall n \bigr[n>N\implies |f_n(p)-f(p)|<\eps \bigr]. $$ For a sequence $(u_k:X\to\R^m)_k$ of functions the series $\sum_ku_k$ of functions is said to converge pointwise or uniformly iff the sequence $f_n=\sum_{k=0}^n u_k$ of partial sum does. \nfd \xmpl Define $f_n:[0,1]\to\R$ by $f_n(x)=x^n$. Then the sequence $(f_n)_n$ converges pointwise but not uniformly to the function $$ f(x) = \left\{\begin{array}{ll} 0 &\mbox{ for } 0\le x < 1\\ 1 & \mbox{ for } x=1. \end{array}\right. $$ \lpmx \begin{theorem}\label{thm:uniform_limit_is_continuous} If $f_n:X\to Y$ is continuous for each $n$ and the sequence $(f_n)_n$ converges uniformly to $f:X\to Y$, then the limit $f$ is also continuous. \end{theorem} \begin{proof} (Buck Theorem~3 page~266.) Choose $x_0$ and $\eps>0$. By uniform convergence there exists an $n$ such that $|f(x)-f_n(x)|<\eps/3$ for all $x$ and all $n>N$. Let $n=N+1$. As $f_n$ is continuous at $x_0$ there exists $\delta>0$ such that $f_n(x)-f_n(x_0)|<\eps/3$ whenever $|x-x_0|<\delta$. Then $$ |f(x)-f(x_0)|\le |f(x)-f_n(x)|+|f_n(x)-f_n(x_0)|+|f_n(x_0)-f(x_0)|<\eps $$ whenever $|x-x_0|<\delta$. \end{proof} \begin{theorem}[\jdef{Weierstrass Comparison Test}]\label{thm:weierstrass_comparison_test} Assume that the functions $u_k:X\to\R^m$ satisfy $|u_k(p)|\le M_k$ where $\sum_k M_k<\infty$. Then the series $\sum_ku_k$ converges uniformly. \end{theorem} \begin{proof} (Buck Theorem~2 page~266.) This is an immediate consequence of the inequality $$ \left|\sum_{k=n+1}^\infty u_k(p)\right|\le \sum_{k=n+1}^\infty |u_k(p)|\le\sum_{k=n+1}^\infty M_k $$ as follows. Since the series on the right converges we have that for every $\eps>0$ there is an $N=N(\eps)$ such that the right hand side is $<\eps$ if $n>N$ and hence the left hand side is $<\eps$ for all $p$. \end{proof} \rmk \label{rmk:dominated} The proof doesn't require that the inequality $|u_k(p)|\le M_k$ hold for {\em all} $k$ but only for all sufficiently large $k$. This inequality is often expressed by saying that the series $\sum_ku_k$ is \jdef{dominated} by the series $\sum_k M_k$ \kmr \begin{theorem}\label{thm:uniform_integral} Assume that the sequence $(f_n:[a,b]\to\R)_n$ converges uniformly to a function $f$ and that each $f_n$ is continuous. Then the limit of the integrals is the integral of the limit, i.e. $$ \lim_{n\to\infty}\int_a^bf(x)\,dx=\int_a^b f(x)\,dx. $$ \end{theorem} \begin{proof} Choose $\eps>0$. Then there is an $N$ such that $|f(x)-f_n(x)|<\eps/(b-a)$ for all $x\in[a,b]$ and all $n>N$. For $n>N$ we have, by the various properties listed in Theorem~\ref{thm:axioms_for_the_integral}, that $$ \begin{aligned} \left|\int_a^bf(x)\,dx-\int_a^b f_n(x)\,dx\right|&= \left|\int_a^b(f(x)-f_n(x))\,dx\right| \\ &\le\int_a^b\left|f(x)-f_n(x)\right|\,dx \\& \le \frac{\eps(b-a)}{b-a}=\eps \end{aligned} $$ as required. \end{proof} \begin{corollary} \label{cor:uniform-derivative} Let $(f_n)_n$ be a sequence of of functions defined on an open interval $I$. Assume that \begin{description} \item[(i)] Each $f_n$ is differentiable; \item[(ii)] Each derivative $f_n'$ is continuous; \item[(iii)] The sequence $(f_n)_n$ converges uniformly on $I$; \item[(iv)] The sequence $(f_n')_n$ converges uniformly on $I$. \end{description} Then the limit $f$ is differentiable and the limit of the derivatives is the derivative of the limit, i.e. $$ \lim_{n\to\infty} f_n'(x)= f'(x) $$ for $x\in I$. \end{corollary} \begin{proof} Define $g(x):=\lim_{n\to\infty} f_n'(x)$. By Theorem~\ref{thm:uniform_limit_is_continuous} $g$ is continuous. By the Fundamental Theorem of Calculus part~(II) we have $$ f_n(x)-f_n(a)=\int_a^x f_n'(t)\,dt $$ so Theorem~\ref{thm:uniform_integral} we have $$ f(x)-f(a)=\lim_{n\to\infty}\int_a^x f_n'(t)\,dt=\int_a^x \lim_{n\to\infty} f'_n(t)\,dt=\int_a^x g(t)\,dt. $$ Hence $f'=g$ by the Fundamental Theorem of Calculus part~(I). \end{proof} \section{Power Series - I} \para A series of form $\sum_{k=0}^\infty c_k(x-a)^k$ is called a \jdef{power series} centered at $a$. The \jdef{radius of convergence} of the power series is the number $R$ defined by $$ \frac1R:=\limsup_{k\to\infty} |c_k|^{1/k}. $$ (If the $\limsup$ is infinite, then $R:=0$ and if the $\limsup$ is zero, then $R:=\infty$.) \arap \prob (A formula for the radius of convergence). Assume that the coefficients $c_k$ are nonzero. Show that $$ \limsup_{k\to\infty} |c_k|^{1/k}=\lim_{k\to\infty}\frac{|c_{k+1}|}{|c_k|} $$ if the limit on the right exists. \borp \begin{theorem} \label{thm:radius_of_convergence} Let $\sum_{k=0}^\infty c_k(x-a)^k$ be a power series and $R$ be its radius of convergence. Then the series converges if $|x-a|R$. More precisely, \begin{description} \item[(i)] If $0R$ then the $n$th term of the series is unbounded and hence does not converge to zero (so the series does not converge by Theorem~\ref{thm:nth-term}). \end{description} \end{theorem} \begin{proof} (Buck Theorem~14 page~240.) Let $a_k=c_k(x-a)^k$. Then by the Root Test (Theorem~\ref{thm:root_test}) the series converges if $\limsup_{k\to\infty} |a_k|^{1/k}$ is less than one and diverges if it is greater than one. But $$ \limsup_{k\to\infty}|a_k|^{1/k}=\limsup_{k\to\infty}|c_k|^{1/k}|x-a|=\frac{|x-a|}{R} $$ so the series converges if $|x-a|R$. To prove that the convergence is uniform on the interval $[a-r,a+r]$ we need to repeat the proof of the Root Test. Let $\rho=(r+R)/2$ so $0N$) so $$ |c_k(x-a)^k| < \left(\frac{r}{\rho}\right)^k. $$ Since $r/\rho<1$ this says that the power series is dominated by a convergent geometric series if $|x-a|N$ and $x\in I$. If the power series $\sum_k c_k(x-a)^k$ has infinitely many nonzero terms, there exist $m>n>N$ with $c_m\ne 0$ and $c_n\ne 0$ and hence $P_n-P_m$ is a nonconstant polynomial. But then $|P_n(x)-P_m(x)|\le |P_n(x)-f(x)|+|f(x)-P_m(x)|\le 2$ for all $x\in I$. Hence the interval $I$ must be unbounded as a nonconstant polynomial becomes infinite as $x\to\pm\infty$. \kmr \begin{theorem} \label{thm:power-diff} Let $\sum_{k=0}^\infty c_k(x-a)^k$ be a power series and $R$ be its radius of convergence. Denote the sum by $$ f(x):=\sum_{k=0}^\infty c_k(x-a)^k $$ for $|x-a|0\\ 0 & \mbox{ if } x\le 0 \end{array}\right. $$ is infinitely differentiable but not analytic. (All its derivatives vanish at zero so it cannot equal its Taylor series.) Hint: Show inductively that the $k$th derivative of $f$ has form $$ f^{(k)}(x)=\frac{P(x)}{Q(x)} e^{-1/x} $$ for $x>0$ where $P(x)$ and $Q(x)$ are polynomials. Then use the definition of the derivative to show that $ f^{(k+1)}(0)=0$. Then $$ \frac{P(x)}{Q(x)} e^{-1/x}=\frac{\tilde{P}(y)}{\tilde{Q}(y)} e^{-y},\qquad y=\frac{1}{x} $$ where $\tilde{P}(y)$ and $\tilde{Q}(y)$ are also polynomials. The variable $x$ approaches $0$ as $y$ approaches $\infty$. Use l'Ho\^pital's rule. \borp \prob Give two proofs that the function $f(x)=x^{-1}$ defined for $x>0$ is analytic. First: Write $f(x)=P_n(x,a)+R_n(x,a)$ where $$ P_n(x,a):=\sum_{k=0}^n \frac{f^{(k)}(a)(x-a)^k}{k!} $$ and show that $\lim_{n\to\infty} R_n(x,a)=0$ for $x$ sufficiently near $a$. Second: Use the identity $$ \frac{1}{x}=\frac{1}{a(1+y)} $$ where $y=(x-a)/a$ and the formula for the sum of a geometric series. \borp \begin{theorem} If a function $f$ is represented by a power series in an open interval $I$ about of some point in its domain, it is analytic in that interval, i.e. if $a\in I$ and $$ f(x)=\sum_{k=0}^\infty \frac{f^{(k)}(a)(x-a)^k}{k!} \eqno(\dagger) $$ for $x\in I$, then $$ f(x)=\sum_{k=0}^\infty \frac{f^{(k)}(b)(x-b)^k}{k!} $$ for $x,b\in I$. \end{theorem} \begin{proof} This is normally proved in a course on complex variables (Math~623 at UW). Here is a proof that doesn't use complex numbers. Choose $b\in I$ and write Taylor's Formula (Theorem~\ref{thm:taylor}) centered at $b$ $$ f(x)=P_n(b,x)+R_n(b,x) $$ $$ P_n(b,x):=\sum_{k=0}^n\frac{f^{(k)}(b)}{k!}(x-b)^k,\qquad R_n(b,x):=\int_b^x \frac{f^{(n+1)}(t)}{n!}(x-t)^n\,dt. $$ We must show that $\lim_{n\to\infty}R_n(b,x)=0$ for $x$ in an open interval about $b$. Let $R$ be the radius of convergence of $(\dagger)$ so that $$ R^{-1}=\limsup_{k\to\infty} |c_k|^{1/k}, \qquad c_k:= \frac{f^{(k)}(a)}{k!}. $$ By Theorem~\ref{thm:radius_of_convergence} the series~$(\dagger)$ diverges for $|x-a|>R$ so we may as well assume that $I=(a-R,a+R)$. Since $b\in I$ we have $|b-a|0$ so small that $(b-\delta,b+\delta)\subseteq(a-r,a+r)$ and $$ \mu:=\left(1-\frac{\rho}{r}\right)^{-1}\delta<1. $$ Then for $x\in (b-\delta,b+\delta)$ and $t$ between $b$ and $x$ we have $|x-t|<\delta$ so $$ \begin{aligned} |R_n(b,x)|&= \left|\int_b^x \frac{f^{(n+1)}(t)}{n!}(x-t)^n\,dt\right|\\ &\le |b-x| \, M\left(1-\frac{r}{\rho}\right)^{-n-1}\frac{\delta^n}{n!}\\ &\le M(n+1)!\left(1-\frac{r}{\rho}\right)^{-n-1}\frac{\delta^{n+1}}{n!}\\ & = M(n+1) \mu^{n+1}. \end{aligned} $$ But $\mu<1$ so $\lim_{n\to\infty}|R_n(b,x)|=M\lim_{n\to\infty}n\mu^n=0$ as required. \end{proof} \section{Power Series - II} \begin{theorem} \label{thm:boundary_of_interval_of_convergence} Assume that the power series $$ f(x)=\sum_{k=0}^\infty c_k(x-a)^k $$ has radius of convergence $R$ and converges pointwise on the closed interval $[a,a+R]$. Then it converges uniformly on that interval. Similarly for the closed interval $[a-R,a]$. \end{theorem} \begin{proof} (See Buck page~279.) We assume that $R=1$ and $a=0$ to simplify the notation: the proof in general is similar but messier. Thus define $$ f(x)=\sum_{k=0}^\infty c_kx^k, \qquad 0\le x<1; \qquad f(1)=\sum_{k=0}^\infty c_k. $$ Define $B_n:= \sum_{k=n}^\infty c_k$. Then $c_k=B_k-B_{k+1}$. Since the series $f(1)$ converges, it follows that $\lim_{n\to\infty}B_n=0$. Choose $\eps>0$. There exists $N$ such that $|B_n|<\eps/2$ for $n>N$. For $x\in[0,1)$ we have $$ \begin{aligned} \sum_{k=n}^\infty c_kx^k &= \sum_{k=n}^\infty(B_k-B_{k+1})x^k\\ &= B_nx^n+\sum_{k=n+1}^\infty B_{k+1}(x^{k+1}-x^k)\\ &= B_nx^n+(x-1)\sum_{k=n}^\infty B_{k+1}x^k \end{aligned} $$ so for $n>N$ $$ \begin{aligned} \left|\sum_{k=n}^\infty c_kx^k\right| &\le |B_n|\,x^n+(1-x)\sum_{k=n}^\infty |B_{k+1}|\,x^k \\ &\le \frac{\eps x^n}{2}+\frac{(1-x)\eps x^n}{2(1-x)}\sum_{j=0}^\infty x^j\\ &=\eps \end{aligned} $$ When $x=1$ this inequality holds because $|B_n|<\eps/2<\eps$. \end{proof} \begin{corollary} \label{cor:boundary_of_interval_of_convergence} Suppose the power series $$ f(x) = \sum_{k=0}^\infty c_k(x-a)^k %f(x) = \sum_{k=0}^\infty \frac{f^{(k)}(a)(x-a)^k}{k!} $$ converges pointwise on the interval $[a,a+R]$. Then the function $f$ is continuous on the interval $[a,a+R]$. Similarly for the closed interval $[a-R,a]$. \end{corollary} \begin{proof} By Theorem~\ref{thm:boundary_of_interval_of_convergence} the series converges uniformly so the function $f$ is continuous by Theorem~\ref{thm:uniform_limit_is_continuous}. \end{proof} \rmk \label{rmk:boundary_of_interval_of_convergence} The formula $$ \frac{1}{1-t}=\sum_{k=0}^\infty t^k $$ was proved in~\ref{xmpl:geometric_series}. By Theorem~\ref{thm:uniform_integral} we may integrate and get $$ \ln(1-x)=-\int_0^x\frac{dt}{1-t}=-\sum_{k=0}^\infty \frac{x^{k+1}}{k+1}=-\sum_{k=1}^\infty \frac{x^k}{k} $$ which holds for $-1N$. \begin{description} \item[(1)] Show that, if $p>1$, the series $$ f(x):=\sum_{n=1}^\infty b_n\sin nx \eqno\mbox{(\ref{prob:sin}-1)} $$ converges uniformly. \item[(2)] Show that, if $p>1$, then $$ b_n=\frac{2}{\pi}\int_0^\pi f(x)\sin(nx)\,dx. \eqno\mbox{(\ref{prob:sin}-2)} $$ \item[(3)] Show that, if $p>2$, then $f$ is differentiable and that $$ f'(x):=\sum_{n=1}^\infty nb_n\cos nx. $$ \end{description} \medskipnoindent Hint: See Problem~\ref{prob:p-series} above. You may use any of the theorems stated above but state which theorems you are using and verify that the hypotheses of the theorems are satisfied. \borp \prob \label{prob:HeatEquation} Continue the notation of Problem~\ref{prob:sin}. Show that the series $$ u(t,x):=\sum_{n=1}^\infty e^{-n^2t} b_n\sin nx \eqno\mbox{(\ref{prob:HeatEquation}-1)} $$ converges uniformly on $[0,\infty)\times[0,\pi]$ if $p>1$ and that the limit satisfies the partial differential equation\footnote{ This PDE is called the \jdef{Heat Equation}. } $$ \frac{\partial u}{\partial t} =\frac{\partial ^2u}{\partial x^2} \eqno\mbox{(\ref{prob:HeatEquation}-2)} $$ on the open set $(0,\infty)\times(0,\pi)$. Show also that $u$ is continuous on the closed set $[0,\infty)\times[0,\pi]$, that it satisfies the initial condition $$ u(0,x)=f(x) \eqno\mbox{(\ref{prob:HeatEquation}-3)} $$ and the boundary condition $$ u(t,0)=u(t,\pi)=0. \eqno\mbox{(\ref{prob:HeatEquation}-4)} $$ (You may use any of the theorems stated above but state which theorems you are using and verify that the hypotheses of the theorems are satisfied. Hint: $e^{-n^2t}$ is very small if $t>0$ and $n$ large.) It looks like this exercise proves that the solution of the partial differential equation~(\ref{prob:HeatEquation}-2) subject to the intial condition~(\ref{prob:HeatEquation}-3) and the boundary condition~(\ref{prob:HeatEquation}-4) is given by~(\ref{prob:HeatEquation}-1) where the coefficients are defined by~(\ref{prob:sin}-2). Is there anything missing for a rigorous proof? \borp \section{Fourier Series - I} \section{Fourier Series - II} \begin{theorem} Assume that the function $f:\R\to\C$ is $2\pi$ periodic and Lipshitz. Then the Fourier series for $f$ converges uniformly to $f$, i.e. $$ f(x)=\lim_{n\to\infty} \sum_{k=-n}^n c_k e^{ikx}, \qquad c_k:=\frac{1}{2\pi}\int_{-\pi}^\pi f(x)e^{-ikx}\,dx $$ and the convergence is uniform. \end{theorem} \begin{proof} See Rudin page~189. \end{proof} \appendix \section{Uniqueness of the Real Numbers}\label{app:uniqueness_of_R} \dfn \label{dfn:field} A \jdef{field} is a set $R$ equipped two binary operations $$ R\times R\to R: (x,y)\mapsto x+y, \qquad R\times R\to R: (x,y)\mapsto x\cdot y, $$ two distinct special elements $0$ and $1$, and two unary operations $$ R\to R:a\mapsto -a,\qquad R\setminus\{0\}\to R\setminus\{0\}:a\mapsto a^{-1}, $$ satisfying the following (additive and multiplicative) commutative, associative, identity, and inverse laws: \begin{center}\renewcommand{\arraystretch}{1.4} \begin{tabular}{l|l@{\quad\quad}ll@{\qquad\quad}} & Addition && Multiplication\\ \hline commutative&$a+b=b+a$ &&$a\cdot b=b\cdot a$\\ associative&$(a+b)+c=a+(b+c)$&& $(a\cdot b)\cdot c= a\cdot (b\cdot c)$\\ identity&$a+0=a$ && $a\cdot 1=a$ \\ inverse& $a+(-a)=0$& &$a\cdot a^{-1}=1$\\ \end{tabular} \end{center} and the distributive law: $$ (a+b)\cdot c= (a\cdot c)+(b\cdot c). $$ The operations of {\em subtraction} and {\em division} are then defined by $$ a-b:=a+(-b) \qquad \frac{a}{b}:=a\cdot b^{-1}=a\cdot\frac{1}{b}. $$ The standard abbreviations $ab:=a\cdot b$, $a-b:=a+(-b)$, and $a/b=a\cdot b^{-1}$ are used. The above axioms are those which appear in~\ref{ax:algebraic}. \nfd \para The rational numbers $\Q$, the real numbers $\R$, and the complex numbers $\C$ are the most important examples of fields, but there are many others, e.g. the field $\mathcal{R}$ of rational functions from problem~\ref{prob:calR} and the field $\Q(\sqrt{2})$ from problem~\ref{prob:Qsqrt2}. In Math~441 (or~541) you will even meet finite fields. (The simplest example of a finite field is the set $\{0,1,2,\ldots,p-1\}$ where $p$ is a prime, and addition and multiplication are done 'modulo $p$'.) \arap \para The axioms in the column headed {\em Addition} above are the axioms for an abelian group in additive notation, and the axioms in the column headed {\em Multiplication} above are the axioms for an abelian group in multiplicative. If you replace $0$ by $1$, $a+b$ by $a\cdot b$, and $-a$ by $a^{-1}$ in the former column you get the axioms in the latter column. Because both addition and multiplication satisfy the axioms for an abelian group there are further analogies. \begin{center}\renewcommand{\arraystretch}{1.8} \begin{tabular}{ll@{\quad}ll@{\qquad\quad}} &Addition&& Multiplication\\ {\bf(0)}& $a+b=0\implies b=-a$& {\bf(0)}&$a\cdot b=1\implies b=a^{-1}$\\ {\bf(i)} & $-(-a)=a$ & {\bf(i)} & $(a^{-1})^{-1}=a$ \\ {\bf(ii)} & $-(a+b)=-a-b$ & {\bf(ii)} & $(a\cdot b)^{-1}=a^{-1}\cdot b^{-1}$ \\ {\bf(iii)} & $-(a-b)=b-a$ & {\bf(iii)} & $\ds \left(\frac{a}{b}\right)^{-1}=\frac{b}{a}$ \\ {\bf(iv)}& $(a-b)+(c-d) = (a+c)-(b+d)$ & {\bf(iv)} & $\ds \frac{a}{b}\cdot\frac{c}{d}=\frac{ac}{bd}$ \\ {\bf(v)} &$a-b=(a+c)-(b+c)$ & {\bf(v)} & $\ds \frac{a}{b}=\frac{ac}{bc}$ \\ {\bf(vi)} &$(a-b)-(c-d) = (a-b)+(c-d)$& {\bf(vi)} & $ \ds \frac{a/b}{c/d} =\frac{a}{b}\cdot\frac{c}{d}$ \end{tabular} \end{center} \medskipnoindent Line~(0) explains the phrase 'necessarily unique' used in~\ref{ax:algebraic}. The last line explains why {\em we invert and multiply to divide fractions}. \arap \para Using the distributive law one can also prove the following familiar identities. \begin{center}\renewcommand{\arraystretch}{1.8} \begin{tabular}{@{\quad}l@{\qquad}l@{\quad}} {\bf(vii)} $a\cdot0=0$ & {\bf(viii)} $-a=(-1)a$ \\ {\bf(ix)} $a(-b)=-ab$ & {\bf(x)} $(-a)(-b)=ab$\\ {\bf(xi)} $\ds \frac{a}{b}+\frac{c}{d}=\frac{ad+cb}{bd}$ & {\bf(xii)} $(a+b)(c+d)=ab+ad+bc+bd$ \\ {\bf(xiii)} $(a+b)^2=a^2+2ab+b^2$& {\bf(xiv)} $(a+b)(a-b)=a^2-b^2$ \end{tabular} \end{center} It follows from these laws that if a product is zero, then one of its factors must be zero. (Proof: if $ab=0$ and $a\ne 0$ then $b=1\cdot b(a^{-1}a)b=a^{-1}(ab)=a^{-1}\cdot 0=0$.) \arap \dfn A \jdef{homomorphism} from a field $R$ to a field $R'$ is a map $\iota:R\to R'$ such that $$ \iota(a+b)=\iota(a)+\iota(b),\qquad \iota(a\cdot b)=\iota(a)\cdot\iota(b) $$ for $a,b\in R$. (In each equation the operation on the left is the one for $R$ and the operation on the right is the one for $R'$.) It follows easily that $\iota(0)=0$, $\iota(1)=1$, $\iota(-a)=-\iota(a)$, and $\iota(a^{-1})=\iota(a)^{-1}$. An \jdef{isomorphism} is a bijective homomorphism. \nfd \rmk The inverse of an isomorphism is an isomorphism. For example, if $a',b',c':=a'+b'\in R$ and $a=\iota^{-1}(a')$, $b=\iota^{-1}(b')$, $c=\iota^{-1}(c')$, then $\iota(a+b)=a'+b'$ (as $\iota$ is a homomorphism) and $\iota(c)=c'=a'+b'$, so $\iota(c)=\iota(a+b)$ so $c=a+b$ (as $\iota$ is injective). \kmr \begin{proposition} A homomorphism of fields is injective. \end{proposition} \begin{proof} Assume that $\iota(a)=\iota(b)$; we must show that $a=b$. If $a\ne b$, then $c:=a-b\ne 0$ so $ 1=\iota(1)=\iota(c^{-1}c) =\iota(c)^{-1}\iota(c)=\iota(c)^{-1}\iota(a-b)= \iota(c)^{-1}\iota(0)=\iota(c)^{-1}0=0 $ contradicting $1\ne 0$. \end{proof} \dfn An \jdef{ordered field} is a field equipped with an order relation satisfying the conditions in~\ref{ax:order}. An \jdef{order preserving} homomorphism from an ordered field $R$ to an ordered field $R'$ is a homomorphism $\iota:R\to R'$ such that $$ a0$ and $R$ obeys the same algebraic and order laws as $Q$, it is immediate that $\iota$ is an order preserving homomorphism. \end{proof} \dfn An ordered field $R$ is \jdef{complete} iff every subset $S$ of $R$ which is bounded above has a least upper bound $\sup(S)$. (The definitions are {\em mutatis mutandis} the same as in~\ref{def:glb}.) \nfd \begin{theorem} \label{thm:R2R} For any complete ordered field $R$, there is a unique order preserving isomorphism $\iota:\R\to R$ from the set $\R$ of real numbers onto $R$. \end{theorem} \begin{proof} For $a\in\R$ we have $a=\sup\{q\in\Q: q0$ to the equation $b^n=a$. Define $a^{1/n}$ to be this unique solution, i.e. $a^{1/n}=b\iff b^n=a$. \item[(2)] For a rational number $q$ define $a^q$ by $a^q=(a^m)^{1/n}$ where $q=m/n$. Prove that this definition is independent of the choice of the integers $m$ and $n$ such that $q=m/n$. \item[(3)] Prove that there is a unique continuous function $$ \R\to(0,\infty): x\mapsto a^x $$ such that $a^x=a^q$ when $x$ is a rational number $q$. \end{description} In your proof make clear which theorems from these notes you are appealing to. Also make your proof self contained so that a person who doesn't have access to the statement of the problem can follow it. (You needn't provide proofs for the theorems you use, but do provide references to them.) In your proof of~(3) you may use the inequality $$ |a^p-a^q|\le M|p-q| $$ which is true when $a>1$, $N$ is a positive integer, $1\le p,q\le N+1$, and $$ M:=\left(\sum_{k=1}^{N}\frac{1}{k}\right) a^N. $$ You need not prove this inequality but use calculus to show where it comes from. Hint: What is the definition of $\ln x$, $e^x$, and $a^x$ used in calculus? Consider the Integral Test~\ref{thm:integral_test}. The natural logarithm function $\ln x$ is usually defined as an integral. How do you bound an integral by a sum? How does the Mean Value Theorem from calculus (see~\ref{thm:MVT})) give inequalities like this? \borp \printindex \end{document}