Chapter 7 · Metric and Normed Spaces

7.1 Metric Spaces and Completeness

Distance as an axiom: metrics on $\mathbb{R}^n$, on sequence spaces and on $C[a,b]$; open and closed sets, closure and boundary; convergence, continuity and equivalent metrics; completeness, the Banach contraction principle and the Baire category theorem.

Everything we have proved about limits so far used the real line in only one way: through the number $|x-y|$, the distance between two points. The definition of a convergent sequence, of a Cauchy sequence, of a continuous function, of an open set and of a compact set all speak about points being close. In 1906 Maurice Fréchet noticed that three properties of $|x-y|$ — it vanishes only when $x=y$, it is symmetric, and it obeys the triangle inequality — are all that these proofs ever use. Any set equipped with a "distance" having these three properties, a metric space, inherits the whole machinery. The points may be vectors in $\mathbb{R}^n$, infinite sequences, continuous functions, matrices, strings of symbols or probability distributions.

This is what makes the subject powerful. Uniform convergence of functions (§5.1) is simply convergence in the metric $d_\infty(f,g)=\sup|f-g|$; Picard's existence theorem for differential equations, Newton's method and the PageRank algorithm are all fixed points of contractions in a complete metric space; and the Baire category theorem turns "a complete space is not a countable union of thin sets" into existence proofs for objects nobody can write down. In CSIR NET, metric spaces appear in almost every paper: "is this a metric?", "find the closure / interior / boundary", "which of these spaces are complete?", "is this map a contraction?", and statements about the discrete metric, $\ell^p$ spaces and $C[a,b]$ are the staple of Part C. This section builds the language; §7.2 adds compactness, §7.3 connectedness and §7.4 norms.

Metrics and the Standard Examples

📘 Definition 7.1 — Metric space

A metric on a nonempty set $X$ is a function $d:X\times X\to[0,\infty)$ such that for all $x,y,z\in X$:

(M1) Positivity$d(x,y)\ge0$, and $d(x,y)=0\iff x=y$.
(M2) Symmetry$d(x,y)=d(y,x)$.
(M3) Triangle inequality$d(x,z)\le d(x,y)+d(y,z)$.

The pair $(X,d)$ is a metric space. If $Y\subseteq X$ is nonempty, the restriction of $d$ to $Y\times Y$ is a metric on $Y$, the subspace (or induced) metric. From (M3) and (M2) follows the reverse triangle inequality $|d(x,z)-d(y,z)|\le d(x,y)$.

The reverse inequality comes from $d(x,z)\le d(x,y)+d(y,z)$ and $d(y,z)\le d(y,x)+d(x,z)$. Notice that a metric is attached to a set: the same set carries many metrics, and changing the metric can change which sequences converge, which sets are open and which spaces are complete. This is the source of most exam questions.

📘 Definition 7.2 — The standard metric spaces
  • $\mathbb{R}^n$ with $d_p$. For $x=(x_1,\dots,x_n)$ put $\|x\|_p=\left(\sum_{i=1}^n|x_i|^p\right)^{1/p}$ for $1\le p\lt\infty$ and $\|x\|_\infty=\max_i|x_i|$, and let $d_p(x,y)=\|x-y\|_p$. The case $p=2$ is the Euclidean metric, $p=1$ the "taxicab" metric, $p=\infty$ the maximum metric. The same formulas work on $\mathbb{C}^n$.
  • The discrete metric on any set: $d(x,y)=1$ if $x\ne y$ and $d(x,x)=0$.
  • Sequence spaces. For $1\le p\lt\infty$, $\ell^p$ is the set of real (or complex) sequences $x=(x_n)$ with $\sum_n|x_n|^p\lt\infty$, with $d_p(x,y)=\|x-y\|_p$, where $\|x\|_p=\left(\sum_{n\ge1}|x_n|^p\right)^{1/p}$. $\ell^\infty$ is the set of bounded sequences with $d_\infty(x,y)=\sup_n|x_n-y_n|$. Inside $\ell^\infty$ sit $c$ (convergent sequences), $c_0$ (sequences tending to $0$) and $c_{00}$ (sequences with only finitely many nonzero terms).
  • Function spaces. $C[a,b]$, the continuous real functions on $[a,b]$, with the sup metric $d_\infty(f,g)=\max_{a\le x\le b}|f(x)-g(x)|$ (the maximum exists by the extreme value theorem, §3.1), or with the integral metric $d_1(f,g)=\int_a^b|f-g|$. More generally $B(S)$, the bounded functions on any set $S$, with $d_\infty(f,g)=\sup_S|f-g|$.
  • The French railway metric on $\mathbb{R}^2$ (all trains run through Paris $=0$): $d(x,y)=\|x-y\|_2$ if $x,y$ and $0$ are collinear, and $d(x,y)=\|x\|_2+\|y\|_2$ otherwise.
  • Bounded versions. If $d$ is a metric, so are $\min(1,d)$ and $\dfrac{d}{1+d}$ (Exercise I.2); both are bounded by $1$.

For $\mathbb{R}^n$ with $p=1,\infty$, for the discrete metric and for $d_\infty$ on $C[a,b]$ the axioms are quick to check: the triangle inequality follows from $|a+b|\le|a|+|b|$ coordinate by coordinate (for $d_\infty$ on $C[a,b]$: $|f(x)-h(x)|$ is at most $|f(x)-g(x)|+|g(x)-h(x)|$, hence at most $d_\infty(f,g)+d_\infty(g,h)$, for every $x$; then take the maximum). For $d_1$ on $C[a,b]$ the only subtle axiom is $d_1(f,g)=0\Rightarrow f=g$, which needs continuity: a continuous $h\ge0$ with $h(x_0)\gt0$ is $\gt h(x_0)/2$ on an interval, so $\int h\gt0$. For $1\lt p\lt\infty$ the triangle inequality is a genuine theorem.

📐 Theorem 7.1 — Young, Hölder and Minkowski inequalities

Let $1\lt p\lt\infty$ and let $q$ be the conjugate exponent, $\tfrac1p+\tfrac1q=1$.

  1. Young: for $a,b\ge0$, $\ ab\le\dfrac{a^p}{p}+\dfrac{b^q}{q}$.
  2. Hölder: for real or complex $x_1,\dots,x_n,y_1,\dots,y_n$, $\ \sum_{i=1}^n|x_iy_i|\le\|x\|_p\,\|y\|_q$. (For $p=q=2$ this is the Cauchy–Schwarz inequality.)
  3. Minkowski: for $1\le p\le\infty$, $\ \|x+y\|_p\le\|x\|_p+\|y\|_p$.

All three remain true for infinite sequences: if $x\in\ell^p$ and $y\in\ell^q$ then $\sum|x_ny_n|\le\|x\|_p\|y\|_q$, and if $x,y\in\ell^p$ then $x+y\in\ell^p$ with $\|x+y\|_p\le\|x\|_p+\|y\|_p$. Consequently each $d_p$ of Definition 7.2 is a metric.

Proof. (1) If $ab=0$ there is nothing to prove. Otherwise, since $\log$ is concave and $\tfrac1p+\tfrac1q=1$, $$\log\!\left(\tfrac1p a^p+\tfrac1q b^q\right)\ge\tfrac1p\log a^p+\tfrac1q\log b^q,$$ and the right-hand side is $\log(ab)$. Exponentiate.

(2) If $\|x\|_p=0$ or $\|y\|_q=0$ one side is $0$. Otherwise put $a_i=|x_i|/\|x\|_p$ and $b_i=|y_i|/\|y\|_q$, so that $\sum a_i^p=\sum b_i^q=1$. By Young, $$\sum_i a_ib_i\le\tfrac1p\sum_ia_i^p+\tfrac1q\sum_ib_i^q,$$ and the right-hand side equals $\tfrac1p+\tfrac1q=1$, which is $\sum|x_iy_i|\le\|x\|_p\|y\|_q$ after multiplying back.

(3) For $p=1$ and $p=\infty$ the triangle inequality for real (or complex) numbers, applied coordinate by coordinate, suffices. For $1\lt p\lt\infty$ write $s_i=|x_i+y_i|$. Then $$\sum s_i^p\le\sum|x_i|s_i^{p-1}+\sum|y_i|s_i^{p-1},$$ and Hölder applied to each sum gives $$\sum s_i^p\le\left(\|x\|_p+\|y\|_p\right)\Big(\sum s_i^{(p-1)q}\Big)^{1/q}.$$ Since $(p-1)q=p$, the last factor is $\left(\sum s_i^p\right)^{1/q}$; if $\sum s_i^p\gt0$, dividing gives $\left(\sum s_i^p\right)^{1-1/q}=\|x+y\|_p\le\|x\|_p+\|y\|_p$.

Infinite sequences. Apply the finite inequalities to the first $N$ terms: $\sum_{n\le N}|x_ny_n|\le\|x\|_p\|y\|_q$ and $\left(\sum_{n\le N}|x_n+y_n|^p\right)^{1/p}\le\|x\|_p+\|y\|_p$ for every $N$, where the right-hand sides are the full (finite) infinite-sum quantities. The partial sums on the left are bounded and increasing, so the series converge and the bounds pass to the limit. Finally the triangle inequality for $d_p$ is Minkowski applied to $x-y$ and $y-z$, whose sum is $x-z$. ∎

The restriction $p\ge1$ is essential: for $p=\tfrac12$ the formula $\left(|x_1-y_1|^{1/2}+|x_2-y_2|^{1/2}\right)^2$ violates the triangle inequality (Example 1(d)).

