\documentclass{article}
\usepackage{amsmath}
\usepackage{amssymb}

\newcommand\from{\colon}
\newcommand\R{\mathbb{R}}
\newcommand\Z{\mathbb{Z}}
\newcommand{\cl}{\mathbf{K}}


\begin{document}
\begin{center}
\Large{Math 101 Group Project \#1}

{The Contraction Mapping Theorem}
\end{center}
\

Let $A$ be a subset of a metric space $(X,d)$.  A function
$f:A\to A$ is called a {\bf contraction\/} on $A$ if there
exists a constant
$C<1$ such that

$$d(f(x),f(y))\le C\cdot d(x,y)$$
for every $x,y\in A$.  The one dimensional {\bf Contraction
Mapping Theorem\/} (CMT) states that if $f:A\to A$ is a
contraction on a nonempty closed subset $A$ of $\mathbb R$,
then $f$ has a unique fixed point in $A$.



\begin{enumerate}
\item
Explain in your own words what this theorem means, your intuition as to why
it seems plausible, and how this result relates or does not relate to
crumbling paper.  Give examples that illustrate applications of the CMT.

\item
Divide the proof of the CMT into several steps and carry them out.
Begin by picking an $x_1$ in $A$ and setting $x_{n+1}=f(x_n)$.  Find a bound
$k_n$ satisfying $d(x_n, x_m) \leq k_n$ for all $m$ and $n$ in $\mathbb
Z^+$.  (Bad hint:  think geometrically.)  Then define intervals $[a_n, b_n]$
with
$a_n = x_n - k_n$ and
$b_n = x_n +k_n$.  What do you know and what do you need to prove about the
intersection of these intervals?

\item
Find a contraction on the open interval $(0,1)$ with no fixed point in
$(0,1)$.  How did your proof of the CMT above use the assumption that $A$
is closed?

\item
Show that the Contraction Mapping Theorem becomes false if we replace
$\mathbb R$ with ${\Bbb Q}$.  (Hint: let $A=\{x\in{\Bbb Q}\mid
x\ge 1\}$, and let $f:A\to A$ be the function arising from continued
fractions that we used to improve approximations to
$\sqrt{2}$.)  How did your proof of the CMT use the assumption that $A$ is
a subset of the reals and not a subset of the rationals?


\item
If $d(f(x),f(y))<d(x,y)$ for all $x,y\in A$ with $x\neq y$,
it does not necessarily follow that there exists $C<1$ such
that $d(f(x),f(y))<C\cdot d(x,y)$ for all $x,y\in A$. Find a
function $f:\mathbb R\to\mathbb R$ such that
$d(f(x),f(y))<d(x,y)$ for all $x,y\in\mathbb R$ and $x\neq
y$ such that $f$ has no fixed point. (Just try drawing the
graph of such a function. It is not so important to find an
explicit formula.)  How does the condition $C<1$ enter into your CMT proof?

\item
Suppose $g(x)= f(f(x))$ for some $f:A\to A$.  Must $g$ be a contraction if
$f$ is?  Can $g$ be a contraction if $f$ is not?  What can you say about the
fixed points of $g$?  Same questions about $g(x)=f^n(x)$, the function
obtained by applying $f$ a total of $n$ times?

\item
Does it matter to your proof whether $A$ is connected?  Why or why not?
Can you apply this theorem when $A$ is a finite set?  A set in
$\mathbb R^n$? Explain.

\item
Make up questions that would be suitable for a hour exam in this course.

\end{enumerate}

\end{document}

