description/proof of the contraction mapping principle
Topics
About: metric space
The table of contents of this article
Starting Context
- The reader knows a definition of complete metric space.
- The reader knows a definition of map.
Target Context
- The reader will have a description and a proof of the contraction mapping principle.
Orientation
There is a list of definitions discussed so far in this site.
There is a list of propositions discussed so far in this site.
Main Body
1: Structured Description
Here is the rules of Structured Description.
Entities:
\(M\): \(\in \{\text{ the complete metric spaces }\}\)
\(f\): \(: M \to M\)
//
Statements:
\(\exists r \in \mathbb{R} \text{ such that } 0 \le r \lt 1 (\forall m_1, m_2 \in M (dist (f (m_1), f (m_2)) \le r dist (m_1, m_2)))\)
\(\implies\)
\(!\exists m \in M (f (m) = m \land \forall m' \in M (lim_{j \to \infty} f^k (m') = m))\)
//
\(m\) is called "fixed point".
2: Proof
Whole Strategy: Step 1: see that \(f^1 (m'), f^2 (m'), ...\) is a Cauchy sequence and take the convergence, \(m\); Step 2: conclude the proposition.
Step 1:
\(dist (f^{j + 1} (m'), f^j (m')) \le r dist (f^j (m'), f^{j - 1} (m')) \le r^2 dist (f^{j - 1} (m'), f^{j - 2} (m')) \le ... \le r^j dist (f (m'), m')\).
\(dist (f^{j + l} (m'), f^j (m')) \le dist (f^{j + l} (m'), f^{j + l - 1} (m')) + dist (f^{j + l - 1} (m'), f^{j + l - 2} (m')) + ... + dist (f^{j + 1} (m'), f^j (m')) \le (r^{j + l - 1} + r^{j + l -2} + . . . + r^j) dist (f (m'), m') = r^j (r^l - 1) / (r - 1) dist (f (m'), m')\).
So, \(f^1 (m'), f^2 (m'), ...\) is a Cauchy sequence, and as \(M\) is complete, the sequence converges to an \(m\).
Step 2:
As \(dist (f (m_1), f (m_2)) \le r dist (m_1, m_2)\), \(f\) is continuous, and so, \(f (m) = \lim_{j \to \infty} f (f^j (m')) = \lim_{j \to \infty} f^{j + 1} (m') = m\).
\(m\) is unique, because for any fixed points, \(m_1\) and \(m_2\), \(dist (m_1, m_2) = dist (f (m_1), f (m_2)) \le r dist (m_1, m_2)\), which is possible only if \(dist (m_1, m_2) = 0\).