✏️ Example 1 — Metric or not?
Decide which of the following are metrics: (a) $d(x,y)=(x-y)^2$ on $\mathbb{R}$; (b) $d(x,y)=\sqrt{|x-y|}$ on $\mathbb{R}$; (c) $d(x,y)=|x^3-y^3|$ on $\mathbb{R}$; (d) $d(x,y)=\left(|x_1-y_1|^{1/2}+|x_2-y_2|^{1/2}\right)^2$ on $\mathbb{R}^2$; (e) $d(x,y)=\min(1,|x-y|)$ on $\mathbb{R}$; (f) $d(x,y)=|\sin(x-y)|$ on $\mathbb{R}$.
(a) No (M1), (M2) hold, but $d(0,2)=4\gt2=d(0,1)+d(1,2)$. Squaring a metric magnifies long distances more than short ones and breaks the triangle inequality.
(b) Yes (M1), (M2) are clear. For (M3): for $s,t\ge0$, $\sqrt{s+t}\le\sqrt s+\sqrt t$ (square both sides). So $\sqrt{|x-z|}\le\sqrt{|x-y|+|y-z|}\le\sqrt{|x-y|}+\sqrt{|y-z|}$. The same argument works for $\varphi(d)$ whenever $\varphi:[0,\infty)\to[0,\infty)$ is increasing, subadditive and $\varphi(t)=0\iff t=0$.
(c) Yes It has the form $d(x,y)=|g(x)-g(y)|$ with $g(x)=x^3$ injective. Then (M2), (M3) are inherited from $|\cdot|$, and $d(x,y)=0\iff g(x)=g(y)\iff x=y$. (With a non-injective $g$, such as $x^2$, (M1) fails: $d(1,-1)=0$.)
(d) No Take $x=(0,0)$, $y=(1,0)$, $z=(1,1)$: $d(x,y)=d(y,z)=1$ but $d(x,z)=(1+1)^2=4\gt2$. This is "$d_p$ with $p=\tfrac12$"; Minkowski's inequality fails for $p\lt1$.
(e) Yes (M1), (M2) are clear. If $|x-y|\ge1$ or $|y-z|\ge1$, the right side of (M3) is at least $1\ge d(x,z)$. Otherwise $d(x,z)\le|x-z|\le|x-y|+|y-z|=d(x,y)+d(y,z)$.
(f) No $d(0,\pi)=|\sin\pi|=0$ although $0\ne\pi$. It is only a pseudometric (it satisfies everything except "$d=0\Rightarrow x=y$"); it becomes a metric on the circle $\mathbb{R}/\pi\mathbb{Z}$.
✏️ Example 2 — Distances in three spaces, and the inclusions $\ell^1\subsetneq\ell^2\subsetneq\ell^\infty$
(a) Find $d_1,d_2,d_\infty$ between $x=(1,2,-2)$ and $y=(4,-2,10)$ in $\mathbb{R}^3$. (b) Find $d_\infty(f,g)$ and $d_1(f,g)$ for $f(x)=x$, $g(x)=x^2$ in $C[0,1]$. (c) Show that $u=(1/n)$ and $v=(1/(n+1))$ lie in $\ell^2$ but not in $\ell^1$, and find $d_2(u,v)$. (d) Prove that if $1\le p\lt q\le\infty$ then $\ell^p\subseteq\ell^q$ with $\|x\|_q\le\|x\|_p$, and that the inclusion is strict.
(a) $x-y=(-3,4,-12)$: $d_1=3+4+12=19$, $d_2=\sqrt{9+16+144}=13$, $d_\infty=12$. Note $d_\infty\le d_2\le d_1$, as always (Theorem 7.5).
(b) $h(x)=x-x^2\ge0$ on $[0,1]$ has its maximum at $x=\tfrac12$: $d_\infty(f,g)=\tfrac14$. And $d_1(f,g)=\int_0^1(x-x^2)\,dx=\tfrac12-\tfrac13=\tfrac16$.
(c) $\sum1/n^2=\pi^2/6\lt\infty$ but $\sum1/n=\infty$ (§2.3), and similarly for $v$. Using $\tfrac1n-\tfrac1{n+1}=\tfrac1{n(n+1)}$ and partial fractions $\tfrac1{n^2(n+1)^2}=\tfrac1{n^2}+\tfrac1{(n+1)^2}-\tfrac2{n}+\tfrac2{n+1}$, $$d_2(u,v)^2=\sum_{n\ge1}\frac1{n^2(n+1)^2}=\frac{\pi^2}6+\left(\frac{\pi^2}6-1\right)-2=\frac{\pi^2}3-3,$$ so $d_2(u,v)=\sqrt{\pi^2/3-3}\approx0.5384$.
(d) For $q=\infty$: $|x_n|\le\|x\|_p$ for each $n$. For $q\lt\infty$, if $x\ne0$ put $y=x/\|x\|_p$, so $\|y\|_p=1$ and every $|y_n|\le1$. Then $|y_n|^q\le|y_n|^p$ (because $q\gt p$ and $|y_n|\le1$), so $\sum|y_n|^q\le\sum|y_n|^p=1$, i.e. $\|y\|_q\le1=\|y\|_p$; multiply by $\|x\|_p$. Strictness: $x_n=n^{-1/p}$ has $\sum x_n^p=\sum\tfrac1n=\infty$ but $\sum x_n^q=\sum n^{-q/p}\lt\infty$ since $q/p\gt1$ (and $(1,1,1,\dots)\in\ell^\infty\setminus\ell^p$).
Contrast On $C[0,1]$ the inequalities go the other way: $d_1\le d_\infty$, so the large exponent gives the strong metric for functions on a bounded interval, while for sequences ($\ell^p$) it is the small exponent that is restrictive.

Open Sets, Closed Sets, Closure and Boundary

📘 Definition 7.3 — Balls, bounded sets, diameter, distance to a set

Let $(X,d)$ be a metric space, $a\in X$, $r\gt0$. The open ball is $B(a,r)=\{x\in X:d(x,a)\lt r\}$ and the closed ball is $\overline{B}(a,r)=\{x\in X:d(x,a)\le r\}$; the sphere is $S(a,r)=\{x:d(x,a)=r\}$. A set $A\subseteq X$ is bounded if $A\subseteq B(a,r)$ for some $a,r$; its diameter is $\operatorname{diam}A=\sup\{d(x,y):x,y\in A\}$. For nonempty $A$ the distance from $x$ to $A$ is $d(x,A)=\inf_{a\in A}d(x,a)$, and $d(A,B)=\inf\{d(a,b):a\in A,\ b\in B\}$.

Balls depend on the metric. In $(\mathbb{R}^2,d_2)$ they are discs, in $d_1$ diamonds, in $d_\infty$ squares; in the discrete metric $B(a,r)=\{a\}$ for $r\le1$ and $B(a,r)=X$ for $r\gt1$; and in a subspace $Y\subseteq X$ the ball is $B_Y(a,r)=B_X(a,r)\cap Y$ — for example, in $Y=[0,1]$ with the usual metric, $B_Y(0,\tfrac12)=[0,\tfrac12)$. Interactive 1 below lets you compare them.

📘 Definition 7.4 — Open and closed sets

A set $U\subseteq X$ is open if for every $x\in U$ there is $r\gt0$ with $B(x,r)\subseteq U$. A set $F\subseteq X$ is closed if $X\setminus F$ is open. A set that is both is clopen. A neighbourhood of $x$ is any set containing an open set that contains $x$.

📐 Theorem 7.2 — The open sets of a metric space
  1. Every open ball is open; every closed ball and every sphere is closed; every finite set is closed.
  2. $\varnothing$ and $X$ are open (and closed). An arbitrary union of open sets is open, and a finite intersection of open sets is open.
  3. Dually, an arbitrary intersection of closed sets is closed and a finite union of closed sets is closed.
  4. A set is open if and only if it is a union of open balls.

Proof. (1) Let $x\in B(a,r)$ and $s=r-d(x,a)\gt0$. If $d(y,x)\lt s$ then $d(y,a)\le d(y,x)+d(x,a)$, which is less than $s+d(x,a)=r$, so $B(x,s)\subseteq B(a,r)$. For the closed ball, let $x\notin\overline{B}(a,r)$ and $s=d(x,a)-r\gt0$; if $d(y,x)\lt s$ then $d(y,a)\ge d(x,a)-d(x,y)\gt r$, so $B(x,s)$ misses $\overline B(a,r)$ and the complement is open. $S(a,r)=\overline B(a,r)\setminus B(a,r)$ is the intersection of the closed sets $\overline B(a,r)$ and $X\setminus B(a,r)$. For a single point $\{a\}$: if $x\ne a$, $B(x,d(x,a))$ misses $a$; finite sets are finite unions of points (use (3)).

(2) The conditions for $\varnothing$ (vacuous) and $X$ (any $r$) are immediate. If $x\in\bigcup U_\alpha$ then $x\in U_\beta$ for some $\beta$, and a ball around $x$ inside $U_\beta$ lies inside the union. If $x\in U_1\cap\dots\cap U_n$ with $B(x,r_i)\subseteq U_i$, then $B(x,\min_ir_i)$ lies in every $U_i$; the minimum of finitely many positive numbers is positive, which is where finiteness is used.

(3) is (2) after taking complements with De Morgan's laws (§1.1). (4) A union of balls is open by (1)–(2); conversely, an open $U$ equals $\bigcup_{x\in U}B(x,r_x)$ for the balls chosen in the definition. ∎

The finiteness in (2) cannot be dropped: $\bigcap_n(-\tfrac1n,\tfrac1n)=\{0\}$ is not open in $\mathbb{R}$, and dually $\bigcup_n[\tfrac1n,1]=(0,1]$ is not closed.

📘 Definition 7.5 — Interior, limit points, closure, boundary, dense sets

Let $A\subseteq X$ and $x\in X$.

  • $x$ is an interior point of $A$ if $B(x,r)\subseteq A$ for some $r\gt0$; the interior $A^\circ$ is the set of interior points.
  • $x$ is a limit point (accumulation point) of $A$ if every ball $B(x,r)$ contains a point of $A$ other than $x$; $A'$ denotes the set of limit points. A point of $A$ that is not a limit point of $A$ is an isolated point of $A$.
  • The closure is $\overline A=A\cup A'$; $x\in\overline A$ iff every ball $B(x,r)$ meets $A$.
  • The boundary is $\partial A=\overline A\setminus A^\circ$; $x\in\partial A$ iff every ball around $x$ meets both $A$ and $X\setminus A$.
  • $A$ is dense in $X$ if $\overline A=X$, i.e. every nonempty open set meets $A$. $X$ is separable if it has a countable dense subset.
📐 Theorem 7.3 — Interior and closure

Let $A\subseteq X$.

  1. $A^\circ$ is open and is the largest open set contained in $A$; $A$ is open iff $A=A^\circ$.
  2. $\overline A$ is closed and is the smallest closed set containing $A$ (the intersection of all closed sets containing $A$); $A$ is closed iff $A=\overline A$ iff $A'\subseteq A$.
  3. Sequential description: $x\in\overline A$ iff there is a sequence $(a_n)$ in $A$ with $a_n\to x$ iff $d(x,A)=0$. Hence $A$ is closed iff it contains the limit of every convergent sequence of its points.
  4. $X\setminus\overline A=(X\setminus A)^\circ$ and $X\setminus A^\circ=\overline{X\setminus A}$. Consequently $\partial A=\overline A\cap\overline{X\setminus A}$ is closed, and $\partial A=\varnothing$ iff $A$ is clopen.

Proof. (1) If $x\in A^\circ$ with $B(x,r)\subseteq A$, every $y\in B(x,r)$ has a ball $B(y,s)\subseteq B(x,r)\subseteq A$ (Theorem 7.2(1)), so $B(x,r)\subseteq A^\circ$: $A^\circ$ is open. If $U\subseteq A$ is open, each point of $U$ has a ball inside $U\subseteq A$, so $U\subseteq A^\circ$.

(4) $x\notin\overline A$ $\iff$ some ball $B(x,r)$ misses $A$ $\iff$ some ball lies in $X\setminus A$ $\iff$ $x\in(X\setminus A)^\circ$. The second identity is the first applied to $X\setminus A$, complemented.

(2) By (4) and (1), $X\setminus\overline A$ is open, so $\overline A$ is closed. If $F\supseteq A$ is closed and $x\notin F$, some ball around $x$ lies in the open set $X\setminus F$, hence misses $A$, so $x\notin\overline A$: $\overline A\subseteq F$. Thus $A$ is closed iff $A=\overline A=A\cup A'$ iff $A'\subseteq A$.

(3) If $x\in\overline A$, choose $a_n\in A\cap B(x,\tfrac1n)$; then $a_n\to x$. If $a_n\to x$ with $a_n\in A$, then $d(x,A)\le d(x,a_n)\to0$. If $d(x,A)=0$, every ball $B(x,r)$ contains some $a$ with $d(x,a)\lt r$. The boundary statements follow from $\partial A=\overline A\cap(X\setminus A^\circ)$ and, by (4), $X\setminus A^\circ=\overline{X\setminus A}$: an intersection of closed sets; it is empty iff $\overline A\subseteq A^\circ$, i.e. iff $\overline A=A=A^\circ$. ∎

The closure of the open ball $B(a,r)$ is always contained in the closed ball $\overline B(a,r)$ (the latter is a closed set containing $B(a,r)$), and in $\mathbb{R}^n$ the two are equal. In general they are not: in a discrete space $\overline{B(a,1)}=\{a\}$ while $\overline B(a,1)=X$. Similarly $\partial B(a,r)\subseteq S(a,r)$ with equality in $\mathbb{R}^n$ but not in general.

Interactive 1 — What an Open Ball Looks Like Depends on the Metric

The blue region is the open ball $B(a,r)$ around $a=(1,\,0.6)$ in the chosen metric on $\mathbb{R}^2$. The dashed circles are the largest Euclidean disc centred at $a$ inside the ball and the smallest one containing it. When both exist for every $r$, the metric has the same open sets as the Euclidean one. Press Play to grow and shrink the ball (in the $\ell^p$ mode Play sweeps $p$); try the discrete and railway metrics.

