Math 101 Group Project #1 The Contraction Mapping Theorem

Let A be a subset of a metric space (X, d). A function f : A → A is called a contraction on A if there exists a constant C < 1 such that

d(f(x), f(y)) ≤ C · d(x, y)

for every x, y ∈ A. The one dimensional Contraction Mapping Theorem (CMT) states that if f : A → A is a contraction on a nonempty closed subset A of ℝ, then f has a unique fixed point in A.

1. 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.

2. 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}) ≤ k_{n} for all m and n in ℤ^{+}. (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?

3. 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?

4. Show that the Contraction Mapping Theorem becomes false if we replace ℝ with ℚ. (Hint: let A = {x ∈ ℚ | x ≥ 1}, and let f : A → 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?

5. If d(f(x), f(y)) < d(x, y) for all x, y ∈ A with x ≠ y, it does not necessarily follow that there exists C < 1 such that d(f(x), f(y)) < C · d(x, y) for all x, y ∈ A. Find a function f : ℝ → ℝ such that d(f(x), f(y)) < d(x, y) for all x, y ∈ ℝ and x ≠ 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?

6. Suppose g(x) = f(f(x)) for some f : A → 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?

7. 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 ℝ^{n}? Explain.

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