metric—
radius r—
Euclidean disc inside B(a, r)—
Euclidean disc containing B(a, r)—
✏️ Example 3 — Interior, closure and boundary in four spaces
Find the interior, closure and boundary of: (a) the set $A=D\cup\{(2,0)\}$ in $(\mathbb{R}^2,d_2)$, where $D=\{0\lt x^2+y^2\le1\}$; (b) $\mathbb{Q}$ in $\mathbb{R}$; (c) an arbitrary set $A$ in a discrete space; (d) the set $\mathcal P$ of polynomial functions, and the set $U=\{f:f(x)\gt0\ \text{for all }x\}$, in $(C[0,1],d_\infty)$.
(a) Interior: $\{0\lt x^2+y^2\lt1\}$ (the punctured open disc; $(2,0)$ is isolated, so not interior, and points of the unit circle have points outside $A$ arbitrarily close). Closure: $\{x^2+y^2\le1\}\cup\{(2,0)\}$ (the origin is a limit point). Boundary: closure minus interior $=\{x^2+y^2=1\}\cup\{(0,0)\}\cup\{(2,0)\}$.
(b) Every interval contains rationals and irrationals (§1.2), so no ball lies inside $\mathbb{Q}$ and every ball meets $\mathbb{Q}$: $\mathbb{Q}^\circ=\varnothing$, $\overline{\mathbb{Q}}=\mathbb{R}$, $\partial\mathbb{Q}=\mathbb{R}$. A set can have a boundary much "bigger" than itself.
(c) $B(x,\tfrac12)=\{x\}$, so every set is open; hence every set is also closed. So $A^\circ=\overline A=A$, $\partial A=\varnothing$, and the only dense set is $X$ itself. Every point is isolated.
(d) Polynomials By the Weierstrass approximation theorem (§5.2), every $f\in C[0,1]$ is a uniform limit of polynomials: $\overline{\mathcal P}=C[0,1]$. But $\mathcal P^\circ=\varnothing$: if $p\in\mathcal P$ and $r\gt0$, then $g(x)=p(x)+\tfrac r2|x-\tfrac12|$ satisfies $d_\infty(g,p)=\tfrac r4\lt r$ and $g$ is not a polynomial (it is not differentiable at $\tfrac12$). Hence $\partial\mathcal P=C[0,1]$ — the function-space analogue of $\mathbb{Q}$ in $\mathbb{R}$.
(d) Positive functions $U$ is open: if $f\in U$, its minimum $m=\min f$ is attained, so $m\gt0$, and every $g$ with $d_\infty(g,f)\lt m$ is positive. $\overline U=\{f:f\ge0\}$: this set is closed (if $f_n\ge0$ and $f_n\to f$ uniformly, then $f\ge0$), and every $f\ge0$ is the limit of $f+\tfrac1n\in U$. So $\partial U=\{f\ge0:\ f(x_0)=0\text{ for some }x_0\}$. (In $(C[0,1],d_1)$ the set $U$ is not open: $f\equiv1$ is $d_1$-close to functions with a narrow negative spike.)
🧭 Problem-solving strategy — open, closed, or neither?
  1. Preimage trick (fastest). If $A=\{x: g(x)\lt c\}$ or $\{x:g(x)\ne c\}$ with $g$ continuous, $A$ is open; if $A=\{x:g(x)\le c\}$, $\{g(x)=c\}$ or $\{g\ge c\}$, $A$ is closed (Theorem 7.4 below). In $C[a,b]$ with $d_\infty$, evaluation $f\mapsto f(x_0)$, $f\mapsto\max f$, $f\mapsto\int_a^bf$ are continuous (they are Lipschitz with constants $1$, $1$, $b-a$).
  2. Not closed? Exhibit a sequence in $A$ converging to a point outside $A$ (Theorem 7.3(3)).
  3. Not open? Exhibit a point $x\in A$ and points outside $A$ arbitrarily close to $x$.
  4. Check the ambient space. "Open" and "closed" are relative: $[0,\tfrac12)$ is open in $[0,1]$, and $\mathbb{Q}\cap(-\sqrt2,\sqrt2)$ is clopen in $\mathbb{Q}$.
  5. Check the metric. In a discrete space every set is clopen; in $C[0,1]$ with $d_1$ far fewer sets are open than with $d_\infty$.

Convergence, Continuity and Equivalent Metrics

📘 Definition 7.6 — Convergent and Cauchy sequences
A sequence $(x_n)$ in $(X,d)$ converges to $x\in X$, written $x_n\to x$, if $d(x_n,x)\to0$, i.e. for every $\varepsilon\gt0$ there is $N$ with $d(x_n,x)\lt\varepsilon$ for all $n\ge N$. It is a Cauchy sequence if for every $\varepsilon\gt0$ there is $N$ with $d(x_m,x_n)\lt\varepsilon$ for all $m,n\ge N$.

The proofs of §2.1 carry over word for word: a limit is unique (if $x_n\to x$ and $x_n\to y$ then $d(x,y)\le d(x,x_n)+d(x_n,y)\to0$); a convergent sequence is Cauchy; a Cauchy sequence is bounded; and a Cauchy sequence with a convergent subsequence converges to the same limit (given $\varepsilon$, choose $N$ for the Cauchy condition with $\varepsilon/2$ and then $n_k\ge N$ with $d(x_{n_k},x)\lt\varepsilon/2$). Convergence depends on the metric: in $\mathbb{R}^n$ with any $d_p$ it means coordinatewise convergence; in $(C[a,b],d_\infty)$ it is uniform convergence; in a discrete space it means "eventually constant".

📘 Definition 7.7 — Continuous, uniformly continuous and Lipschitz maps; isometries, homeomorphisms, contractions

Let $f:(X,d)\to(Y,\rho)$.

  • $f$ is continuous at $a$ if for every $\varepsilon\gt0$ there is $\delta\gt0$ with $\rho(f(x),f(a))\lt\varepsilon$ whenever $d(x,a)\lt\delta$; continuous if continuous at every point; uniformly continuous if $\delta$ can be chosen independent of $a$.
  • $f$ is Lipschitz with constant $k\ge0$ if $\rho(f(x),f(y))\le k\,d(x,y)$ for all $x,y$. A Lipschitz self-map $T:X\to X$ with constant $k\lt1$ is a contraction.
  • $f$ is an isometry if $\rho(f(x),f(y))=d(x,y)$ for all $x,y$; a homeomorphism if it is a bijection with $f$ and $f^{-1}$ continuous.
📐 Theorem 7.4 — Four descriptions of continuity
For $f:(X,d)\to(Y,\rho)$ the following are equivalent: (i) $f$ is continuous; (ii) $f$ is sequentially continuous: $x_n\to x$ in $X$ implies $f(x_n)\to f(x)$ in $Y$; (iii) $f^{-1}(V)$ is open in $X$ for every open $V\subseteq Y$; (iv) $f^{-1}(F)$ is closed in $X$ for every closed $F\subseteq Y$. Moreover Lipschitz $\Rightarrow$ uniformly continuous $\Rightarrow$ continuous, and the distance functions $x\mapsto d(x,a)$ and $x\mapsto d(x,A)$ are Lipschitz with constant $1$.

Proof. (i)⇒(ii): given $\varepsilon$, take $\delta$ for the point $x$, and $N$ with $d(x_n,x)\lt\delta$ for $n\ge N$; then $\rho(f(x_n),f(x))\lt\varepsilon$. (ii)⇒(i): if $f$ is not continuous at $a$, there is $\varepsilon\gt0$ such that every $\delta=\tfrac1n$ fails: some $x_n$ has $d(x_n,a)\lt\tfrac1n$ but $\rho(f(x_n),f(a))\ge\varepsilon$; then $x_n\to a$ and $f(x_n)\not\to f(a)$.

(i)⇒(iii): let $V$ be open and $a\in f^{-1}(V)$. Some $B(f(a),\varepsilon)\subseteq V$; the corresponding $\delta$ gives $f(B(a,\delta))\subseteq B(f(a),\varepsilon)\subseteq V$, i.e. $B(a,\delta)\subseteq f^{-1}(V)$. (iii)⇒(i): $f^{-1}(B(f(a),\varepsilon))$ is open and contains $a$, so it contains some $B(a,\delta)$ — that is the $\varepsilon$–$\delta$ condition. (iii)⇔(iv) because $f^{-1}(Y\setminus F)=X\setminus f^{-1}(F)$ (§1.1).

A Lipschitz map with constant $k\gt0$ is uniformly continuous with $\delta=\varepsilon/k$. For the distance functions: for any $a'\in A$, $d(x,A)\le d(x,a')\le d(x,y)+d(y,a')$; taking the infimum over $a'$ gives $d(x,A)\le d(x,y)+d(y,A)$, and by symmetry $|d(x,A)-d(y,A)|\le d(x,y)$. ∎

So, for example, $\{x:d(x,A)\lt\varepsilon\}$ is open and $\{x:d(x,A)\le\varepsilon\}$ is closed, and in $(C[0,1],d_\infty)$ the set $\{f:\int_0^1f=1,\ f(0)=0\}$ is closed (the intersection of two preimages of points under continuous maps).

📘 Definition 7.8 — Equivalent metrics
Two metrics $d$ and $\rho$ on the same set $X$ are topologically equivalent if they have the same open sets (equivalently, the identity map $(X,d)\to(X,\rho)$ is a homeomorphism; equivalently, they have the same convergent sequences). They are strongly (or Lipschitz) equivalent if there are constants $0\lt\alpha\le\beta$ with $\alpha\,d(x,y)\le\rho(x,y)\le\beta\,d(x,y)$ for all $x,y$.
📐 Theorem 7.5 — Comparing metrics
  1. Strongly equivalent metrics are topologically equivalent, and they have the same Cauchy sequences and the same bounded sets; so one is complete iff the other is.
  2. On $\mathbb{R}^n$, for $1\le p\le\infty$: $\ \|x\|_\infty\le\|x\|_p\le n^{1/p}\|x\|_\infty$. Hence all the metrics $d_p$ are strongly equivalent; in particular $d_\infty\le d_2\le d_1\le\sqrt n\,d_2\le n\,d_\infty$.
  3. For any metric $d$, the bounded metrics $\min(1,d)$ and $d/(1+d)$ are topologically equivalent to $d$ and have the same Cauchy sequences as $d$ — but they need not be strongly equivalent to it.

Proof. (1) If $\alpha d\le\rho\le\beta d$, then $B_d(x,r/\beta)\subseteq B_\rho(x,r)$ and $B_\rho(x,\alpha r)\subseteq B_d(x,r)$: every $\rho$-ball around $x$ contains a $d$-ball around $x$ and vice versa, so the open sets coincide. The inequalities also transport the Cauchy condition and boundedness, with $\varepsilon$ rescaled.

(2) $\max_i|x_i|^p\le\sum_i|x_i|^p\le n\max_i|x_i|^p$; take $p$-th roots. For $\|x\|_2\le\|x\|_1$ square: $\left(\sum|x_i|\right)^2$ equals $\sum|x_i|^2$ plus the non-negative cross terms $\sum_{i\ne j}|x_i||x_j|$. For $\|x\|_1\le\sqrt n\|x\|_2$ apply Cauchy–Schwarz to $(|x_i|)$ and $(1,\dots,1)$.

(3) For $r\lt1$ the $\min(1,d)$-ball of radius $r$ is the $d$-ball of radius $r$, and every open set is a union of small balls. For $\sigma=d/(1+d)$: $\sigma\lt r\iff d\lt r/(1-r)$ when $r\lt1$, so again small balls of one kind are balls of the other kind. The Cauchy conditions with $\varepsilon\lt1$ coincide in the same way. But $d$ may be unbounded while $\min(1,d)\le1$, so no inequality $d\le\beta\min(1,d)$ can hold for the usual metric on $\mathbb{R}$. ∎

Part (3) shows that boundedness is not a topological property: every metric space can be re-metrised, without changing its open sets or its convergent sequences, so that it becomes bounded. Example 4 shows that completeness is not topological either.

✏️ Example 4 — Same open sets, different Cauchy sequences
On $\mathbb{R}$ let $d(x,y)=|x-y|$ and $\rho(x,y)=|\arctan x-\arctan y|$. (a) Show that $\rho$ is a metric topologically equivalent to $d$. (b) Show that they are not strongly equivalent. (c) Show that $(\mathbb{R},\rho)$ is not complete, although $(\mathbb{R},d)$ is. (d) Is $\min(1,d)$ strongly equivalent to $d$?
(a) $\rho(x,y)=|g(x)-g(y)|$ with $g=\arctan$ injective, so $\rho$ is a metric (Example 1(c)). $g$ is a homeomorphism of $\mathbb{R}$ onto $(-\tfrac\pi2,\tfrac\pi2)$ (continuous, strictly increasing, continuous inverse $\tan$). Hence $x_n\to x$ in $d$ $\iff$ $\arctan x_n\to\arctan x$ $\iff$ $x_n\to x$ in $\rho$: the same convergent sequences, hence the same closed sets and the same open sets.
(b) $\rho\lt\pi$ always while $d$ is unbounded, so $d\le\beta\rho$ fails for every $\beta$. (In the other direction $\rho\le d$ by the mean value theorem, since $|\arctan'|\le1$.)
(c) $x_n=n$: $\rho(m,n)=|\arctan m-\arctan n|\to0$ as $m,n\to\infty$ (both terms tend to $\tfrac\pi2$), so $(n)$ is $\rho$-Cauchy. If $n\to x$ in $\rho$, then $n\to x$ in $d$ by (a) — impossible. So $(\mathbb{R},\rho)$ is not complete. In fact $g$ is an isometry of $(\mathbb{R},\rho)$ onto the incomplete space $(-\tfrac\pi2,\tfrac\pi2)$ with the usual metric.
(d) No: $d(0,n)=n$ but $\min(1,d)(0,n)=1$. Yet by Theorem 7.5(3) they have the same Cauchy sequences, so $(\mathbb{R},\min(1,d))$ is complete. Topological equivalence alone preserves neither boundedness nor completeness; strong equivalence preserves both.

Complete Metric Spaces

📘 Definition 7.9 — Complete metric space
A metric space $(X,d)$ is complete if every Cauchy sequence in $X$ converges to a point of $X$. A complete normed vector space is called a Banach space (§7.4).

The real line is complete (§2.1, Cauchy criterion), and $\mathbb{Q}$ is not: the decimal approximations $1,\ 1.4,\ 1.41,\ 1.414,\dots$ of $\sqrt2$ form a Cauchy sequence of rationals with no rational limit. Completeness is the metric-space form of "no holes".

📐 Theorem 7.6 — The standard complete spaces
The following metric spaces are complete: (a) $\mathbb{R}^n$ and $\mathbb{C}^n$ with any $d_p$, $1\le p\le\infty$; (b) $\ell^p$ for $1\le p\lt\infty$, and $\ell^\infty$; (c) $C[a,b]$ with the sup metric $d_\infty$, and more generally $B(S)$ and the space $C_b(X)$ of bounded continuous functions on a metric space $X$; (d) every discrete metric space.

Proof. (a) By Theorem 7.5(2) it suffices to treat $d_\infty$. If $(x^{(k)})$ is Cauchy, then for each coordinate $i$, $|x^{(k)}_i-x^{(m)}_i|\le d_\infty(x^{(k)},x^{(m)})$, so $(x^{(k)}_i)_k$ is a Cauchy sequence of reals with a limit $x_i$. Given $\varepsilon$, choose $N$ with $d_\infty(x^{(k)},x^{(m)})\lt\varepsilon$ for $k,m\ge N$; letting $m\to\infty$ in each of the finitely many coordinates gives $d_\infty(x^{(k)},x)\le\varepsilon$ for $k\ge N$.

(b) Let $(x^{(k)})$ be Cauchy in $\ell^p$, $1\le p\lt\infty$. As in (a), $|x^{(k)}_n-x^{(m)}_n|\le\|x^{(k)}-x^{(m)}\|_p$, so each coordinate converges: $x^{(k)}_n\to x_n$. Given $\varepsilon\gt0$ choose $N$ with $\|x^{(k)}-x^{(m)}\|_p\lt\varepsilon$ for $k,m\ge N$. For every finite $M$, $$\sum_{n=1}^M|x^{(k)}_n-x^{(m)}_n|^p\lt\varepsilon^p\qquad(k,m\ge N).$$ Let $m\to\infty$ (finitely many terms): $\sum_{n\le M}|x^{(k)}_n-x_n|^p\le\varepsilon^p$. This holds for every $M$, so $\sum_{n\ge1}|x^{(k)}_n-x_n|^p\le\varepsilon^p$. Thus $x^{(k)}-x\in\ell^p$, hence $x=x^{(k)}-(x^{(k)}-x)\in\ell^p$ by Minkowski, and $\|x^{(k)}-x\|_p\le\varepsilon$ for $k\ge N$: $x^{(k)}\to x$ in $\ell^p$. For $\ell^\infty$ replace the sums by suprema. The two-step pattern — find the candidate limit coordinatewise, then show it lies in the space and is the limit in the metric — is the template for every completeness proof.

(c) A $d_\infty$-Cauchy sequence $(f_k)$ is uniformly Cauchy, so it converges uniformly to some function $f$ (Cauchy criterion for uniform convergence, §5.1); $f$ is bounded, being within $1$ of some $f_k$, and a uniform limit of continuous functions is continuous (§5.2). Uniform convergence is exactly $d_\infty(f_k,f)\to0$. (d) A Cauchy sequence in a discrete space satisfies $d(x_m,x_n)\lt1$, i.e. $x_m=x_n$, for $m,n\ge N$: it is eventually constant, hence convergent. ∎

📐 Theorem 7.7 — Complete subspaces are the closed subsets
Let $(X,d)$ be a metric space and $Y\subseteq X$, with the subspace metric. (a) If $Y$ is complete, then $Y$ is closed in $X$. (b) If $X$ is complete and $Y$ is closed in $X$, then $Y$ is complete. So inside a complete space, "complete" and "closed" mean the same thing.

Proof. (a) Let $x\in\overline Y$ and choose $y_n\in Y$ with $y_n\to x$ (Theorem 7.3(3)). Then $(y_n)$ is Cauchy, so it converges to some $y\in Y$; by uniqueness of limits in $X$, $x=y\in Y$. (b) A Cauchy sequence in $Y$ is Cauchy in $X$, so it converges to some $x\in X$; as $Y$ is closed, $x\in Y$. ∎

For example, $c_0$ is closed in $\ell^\infty$ (Exercise III.6), hence complete; $[0,1]$, $\mathbb{Z}$ and $\{0\}\cup\{\tfrac1n\}$ are complete; $(0,1]$, $\mathbb{Q}$ and $\{\tfrac1n:n\in\mathbb{N}\}$ are not.

📐 Theorem 7.8 — Cantor's intersection theorem
A metric space $X$ is complete if and only if every decreasing sequence $F_1\supseteq F_2\supseteq\cdots$ of nonempty closed sets with $\operatorname{diam}F_n\to0$ has nonempty intersection. The intersection is then a single point.

Proof. Suppose $X$ is complete. Choose $x_n\in F_n$. For $m\ge n$ both $x_m,x_n$ lie in $F_n$, so $d(x_m,x_n)\le\operatorname{diam}F_n\to0$: the sequence is Cauchy, with a limit $x$. For each fixed $n$, the tail $(x_m)_{m\ge n}$ lies in the closed set $F_n$, so $x\in F_n$. Thus $x\in\bigcap F_n$; and two points of the intersection are at distance $\le\operatorname{diam}F_n$ for every $n$, hence equal.

Conversely, let $(x_n)$ be Cauchy and $F_n=\overline{\{x_k:k\ge n\}}$. These are nonempty, closed and decreasing, and $\operatorname{diam}F_n=\operatorname{diam}\{x_k:k\ge n\}\to0$ by the Cauchy condition (closure does not increase diameter, because $d$ is continuous). If $x\in\bigcap F_n$, then $d(x_n,x)\le\operatorname{diam}F_n\to0$. ∎

Both hypotheses matter even in $\mathbb{R}$: $F_n=[n,\infty)$ is a decreasing sequence of nonempty closed sets with empty intersection (diameters infinite), and $F_n=(0,\tfrac1n]$ has diameters $\to0$ and empty intersection (not closed).

📐 Theorem 7.9 — Completion (statement and idea)
For every metric space $(X,d)$ there is a complete metric space $(\widehat X,\widehat d)$ and an isometry $\iota:X\to\widehat X$ whose image $\iota(X)$ is dense in $\widehat X$. The completion is unique: any two are isometric by an isometry that respects the embeddings of $X$.

Idea of proof. Mimic the construction of $\mathbb{R}$ from $\mathbb{Q}$ by Cauchy sequences. Call two Cauchy sequences $(x_n),(y_n)$ in $X$ equivalent if $d(x_n,y_n)\to0$; let $\widehat X$ be the set of equivalence classes and $\widehat d([x_n],[y_n])=\lim d(x_n,y_n)$ (the limit exists because $|d(x_n,y_n)-d(x_m,y_m)|$ is at most $d(x_n,x_m)+d(y_n,y_m)$, which makes $d(x_n,y_n)$ a Cauchy sequence of reals, and it does not depend on the representatives). The map $\iota(x)=[x,x,x,\dots]$ is an isometry; a class $[x_n]$ is the $\widehat d$-limit of $\iota(x_n)$, so $\iota(X)$ is dense; and a diagonal argument shows that a Cauchy sequence of classes converges. Uniqueness: an isometry between dense subsets extends uniquely to the completions by continuity. ∎

In practice one recognises the completion as the closure of $X$ inside a known complete space: the completion of $\mathbb{Q}$ is $\mathbb{R}$; of $(0,1)$ is $[0,1]$; of $c_{00}$ with $d_\infty$ is $c_0$, and with $d_p$ is $\ell^p$; of the polynomials with $d_\infty$ on $[a,b]$ is $C[a,b]$ (Weierstrass). The completion of $(C[a,b],d_1)$ is the Lebesgue space $L^1[a,b]$ of §4.5 — which is one reason the Lebesgue integral was needed.

✏️ Example 5 — Complete or not?
Decide whether each space is complete: (a) $\mathbb{N}$ with $d(m,n)=\left|\tfrac1m-\tfrac1n\right|$; (b) $(0,\infty)$ with $d(x,y)=|\log x-\log y|$; (c) $c_{00}$ with $d_\infty$; (d) $\mathbb{R}$ with $d(x,y)=|e^x-e^y|$; (e) the set $\{x\in\ell^2:\ |x_n|\le1\ \text{for all }n\}$ with $d_2$.
(a) No $n\mapsto\tfrac1n$ is an isometry onto $\{\tfrac1n\}\subseteq\mathbb{R}$, which is not closed in $\mathbb{R}$ (it misses its limit point $0$). Concretely, $x_n=n$ is Cauchy ($|\tfrac1m-\tfrac1n|\to0$) but $d(n,k)\to\tfrac1k\ne0$ for every fixed $k$. Note that the topology is discrete (each point is isolated), yet the space is not complete — the discrete metric would make it complete.
(b) Yes $\log$ is an isometry of this space onto $(\mathbb{R},|\cdot|)$, which is complete. So the "hole" at $0$ has been pushed to infinite distance.
(c) No $x^{(k)}=(1,\tfrac12,\dots,\tfrac1k,0,0,\dots)\in c_{00}$ satisfies $d_\infty(x^{(k)},x^{(m)})=\tfrac1{k+1}$ for $m\gt k$: Cauchy. Its $d_\infty$-limit in $\ell^\infty$ is $(\tfrac1n)$, which is not in $c_{00}$; by Theorem 7.7(a), $c_{00}$ is not complete. Its completion is $c_0$.
(d) No $x\mapsto e^x$ is an isometry onto $(0,\infty)$ with the usual metric, which is not closed in $\mathbb{R}$. The sequence $x_n=-n$ is Cauchy ($|e^{-m}-e^{-n}|\to0$) with no limit.
(e) Yes It is closed in the complete space $\ell^2$: if $x^{(k)}\to x$ in $\ell^2$ then each coordinate converges, so $|x_n|\le1$. Theorem 7.7(b). (It is closed and bounded — but §7.2 shows it is not compact.)

The Banach Contraction Principle and the Baire Category Theorem

Complete metric spaces have two theorems that make them indispensable. The first produces solutions of equations by iteration; the second shows that a complete space is too "large" to be a countable union of thin pieces.

📐 Theorem 7.10 — Banach contraction principle (Banach fixed point theorem, 1922)

Let $(X,d)$ be a nonempty complete metric space and $T:X\to X$ a contraction: $d(Tx,Ty)\le k\,d(x,y)$ for all $x,y$, with a constant $0\le k\lt1$. Then:

  1. $T$ has exactly one fixed point $x^*$ ($Tx^*=x^*$);
  2. for every starting point $x_0$, the iterates $x_{n+1}=Tx_n$ converge to $x^*$;
  3. a priori estimate: $d(x_n,x^*)\le\dfrac{k^n}{1-k}\,d(x_0,x_1)$; a posteriori estimate: $d(x_n,x^*)\le\dfrac{k}{1-k}\,d(x_{n-1},x_n)$.

Proof. By induction, $d(x_{j},x_{j+1})\le k^j d(x_0,x_1)$. For $m\gt n$, the triangle inequality and the geometric series give $$d(x_n,x_m)\le\sum_{j=n}^{m-1}k^j\,d(x_0,x_1),$$ and summing the geometric series, $$d(x_n,x_m)\le\frac{k^n}{1-k}\,d(x_0,x_1).\qquad(*)$$ Since $k^n\to0$, $(x_n)$ is Cauchy; by completeness $x_n\to x^*$ for some $x^*\in X$. A contraction is continuous, so $Tx^*=\lim Tx_n=\lim x_{n+1}=x^*$. If also $Ty=y$, then $d(x^*,y)=d(Tx^*,Ty)\le k\,d(x^*,y)$, and $k\lt1$ forces $d(x^*,y)=0$. Letting $m\to\infty$ in $(*)$ gives the a priori estimate (the distance function is continuous). Applying it to the sequence that starts at $x_{n-1}$ gives $d(x_n,x^*)\le\frac{k}{1-k}d(x_{n-1},x_n)$. ∎

Every hypothesis is needed. On the incomplete space $(0,1]$, $Tx=x/2$ is a contraction with no fixed point. On the complete space $[1,\infty)$, $Tx=x+\tfrac1x$ satisfies $|Tx-Ty|=|x-y|\left(1-\tfrac1{xy}\right)\lt|x-y|$ for $x\ne y$, but there is no single $k\lt1$, and $Tx\gt x$ has no solution of $Tx=x$. And $Tx=x+1$ on $\mathbb{R}$ is an isometry ($k=1$) without fixed points. On a compact space the weaker condition $d(Tx,Ty)\lt d(x,y)$ does suffice (Edelstein's theorem, §7.2).

A useful variant: if some iterate $T^m$ is a contraction on a complete space, then $T$ has a unique fixed point (the fixed point $x^*$ of $T^m$ satisfies $T^m(Tx^*)=T(T^mx^*)=Tx^*$, so $Tx^*$ is also a fixed point of $T^m$, hence $Tx^*=x^*$). Exercise III.7 uses this for $\cos$.

Interactive 2 — Banach Iteration in the Function Space $C[a,b]$

Each point of the space is a whole function. Starting from $f_0$, the lab applies the operator $T$ again and again; the red curve is the current iterate $f_n$, faint curves are earlier ones, and the dashed curve is the fixed point $f^*$ (when it exists). The readouts compare the true error $d_\infty(f_n,f^*)$ with the a priori bound $\tfrac{k^n}{1-k}d_\infty(f_0,f_1)$ of Theorem 7.10. Modes 2 and 4 have Lipschitz constant $k\gt1$: in one the iterates still converge, in the other there is no fixed point at all.

iterate n—
d∞(fₙ₋₁, fₙ)—
a priori bound—
true error d∞(fₙ, f*)—
✏️ Example 6 — Solving an integral equation by iteration
Consider the Fredholm integral equation $$f(x)=x+\frac12\int_0^1xt\,f(t)\,dt$$ for $0\le x\le1$. (a) Show that $(Tf)(x)=x+\tfrac12\int_0^1xt\,f(t)\,dt$ is a contraction of $(C[0,1],d_\infty)$ and find its constant. (b) Conclude that the equation has exactly one continuous solution, and find it. (c) Starting from $f_0=0$, how many iterations does the a priori estimate require for an error at most $10^{-6}$? How many are actually needed?
(a) $Tf$ is continuous (it is $x$ times a constant, plus $x$), so $T$ maps $C[0,1]$ into itself. For $f,g\in C[0,1]$ and $x\in[0,1]$: $$|Tf(x)-Tg(x)|=\frac x2\left|\int_0^1t\,(f-g)(t)\,dt\right|\le\frac12\cdot1\cdot\int_0^1t\,dt\cdot d_\infty(f,g)=\frac14\,d_\infty(f,g).$$ So $k=\tfrac14$ (and this is sharp: take $f-g\equiv1$, $x=1$).
(b) $(C[0,1],d_\infty)$ is complete (Theorem 7.6), so Theorem 7.10 gives a unique fixed point. To find it, note that any solution has the form $f(x)=x+\tfrac c2x$ with $c=\int_0^1tf(t)\,dt$. Substituting: $c=\int_0^1t^2\left(1+\tfrac c2\right)dt=\tfrac13+\tfrac c6$, so $c=\tfrac25$ and $f^*(x)=\tfrac65x$. Check: $\int_0^1t\cdot\tfrac65t\,dt=\tfrac25$ and $x+\tfrac12\cdot\tfrac25x=\tfrac65x$. ✓
(c) A priori $f_1=Tf_0=x$, so $d_\infty(f_0,f_1)=1$ and the bound is $\tfrac{(1/4)^n}{3/4}=\tfrac43\,4^{-n}$. We need $4^n\ge\tfrac43\cdot10^6$, i.e. $n\ge\log(1.33\times10^6)/\log4\approx10.17$: 11 iterations.
(c) Actual If $f_n=c_nx$ then $f_{n+1}=(1+c_n/6)x$, so $c_{n+1}-\tfrac65=\tfrac16\left(c_n-\tfrac65\right)$ and $d_\infty(f_n,f^*)=\tfrac65\,6^{-n}$. This is below $10^{-6}$ for $n\ge8$ ($\tfrac65\cdot6^{-8}\approx7.1\times10^{-7}$, while $n=7$ gives $4.3\times10^{-6}$). The a priori estimate is safe but pessimistic: the true rate $\tfrac16$ is better than $k=\tfrac14$. (Mode 3 of Interactive 2.)
📘 Definition 7.10 — Nowhere dense and meagre sets; $G_\delta$ and $F_\sigma$ sets
A subset $A$ of a metric space $X$ is nowhere dense if its closure has empty interior: $(\overline A)^\circ=\varnothing$. A countable union of nowhere dense sets is meagre (of first category); a set that is not meagre is of second category. A $G_\delta$ set is a countable intersection of open sets, and an $F_\sigma$ set is a countable union of closed sets.

Examples in $\mathbb{R}$: finite sets, $\mathbb{Z}$, $\{\tfrac1n\}$ and the Cantor set are nowhere dense; $\mathbb{Q}$ is dense but meagre (a countable union of points); a line is nowhere dense in $\mathbb{R}^2$. Every closed set is a $G_\delta$ ($F=\bigcap_n\{x:d(x,F)\lt\tfrac1n\}$), and $\mathbb{Q}$ is an $F_\sigma$.

📐 Theorem 7.11 — Baire category theorem

Let $(X,d)$ be a nonempty complete metric space.

  1. If $U_1,U_2,\dots$ are open and dense in $X$, then $\bigcap_{n=1}^\infty U_n$ is dense in $X$ (in particular nonempty).
  2. Equivalently: $X$ is not meagre in itself. If $X=\bigcup_{n=1}^\infty F_n$ with every $F_n$ closed, then some $F_n$ has nonempty interior.

Proof. (1) Let $W$ be a nonempty open set; we find a point of $W\cap\bigcap U_n$. Since $U_1$ is dense, $W\cap U_1$ is nonempty and open, so it contains a closed ball $\overline B(x_1,r_1)$ with $0\lt r_1\lt1$ (take a smaller radius than an open ball inside it). Since $U_2$ is dense, the open set $B(x_1,r_1)\cap U_2$ is nonempty and contains a closed ball $\overline B(x_2,r_2)$ with $0\lt r_2\lt\tfrac12$. Continuing, we get $$\overline B(x_{n+1},r_{n+1})\subseteq B(x_n,r_n)\cap U_{n+1}$$ with $0\lt r_n\lt\tfrac1n$. The closed balls $\overline B(x_n,r_n)$ are nonempty, closed, decreasing and have diameters $\le2r_n\to0$. By Cantor's intersection theorem (Theorem 7.8) they have a common point $x$. Then $x\in\overline B(x_1,r_1)\subseteq W$ and $x\in\overline B(x_{n},r_{n})\subseteq U_n$ for every $n$.

(2) If every $F_n$ had empty interior, $U_n=X\setminus F_n$ would be open and dense (Theorem 7.3(4): $\overline{U_n}=X\setminus F_n^\circ=X$), and by (1) $\bigcap U_n=X\setminus\bigcup F_n$ would be nonempty — contradicting $X=\bigcup F_n$. (Conversely, (1) follows from (2) applied to the closed balls of $X$, which are complete by Theorem 7.7.) ∎

Consequences. (a) A nonempty complete metric space without isolated points is uncountable: if $X=\{x_1,x_2,\dots\}$, the sets $U_n=X\setminus\{x_n\}$ are open, and dense because $x_n$ is not isolated, yet $\bigcap U_n=\varnothing$. This gives another proof that $\mathbb{R}$, every nondegenerate closed interval and the Cantor set are uncountable (§1.1, §4.4). (b) $\mathbb{Q}$ is not a $G_\delta$ subset of $\mathbb{R}$ (Example 7). (c) No function $f:\mathbb{R}\to\mathbb{R}$ is continuous exactly at the rational points: for any $f$, the set of points of continuity is $\bigcap_n\{x:\omega_f(x)\lt\tfrac1n\}$, where $\omega_f(x)=\inf_{\delta\gt0}\operatorname{diam}f\big((x-\delta,x+\delta)\big)$ is the oscillation; each of these sets is open, so the continuity set is a $G_\delta$, and by (b) it cannot be $\mathbb{Q}$. Thomae's function (§3.1) shows that the irrationals can be the continuity set. (d) Stated without proof: in $(C[0,1],d_\infty)$ the continuous nowhere-differentiable functions form a dense $G_\delta$ — "most" continuous functions are nowhere differentiable — and an infinite-dimensional Banach space has no countable (Hamel) basis (§7.4).

✏️ Example 7 — Three applications of Baire
Prove: (a) $\mathbb{Q}$ is not a $G_\delta$ set in $\mathbb{R}$, and $\mathbb{R}\setminus\mathbb{Q}$ is not an $F_\sigma$; (b) $\mathbb{R}^2$ is not a countable union of straight lines; (c) every nonempty countable closed subset of $\mathbb{R}$ has an isolated point.
(a) Suppose $\mathbb{Q}=\bigcap_nG_n$ with $G_n$ open. Each $G_n\supseteq\mathbb{Q}$ is dense. Enumerate $\mathbb{Q}=\{q_1,q_2,\dots\}$; the sets $V_k=\mathbb{R}\setminus\{q_k\}$ are open and dense. Then the countable family $\{G_n\}\cup\{V_k\}$ consists of open dense sets whose intersection is $\mathbb{Q}\cap(\mathbb{R}\setminus\mathbb{Q})=\varnothing$ — contradicting Theorem 7.11 in the complete space $\mathbb{R}$. Complementing, $\mathbb{R}\setminus\mathbb{Q}$ is not an $F_\sigma$.
(b) A line $L$ is closed in $\mathbb{R}^2$ and has empty interior (every disc around a point of $L$ contains points off $L$). If $\mathbb{R}^2=\bigcup_nL_n$, the complete space $\mathbb{R}^2$ would be a countable union of closed sets with empty interior, contradicting Theorem 7.11(2). (The same argument shows $\mathbb{R}^2$ is not a countable union of circles, or of graphs of continuous functions.)
(c) Let $F\ne\varnothing$ be closed and countable. With the usual metric $F$ is complete (Theorem 7.7(b)). By consequence (a) above, a nonempty complete metric space without isolated points is uncountable; so $F$ has an isolated point. For instance $\{0\}\cup\{\tfrac1n\}$ has isolated points $\tfrac1n$, whereas $\mathbb{Q}$, which has no isolated points, is not closed — and indeed cannot be made complete by any topologically equivalent metric.
⚠️ Counterexamples and pitfalls
  1. Not every "distance formula" is a metric. $(x-y)^2$ and $d_p$ with $p\lt1$ fail the triangle inequality; $|x^2-y^2|$ and $|\sin(x-y)|$ fail "$d=0\Rightarrow x=y$".
  2. Closure of the open ball $\ne$ closed ball. In a discrete space $\overline{B(a,1)}=\{a\}$ but $\overline B(a,1)=X$; also $\partial B(a,1)=\varnothing\ne S(a,1)=X\setminus\{a\}$.
  3. A ball can be inside a ball of smaller radius. In $[0,1]$: $B(0,3)=[0,1]\subseteq B(\tfrac12,1)$. Radius and centre of a ball are not determined by the set.
  4. Infinite intersections of open sets need not be open ($\bigcap(-\tfrac1n,\tfrac1n)=\{0\}$); infinite unions of closed sets need not be closed ($\bigcup[\tfrac1n,1]=(0,1]$; $\mathbb{Q}$ is a union of points).
  5. Open and closed are not opposites. In a discrete space every set is clopen; in $\mathbb{Q}$ the set $\mathbb{Q}\cap(-\sqrt2,\sqrt2)$ is clopen; $[0,1)$ is neither open nor closed in $\mathbb{R}$.
  6. Boundedness and completeness are not topological. $\min(1,|x-y|)$ is bounded and equivalent to $|x-y|$; $(0,1)$ and $\mathbb{R}$ are homeomorphic but only $\mathbb{R}$ is complete; $|\arctan x-\arctan y|$ is equivalent to $|x-y|$ on $\mathbb{R}$ but not complete.
  7. Isolated points do not make a space complete. $\{\tfrac1n:n\in\mathbb{N}\}$ has the discrete topology but is not complete; the discrete metric on it would be.
  8. Cauchy depends on the metric, convergence on the topology. $x_n=n$ is Cauchy in $|\arctan x-\arctan y|$ but not in $|x-y|$; $x^n\to0$ in $(C[0,1],d_1)$ but has no limit in $d_\infty$.
  9. "$d(Tx,Ty)\lt d(x,y)$" is not a contraction. $Tx=x+\tfrac1x$ on $[1,\infty)$ has no fixed point. A genuine contraction on an incomplete space ($x/2$ on $(0,1]$) need not have one either.
  10. A uniformly continuous image of a Cauchy sequence is Cauchy; a continuous image need not be. $x_n=\tfrac1n$ is Cauchy in $(0,1)$, but $\tfrac1{x_n}=n$ is not.
  11. $\ell^p$ inclusions run one way, $C[0,1]$ inequalities the other. $\ell^1\subsetneq\ell^2\subsetneq\ell^\infty$ with $\|x\|_\infty\le\|x\|_2\le\|x\|_1$; but on $[0,1]$, $d_1\le d_2\le d_\infty$ for functions.
  12. Baire needs completeness. $\mathbb{Q}=\bigcup_q\{q\}$ is a countable union of nowhere dense sets; dense does not imply "large" ($\mathbb{Q}$ is dense and meagre; a dense $G_\delta$ in $\mathbb{R}$ is uncountable).

Exercises

I
Metrics and the spaces $\ell^p$.
  • 1 Which of these are metrics on $\mathbb{R}$? (a) $|x-y|^{1/3}$; (b) $|x^2-y^2|$; (c) $|e^x-e^y|$; (d) $\max(|x-y|,1)$.
  • 2 Prove that if $d$ is a metric then $\min(1,d)$ and $\dfrac{d}{1+d}$ are metrics.
  • 3 For $x=(3,-4,12)\in\mathbb{R}^3$ compute $\|x\|_1$, $\|x\|_2$, $\|x\|_\infty$ and verify $\|x\|_\infty\le\|x\|_2\le\|x\|_1\le3\|x\|_\infty$.
  • 4 In $C[0,1]$ find $d_1$, $d_2=\left(\int_0^1|f-g|^2\right)^{1/2}$ and $d_\infty$ for $f(x)=x$, $g(x)=x^2$.
  • 5 Show that $(n^{-1/2})\in\ell^3\setminus\ell^2$ and compute $\|(1/n)\|_2$.
  • 6 Show that equality holds in Hölder's inequality for $x=(1,2)$, $y=(1,2)$ with $p=q=2$, and find the value of both sides for $x=(1,1,1)$, $y=(1,2,3)$, $p=3$, $q=\tfrac32$ (approximately).
  • 7 Verify that the French railway metric (Definition 7.2) satisfies the triangle inequality.
  • 8 A metric is an ultrametric if $d(x,z)\le\max\{d(x,y),d(y,z)\}$. Prove that in an ultrametric space every point of a ball $B(a,r)$ is a centre of it, and two open balls are either disjoint or one contains the other. Show that the discrete metric is an ultrametric.
1 (a) Yes: $t\mapsto t^{1/3}$ is increasing and subadditive ($(s+t)^{1/3}\le s^{1/3}+t^{1/3}$, cube the right side), as in Example 1(b). (b) No: $d(1,-1)=0$. (c) Yes: $|g(x)-g(y)|$ with $g=\exp$ injective. (d) No: $d(x,x)=1\ne0$.
2 Example 1(e) handles $\min(1,d)$. For $\sigma=d/(1+d)$: $\varphi(t)=t/(1+t)=1-\tfrac1{1+t}$ is increasing, $\varphi(t)=0\iff t=0$, and subadditive: $\varphi(s+t)=\tfrac{s}{1+s+t}+\tfrac{t}{1+s+t}\le\tfrac s{1+s}+\tfrac t{1+t}$. Hence $\sigma(x,z)=\varphi(d(x,z))\le\varphi(d(x,y)+d(y,z))\le\varphi(d(x,y))+\varphi(d(y,z))$.
3 $\|x\|_1=19$, $\|x\|_2=\sqrt{9+16+144}=13$, $\|x\|_\infty=12$, and $12\le13\le19\le36$.
4 $h=x-x^2\ge0$: $d_1=\int h=\tfrac16$; $d_2^2=\int_0^1(x^2-2x^3+x^4)\,dx=\tfrac13-\tfrac12+\tfrac15=\tfrac1{30}$, so $d_2=1/\sqrt{30}\approx0.1826$; $d_\infty=h(\tfrac12)=\tfrac14$. Indeed $d_1\le d_2\le d_\infty$ (Hölder on $[0,1]$).
5 $\sum(n^{-1/2})^3=\sum n^{-3/2}\lt\infty$ but $\sum(n^{-1/2})^2=\sum\tfrac1n=\infty$. $\|(1/n)\|_2=\left(\sum1/n^2\right)^{1/2}=\pi/\sqrt6\approx1.2825$.
6 For $x=y=(1,2)$: $\sum x_iy_i=5=\sqrt5\cdot\sqrt5$ — equality, because $y$ is a multiple of $x$. For $p=3$: $\sum x_iy_i=6$; $\|x\|_3=3^{1/3}\approx1.4422$ and $\|y\|_{3/2}=(1+2^{3/2}+3^{3/2})^{2/3}\approx(1+2.8284+5.1962)^{2/3}=9.0246^{2/3}\approx4.3346$, product $\approx6.2516\ge6$.
7 Write $|\cdot|=\|\cdot\|_2$ and note $d(x,y)\ge|x-y|$ always, $d(x,y)\le|x|+|y|$ always. Case 1: $x,z$ collinear with $0$. Then $d(x,z)=|x-z|\le|x-y|+|y-z|\le d(x,y)+d(y,z)$. Case 2: $x,z$ not collinear with $0$, so $d(x,z)=|x|+|z|$. If $y$ is collinear with neither pair, $d(x,y)+d(y,z)=|x|+2|y|+|z|\ge d(x,z)$. If $y$ is collinear with $x$ and $0$ but not with $z$ (the other case is symmetric; $y$ cannot be collinear with both unless $y=0$, when the right side is $|x|+|z|$), then $d(x,y)+d(y,z)=|x-y|+|y|+|z|\ge|x|+|z|$.
8 If $b\in B(a,r)$ and $d(x,b)\lt r$, then $d(x,a)\le\max(d(x,b),d(b,a))\lt r$: $B(b,r)\subseteq B(a,r)$, and symmetrically $B(a,r)\subseteq B(b,r)$. If $B(a,r)$ and $B(c,s)$ with $r\le s$ share a point $b$, both are balls about $b$: $B(b,r)\subseteq B(b,s)$. Discrete: if $x\ne z$, $y$ differs from at least one of them, so $\max\ge1=d(x,z)$.
II
Open sets, closed sets, closure and boundary.
  • 1 In $\mathbb{R}^2$ find the interior, closure and boundary of $\mathbb{Q}\times\mathbb{R}$ and of $\{(x,y):x\gt0,\ y=\sin(1/x)\}$.
  • 2 In $(C[0,1],d_\infty)$ show that $F=\{f:f(\tfrac12)=0\}$ is closed with empty interior, and that $\{f:\max f\lt1\}$ is open.
  • 3 Find all open sets, all closed sets and all dense subsets of a discrete metric space. Which subsets have nonempty boundary?
  • 4 Prove that $(A\cap B)^\circ=A^\circ\cap B^\circ$ and $\overline{A\cup B}=\overline A\cup\overline B$. Give examples in $\mathbb{R}$ with $(A\cup B)^\circ\ne A^\circ\cup B^\circ$ and $\overline{A\cap B}\ne\overline A\cap\overline B$.
  • 5 Find a set $A\subseteq\mathbb{R}$ for which the seven sets $A$, $\overline A$, $A^\circ$, $\overline{A^\circ}$, $(\overline A)^\circ$, $\overline{(\overline A)^\circ}$, $(\overline{A^\circ})^\circ$ are all different.
  • 6 Show that $d(x,A)=0$ iff $x\in\overline A$, and that for closed $A$ and $x\notin A$, $d(x,A)\gt0$.
  • 7 Let $Y=[0,1]\cup[2,3]$ with the usual metric. Show that $[0,1]$ is clopen in $Y$, and find $B_Y(1,\tfrac32)$.
  • 8 Prove that $\mathbb{R}^n$ (with $d_2$), $\ell^p$ ($1\le p\lt\infty$) and $C[a,b]$ (with $d_\infty$) are separable, and that $\ell^\infty$ is not. (Hint for $\ell^\infty$: the $0$–$1$ sequences.)
  • 9 Show that in any metric space a limit point $x$ of $A$ has infinitely many points of $A$ in each ball $B(x,r)$. Deduce that finite sets have no limit points.
1 $\mathbb{Q}\times\mathbb{R}$: every disc contains points with rational and with irrational first coordinate, so interior $\varnothing$, closure $\mathbb{R}^2$, boundary $\mathbb{R}^2$. The graph $G$ of $\sin(1/x)$, $x\gt0$: interior $\varnothing$ (a curve contains no disc); closure $G\cup(\{0\}\times[-1,1])$ (each $(0,c)$ with $|c|\le1$ is a limit of points $(x_n,c)$ with $\sin(1/x_n)=c$, $x_n\to0$); boundary $=$ closure.
2 $F=e^{-1}(\{0\})$ for the continuous evaluation $e(f)=f(\tfrac12)$, so it is closed. Interior empty: for $f\in F$ and $r\gt0$, $f+\tfrac r2\in B(f,r)\setminus F$. $\{f:\max f\lt1\}=M^{-1}((-\infty,1))$ with $M(f)=\max f$, which is $1$-Lipschitz ($|\max f-\max g|\le d_\infty(f,g)$).
3 Every subset is open and closed (Example 3(c)); the only dense subset is $X$; no subset has nonempty boundary.
4 $(A\cap B)^\circ$ is an open subset of $A$ and of $B$, so lies in $A^\circ\cap B^\circ$; conversely $A^\circ\cap B^\circ$ is open and inside $A\cap B$. Complement for closures. Examples: $A=\mathbb{Q}$, $B=\mathbb{R}\setminus\mathbb{Q}$: $(A\cup B)^\circ=\mathbb{R}$ but $A^\circ\cup B^\circ=\varnothing$; and $\overline{A\cap B}=\varnothing$ while $\overline A\cap\overline B=\mathbb{R}$.
5 $A=(0,1)\cup(1,2)\cup\{3\}\cup(\mathbb{Q}\cap(4,5))$. Then $\overline A=[0,2]\cup\{3\}\cup[4,5]$, $A^\circ=(0,1)\cup(1,2)$, $\overline{A^\circ}=[0,2]$, $(\overline A)^\circ=(0,2)\cup(4,5)$, $\overline{(\overline A)^\circ}=[0,2]\cup[4,5]$, $(\overline{A^\circ})^\circ=(0,2)$: seven different sets. (Kuratowski: at most 14 sets arise from one set by closure and complement.)
6 Theorem 7.3(3). If $A$ is closed and $x\notin A$, then $x\notin\overline A$, so $d(x,A)\ne0$.
7 $[0,1]=Y\cap(-1,1.5)$ is open in $Y$ and $[0,1]=Y\cap[-1,1.5]$ is closed in $Y$. $B_Y(1,\tfrac32)=(-\tfrac12,\tfrac52)\cap Y=[0,1]\cup[2,\tfrac52)$.
8 $\mathbb{Q}^n$ is dense in $\mathbb{R}^n$. In $\ell^p$: sequences with finitely many nonzero rational terms form a countable set $D$; given $x\in\ell^p$ and $\varepsilon$, choose $N$ with $\sum_{n\gt N}|x_n|^p\lt\varepsilon^p/2$ and rationals $q_n$ with $\sum_{n\le N}|x_n-q_n|^p\lt\varepsilon^p/2$. In $C[a,b]$: polynomials with rational coefficients (Weierstrass plus approximating coefficients). In $\ell^\infty$: the $0$–$1$ sequences form an uncountable set whose points are at mutual distance $1$; the balls $B(x,\tfrac12)$ around them are disjoint, and a dense set must meet each of them, so it is uncountable.
9 If $B(x,r)\cap A\setminus\{x\}$ were finite, say $\{a_1,\dots,a_k\}$, the ball of radius $\min_i d(x,a_i)\gt0$ would contain no point of $A$ other than $x$. A finite set therefore has no limit points (and is closed, by Theorem 7.3(2)).
III
Convergence, equivalent metrics and completeness.
  • 1 Show that a sequence in a discrete metric space converges iff it is Cauchy iff it is eventually constant.
  • 2 Show that $f_n(x)=x^n$ converges to $0$ in $(C[0,1],d_1)$ but has no limit in $(C[0,1],d_\infty)$.
  • 3 Is $d_1$ on $C[0,1]$ strongly equivalent to $d_\infty$? Topologically equivalent?
  • 4 Which of these are complete with the usual metric: $\mathbb{Z}$, $\{\tfrac1n:n\in\mathbb{N}\}$, $\{0\}\cup\{\tfrac1n\}$, $[0,\infty)$, $\mathbb{R}\setminus\{0\}$, the Cantor set?
  • 5 Show that a uniformly continuous map sends Cauchy sequences to Cauchy sequences, and that a homeomorphism need not.
  • 6 Prove that $c_0$ is closed in $\ell^\infty$ (so complete) and that $c_{00}$ is dense in $c_0$.
  • 7 Show that $\cos$ is not a contraction of $\mathbb{R}$ but $\cos\circ\cos$ is, and deduce that $\cos x=x$ has exactly one real solution.
  • 8 Show that $C^1[0,1]$ (continuously differentiable functions) with $d_\infty$ is not complete, but is complete with $d(f,g)=d_\infty(f,g)+d_\infty(f',g')$.
  • 9 Let $(x_n)$ be a sequence in a metric space with $d(x_n,x_{n+1})\le2^{-n}$. Prove that $(x_n)$ is Cauchy. Is the conclusion still true if only $d(x_n,x_{n+1})\le\tfrac1n$?
1 With $\varepsilon=\tfrac12$, "$d(x_n,x)\lt\tfrac12$ for $n\ge N$" means $x_n=x$ for $n\ge N$, and "$d(x_m,x_n)\lt\tfrac12$" means $x_m=x_n$. Eventually constant sequences obviously converge.
2 $d_1(f_n,0)=\int_0^1x^n\,dx=\tfrac1{n+1}\to0$. In $d_\infty$ a limit $g$ would be a uniform, hence pointwise, limit: $g(x)=0$ for $x\lt1$ and $g(1)=1$ — not continuous. (Or: $d_\infty(f_n,f_{2n})=\max(x^n-x^{2n})=\tfrac14$, so $(f_n)$ is not $d_\infty$-Cauchy.)
3 Neither. $d_1\le d_\infty$ always, but $d_\infty(x^n,0)=1$ while $d_1(x^n,0)\to0$, so no inequality $d_\infty\le\beta d_1$; and the two metrics have different convergent sequences ($x^n\to0$ in $d_1$ only), so different open sets.
4 By Theorem 7.7, complete iff closed in $\mathbb{R}$: $\mathbb{Z}$ yes; $\{\tfrac1n\}$ no; $\{0\}\cup\{\tfrac1n\}$ yes; $[0,\infty)$ yes; $\mathbb{R}\setminus\{0\}$ no ($\tfrac1n$); Cantor set yes (an intersection of closed sets).
5 Given $\varepsilon$, take $\delta$ from uniform continuity and $N$ with $d(x_m,x_n)\lt\delta$ for $m,n\ge N$; then $\rho(f(x_m),f(x_n))\lt\varepsilon$. The homeomorphism $x\mapsto1/x$ of $(0,1)$ onto $(1,\infty)$ maps the Cauchy sequence $\tfrac1n$ to $n$.
6 Let $x^{(k)}\in c_0$, $x^{(k)}\to x$ in $\ell^\infty$. Given $\varepsilon$, fix $k$ with $\|x^{(k)}-x\|_\infty\lt\varepsilon/2$ and then $N$ with $|x^{(k)}_n|\lt\varepsilon/2$ for $n\ge N$; then $|x_n|\lt\varepsilon$ for $n\ge N$, so $x\in c_0$. For $x\in c_0$, its truncations $(x_1,\dots,x_k,0,\dots)$ are at $d_\infty$-distance $\sup_{n\gt k}|x_n|\to0$.
7 $|\cos x-\cos y|=|\sin c||x-y|$, and $|\sin c|$ can be arbitrarily close to $1$, so no $k\lt1$ works on $\mathbb{R}$. For $g=\cos\circ\cos$, $|g'(x)|=|\sin(\cos x)\sin x|\le\sin1\approx0.8415$ (as $|\cos x|\le1$), so $g$ is a contraction of the complete space $\mathbb{R}$ with $k=\sin1$. By the variant after Theorem 7.10, $\cos$ has exactly one fixed point ($x^*\approx0.739085$).
8 $f_n(x)=\sqrt{(x-\tfrac12)^2+\tfrac1{n^2}}\in C^1$ converges uniformly to $|x-\tfrac12|$ (indeed $0\le f_n-|x-\tfrac12|\le\tfrac1n$), which is not differentiable; so $(f_n)$ is $d_\infty$-Cauchy without a limit in $C^1$. With the new metric, a Cauchy sequence has $f_n\to f$ and $f_n'\to g$ uniformly; by the theorem on differentiating uniform limits (§5.2), $f\in C^1$ with $f'=g$, and $d(f_n,f)\to0$.
9 For $m\gt n$, $d(x_n,x_m)\le\sum_{j=n}^{m-1}2^{-j}\lt2^{1-n}\to0$. With $\tfrac1n$ the conclusion fails: $x_n=1+\tfrac12+\cdots+\tfrac1{n-1}$ in $\mathbb{R}$ has $|x_{n+1}-x_n|=\tfrac1n$ but diverges to $\infty$.
IV
Contractions and the Baire category theorem.
  • 1 Show that $T(x)=\tfrac x2+\tfrac1x$ maps $[1,\infty)$ into itself and is a contraction there with $k=\tfrac12$. Find its fixed point. Starting from $x_0=1$, how many iterations does the a priori estimate demand for error $\le10^{-6}$, and how many are actually needed?
  • 2 Show that $T(x)=x+\tfrac1x$ on $[1,\infty)$ satisfies $|Tx-Ty|\lt|x-y|$ for $x\ne y$ but has no fixed point. Which hypothesis of Theorem 7.10 fails?
  • 3 Solve $f(x)=x^2+\int_0^1xt\,f(t)\,dt$ on $[0,1]$, after showing that the right-hand side defines a contraction of $(C[0,1],d_\infty)$.
  • 4 Show that $(Tf)(x)=1+\int_0^xt\,f(t)\,dt$ is a contraction of $(C[0,1],d_\infty)$, and identify its fixed point.
  • 5 Let $(Kf)(x)=\int_0^1\cos(x-t)\,f(t)\,dt$. For which real $\lambda$ is $Tf=\sin x+\lambda Kf$ guaranteed by the sup-metric estimate to be a contraction of $C[0,1]$?
  • 6 Prove that a countable complete metric space has an isolated point. Deduce that there is no metric on $\mathbb{Q}$, topologically equivalent to the usual one, for which $\mathbb{Q}$ is complete.
  • 7 Let $\mathcal P_n$ be the polynomials of degree at most $n$, viewed in $(C[0,1],d_\infty)$. Assuming that $\mathcal P_n$ is closed (§7.4: finite-dimensional subspaces are closed), show that $\mathcal P_n$ is nowhere dense and deduce that the space $\mathcal P$ of all polynomials with $d_\infty$ is not complete.
  • 8 Let $f:\mathbb{R}\to\mathbb{R}$ and $\omega_f(x)$ be its oscillation at $x$. Show that $\{x:\omega_f(x)\lt\varepsilon\}$ is open for each $\varepsilon\gt0$, and that $f$ is continuous at $x$ iff $\omega_f(x)=0$.
1 By AM–GM, $\tfrac x2+\tfrac1x\ge2\sqrt{\tfrac12}=\sqrt2\ge1$. $T'(x)=\tfrac12-\tfrac1{x^2}\in[-\tfrac12,\tfrac12)$ on $[1,\infty)$, so $|Tx-Ty|\le\tfrac12|x-y|$ by the MVT; $[1,\infty)$ is closed in $\mathbb{R}$, hence complete. Fixed point: $\tfrac x2=\tfrac1x$, $x^*=\sqrt2$. A priori: $x_1=1.5$, $d(x_0,x_1)=\tfrac12$, bound $\tfrac{(1/2)^n}{1/2}\cdot\tfrac12=2^{-n}\le10^{-6}$ needs $n\ge20$. Actually $x_2=1.41667$, $x_3=1.4142157$ (error $2.1\times10^{-6}$), $x_4$ has error $1.6\times10^{-12}$: four iterations — this is Newton's method for $x^2=2$, which converges quadratically.
2 $|Tx-Ty|=|x-y|\,\left|1-\tfrac1{xy}\right|$ and $0\le1-\tfrac1{xy}\lt1$ for $x\ne y$ in $[1,\infty)$ (if $x=y=1$ there is nothing to compare). $Tx=x$ would need $\tfrac1x=0$. The space is complete; what fails is a uniform constant: $\sup_{x\ne y}\tfrac{|Tx-Ty|}{|x-y|}=1$.
3 $|Tf(x)-Tg(x)|\le x\int_0^1t\,dt\,d_\infty(f,g)\le\tfrac12d_\infty(f,g)$: $k=\tfrac12$. A solution has the form $x^2+cx$ with $c=\int_0^1tf(t)\,dt=\int_0^1(t^3+ct^2)\,dt=\tfrac14+\tfrac c3$, so $c=\tfrac38$ and $f(x)=x^2+\tfrac38x$.
4 $|Tf(x)-Tg(x)|\le\int_0^xt\,dt\,d_\infty(f,g)\le\tfrac12d_\infty(f,g)$. The fixed point satisfies $f(0)=1$, $f'(x)=xf(x)$, so $f(x)=e^{x^2/2}$; check: $1+\int_0^xte^{t^2/2}dt=1+(e^{x^2/2}-1)$. ✓
5 $|Tf(x)-Tg(x)|\le|\lambda|\int_0^1|\cos(x-t)|\,dt\;d_\infty(f,g)$. For $x,t\in[0,1]$, $|x-t|\le1$ so $\cos(x-t)\gt0$, and $\int_0^1\cos(x-t)\,dt=\sin x+\sin(1-x)=2\sin\tfrac12\cos(x-\tfrac12)$, which is largest at $x=\tfrac12$: $2\sin\tfrac12\approx0.9589$. So $k=0.9589|\lambda|$, a contraction for $|\lambda|\lt1/(2\sin\tfrac12)\approx1.0429$.
6 Consequence (a) of Theorem 7.11. A complete metric on $\mathbb{Q}$ equivalent to the usual one would make $\mathbb{Q}$ a countable complete space without isolated points (isolatedness is a topological notion, so it does not change) — impossible.
7 $\mathcal P_n$ has empty interior: for $p\in\mathcal P_n$ and $r\gt0$, $p+\tfrac r2x^{n+1}\in B(p,r)\setminus\mathcal P_n$. So $\mathcal P=\bigcup_n\mathcal P_n$ is a countable union of closed nowhere dense subsets of $(\mathcal P,d_\infty)$ (each $\mathcal P_n$ is also closed in $\mathcal P$ and has empty interior there by the same perturbation). By Baire, $(\mathcal P,d_\infty)$ is not complete — consistent with its completion being $C[0,1]$.
8 If $\omega_f(x)\lt\varepsilon$, there is $\delta$ with $\operatorname{diam}f((x-\delta,x+\delta))\lt\varepsilon$. For $y$ with $|y-x|\lt\delta/2$, the interval $(y-\delta/2,y+\delta/2)$ lies inside $(x-\delta,x+\delta)$, so $\omega_f(y)\lt\varepsilon$: the set is open. $\omega_f(x)=0$ iff for every $\varepsilon$ some $\delta$-interval has image of diameter $\lt\varepsilon$, which is exactly continuity at $x$.
🎯 Exam corner CSIR Part BCSIR Part CGATE MA

E1. CSIR Part B GATE MA Which of the following defines a metric on $\mathbb{R}$? (A) $d(x,y)=(x-y)^2$; (B) $d(x,y)=\dfrac{|x-y|}{1+|x-y|}$; (C) $d(x,y)=|x|+|y|$; (D) $d(x,y)=|\sin(x-y)|$.

Idea Test (M1) with $x=y$ and with "periodic" pairs, and test (M3) with three collinear points.
Options (A) $d(0,2)=4\gt d(0,1)+d(1,2)=2$. (B) a metric (Exercise I.2). (C) $d(1,1)=2\ne0$. (D) $d(0,\pi)=0$.
Answer (B).

E2. CSIR Part B Let $X$ be an infinite set with the discrete metric, $a\in X$, $B=B(a,1)$ the open ball and $K=\{x:d(x,a)\le1\}$ the closed ball. Then (A) $\overline B=K=X$; (B) $\overline B=\{a\}$ and $K=X$; (C) $\overline B=K=\{a\}$; (D) $\overline B=X$ and $K=\{a\}$.

Idea In the discrete metric every set is closed, and distances are only $0$ or $1$.
Compute $B=\{x:d(x,a)\lt1\}=\{a\}$, closed, so $\overline B=\{a\}$; $K=\{x:d(x,a)\le1\}=X$.
Answer (B). The closure of an open ball can be strictly smaller than the closed ball.

E3. CSIR Part B For a real parameter $\lambda$ define $T:C[0,1]\to C[0,1]$ by $(Tf)(x)=x+\lambda\int_0^1(x+t)f(t)\,dt$, with the sup metric. $T$ is a contraction if and only if (A) $|\lambda|\lt1$; (B) $|\lambda|\lt\tfrac23$; (C) $|\lambda|\lt\tfrac12$; (D) $|\lambda|\lt\tfrac32$.

Upper bound $|Tf(x)-Tg(x)|\le|\lambda|\int_0^1(x+t)\,dt\;d_\infty(f,g)=|\lambda|\left(x+\tfrac12\right)d_\infty(f,g)\le\tfrac32|\lambda|\,d_\infty(f,g)$.
Sharpness With $f-g\equiv1$ and $x=1$: $|Tf(1)-Tg(1)|=|\lambda|\cdot\tfrac32$, so the best Lipschitz constant is exactly $\tfrac32|\lambda|$ (if $\lambda\ne0$).
Answer (B): $\tfrac32|\lambda|\lt1\iff|\lambda|\lt\tfrac23$.

E4. CSIR Part C Which of the following metric spaces are complete? (One or more options may be correct.) (A) $\mathbb{N}$ with $d(m,n)=\left|\tfrac1m-\tfrac1n\right|$; (B) $\mathbb{R}$ with $d(x,y)=|e^x-e^y|$; (C) $\mathbb{Z}$ with $d(m,n)=|m-n|$; (D) $(0,\infty)$ with $d(x,y)=|\log x-\log y|$.

Idea Each metric is $|g(x)-g(y)|$ for an injective $g$, so the space is isometric to $g(X)\subseteq\mathbb{R}$; it is complete iff $g(X)$ is closed in $\mathbb{R}$.
(A) Not complete $g(\mathbb{N})=\{\tfrac1n\}$ is not closed; $(n)$ is Cauchy with no limit.
(B) Not complete $g(\mathbb{R})=(0,\infty)$; $x_n=-n$ is Cauchy, no limit.
(C) Complete Cauchy sequences of integers are eventually constant.
(D) Complete $\log$ maps it isometrically onto $\mathbb{R}$.
Answer (C) and (D).

E5. CSIR Part C In $X=C[0,1]$ with $d_\infty(f,g)=\max|f-g|$, which of the following are true? (A) $\{f\in X:f(0)=0\}$ is closed. (B) $\{f\in X:f(x)\gt0\text{ for all }x\}$ is open. (C) The polynomials form a dense subset of $X$. (D) The polynomials form an open subset of $X$.

(A) True It is the preimage of $\{0\}$ under the $1$-Lipschitz evaluation $f\mapsto f(0)$.
(B) True A positive continuous $f$ has a positive minimum $m$ (EVT); the ball $B(f,m)$ consists of positive functions.
(C) True Weierstrass approximation theorem.
(D) False Every ball around a polynomial $p$ contains the non-polynomial $p+\tfrac r2|x-\tfrac12|$ (Example 3(d)); the polynomials have empty interior.
Answer (A), (B) and (C).

E6. CSIR Part C Which of the following statements are true? (A) $\mathbb{R}$ is a countable union of closed sets each with empty interior. (B) $\mathbb{Q}$ is a countable intersection of open subsets of $\mathbb{R}$. (C) $\mathbb{R}\setminus\mathbb{Q}$ is a countable intersection of open subsets of $\mathbb{R}$. (D) Every nonempty complete metric space with no isolated points is uncountable.

(A) False Baire category theorem (Theorem 7.11(2)): in the complete space $\mathbb{R}$ one of the closed sets must have interior.
(B) False $\mathbb{Q}$ is not a $G_\delta$ (Example 7(a)).
(C) True $\mathbb{R}\setminus\mathbb{Q}=\bigcap_{q\in\mathbb{Q}}(\mathbb{R}\setminus\{q\})$, a countable intersection of open sets.
(D) True Consequence (a) of Theorem 7.11: the complements of the points of a countable list would be open dense sets with empty intersection.
Answer (C) and (D).
🧑‍🏫 For the teacher

Suggested plan — 3 lectures × 60 min.

  1. Metrics. Definition 7.1 and the zoo of Definition 7.2; Example 1 as a class poll (ask for a counterexample to each failed axiom). Prove Hölder and Minkowski (Theorem 7.1) in full — it is the only real inequality in the section. Example 2(d) on $\ell^p\subseteq\ell^q$. Project Interactive 1: $\ell^1$, $\ell^2$, $\ell^\infty$, then sweep $p$; then the discrete and railway metrics.
  2. Topology of a metric space. Balls, open and closed sets (Theorem 7.2), interior/closure/boundary (Theorem 7.3), Example 3 with (d) done carefully; continuity (Theorem 7.4) and the preimage trick; equivalent metrics (Theorem 7.5) and Example 4.
  3. Completeness. Theorem 7.6(b) as the model completeness proof; Theorems 7.7–7.8; Example 5. Banach's theorem with both estimates; project Interactive 2 (mode 1, then 3, then the two $k\gt1$ modes) and do Example 6 on the board. Close with the statement of Baire, its proof by nested balls, and Example 7(a).

Discussion questions. (1) The metrics $|x-y|$ and $|\arctan x-\arctan y|$ have the same open sets. Which of "convergent", "Cauchy", "bounded", "complete", "continuous", "uniformly continuous" do they share? (2) Why does the proof of Banach's theorem need completeness but not, say, boundedness? Find the line where it is used. (3) "Most continuous functions are nowhere differentiable" — in what sense of "most"? Is the same set "small" in some other sense?

Misconceptions to watch for. Assuming $\overline{B(a,r)}=\overline B(a,r)$ in every space; treating "closed" as "not open"; thinking a space with all points isolated must be complete; believing "$d(Tx,Ty)\lt d(x,y)$" suffices for a fixed point; forgetting that $T$ must map $X$ into $X$; confusing nowhere dense with "not dense".

Suggested homework. I(1, 2, 4, 6, 8), II(1, 2, 4, 7, 8), III(2, 4, 6, 7, 8), IV(1, 3, 5, 6); Exam corner E3, E4, E6.

🔬 Research–Teaching NexusResearch-tutored · optional, about 60 minutes

Research question. A web search engine ranks pages by a vector $r$ satisfying $r=\alpha Pr+(1-\alpha)u$, where $P$ is the link matrix of the web and $u$ is uniform. Why does this equation have exactly one solution, how fast does simple iteration find it, and what happens as the damping factor $\alpha$ approaches $1$?

Why it matters. The PageRank idea (Brin and Page, 1998) is a Banach fixed-point computation on a space with billions of coordinates; the same "damped iteration" appears in ranking football teams, in citation analysis of scientific journals, in epidemiological contact networks and in the stationary distributions of Markov chains (Unit 4).

What to do.

  1. Let $\Delta=\{r\in\mathbb{R}^N:r_i\ge0,\ \sum r_i=1\}$ with the metric $d_1$. Show $\Delta$ is closed in $\mathbb{R}^N$, hence complete, and that if $P$ is column-stochastic (non-negative entries, columns summing to $1$), then $T(r)=\alpha Pr+(1-\alpha)u$ maps $\Delta$ into $\Delta$ with $d_1(Tr,Ts)\le\alpha\,d_1(r,s)$.
  2. Build a small "web" of 8 pages (draw the links, include a page with no out-links and treat it as linking to every page), form $P$, and iterate $T$ from $u$ for $\alpha=0.5,\ 0.85,\ 0.99$. Record $d_1(r_n,r_{n+1})$ and compare with the a priori bound of Theorem 7.10.
  3. Plot $\log d_1(r_n,r_{n+1})$ against $n$. Is the observed rate $\alpha$, or better? Relate the rate to the second-largest eigenvalue modulus of $\alpha P+(1-\alpha)u\mathbf 1^{T}$.
  4. Change one link and measure how much the ranking vector moves. Prove the sensitivity bound $d_1(r^*,s^*)\le\frac{\alpha}{1-\alpha}\,\|(P-Q)r^*\|_1$ for two link matrices $P,Q$.

Tools: Python with NumPy (or a spreadsheet for $N=8$); a sheet of paper for the web graph.

Hand in: A two-page note with the graph, the three convergence plots, the final rankings, and the proof of the sensitivity bound.

Going further. Read about why search engines settled on $\alpha\approx0.85$ (a trade-off between speed $\sim\alpha^n$ and faithfulness to the link structure), and about the Perron–Frobenius theorem, which gives uniqueness without the contraction argument.

Instructor note: step 1 is a clean exercise in Theorem 7.10 — the key identity is $\sum_i(P(r-s))_i=\sum_j(r-s)_j=0$ and $\|P(r-s)\|_1\le\|r-s\|_1$ for column-stochastic $P$. Students usually observe a rate close to $\alpha$ on small graphs with several "sink" pages, and noticeably faster rates on well-connected ones; this is a good moment to stress that $k$ in Banach's theorem is only an upper bound for the rate (compare Example 6). For $\alpha=0.99$ the a priori bound (with $d_1(r_0,r_1)\le2$) asks for about $1900$ iterations for accuracy $10^{-6}$, against about $100$ for $\alpha=0.85$.

🧪 Self-check quiz

0/5 correct

Q1. In a metric space, which of the following is always open?

Q2. Which of these spaces is not complete?

Q3. On $\mathbb{R}$, the metrics $|x-y|$ and $|\arctan x-\arctan y|$

Q4. The Banach contraction principle requires

Q5. The Baire category theorem implies that