Chapter 4 · Real Analysis

4.1 Metric Spaces: Completeness, Compactness, Connectedness, Contractions

Distance as an axiom: metric spaces and their open and closed sets, completeness and the spaces that have it, the contraction mapping principle and how GATE uses it, compactness (and why closed and bounded is not enough outside $\mathbb{R}^n$), and connectedness — the language of all of analysis.

Newton's method for $\sqrt2$, the Picard iterates that solve an initial value problem, the Jacobi iteration for a linear system and the power method for an eigenvector all have the same shape: start somewhere, apply a map again and again, and hope the iterates settle down. Whether they do — and how fast — is answered by one theorem, the contraction mapping principle. To state it we need only two things: a notion of distance between the objects being iterated (numbers, vectors, functions), and the guarantee that a sequence whose terms get closer and closer together really has a limit (completeness). A metric space is exactly a set with a distance. In it, the ideas of real analysis — convergence, continuity, open and closed sets, compactness, connectedness — make sense word for word, whether the points are real numbers, vectors in $\mathbb{R}^n$, sequences or continuous functions.

GATE MA asks about this material every year, almost always as "which of the following is true" judgement: is this a metric, is this space complete, is this set compact or connected, does this map have a unique fixed point, and how many components does this set have? The answers rest on a small number of theorems and a longer list of counterexamples — $(0,1)$ is not complete although $\mathbb{R}$ is; the closed unit ball of $\ell^2$ is closed and bounded but not compact; the topologist's sine curve is connected but not path-connected; $x\mapsto x+1/x$ moves points closer together but has no fixed point. This section develops the theorems with proofs of the key ones, and collects the counterexamples in one place.

Metric Spaces, Open and Closed Sets, Convergence

📘 Definition 4.1 — Metric space

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

(M1) Definiteness$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. The standard examples, used throughout this course:

  • $\mathbb{R}^n$ (or $\mathbb{C}^n$) with $d_p(x,y)=\|x-y\|_p$, where $\|x\|_p=\big(\sum_i|x_i|^p\big)^{1/p}$ for $1\le p\lt\infty$ and $\|x\|_\infty=\max_i|x_i|$: $d_2$ is the Euclidean metric, $d_1$ the "taxicab" metric, $d_\infty$ the maximum metric.
  • The discrete metric on any set: $d(x,y)=1$ for $x\ne y$, $d(x,x)=0$.
  • The sequence spaces $\ell^p$ ($1\le p\lt\infty$) with $d_p(x,y)=\big(\sum_n|x_n-y_n|^p\big)^{1/p}$, and $\ell^\infty$ (bounded sequences) with $d_\infty(x,y)=\sup_n|x_n-y_n|$; inside $\ell^\infty$ sit $c_0$ (sequences tending to $0$) and $c_{00}$ (sequences with finitely many nonzero terms).
  • $C[a,b]$, the continuous real functions on $[a,b]$, with the sup metric $d_\infty(f,g)=\max_{[a,b]}|f-g|$ or the integral metric $d_1(f,g)=\int_a^b|f-g|$.
  • Any subset $Y\subseteq X$ with the restricted metric (a subspace).

The triangle inequality for $d_p$ is Minkowski's inequality (§8.1); for $d_\infty$ on $C[a,b]$ it follows from $|f-h|\le|f-g|+|g-h|$ at each point. For $d_1$ on $C[a,b]$, (M1) needs continuity: if $\int_a^b|f-g|=0$ and $|f-g|$ were positive at some point, it would be positive on a whole interval around it and the integral would be positive. (On the Riemann integrable functions $d_1$ fails (M1): change a function at one point.)

New metrics are often built from old ones. If $d$ is a metric and $\varphi:X\to\mathbb{R}$ is injective, then $\rho(x,y)=|\varphi(x)-\varphi(y)|$ is a metric (it is the usual distance between the images); this gives $|\arctan x-\arctan y|$ and $|e^x-e^y|$ on $\mathbb{R}$, and $|1/x-1/y|$ on $(0,\infty)$. And $\min\{d,1\}$ and $\dfrac{d}{1+d}$ are metrics; for the second, $t\mapsto\frac{t}{1+t}$ is increasing and $\frac{a+b}{1+a+b}\le\frac a{1+a}+\frac b{1+b}$.

📘 Definition 4.2 — Balls, open and closed sets, closure, boundary, density

Let $(X,d)$ be a metric space, $a\in X$, $r\gt0$. The open ball is $B(a,r)=\{x:d(x,a)\lt r\}$ and the closed ball is $\overline{B}(a,r)=\{x:d(x,a)\le r\}$. A set $A\subseteq X$ is

  • open if for every $x\in A$ there is $r\gt0$ with $B(x,r)\subseteq A$; closed if $X\setminus A$ is open;
  • bounded if $A\subseteq B(a,r)$ for some $a$ and $r$; its diameter is $\operatorname{diam}A=\sup\{d(x,y):x,y\in A\}$.

A point $x$ is an interior point of $A$ if some ball $B(x,r)\subseteq A$, and a limit point of $A$ if every ball $B(x,r)$ contains a point of $A$ other than $x$. The interior $A^\circ$ is the set of interior points, the closure is $\overline A=A\cup\{\text{limit points of }A\}$, the boundary is $\partial A=\overline A\setminus A^\circ$, and $A$ is dense in $X$ if $\overline A=X$.

📐 Theorem 4.1 — Open sets, closed sets and sequences

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

  1. Every open ball is open and every closed ball is closed.
  2. Arbitrary unions and finite intersections of open sets are open; arbitrary intersections and finite unions of closed sets are closed. $\varnothing$ and $X$ are both open and closed.
  3. $x\in\overline A$ if and only if some sequence of points of $A$ converges to $x$ (that is, $d(a_n,x)\to0$). Consequently $A$ is closed $\iff$ $A$ contains the limit of every convergent sequence of its points $\iff$ $A=\overline A$, and $\overline A$ is the smallest closed set containing $A$.
  4. In a subspace $Y\subseteq X$, the balls are $B_Y(a,r)=B(a,r)\cap Y$, and $U\subseteq Y$ is open in $Y$ if and only if $U=V\cap Y$ for some open $V\subseteq X$ (similarly for closed sets).

Proof. (1) If $y\in B(a,r)$, put $s=r-d(a,y)\gt0$. For $z\in B(y,s)$, $d(a,z)\le d(a,y)+d(y,z)\lt d(a,y)+s=r$, so $B(y,s)\subseteq B(a,r)$. If $d(a,y)\gt r$, the same computation shows $B(y,d(a,y)-r)$ misses $\overline B(a,r)$, so the complement of the closed ball is open.

(2) A point of a union lies in one of the sets, together with a ball. If $x\in U_1\cap\dots\cap U_m$ with $B(x,r_i)\subseteq U_i$, then $B(x,\min_ir_i)$ lies in all of them; the minimum of finitely many positive radii is positive (and $\bigcap_n(-\frac1n,\frac1n)=\{0\}$ shows that infinite intersections may fail). The statements about closed sets follow by taking complements (De Morgan).

(3) If $x\in\overline A$, every ball $B(x,\frac1n)$ meets $A$; choosing $a_n$ in it gives $a_n\to x$. Conversely, if $a_n\to x$ with $a_n\in A$, every ball around $x$ contains some $a_n$, so $x\in A$ or $x$ is a limit point of $A$. Now suppose $A$ is closed and $a_n\to x$, $a_n\in A$; if $x\notin A$, some ball $B(x,r)$ lies in the open set $X\setminus A$, but it contains $a_n$ for large $n$ — a contradiction. If $A$ contains all such limits then $\overline A=A$, and then each $x\notin A$ has a ball missing $A$, so $X\setminus A$ is open. Finally, if $F\supseteq A$ is closed, limits of sequences in $A$ lie in $F$, so $\overline A\subseteq F$; and $\overline A$ is closed, since a limit of points of $\overline A$ is (by a diagonal choice of points of $A$) a limit of points of $A$.

(4) The description of balls is immediate. If $U$ is open in $Y$, each $y\in U$ has $B(y,r_y)\cap Y\subseteq U$, and $V=\bigcup_yB(y,r_y)$ is open in $X$ with $V\cap Y=U$; the converse is similar. ∎

📘 Definition 4.3 — Convergence, Cauchy sequences, continuity

A sequence $(x_n)$ in $X$ converges to $x$ if $d(x_n,x)\to0$, and is Cauchy if for every $\varepsilon\gt0$ there is $N$ with $d(x_m,x_n)\lt\varepsilon$ for all $m,n\ge N$. A map $f:(X,d)\to(Y,\rho)$ 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 independently of $a$;
  • Lipschitz with constant $L$ if $\rho(f(x),f(y))\le L\,d(x,y)$ for all $x,y$; an isometry if $\rho(f(x),f(y))=d(x,y)$;
  • a homeomorphism if it is a continuous bijection with continuous inverse.
📐 Theorem 4.2 — Continuity and Cauchy sequences
  1. For $f:X\to Y$ the following are equivalent: (i) $f$ is continuous; (ii) $x_n\to x$ implies $f(x_n)\to f(x)$; (iii) $f^{-1}(V)$ is open in $X$ for every open $V\subseteq Y$; (iv) $f^{-1}(F)$ is closed for every closed $F\subseteq Y$.
  2. Lipschitz $\Rightarrow$ uniformly continuous $\Rightarrow$ continuous, and a uniformly continuous map sends Cauchy sequences to Cauchy sequences.
  3. Limits are unique; every convergent sequence is Cauchy; every Cauchy sequence is bounded; a Cauchy sequence with a convergent subsequence converges (to the same limit).

Proof. (1) (i)⇒(ii): given $\varepsilon$, take $\delta$ from continuity at $x$; for large $n$, $d(x_n,x)\lt\delta$, so $\rho(f(x_n),f(x))\lt\varepsilon$. (ii)⇒(i): if $f$ is not continuous at $a$, there is $\varepsilon\gt0$ such that for each $n$ some $x_n$ has $d(x_n,a)\lt\frac1n$ but $\rho(f(x_n),f(a))\ge\varepsilon$ — a sequence violating (ii). (i)⇒(iii): if $V$ is open and $f(a)\in V$, choose $\varepsilon$ with $B(f(a),\varepsilon)\subseteq V$ and then $\delta$; $B(a,\delta)\subseteq f^{-1}(V)$. (iii)⇒(i): $f^{-1}(B(f(a),\varepsilon))$ is open and contains $a$, so it contains a ball $B(a,\delta)$. (iii)⇔(iv) by complements.

(2) For Lipschitz $f$ take $\delta=\varepsilon/L$. If $f$ is uniformly continuous and $(x_n)$ is Cauchy, the $\delta$ for a given $\varepsilon$ works at every point, and $d(x_m,x_n)\lt\delta$ for large $m,n$. (3) $d(x,y)\le d(x,x_n)+d(x_n,y)\to0$ gives uniqueness; $d(x_m,x_n)\le d(x_m,x)+d(x,x_n)$ gives Cauchy. With $\varepsilon=1$ all terms from $x_N$ on lie in $B(x_N,1)$, and finitely many earlier terms do not spoil boundedness. If $x_{n_j}\to x$ and $d(x_m,x_n)\lt\varepsilon$ for $m,n\ge N$, then $d(x_n,x)\le d(x_n,x_{n_j})+d(x_{n_j},x)\lt2\varepsilon$ for $n\ge N$ and $j$ large. ∎

📘 Definition 4.4 — Equivalent metrics
Two metrics $d$ and $\rho$ on the same set $X$ are equivalent (topologically equivalent) if they have the same open sets — equivalently, the same convergent sequences. They are strongly equivalent (Lipschitz equivalent) if there are constants $c,C\gt0$ with $c\,d(x,y)\le\rho(x,y)\le C\,d(x,y)$ for all $x,y$.
📐 Theorem 4.3 — Comparing metrics
  1. Strongly equivalent metrics are equivalent and have the same Cauchy sequences and the same bounded sets.
  2. On $\mathbb{R}^n$: $d_\infty\le d_2\le d_1\le n\,d_\infty$, so $d_1,d_2,d_\infty$ (indeed all $d_p$) are strongly equivalent.
  3. On $C[a,b]$: $d_1\le(b-a)\,d_\infty$, but there is no inequality $d_\infty\le C\,d_1$. Every $d_1$-open set is $d_\infty$-open, not conversely: the two metrics are not equivalent.
  4. $d$, $\min\{d,1\}$ and $\frac{d}{1+d}$ are equivalent and have the same Cauchy sequences, although the last two make every set bounded. On $\mathbb{R}$, $|x-y|$ and $|\arctan x-\arctan y|$ are equivalent but do not have the same Cauchy sequences.

Proof. (1) $\rho\le Cd$ puts the $d$-ball $B_d(x,r/C)$ inside the $\rho$-ball $B_\rho(x,r)$, so $\rho$-open sets are $d$-open; the other inequality gives the converse, and both inequalities transport Cauchy sequences and bounded sets. (2) For each $i$, $|x_i|\le\|x\|_2$; $\|x\|_2^2=\sum x_i^2\le(\sum|x_i|)^2$; and $\sum|x_i|\le n\max|x_i|$. (3) $\int_a^b|f-g|\le(b-a)\max|f-g|$. For the failure, let $t_n$ be the tent of height $1$ on $[a,a+\frac2n]$ (zero elsewhere). Then $d_1(t_n,0)=\frac1n\to0$ while $d_\infty(t_n,0)=1$, so $t_n\to0$ in $d_1$ but not in $d_\infty$; by Theorem 4.1(3) the $d_\infty$-closed set $\{f:\max|f|\ge1\}$ is not $d_1$-closed. (4) For $t\le1$ (respectively $t$ small) $\min\{t,1\}=t$ and $\frac t{1+t}\in[\frac t2,t]$, so small balls, convergent sequences and Cauchy sequences are the same. On $\mathbb{R}$, $\arctan$ is a homeomorphism onto $(-\frac\pi2,\frac\pi2)$, so the open sets agree; but $x_n=n$ is Cauchy for $|\arctan x-\arctan y|$ (since $\arctan n$ converges) and not for $|x-y|$. ∎

✏️ Example 1 — Is it a metric? Is the set open or closed?
(a) Decide which of $d_1(x,y)=(x-y)^2$, $d_2(x,y)=\sqrt{|x-y|}$, $d_3(x,y)=|x^2-y^2|$ are metrics on $\mathbb{R}$, and whether $d_3$ is a metric on $[0,\infty)$. (b) In a set $X$ with the discrete metric and at least two points, find $B(a,1)$, $\overline B(a,1)$ and the closure of $B(a,1)$. Which subsets of $X$ are open? (c) In $Y=[0,1)\cup[2,3]$ with the usual metric, is $[0,1)$ open in $Y$? Closed in $Y$? (d) For $A=\{\frac1n:n\in\mathbb{N}\}\subseteq\mathbb{R}$ find $A^\circ$, $\overline A$ and $\partial A$, and decide whether $A$ is open or closed.
(a) $d_1$: no The triangle inequality fails: $d_1(0,2)=4\gt d_1(0,1)+d_1(1,2)=1+1$. (Squaring a metric usually destroys (M3).)
(a) $d_2$: yes (M1) and (M2) are clear. For (M3), $\sqrt{s+t}\le\sqrt s+\sqrt t$ for $s,t\ge0$ (square both sides), so $\sqrt{|x-z|}\le\sqrt{|x-y|+|y-z|}\le\sqrt{|x-y|}+\sqrt{|y-z|}$. More generally $\varphi\circ d$ is a metric whenever $\varphi$ is increasing, subadditive and $\varphi(t)=0\iff t=0$.
(a) $d_3$ On $\mathbb{R}$ it fails (M1): $d_3(1,-1)=0$ with $1\ne-1$. On $[0,\infty)$ the map $x\mapsto x^2$ is injective, so $d_3(x,y)=|x^2-y^2|$ is the pull-back of the usual metric: a metric.
(b) Discrete $B(a,1)=\{x:d(x,a)\lt1\}=\{a\}$ and $\overline B(a,1)=\{x:d(x,a)\le1\}=X$. Every singleton $\{a\}=B(a,1)$ is open, so every subset (a union of singletons) is open, and hence every subset is also closed. In particular the closure of $B(a,1)$ is $\{a\}$, which is not the closed ball $X$: in a general metric space $\overline{B(a,r)}\subseteq\overline B(a,r)$, with equality in normed spaces but not always.
(c) Both $[0,1)=(-1,1)\cap Y$ is open in $Y$ by Theorem 4.1(4), and $[0,1)=[0,1]\cap Y$ is closed in $Y$; equivalently its complement $[2,3]=(1.5,4)\cap Y$ is open in $Y$. In $\mathbb{R}$ the set $[0,1)$ is neither open nor closed — openness depends on the ambient space.
(d) No ball around $\frac1n$ lies in $A$, so $A^\circ=\varnothing$ and $A$ is not open. The only limit point is $0$ ($\frac1n\to0$, and any other point has a ball containing at most one point of $A$). So $\overline A=A\cup\{0\}$, $A$ is not closed, and $\partial A=\overline A\setminus A^\circ=A\cup\{0\}$.

Completeness

📘 Definition 4.5 — Complete metric space
A metric space is complete if every Cauchy sequence in it converges to a point of the space.

Completeness is what makes "the iterates get closer together, so they have a limit" a valid argument. $\mathbb{R}$ is complete (this is one form of the completeness axiom); $\mathbb{Q}$ is not, since the decimal approximations of $\sqrt2$ form a Cauchy sequence in $\mathbb{Q}$ with no limit in $\mathbb{Q}$.

📐 Theorem 4.4 — Which spaces are complete
  1. $\mathbb{R}^n$ and $\mathbb{C}^n$ are complete with every $d_p$.
  2. A subspace $Y$ of a complete space $X$ is complete if and only if $Y$ is closed in $X$. In any metric space, a complete subspace is closed.
  3. $(C[a,b],d_\infty)$ is complete; so are $\ell^p$ ($1\le p\le\infty$) and $c_0$. Every discrete metric space is complete.
  4. $(C[a,b],d_1)$ is not complete; neither are $\mathbb{Q}$, $(0,1)$, $c_{00}$ (with $d_\infty$), the polynomials on $[0,1]$ (with $d_\infty$), or $\mathbb{R}$ with $|\arctan x-\arctan y|$.

Proof. (1) If $(x^{(k)})$ is Cauchy in $(\mathbb{R}^n,d_\infty)$, each coordinate sequence is Cauchy in $\mathbb{R}$ and converges, say $x^{(k)}_i\to x_i$; then $d_\infty(x^{(k)},x)=\max_i|x^{(k)}_i-x_i|\to0$. The other $d_p$ are strongly equivalent (Theorem 4.3).

(2) Let $Y$ be closed and $(y_n)$ Cauchy in $Y$. It is Cauchy in $X$, so $y_n\to x\in X$, and $x\in Y$ because $Y$ is closed. Conversely let $Y$ be complete and $y_n\to x\in X$ with $y_n\in Y$. Then $(y_n)$ is Cauchy, so it converges to some $y\in Y$; by uniqueness of limits $x=y\in Y$, and $Y$ is closed by Theorem 4.1(3).

(3) Let $(f_n)$ be Cauchy in $d_\infty$. For each $x$, $|f_n(x)-f_m(x)|\le d_\infty(f_n,f_m)$, so $(f_n(x))$ is Cauchy in $\mathbb{R}$; call its limit $f(x)$. Given $\varepsilon$, choose $N$ with $|f_n(x)-f_m(x)|\lt\varepsilon$ for all $x$ and $m,n\ge N$, and let $m\to\infty$: $|f_n(x)-f(x)|\le\varepsilon$ for all $x$ and $n\ge N$. So $f_n\to f$ uniformly, and a uniform limit of continuous functions is continuous (§4.2), so $f\in C[a,b]$ and $d_\infty(f_n,f)\to0$. The sequence spaces are treated in the same way in §8.1 (the standard Banach spaces). In a discrete space a Cauchy sequence has $d(x_m,x_n)\lt1$, i.e. $x_m=x_n$, for $m,n\ge N$: it is eventually constant.

(4) In $(C[0,1],d_1)$ let $f_n$ be $0$ on $[0,\frac12]$, rise linearly to $1$ on $[\frac12,\frac12+\frac1n]$ and equal $1$ afterwards. For $m\gt n$, $f_m\ge f_n$ and $d_1(f_n,f_m)=\int(f_m-f_n)=\frac1{2n}-\frac1{2m}$, so $(f_n)$ is Cauchy. If $d_1(f_n,f)\to0$ for a continuous $f$, then $\int_0^{1/2}|f|\le d_1(f_n,f)\to0$, so $f=0$ on $[0,\frac12]$; and for each $\delta\gt0$, $f_n=1$ on $[\frac12+\delta,1]$ once $n\gt\frac1\delta$, so $f=1$ on $(\frac12,1]$ — impossible for a continuous function. In $c_{00}$, $x^{(k)}=(1,\frac12,\dots,\frac1k,0,0,\dots)$ is Cauchy ($d_\infty(x^{(k)},x^{(l)})=\frac1{k+1}$ for $l\gt k$) and its only possible limit $(\frac1n)$ is not in $c_{00}$. The Taylor polynomials of $e^x$ converge uniformly on $[0,1]$ to $e^x$, which is not a polynomial, so the polynomials are not closed in $C[0,1]$ and, by (2), not complete. In $\mathbb{R}$ with the arctan metric $x_n=n$ is Cauchy, and a limit $x$ would need $\arctan x=\lim\arctan n=\frac\pi2$. ∎

Completeness is not preserved by homeomorphisms: $(0,1)$ is homeomorphic to $\mathbb{R}$ (by $x\mapsto\tan(\pi x-\frac\pi2)$), and $\mathbb{R}$ with the usual and with the arctan metric have the same open sets, yet in each pair one space is complete and the other is not. It is preserved by strongly equivalent metrics and by isometries — which is often the fastest way to decide it.

📐 Theorem 4.5 — Cantor's intersection theorem and Baire's theorem
  1. Cantor. Let $X$ be complete and $F_1\supseteq F_2\supseteq\cdots$ nonempty closed sets with $\operatorname{diam}F_n\to0$. Then $\bigcap_nF_n$ consists of exactly one point. Conversely, a metric space in which every such sequence has nonempty intersection is complete.
  2. Baire. In a complete metric space, a countable intersection of dense open sets is dense. Equivalently, if $X=\bigcup_{n}F_n$ with every $F_n$ closed, then some $F_n$ contains a ball.

Proof. (1) Pick $x_n\in F_n$. For $m\ge n$, $x_m\in F_n$, so $d(x_m,x_n)\le\operatorname{diam}F_n\to0$: the sequence is Cauchy and converges to some $x$. For each $n$ the tail $(x_m)_{m\ge n}$ lies in the closed set $F_n$, so $x\in F_n$. Two points of the intersection have distance at most $\operatorname{diam}F_n$ for every $n$, hence coincide. For the converse, given a Cauchy sequence put $F_n=\overline{\{x_m:m\ge n\}}$; these are nested, closed, nonempty with $\operatorname{diam}F_n\to0$, and a point $x$ of their intersection satisfies $d(x_n,x)\le\operatorname{diam}F_n\to0$.

(2) (Sketch.) Let $U_1,U_2,\dots$ be open and dense and $W$ any nonempty open set. $W\cap U_1$ is open and nonempty, so it contains a closed ball $\overline B_1$ of radius $\le1$; $B_1\cap U_2$ is open and nonempty, so it contains a closed ball $\overline B_2$ of radius $\le\frac12$; and so on. By Cantor the centres converge to a point lying in $W$ and in every $U_n$. The second form follows by applying the first to $U_n=X\setminus F_n$. ∎

Both hypotheses of Cantor's theorem are needed: $F_n=[n,\infty)$ in $\mathbb{R}$ are nested and closed with empty intersection (the diameters do not shrink), and $F_n=(0,\frac1n]$ in the incomplete space $(0,1]$ have empty intersection although the diameters shrink. Baire's theorem is the engine of the uniform boundedness, open mapping and closed graph theorems of §8.2; in this section we use only one consequence: a nonempty complete metric space with no isolated points is uncountable (the singletons $\{x\}$ would be closed sets with empty interior). So $\mathbb{R}$ is uncountable, and $\mathbb{Q}$ is not complete under any metric equivalent to the usual one.

✏️ Example 2 — Complete or not?
Decide which of these metric spaces are complete. (a) $\mathbb{N}$ with $d(m,n)=\left|\frac1m-\frac1n\right|$. (b) $\mathbb{Z}$ with $|m-n|$. (c) $(0,1]$ with $\rho(x,y)=\left|\frac1x-\frac1y\right|$. (d) $\{f\in C[0,1]:f(0)=0\}$ with $d_\infty$. (e) $\mathbb{R}$ with $d(x,y)=|e^x-e^y|$. (f) $C[0,1]$ with $d(f,g)=\max_{[0,1]}|f-g|+\big|f(\tfrac12)-g(\tfrac12)\big|$.
(a) No $x_n=n$ is Cauchy: $d(m,n)=|\frac1m-\frac1n|\le\max\{\frac1m,\frac1n\}$. A limit $k$ would need $\frac1n\to\frac1k$, impossible. Note that every point is isolated ($d(k,n)\ge\frac1k-\frac1{k+1}$ for $n\ne k$), so this metric has the same open sets as the discrete metric, which is complete — completeness is not a topological property.
(b) Yes Distinct integers are at distance $\ge1$, so a Cauchy sequence is eventually constant.
(c) Yes $x\mapsto\frac1x$ is an isometry of $((0,1],\rho)$ onto $[1,\infty)$ with the usual metric, which is closed in $\mathbb{R}$ and hence complete (Theorem 4.4(2)). The sequence $\frac1n$, which "wants" to converge to $0$, is not Cauchy for $\rho$: $\rho(\frac1n,\frac1m)=|n-m|$.
(d) Yes Evaluation $f\mapsto f(0)$ is $1$-Lipschitz for $d_\infty$, so the set is the preimage of the closed set $\{0\}$, closed in the complete space $(C[0,1],d_\infty)$.
(e) No $x\mapsto e^x$ is an isometry onto $(0,\infty)$ with the usual metric, which is not complete: $x_n=-n$ is Cauchy ($|e^{-n}-e^{-m}|\to0$) with no limit, since $e^x\gt0$.
(f) Yes $d_\infty\le d\le2d_\infty$ because $|f(\frac12)-g(\frac12)|\le d_\infty(f,g)$. Strongly equivalent to the complete metric $d_\infty$, so complete.

The Contraction Mapping Principle

📘 Definition 4.6 — Contraction, fixed point
A map $T:X\to X$ on a metric space is a contraction if there is a constant $k\in[0,1)$ with $d(Tx,Ty)\le k\,d(x,y)$ for all $x,y\in X$; $k$ is a contraction constant. A point with $Tx=x$ is a fixed point of $T$. A map with $d(Tx,Ty)\lt d(x,y)$ for all $x\ne y$ is called contractive; it need not be a contraction.
📐 Theorem 4.6 — Banach contraction principle (Banach fixed point theorem)

Let $(X,d)$ be a nonempty complete metric space and $T:X\to X$ a contraction with constant $k\lt1$. Then:

  1. $T$ has exactly one fixed point $x^*$;
  2. for every starting point $x_0$, the iterates $x_n=T^nx_0$ converge to $x^*$;
  3. the errors satisfy
$$d(x_n,x^*)\le\frac{k^n}{1-k}\,d(x_1,x_0),$$ $$d(x_n,x^*)\le\frac{k}{1-k}\,d(x_n,x_{n-1}),$$

and $d(x_n,x^*)\le k\,d(x_{n-1},x^*)$ (the error shrinks at least geometrically).

Proof. Uniqueness. If $Tx=x$ and $Ty=y$ then $d(x,y)=d(Tx,Ty)\le k\,d(x,y)$, and since $k\lt1$ this forces $d(x,y)=0$.

Existence. Fix $x_0$ and put $x_n=Tx_{n-1}$. By induction $d(x_{j+1},x_j)\le k^j\,d(x_1,x_0)$. For $m\gt n$, the triangle inequality and the geometric series give

$$d(x_m,x_n)\le\sum_{j=n}^{m-1}d(x_{j+1},x_j)\le\frac{k^n}{1-k}\,d(x_1,x_0).$$

The right side tends to $0$, so $(x_n)$ is Cauchy; by completeness $x_n\to x^*$ for some $x^*\in X$. A contraction is Lipschitz, hence continuous, so $Tx^*=\lim Tx_n=\lim x_{n+1}=x^*$.

Error bounds. Let $m\to\infty$ in the displayed inequality (the distance is continuous in each variable) to get the first bound. Applying the first bound with $x_{n-1}$ as the starting point (one step) gives $d(x_n,x^*)\le\frac{k}{1-k}d(x_n,x_{n-1})$. Finally $d(x_n,x^*)=d(Tx_{n-1},Tx^*)\le k\,d(x_{n-1},x^*)$. ∎

The first bound is called a priori: it is known before computing, and gives the number of iterations needed for accuracy $\varepsilon$: $\frac{k^n}{1-k}d(x_1,x_0)\le\varepsilon$ as soon as $n\ge\log\!\big(\varepsilon(1-k)/d(x_1,x_0)\big)/\log k$. The second, a posteriori, bound uses the last step actually taken, and is usually much sharper. Every hypothesis is needed: $Tx=\frac x2$ on the incomplete space $(0,1]$ is a contraction without a fixed point; $Tx=x+1$ on $\mathbb{R}$ is an isometry ($k=1$) without one; and $Tx=x+\frac1x$ on the complete space $[1,\infty)$ is contractive, since $|Tx-Ty|=|x-y|\big(1-\frac1{xy}\big)\lt|x-y|$, yet $x+\frac1x=x$ has no solution.

📐 Theorem 4.7 — Three working versions
  1. Derivative test. Let $I\subseteq\mathbb{R}$ be a closed interval (bounded or not) and $g:I\to I$ differentiable with $|g'(x)|\le k\lt1$ on $I$. Then $g$ is a contraction of $I$ with constant $k$, so it has a unique fixed point in $I$, and $x_{n+1}=g(x_n)$ converges to it from every $x_0\in I$.
  2. A power that contracts. If $X$ is complete and some iterate $T^m$ ($m\ge1$) is a contraction, then $T$ has a unique fixed point $x^*$ and $T^nx_0\to x^*$ for every $x_0$.
  3. Local version. Let $X$ be complete, $x_0\in X$, $r\gt0$ and $T:\overline B(x_0,r)\to X$ with $d(Tx,Ty)\le k\,d(x,y)$ on the ball, $k\lt1$. If $d(Tx_0,x_0)\le(1-k)r$, then $T$ maps $\overline B(x_0,r)$ into itself and has a unique fixed point in it.

Proof. (1) By the mean value theorem $|g(x)-g(y)|=|g'(\xi)|\,|x-y|\le k|x-y|$, and a closed interval is complete. (2) Put $S=T^m$ with fixed point $x^*$. Then $S(Tx^*)=T(Sx^*)=Tx^*$, so $Tx^*$ is also a fixed point of $S$; by uniqueness $Tx^*=x^*$. Any fixed point of $T$ is a fixed point of $S$, so it is $x^*$. For convergence, each of the $m$ subsequences $T^{qm+r}x_0=S^q(T^rx_0)$, $r=0,\dots,m-1$, converges to $x^*$ by Theorem 4.6, hence so does the whole sequence. (3) For $x$ in the ball, $d(Tx,x_0)\le d(Tx,Tx_0)+d(Tx_0,x_0)$, and this is $\le kr+(1-k)r=r$. A closed ball is closed in $X$, so complete, and Theorem 4.6 applies. ∎

Version (3) is how the contraction principle proves the inverse and implicit function theorems (§1.1) and the Picard–Lindelöf existence theorem for $y'=F(x,y)$ (§6.1): the Picard map $(Ty)(x)=y_0+\int_{x_0}^xF(t,y(t))\,dt$ is a contraction on a small ball of $C[x_0-h,x_0+h]$, or — by version (2) — some power of it is a contraction on the whole interval. In numerical analysis, version (1) is the convergence criterion for fixed-point iteration (§9.1).

🧭 Fixed-point questions in GATE time
  1. Find a closed set the map sends into itself — an interval $[a,b]$ with $g(a),g(b)$ and the extreme values of $g$ inside it, a closed ball, a closed subset of $C[a,b]$.
  2. Bound the Lipschitz constant on that set: $\max|g'|$ for a real function; a row-sum (for $d_\infty$) or column-sum (for $d_1$) norm for a linear map of $\mathbb{R}^n$; $\max_x\int|K(x,t)|\,dt$ for an integral operator on $(C[a,b],d_\infty)$.
  3. Conclude existence, uniqueness and convergence from every starting point of the set; use the a priori bound for "how many iterations" and the a posteriori bound for "how accurate is $x_n$".
  4. If $k\ge1$, try a smaller set, an iterate $g\circ g$, or a different metric — or look for a counterexample: two fixed points, none, or an orbit that does not converge.
✏️ Example 3 — Solving $x=\cos x$
Show that $x=\cos x$ has exactly one real solution, that the iteration $x_{n+1}=\cos x_n$ converges to it from every real $x_0$, and find how many iterations from $x_0=1$ the a priori bound requires for an error below $10^{-4}$. How many are actually needed?
Invariant interval $\cos$ is not a contraction of $\mathbb{R}$ ($|\sin x|$ reaches $1$), so restrict it. On $I=[0,1]$, $\cos$ is decreasing with $\cos0=1$ and $\cos1\approx0.5403$, so $\cos(I)=[\cos1,1]\subseteq I$, and $|(\cos)'(x)|=\sin x\le\sin1\approx0.8415\lt1$ on $I$.
Fixed point in $I$ By Theorem 4.7(1), $\cos$ has exactly one fixed point $x^*\in[0,1]$ and the iterates from any $x_0\in[0,1]$ converge to it; numerically $x^*\approx0.739085$.
All of $\mathbb{R}$ Any real solution of $x=\cos x$ satisfies $|x|\le1$; on $[-1,0)$, $\cos x\gt0\gt x$, so every solution lies in $[0,1]$ and $x^*$ is the only one. For an arbitrary $x_0\in\mathbb{R}$, $x_1=\cos x_0\in[-1,1]$ and $x_2=\cos x_1\in[\cos1,1]\subseteq[0,1]$; from then on the previous step applies.
A priori count $k=\sin1$ and $d(x_1,x_0)=1-\cos1\approx0.4597$. We need $\dfrac{k^n}{1-k}(0.4597)\lt10^{-4}$, that is $n\gt\dfrac{\log\big(10^{-4}(1-k)/0.4597\big)}{\log k}\approx59.5$: the bound guarantees accuracy after $60$ iterations.
Check Actually $|x_n-x^*|\lt10^{-4}$ already for $n=20$: the true rate is $|g'(x^*)|=\sin x^*\approx0.674$, much better than the worst case $\sin1$. The a priori bound is a guarantee, not a prediction. Interactive 1 shows the cobweb and both bounds.
✏️ Example 4 — An integral equation, and how much the metric matters
For which $\lambda$ does the contraction principle on $(C[0,1],d_\infty)$ guarantee a unique continuous solution of $f(x)=x+\lambda\displaystyle\int_0^1xt\,f(t)\,dt$? Solve the equation exactly and compare.
The map $(Tf)(x)=x+\lambda x\int_0^1tf(t)\,dt$ sends $C[0,1]$ into itself (it is $x$ times a constant, plus $x$).
Lipschitz constant For $f,g\in C[0,1]$ and $x\in[0,1]$: $|(Tf-Tg)(x)|\le|\lambda|\,x\int_0^1t\,|f-g|\,dt\le|\lambda|\cdot1\cdot\tfrac12\,d_\infty(f,g)$. So $T$ is a contraction with $k=\frac{|\lambda|}2$ when $|\lambda|\lt2$, and $(C[0,1],d_\infty)$ is complete: a unique solution exists for $|\lambda|\lt2$, and the iterates from $f_0=0$ converge to it uniformly.
Exact solution Any solution has the form $f(x)=x(1+\lambda c)$ with $c=\int_0^1tf(t)\,dt$. Substituting, $c=(1+\lambda c)\int_0^1t^2\,dt=\frac{1+\lambda c}3$, so $c(3-\lambda)=1$. For $\lambda\ne3$: $c=\frac1{3-\lambda}$ and $f(x)=\dfrac{3x}{3-\lambda}$, the unique solution. For $\lambda=3$ there is no solution.
Compare The contraction principle gave $|\lambda|\lt2$, but the equation is uniquely solvable for every $\lambda\ne3$: the principle is sufficient, not necessary. The iterates from $f_0=0$ are $f_n(x)=x\big(1+\frac\lambda3+\dots+(\frac\lambda3)^{n-1}\big)$, which converge exactly when $|\lambda|\lt3$ — on the line of functions $cx$, $T$ contracts by the factor $\frac{|\lambda|}3$, a sharper constant than the sup-metric estimate $\frac{|\lambda|}2$. (In the $L^2$ norm of §8.3 the kernel $xt$ has norm $\frac13$, which gives $|\lambda|\lt3$ directly.)
✏️ Example 5 — Contraction or not?
For each map decide whether it is a contraction, whether it has a fixed point, and whether the iterates converge. (a) $g(x)=\frac12\left(x+\frac2x\right)$ on $[1,2]$. (b) $g(x)=x+\frac1x$ on $[1,\infty)$. (c) $T(v)=Av+b$ on $\mathbb{R}^2$ with $A=\begin{pmatrix}0.5&0.6\\0&0.3\end{pmatrix}$, $b=\begin{pmatrix}1\\1\end{pmatrix}$, with respect to $d_\infty$ and to $d_1$. (d) $g(x)=\sin x$ on $\mathbb{R}$.
(a) Yes $g'(x)=\frac12-\frac1{x^2}\in[-\frac12,\frac14]$ on $[1,2]$, so $|g'|\le\frac12$; $g$ has its minimum $\sqrt2$ at $x=\sqrt2$ and $g(1)=1.5$, $g(2)=1.5$, so $g([1,2])=[\sqrt2,1.5]\subseteq[1,2]$. Unique fixed point $x=\frac2x$, i.e. $\sqrt2$: this is Newton's method for $x^2=2$, and it converges from every $x_0\in[1,2]$.
(b) Contractive only $|g(x)-g(y)|=|x-y|\,\big(1-\frac1{xy}\big)\lt|x-y|$ for $x\ne y$, but the ratio tends to $1$ as $x,y\to\infty$, so no $k\lt1$ works. There is no fixed point, and the iterates increase to $\infty$ (if they converged to $L$, then $L=L+\frac1L$). A contractive map on a compact space does have a fixed point (Theorem 4.10); $[1,\infty)$ is not compact.
(c) Depends on the metric $d_\infty(Tv,Tw)=\|A(v-w)\|_\infty$, and the best constant is the largest row sum of $|A|$: $\max\{1.1,\ 0.3\}=1.1$ — not a contraction for $d_\infty$ (indeed $\|A(1,1)^{\mathsf T}\|_\infty=1.1$). For $d_1$ the best constant is the largest column sum: $\max\{0.5,\ 0.9\}=0.9\lt1$, a contraction. $(\mathbb{R}^2,d_1)$ is complete, so there is a unique fixed point and all iterates converge to it, also in $d_\infty$ (the metrics are strongly equivalent). Solving $(I-A)v=b$: $0.7v_2=1$, $0.5v_1-0.6v_2=1$, so $v^*=(\frac{26}7,\frac{10}7)$.
(d) Not a contraction $|\sin x-\sin y|\lt|x-y|$ for $x\ne y$ (because $\sin x-\sin y=\int_y^x\cos t\,dt$ and $|\cos t|\lt1$ except at isolated points), but $\frac{\sin x}{x}\to1$ as $x\to0$, so no $k\lt1$ works. The only fixed point is $0$ (since $|\sin x|\lt|x|$ for $x\ne0$), and the iterates do converge to it — but slowly, like $\sqrt{3/n}$, not geometrically. Contraction is sufficient for geometric convergence, not necessary for convergence.

Compactness

📘 Definition 4.7 — Compact, sequentially compact, totally bounded

Let $K$ be a subset of a metric space $X$.

  • An open cover of $K$ is a family of open sets whose union contains $K$. $K$ is compact if every open cover of $K$ has a finite subcover.
  • $K$ is sequentially compact if every sequence in $K$ has a subsequence converging to a point of $K$.
  • $K$ is totally bounded if for every $\varepsilon\gt0$ it is covered by finitely many balls of radius $\varepsilon$ (an $\varepsilon$-net).
📐 Theorem 4.8 — Characterisation of compact metric spaces

For a metric space $K$ the following are equivalent:

  1. $K$ is compact;
  2. $K$ is sequentially compact;
  3. $K$ is complete and totally bounded.

Moreover, a compact subset of any metric space is closed and bounded, and a closed subset of a compact set is compact.

Proof. (1)⇒(2). Suppose $(x_n)$ has no subsequence converging in $K$. Then each $y\in K$ has a ball $B(y,r_y)$ containing $x_n$ for only finitely many $n$ (otherwise one could pick a subsequence converging to $y$). These balls cover $K$; finitely many of them cover $K$, and so contain $x_n$ for only finitely many $n$ — a contradiction.

(2)⇒(3). A Cauchy sequence has a convergent subsequence, hence converges (Theorem 4.2(3)): $K$ is complete. If $K$ were not totally bounded, for some $\varepsilon$ no finite family of $\varepsilon$-balls would cover $K$; choose $x_1$, then $x_2\notin B(x_1,\varepsilon)$, then $x_3\notin B(x_1,\varepsilon)\cup B(x_2,\varepsilon)$, and so on. Then $d(x_m,x_n)\ge\varepsilon$ for $m\ne n$, and no subsequence is Cauchy.

(3)⇒(2). Given $(x_n)$, cover $K$ by finitely many balls of radius $1$; one of them contains $x_n$ for infinitely many $n$ — a subsequence $S_1$. Cover by finitely many balls of radius $\frac12$; one contains infinitely many terms of $S_1$ — a subsequence $S_2$; and so on. The diagonal sequence (the $j$-th term of $S_j$) has its $j$-th and later terms in a ball of radius $\frac1j$, so it is Cauchy, and it converges by completeness.

(2)⇒(1). Lebesgue number lemma: for an open cover $\mathcal{U}$ of a sequentially compact $K$ there is $\delta\gt0$ such that every ball $B(x,\delta)$ lies in some member of $\mathcal{U}$. If not, for each $n$ some $B(x_n,\frac1n)$ lies in no member; a subsequence $x_{n_j}\to x\in U\in\mathcal{U}$, with $B(x,r)\subseteq U$; for large $j$, $d(x_{n_j},x)\lt\frac r2$ and $\frac1{n_j}\lt\frac r2$, so $B(x_{n_j},\frac1{n_j})\subseteq B(x,r)\subseteq U$ — a contradiction. Now $K$ is totally bounded (by (2)⇒(3)), so finitely many balls $B(x_i,\delta)$ cover $K$, and each lies in some $U_i\in\mathcal{U}$: $U_1,\dots,U_m$ is a finite subcover.

Finally, a compact $K\subseteq X$ is complete, hence closed in $X$ (Theorem 4.4(2)); it is covered by finitely many balls $B(x_i,1)$, hence bounded. If $F\subseteq K$ is closed, a sequence in $F$ has a subsequence converging in $K$, and the limit lies in $F$ because $F$ is closed. ∎

📐 Theorem 4.9 — Heine–Borel in $\mathbb{R}^n$; failure in infinite dimensions
  1. Heine–Borel. A subset of $\mathbb{R}^n$ (with any $d_p$) is compact if and only if it is closed and bounded.
  2. In $\ell^p$ ($1\le p\le\infty$), $c_0$ and $(C[a,b],d_\infty)$ the closed unit ball is closed and bounded but not compact. (More generally, the closed unit ball of a normed space is compact if and only if the space is finite-dimensional — Riesz's theorem, §8.1.)
  3. The Hilbert cube $\{x\in\ell^2:|x_n|\le\frac1n\text{ for all }n\}$ is compact.

Proof. (1) Compact sets are closed and bounded by Theorem 4.8. Conversely a bounded set lies in a cube $Q=[-M,M]^n$. $Q$ is complete (closed in $\mathbb{R}^n$) and totally bounded: the grid points with coordinates in $\varepsilon\mathbb{Z}\cap[-M,M]$ are finitely many and every point of $Q$ is within $d_\infty$-distance $\varepsilon$ of one. So $Q$ is compact, and a closed subset of $Q$ is compact.

(2) In $\ell^p$ let $e_k$ have a $1$ in place $k$ and $0$ elsewhere. Then $\|e_k\|_p=1$ and $d_p(e_k,e_l)=2^{1/p}$ (or $1$ for $p=\infty$) for $k\ne l$, so $(e_k)$ has no Cauchy subsequence. In $C[0,1]$ take tents $t_k$ of height $1$ with disjoint supports in $[\frac1{k+1},\frac1k]$: $d_\infty(t_k,t_l)=1$ for $k\ne l$. Either way the ball is not totally bounded.

(3) The cube $H$ is closed in $\ell^2$ (each condition $|x_n|\le\frac1n$ is preserved by $\ell^2$-limits, which converge coordinatewise), so complete. Given $\varepsilon$, choose $N$ with $\sum_{n\gt N}\frac1{n^2}\lt\frac{\varepsilon^2}4$; the tails of points of $H$ beyond $N$ then have $\ell^2$-norm $\lt\frac\varepsilon2$, and the first $N$ coordinates range over a compact box in $\mathbb{R}^N$, which has a finite $\frac\varepsilon2$-net. Together these give a finite $\varepsilon$-net of $H$: it is totally bounded. ∎

📐 Theorem 4.10 — Continuous maps on compact spaces

Let $K$ be a compact metric space and $f:K\to Y$ continuous.

  1. $f(K)$ is compact. If $Y=\mathbb{R}$, $f$ is bounded and attains its maximum and minimum.
  2. (Heine) $f$ is uniformly continuous.
  3. If $f$ is a bijection of $K$ onto $Y$, then $f^{-1}$ is continuous: $f$ is a homeomorphism.
  4. If $K$ lies in a metric space $X$ and $F\subseteq X$ is closed with $K\cap F=\varnothing$, then $d(K,F)=\inf\{d(x,y):x\in K,\ y\in F\}\gt0$.
  5. (Edelstein) If $T:K\to K$ satisfies $d(Tx,Ty)\lt d(x,y)$ for all $x\ne y$, then $T$ has a unique fixed point $x^*$ and $T^nx_0\to x^*$ for every $x_0$.

Proof. (1) If $(V_\alpha)$ is an open cover of $f(K)$, the open sets $f^{-1}(V_\alpha)$ cover $K$; finitely many do, and the corresponding $V_\alpha$ cover $f(K)$. A compact subset of $\mathbb{R}$ is closed and bounded, so it contains its supremum and infimum.

(2) If not, there are $\varepsilon\gt0$ and points with $d(x_n,y_n)\lt\frac1n$ but $\rho(f(x_n),f(y_n))\ge\varepsilon$. A subsequence $x_{n_j}\to x$; then $y_{n_j}\to x$ too, and continuity at $x$ gives $\rho(f(x_{n_j}),f(y_{n_j}))\to0$ — a contradiction.

(3) If $F\subseteq K$ is closed, it is compact, so $f(F)$ is compact, hence closed in $Y$. Thus $(f^{-1})^{-1}(F)=f(F)$ is closed for every closed $F$, and $f^{-1}$ is continuous by Theorem 4.2(1).

(4) $x\mapsto d(x,F)$ is $1$-Lipschitz and positive on $K$ (positive because $F$ is closed and $x\notin F$), so by (1) it has a positive minimum on $K$.

(5) $\varphi(x)=d(x,Tx)$ is continuous ($T$ is $1$-Lipschitz), so it attains its minimum at some $x^*$. If $Tx^*\ne x^*$, then $\varphi(Tx^*)=d(Tx^*,T^2x^*)\lt d(x^*,Tx^*)=\varphi(x^*)$, contradicting minimality; so $Tx^*=x^*$, and uniqueness is as in Theorem 4.6. The numbers $d(T^nx_0,x^*)$ decrease to some $c\ge0$. A subsequence $T^{n_j}x_0\to y$ with $d(y,x^*)=c$, and $d(Ty,x^*)=\lim d(T^{n_j+1}x_0,x^*)=c$ as well. If $y\ne x^*$ then $d(Ty,x^*)=d(Ty,Tx^*)\lt d(y,x^*)=c$, a contradiction; so $c=0$. ∎

Each conclusion fails without compactness: $x^2$ is continuous but not uniformly continuous on $\mathbb{R}$, and $\frac1x$ on $(0,1]$ is continuous and unbounded; $t\mapsto(\cos t,\sin t)$ is a continuous bijection of $[0,2\pi)$ onto the circle whose inverse is discontinuous at $(1,0)$; the closed sets $\{xy=1\}$ and $\{y=0\}$ in $\mathbb{R}^2$ are disjoint at distance $0$; and $x+\frac1x$ on $[1,\infty)$ is contractive without a fixed point.

✏️ Example 6 — Which sets are compact?
(a) $A=\{\frac1n:n\in\mathbb{N}\}\cup\{0\}\subseteq\mathbb{R}$. (b) $\mathbb{Q}\cap[0,1]$. (c) $E=\{(x,y)\in\mathbb{R}^2:x^2+xy+y^2\le1\}$. (d) The orthogonal group $O(n)=\{A\in M_n(\mathbb{R}):A^{\mathsf T}A=I\}$, and $GL_n(\mathbb{R})$, as subsets of $M_n(\mathbb{R})\cong\mathbb{R}^{n^2}$. (e) An infinite set with the discrete metric. (f) The unit sphere $\{x\in\ell^2:\|x\|_2=1\}$.
(a) Compact Closed ($0$ is its only limit point and belongs to it) and bounded. Directly from covers: the member $U\ni0$ contains $\frac1n$ for all $n\ge N$, and $N-1$ further members cover the rest.
(b) Not compact Not closed in $\mathbb{R}$: rationals $\to\frac1{\sqrt2}$. Equivalently, a sequence of rationals tending to $\frac1{\sqrt2}$ has no subsequence converging in $\mathbb{Q}\cap[0,1]$.
(c) Compact Closed (preimage of $(-\infty,1]$ under a continuous function). Bounded, because $x^2+xy+y^2\ge\frac12(x^2+y^2)$ (equivalently $\frac12(x+y)^2\ge0$), so $E\subseteq\{x^2+y^2\le2\}$. Heine–Borel.
(d) $O(n)$ yes, $GL_n$ no $A\mapsto A^{\mathsf T}A$ is continuous, so $O(n)$ is closed; each column of an orthogonal matrix is a unit vector, so $\sum_{i,j}a_{ij}^2=n$: bounded. $GL_n(\mathbb{R})$ is neither bounded ($kI$) nor closed ($\frac1kI\to0$, singular).
(e) Not compact It is closed and bounded (diameter $1$) in itself, but the cover by the open singletons has no finite subcover. Closed and bounded is enough only in $\mathbb{R}^n$.
(f) Not compact Closed and bounded, but contains $e_1,e_2,\dots$ with $\|e_k-e_l\|_2=\sqrt2$ (Theorem 4.9(2)).

Connectedness

📘 Definition 4.8 — Connected, path-connected, components

A separation of a metric space $X$ is a pair of disjoint nonempty open sets $U,V$ with $X=U\cup V$. $X$ is connected if it has no separation; a subset is connected if it is connected as a subspace. A path from $x$ to $y$ is a continuous $\gamma:[0,1]\to X$ with $\gamma(0)=x$, $\gamma(1)=y$; $X$ is path-connected if any two points are joined by a path. A component is a maximal connected subset; $X$ is totally disconnected if its components are single points.

📐 Theorem 4.11 — The basic facts about connectedness
  1. $X$ is connected $\iff$ the only subsets that are both open and closed are $\varnothing$ and $X$ $\iff$ every continuous $f:X\to\{0,1\}$ is constant.
  2. A subset of $\mathbb{R}$ is connected if and only if it is an interval.
  3. A continuous image of a connected set is connected. (Intermediate value theorem: a continuous $f:X\to\mathbb{R}$ on a connected $X$ takes every value between any two of its values.)
  4. Path-connected $\Rightarrow$ connected. An open connected subset of $\mathbb{R}^n$ is path-connected (even by polygonal paths).
  5. If $A$ is connected and $A\subseteq B\subseteq\overline A$, then $B$ is connected. A union of connected sets that all contain a common point is connected. The components of $X$ are closed, pairwise disjoint and cover $X$.

Proof. (1) If $U,V$ is a separation, $U$ is open and closed (its complement $V$ is open), and the indicator of $U$ is a continuous non-constant map to $\{0,1\}$; each step reverses.

(2) If $A$ is not an interval, there are $a\lt c\lt b$ with $a,b\in A$ and $c\notin A$; then $A\cap(-\infty,c)$ and $A\cap(c,\infty)$ separate $A$. Conversely let $I$ be an interval and suppose $I=U\cup V$ is a separation (by sets open in $I$), with $a\in U$, $b\in V$, say $a\lt b$; then $[a,b]\subseteq I$. Let $s=\sup(U\cap[a,b])$. The set $U\cap[a,b]=[a,b]\setminus V$ is closed in $[a,b]$, hence closed in $\mathbb{R}$, so $s\in U$, and $s\lt b$ because $b\in V$. As $U$ is open in $I$, some $[s,s+\delta)$ lies in $U\cap[a,b]$, contradicting the definition of $s$.

(3) If $f(X)=U'\cup V'$ were a separation, $f^{-1}(U'),f^{-1}(V')$ would separate $X$. For the IVT, $f(X)$ is a connected subset of $\mathbb{R}$, i.e. an interval, by (2).

(4) If $X=U\cup V$ were a separation with $x\in U$, $y\in V$ joined by a path $\gamma$, then $\gamma^{-1}(U),\gamma^{-1}(V)$ would separate $[0,1]$, contradicting (2). For an open connected $\Omega\subseteq\mathbb{R}^n$ and $a\in\Omega$, the set $P$ of points of $\Omega$ joined to $a$ by a polygonal path in $\Omega$ is open (a ball around a point of $P$ lies in $\Omega$, and its points are reached by one more segment), and $\Omega\setminus P$ is open for the same reason. $P\ne\varnothing$, so $P=\Omega$ by connectedness.

(5) A continuous $f:B\to\{0,1\}$ is constant on $A$ by (1), hence on $\overline A\cap B=B$ by continuity. If the $A_\alpha$ share the point $p$ and $f:\bigcup A_\alpha\to\{0,1\}$ is continuous, $f$ is constant on each $A_\alpha$ with value $f(p)$. The component of $x$ is the union of all connected sets containing $x$ (connected by the previous sentence), so components are disjoint and cover $X$, and each is closed since its closure is connected. ∎

The converse of the first part of (4) fails. The topologist's sine curve $S=\{(x,\sin\frac1x):0\lt x\le1\}\cup\big(\{0\}\times[-1,1]\big)$ is connected — it is the closure of the graph, which is connected as a continuous image of $(0,1]$ — but not path-connected: if a path $\gamma=(\gamma_1,\gamma_2)$ ran from $(0,0)$ to $(1,\sin1)$, let $t_0$ be the last time with $\gamma_1(t_0)=0$; just after $t_0$ the point $\gamma(t)$ is on the graph with $\gamma_1(t)\to0$, so $\gamma_2(t)=\sin(1/\gamma_1(t))$ takes the values $1$ and $-1$ in every interval $(t_0,t_0+\delta)$, and $\gamma_2$ is not continuous at $t_0$.

📐 Theorem 4.12 — Connectedness as a tool
  1. A homeomorphism $h:X\to Y$ maps components onto components, and for each $p\in X$ the spaces $X\setminus\{p\}$ and $Y\setminus\{h(p)\}$ have the same number of components.
  2. Consequently $\mathbb{R}$ is not homeomorphic to $\mathbb{R}^n$ for $n\ge2$; the intervals $[0,1]$, $[0,1)$ and $(0,1)$ are pairwise non-homeomorphic; and the circle $S^1$ is not homeomorphic to any subset of $\mathbb{R}$.
  3. A continuous $f:X\to\mathbb{R}$ on a connected $X$ that takes only rational (or only integer) values is constant. There is no continuous injection $\mathbb{R}^2\to\mathbb{R}$.
  4. $GL_n(\mathbb{R})$ has exactly two components, $\{\det\gt0\}$ and $\{\det\lt0\}$; $GL_n(\mathbb{C})$ is connected; $O(n)$ has two components and $SO(n)=\{A\in O(n):\det A=1\}$ is connected.

Proof. (1) Images and preimages of connected sets under $h$ and $h^{-1}$ are connected, and $h$ restricts to a homeomorphism $X\setminus\{p\}\to Y\setminus\{h(p)\}$. (2) $\mathbb{R}\setminus\{0\}$ has two components, while $\mathbb{R}^n\setminus\{p\}$ is path-connected for $n\ge2$ (go around $p$). Removing an endpoint of $[0,1]$ leaves it connected, removing any point of $(0,1)$ disconnects it, and $[0,1)$ has exactly one point (namely $0$) whose removal leaves it connected, while $[0,1]$ has two. If $S^1$ were homeomorphic to $A\subseteq\mathbb{R}$, $A$ would be a connected set with more than one point, i.e. an interval, and removing an interior point of $A$ disconnects it, while removing any point of $S^1$ leaves an arc, which is connected. (3) $f(X)$ is an interval contained in $\mathbb{Q}$, hence a single point. If $f:\mathbb{R}^2\to\mathbb{R}$ were continuous and injective, $f(\mathbb{R}^2)$ would be an interval with more than one point; pick $p$ with $f(p)$ an interior point of it. Then $f(\mathbb{R}^2\setminus\{p\})$ is connected but equals the interval minus the point $f(p)$, which is disconnected. (4) $\det$ is continuous and $GL_n(\mathbb{R})=\det^{-1}(0,\infty)\cup\det^{-1}(-\infty,0)$ is a separation. That each piece is connected, and that $GL_n(\mathbb{C})$ and $SO(n)$ are path-connected, is proved in the CSIR course (see 📚 Go deeper); for $n=2$, $SO(2)$ is the set of rotation matrices, a continuous image of the circle. ∎

✏️ Example 7 — Counting components, and two classic arguments
(a) Find the number of components of $A=\{(x,y)\in\mathbb{R}^2:x^2-y^2\ge1\}$ and of $B=\{(x,y):xy\ne0\}$. (b) Show that $\mathbb{R}^2$ minus a countable set $C$ is path-connected. (c) Show that every continuous $f:S^1\to\mathbb{R}$ takes equal values at some pair of antipodal points. (d) Is $X=\{(x,y):xy=0\}$ homeomorphic to $\mathbb{R}$?
(a) $2$ and $4$ $x^2\ge1+y^2\ge1$ forces $|x|\ge1$, so $A=A_+\cup A_-$ with $A_\pm=A\cap\{\pm x\ge1\}$, disjoint and closed in $A$ (and open in $A$, being $A\cap\{\pm x\gt0\}$). Each of $A_\pm$ is path-connected: from $(x,y)\in A_+$ the vertical segment to $(x,0)$ stays in $A_+$, because $x^2-t^2\ge x^2-y^2\ge1$ for $|t|\le|y|$, and all the points $(x,0)$ with $x\ge1$ lie on one ray. So $A$ has $2$ components. $B$ is the plane minus the two axes: the four open quadrants, each convex, and no path can cross an axis without leaving $B$ (the IVT applied to a coordinate). So $B$ has $4$ components.
(b) Let $p,q\notin C$. The lines through $p$ form an uncountable family whose members meet only at $p$, so all but countably many of them miss $C$; the same holds at $q$. Choose a line $L_p$ through $p$ and a line $L_q$ through $q$, both missing $C$ and not parallel; they meet at a point $r$, and the broken line $p\to r\to q$ lies in $\mathbb{R}^2\setminus C$. (So $\mathbb{R}^2\setminus\mathbb{Q}^2$ is path-connected, although $\mathbb{R}\setminus\mathbb{Q}$ is totally disconnected.)
(c) $g(z)=f(z)-f(-z)$ is continuous on the connected set $S^1$ (a continuous image of $[0,2\pi]$) and $g(-z)=-g(z)$. If $g(z_0)\ne0$, then $g$ takes the values $g(z_0)$ and $-g(z_0)$ of opposite signs, so by the IVT it vanishes somewhere: $f(z)=f(-z)$. (On any day there are two opposite points on the equator with the same temperature.)
(d) No Removing the origin from $X$ (the union of the two axes) leaves $4$ components, while removing any point of $\mathbb{R}$ leaves $2$. By Theorem 4.12(1) no homeomorphism exists.
⚠️ Counterexamples and pitfalls
  1. Not every "distance" is a metric. $(x-y)^2$ fails the triangle inequality and $|x^2-y^2|$ fails (M1) on $\mathbb{R}$; $\sqrt{|x-y|}$, $\min\{|x-y|,1\}$ and $\frac{|x-y|}{1+|x-y|}$ are metrics.
  2. The closure of an open ball need not be the closed ball. Discrete metric: $\overline{B(a,1)}=\{a\}$, $\overline B(a,1)=X$.
  3. Completeness is not a topological property. $(0,1)\cong\mathbb{R}$; $\mathbb{N}$ with $|\frac1m-\frac1n|$ has the discrete topology but is not complete; $\mathbb{R}$ with $|\arctan x-\arctan y|$ is not complete.
  4. The same set can be complete for one metric and not another: $C[0,1]$ is complete for $d_\infty$, not for $d_1$; $(0,1]$ is complete for $|\frac1x-\frac1y|$.
  5. Contraction needs completeness: $x\mapsto\frac x2$ on $(0,1]$ has no fixed point. Contractive is not contraction: $x+\frac1x$ on $[1,\infty)$ has no fixed point.
  6. Being a contraction depends on the metric; the fixed point does not. $A=\begin{pmatrix}0.5&0.6\\0&0.3\end{pmatrix}$ is a contraction for $d_1$ (column sums) but not for $d_\infty$ (row sums). The contraction constant from a crude estimate may be far from sharp (Example 4).
  7. Nested closed sets can have empty intersection: $[n,\infty)$ (diameters do not shrink); $(0,\frac1n]$ in $(0,1]$ (not complete).
  8. Closed and bounded $\not\Rightarrow$ compact outside $\mathbb{R}^n$: an infinite discrete space, the unit ball of $\ell^2$, of $c_0$ or of $C[0,1]$.
  9. Continuous images of closed sets need not be closed ($\arctan(\mathbb{R})=(-\frac\pi2,\frac\pi2)$; the projection of $\{xy=1\}$ to the $x$-axis is $\mathbb{R}\setminus\{0\}$), and preimages of compact sets need not be compact (a constant map on $\mathbb{R}$). Only images of compact sets are guaranteed compact.
  10. A continuous bijection need not be a homeomorphism unless the domain is compact: $[0,2\pi)\to S^1$.
  11. Disjoint closed sets can be at distance $0$: $\{xy=1\}$ and the $x$-axis. One of them compact forces a positive distance.
  12. Connected $\not\Rightarrow$ path-connected: the topologist's sine curve. For open subsets of $\mathbb{R}^n$ the two notions agree.
  13. Unions and intersections. Two disjoint connected sets can have a connected union ($[0,1)$ and $[1,2]$), two connected sets with a common point always do, but the intersection of two connected sets can be disconnected (two arcs of a circle meeting at both ends).
  14. Removing a point is a powerful invariant — but only for homeomorphisms. $[0,1)$ and $(0,1)$ are not homeomorphic, yet each is a continuous image of the other: $x\mapsto|2x-1|$ maps $(0,1)$ onto $[0,1)$, and $x\mapsto\frac12+\frac x2\sin\frac1{1-x}$ maps $[0,1)$ onto $(0,1)$.
📚 Go deeper — full proofs in the CSIR NET course
  • CSIR Unit 1 · §7.1 Metric Spaces and Completeness — Young, Hölder and Minkowski inequalities, interior and closure in full, four descriptions of continuity, comparison of metrics, the completion of a metric space, and the Baire category theorem with its consequences.
  • CSIR Unit 1 · §7.2 Compactness in Metric Spaces — the finite intersection property, the Lebesgue number lemma, the complete proof that compact, sequentially compact and complete-plus-totally-bounded agree, the Hilbert cube, and Edelstein's theorem.
  • CSIR Unit 1 · §7.3 Connectedness — four equivalent forms of connectedness, the topologist's sine curve in detail, the connectedness of $GL_n(\mathbb{C})$, $SO(n)$ and $GL_n^+(\mathbb{R})$, components and path components, totally disconnected sets (the Cantor set) and the structure of open subsets of $\mathbb{R}$.

Two Labs

Interactive 1 — Fixed-Point Iteration and the Contraction Bounds

The cobweb diagram of $x_{n+1}=g(x_n)$: go up to the graph of $g$ (black), across to the diagonal $y=x$ (grey), up again… The green square is a set that $g$ maps into itself. Choose a map and a starting point and press Play. The readouts compare the true error $|x_n-x^*|$ with the a posteriori bound $\frac{k}{1-k}|x_n-x_{n-1}|$ of Theorem 4.6 — when there is a contraction constant $k$ at all. The last three maps break one hypothesis each.

n, xₙ—
|xₙ − xₙ₋₁|—
bound k/(1−k)·step—
true error |xₙ − x*|—
Interactive 2 — One Space, Two Metrics: $d_1$ and $d_\infty$ on $C[0,1]$

The red curve is $f_n$ and the blue curve is $f_{2n}$. The purple area between them is $d_1(f_n,f_{2n})$; the amber segment is the largest vertical gap $d_\infty(f_n,f_{2n})$. The dashed green graph is the candidate limit. Drag $n$ or press Play: when does the area shrink while the gap stays put, and is the limit still in $C[0,1]$?

n—
d₁(fₙ, f₂ₙ)—
d∞(fₙ, f₂ₙ)—
d₁(fₙ, limit)—

Exercises

I
Metrics, open and closed sets, continuity.
  • 1 Show that $d(x,y)=\dfrac{|x-y|}{1+|x-y|}$ is a metric on $\mathbb{R}$. Is $\mathbb{R}$ bounded for $d$? Does $d$ have the same convergent sequences as $|x-y|$? Is $(\mathbb{R},d)$ complete?
  • 2 Which of the following are metrics on $\mathbb{R}$: (a) $|x^3-y^3|$; (b) $|x-y|^2$; (c) $\min\{|x-y|,1\}$; (d) $|\sin(x-y)|$?
  • 3 Find $d_1$, $d_2$ and $d_\infty$ between $(1,2)$ and $(4,-2)$ in $\mathbb{R}^2$, and describe the open unit ball and the unit sphere of $d_\infty$.
  • 4 Find the interior, closure and boundary of $\mathbb{Q}$ in $\mathbb{R}$, and of $A=\{(x,y):0\lt x^2+y^2\le1\}$ in $\mathbb{R}^2$.
  • 5 Let $X$ carry the discrete metric. Show that a sequence converges if and only if it is eventually constant, and that every map from $X$ to any metric space is continuous.
  • 6 In $Y=(0,1]\cup[2,3)$ with the usual metric, which of $(0,1]$, $[2,3)$, $(\frac12,1]$ are open in $Y$, and which are closed in $Y$?
  • 7 Show that every finite subset of a metric space is closed, and give a countable union of closed subsets of $\mathbb{R}$ that is not closed.
  • 8 Let $f,g:X\to Y$ be continuous. Show that $\{x:f(x)=g(x)\}$ is closed, and deduce that two continuous maps that agree on a dense set are equal.
  • 9 Prove that a connected metric space with at least two points is uncountable. (Hint: look at $x\mapsto d(a,x)$; this uses Theorem 4.11.)
1 (M1), (M2) are clear; (M3) holds because $\varphi(t)=\frac t{1+t}$ is increasing and subadditive: $\varphi(a+b)=\frac a{1+a+b}+\frac b{1+a+b}\le\varphi(a)+\varphi(b)$. $d\lt1$, so $\mathbb{R}$ is bounded. By Theorem 4.3(4) the convergent and the Cauchy sequences are the same as for $|x-y|$, so $(\mathbb{R},d)$ is complete — boundedness of the whole space does not prevent completeness.
2 (a) Yes: $x\mapsto x^3$ is injective. (b) No: $d(0,2)=4\gt1+1$. (c) Yes. (d) No: $|\sin(\pi-0)|=0$ with $\pi\ne0$.
3 The difference is $(3,-4)$: $d_1=7$, $d_2=5$, $d_\infty=4$. $B_\infty(0,1)$ is the open square $(-1,1)^2$; the unit sphere is the boundary of the square $\{\max(|x|,|y|)=1\}$.
4 $\mathbb{Q}^\circ=\varnothing$ (every interval contains irrationals), $\overline{\mathbb{Q}}=\mathbb{R}$, $\partial\mathbb{Q}=\mathbb{R}$. For $A$: interior $\{0\lt x^2+y^2\lt1\}$, closure the closed disc $\{x^2+y^2\le1\}$, boundary $\{x^2+y^2=1\}\cup\{(0,0)\}$.
5 $d(x_n,x)\lt1$ means $x_n=x$, so convergence means eventually constant. Every subset of $X$ is open, so every preimage of an open set is open (Theorem 4.2(1)).
6 $(0,1]=Y\cap(-1,1.5)=Y\cap[0,1]$ and $[2,3)=Y\cap(1.5,3)=Y\cap[2,3]$ are both open and closed in $Y$. $(\frac12,1]=Y\cap(\frac12,1.5)$ is open in $Y$ but not closed: $\frac12+\frac1n$ converges in $Y$ to $\frac12\notin(\frac12,1]$.
7 If $F=\{p_1,\dots,p_m\}$ and $x\notin F$, the ball $B(x,\min_id(x,p_i))$ misses $F$. $\bigcup_{n\ge1}[\frac1n,1]=(0,1]$ is a countable union of closed sets, not closed.
8 $h(x)=\rho(f(x),g(x))$ is continuous ($|\rho(a,b)-\rho(a',b')|\le\rho(a,a')+\rho(b,b')$), and $\{f=g\}=h^{-1}(\{0\})$ is closed. A closed set containing a dense set $D$ contains $\overline D=X$.
9 Pick $a\ne b$ and let $f(x)=d(a,x)$, a continuous real function. $f(X)$ is connected, so an interval, and it contains $0=f(a)$ and $f(b)\gt0$; hence $f(X)\supseteq[0,d(a,b)]$, which is uncountable, so $X$ is uncountable. (In particular $\mathbb{Q}$ and every countable metric space with two or more points are disconnected.)
II
Completeness and the contraction principle.
  • 1 Which are complete (usual metric unless stated): (a) $[0,\infty)$; (b) $\mathbb{Q}\cap[0,1]$; (c) $\{\frac1n:n\in\mathbb{N}\}\cup\{0\}$; (d) $\{\frac1n:n\in\mathbb{N}\}$; (e) $\mathbb{R}$ with $|e^x-e^y|$?
  • 2 Show that $f_n(x)=x^n$ is Cauchy in $(C[0,1],d_1)$ but not in $(C[0,1],d_\infty)$. Does it converge in $(C[0,1],d_1)$?
  • 3 Show that $g(x)=e^{-x}$ maps $[0.4,0.7]$ into itself and is a contraction there. Find its fixed point to three decimal places, and the number of iterations from $x_0=0.5$ that the a priori bound needs for an error below $10^{-6}$.
  • 4 Show that $g(x)=\frac1{1+x}$ is a contraction of $[\frac12,1]$, find its fixed point, and identify the iterates from $x_0=1$. Is $g$ a contraction of $[0,\infty)$? Is $g\circ g$? What follows?
  • 5 Show that $g(x)=\sqrt{2+x}$ is a contraction of $[0,\infty)$ and find its fixed point.
  • 6 Show that $(Tf)(x)=x+\frac12\int_0^1f(t)\,dt$ is a contraction of $(C[0,1],d_\infty)$ and find its fixed point.
  • 7 Let $(Tf)(x)=1+\int_0^xf(t)\,dt$ on $(C[0,1],d_\infty)$. Show that $T$ is not a contraction, but that $T^n$ has Lipschitz constant $\frac1{n!}$. What is the fixed point, and what are the iterates from $f_0=0$?
  • 8 Show that the system $x=\frac14(\sin x+\cos y)$, $y=\frac14(\cos x-\sin y)$ has exactly one solution in $\mathbb{R}^2$.
  • 9 $T$ is a contraction with constant $k=0.4$ of a complete space, and $d(x_0,Tx_0)=0.3$. Find a ball around $x_0$ that must contain the fixed point, and the least $n$ for which the a priori bound guarantees $d(x_n,x^*)\lt10^{-3}$.
  • 10 Modelling (input–output economics). Two industries, energy and manufacturing, need $A=\begin{pmatrix}0.2&0.3\\0.4&0.1\end{pmatrix}$ units of each other's output per unit produced (column $j$ = inputs used by industry $j$), and outside demand is $d=(10,20)$ million dollars. The production $x$ must satisfy $x=Ax+d$. Show that $x\mapsto Ax+d$ is a contraction for $d_1$, find $x$, and find how many iterations from $x_0=d$ the a priori bound needs for an error below $0.1$ million dollars in $d_1$.
1 (a) Yes, closed in $\mathbb{R}$. (b) No, not closed. (c) Yes, closed. (d) No: $(\frac1n)$ is Cauchy and its limit $0$ is missing. (e) No: isometric to $(0,\infty)$ via $e^x$; $x_n=-n$ is Cauchy without a limit.
2 $d_1(f_n,f_m)=\left|\frac1{n+1}-\frac1{m+1}\right|\to0$: Cauchy. $d_\infty(f_n,f_{2n})=\max_x(x^n-x^{2n})=\frac14$ (at $x^n=\frac12$): not Cauchy. It does converge in $d_1$ — to the zero function, since $d_1(f_n,0)=\frac1{n+1}$, although the pointwise limit is $1$ at $x=1$. Interactive 2 shows this.
3 $g$ is decreasing, $g(0.4)\approx0.6703$, $g(0.7)\approx0.4966$, so $g([0.4,0.7])\subseteq[0.4,0.7]$; $|g'|=e^{-x}\le e^{-0.4}\approx0.6703=k$. Fixed point $x^*\approx0.567$ (the solution of $xe^x=1$). $d(x_1,x_0)=e^{-0.5}-0.5\approx0.1065$; $\frac{k^n}{1-k}(0.1065)\lt10^{-6}$ needs $n\gt31.7$: $32$ iterations.
4 $g$ is decreasing with $g(\frac12)=\frac23$, $g(1)=\frac12$, so $g([\frac12,1])\subseteq[\frac12,1]$, and $|g'|=\frac1{(1+x)^2}\le\frac49$. Fixed point $x^2+x-1=0$: $x^*=\frac{\sqrt5-1}2\approx0.618$. From $x_0=1$: $1,\frac12,\frac23,\frac35,\frac58,\dots$ — ratios $F_n/F_{n+1}$ of consecutive Fibonacci numbers. On $[0,\infty)$, $|g'(0)|=1$ and $|g(x)-g(0)|/x=\frac1{1+x}\to1$ as $x\to0$, so $g$ is not a contraction; but $g(g(x))=\frac{1+x}{2+x}$ has derivative $\frac1{(2+x)^2}\le\frac14$, so $g\circ g$ is. By Theorem 4.7(2) the iterates converge to $x^*$ from every $x_0\ge0$.
5 $g$ maps $[0,\infty)$ into $[\sqrt2,\infty)$ and $|g'(x)|=\frac1{2\sqrt{2+x}}\le\frac1{2\sqrt2}\approx0.354$. Fixed point: $x^2=2+x$, $x\ge0$, so $x^*=2$.
6 $|(Tf-Tg)(x)|=\frac12\left|\int_0^1(f-g)\right|\le\frac12d_\infty(f,g)$. A fixed point is $f(x)=x+c$ with $c=\frac12\int_0^1(t+c)\,dt=\frac14+\frac c2$, so $c=\frac12$ and $f(x)=x+\frac12$.
7 For $f-g\equiv1$, $(Tf-Tg)(1)=1$, so the best constant is $1$. By induction $|(T^nf-T^ng)(x)|\le\frac{x^n}{n!}d_\infty(f,g)$, so $T^n$ has constant $\frac1{n!}$, and $T^2$ is already a contraction ($k=\frac12$). By Theorem 4.7(2) the unique fixed point is the solution of $f=1+\int_0^xf$, i.e. $f'=f$, $f(0)=1$: $f=e^x$. The iterates $0,\ 1,\ 1+x,\ 1+x+\frac{x^2}2,\dots$ are the Taylor polynomials of $e^x$ — the Picard iterates of §6.1.
8 For $T(x,y)$ the right side, the mean value theorem gives $|T_1(v)-T_1(w)|\le\frac14(|x-x'|+|y-y'|)\le\frac12d_\infty(v,w)$, and the same for $T_2$. So $T$ is a contraction of the complete space $(\mathbb{R}^2,d_\infty)$ with $k=\frac12$: exactly one solution (numerically $(0.3254,0.1897)$).
9 $d(x_0,x^*)\le\frac{d(x_0,x_1)}{1-k}=\frac{0.3}{0.6}=0.5$: the fixed point lies in $\overline B(x_0,0.5)$. $\frac{(0.4)^n}{0.6}(0.3)=0.5(0.4)^n\lt10^{-3}$ needs $(0.4)^n\lt0.002$, i.e. $n\gt6.78$: $n=7$ (check: $0.5\cdot0.4^6=0.002048$, $0.5\cdot0.4^7\approx0.00082$).
10 $\|Av\|_1\le(\max\text{column sum})\|v\|_1=0.6\|v\|_1$ (column sums $0.6$ and $0.4$: each industry spends less than a dollar of inputs per dollar of output). So $k=0.6$. $(I-A)x=d$ gives $x=\frac1{0.6}\begin{pmatrix}0.9&0.3\\0.4&0.8\end{pmatrix}\begin{pmatrix}10\\20\end{pmatrix}=(25,\ 33.\overline3)$ million dollars. $x_1=Ad+d=(18,26)$, $d_1(x_1,x_0)=14$; $\frac{0.6^n}{0.4}\cdot14\lt0.1$ needs $n\gt11.47$: $12$ iterations (in fact $9$ suffice).
III
Compactness.
  • 1 Which are compact: (a) $\{x^4+y^4\le1\}\subseteq\mathbb{R}^2$; (b) $\{x^2-y^2\le1\}$; (c) $\{x\in\ell^2:|x_n|\le2^{-n}\ \forall n\}$; (d) $\{A\in M_2(\mathbb{R}):\det A=1\}$; (e) $\{(x,\sin\frac1x):0\lt x\le1\}$; (f) $\{A\in M_2(\mathbb{R}):A^2=0,\ |a_{ij}|\le1\}$?
  • 2 Show directly from the definition (open covers) that $(0,1]$ is not compact.
  • 3 Show that the closed unit ball of $(C[0,1],d_\infty)$ is not compact.
  • 4 Let $K$ be compact and $f:K\to\mathbb{R}$ continuous with $f(x)\gt0$ for all $x$. Show $\inf_Kf\gt0$. Does this hold on $(0,1]$?
  • 5 Show that $x^2$ is uniformly continuous on $[0,10]$ but not on $\mathbb{R}$, and that $\frac1x$ is not uniformly continuous on $(0,1]$.
  • 6 Let $K\subseteq\mathbb{R}^n$ be compact and nonempty. Show that there are $p,q\in K$ with $\|p-q\|_2=\operatorname{diam}K$.
  • 7 Let $K$ be compact and $T:K\to K$ an isometry. Prove that $T$ is surjective. Is this true on $[0,\infty)$?
  • 8 Show that $T(x)=x-\frac{x^2}2$ maps $[0,1]$ into itself and is contractive but not a contraction. What does Theorem 4.10 say about its iterates?
  • 9 Let $f:\mathbb{R}\to\mathbb{R}$ be continuous with $f(x)\to0$ as $x\to\pm\infty$. Show that $f$ is bounded and uniformly continuous, and that it attains a maximum if $f$ takes some positive value.
1 (a) Yes: closed, and $|x|,|y|\le1$. (b) No: it contains the whole $y$-axis. (c) Yes: closed in $\ell^2$ and totally bounded exactly as for the Hilbert cube ($\sum_{n\gt N}4^{-n}\to0$). (d) No: $\operatorname{diag}(t,\frac1t)$ is unbounded. (e) No: not closed — $(\frac1{n\pi},0)\to(0,0)$, which is missing. (f) Yes: $A\mapsto A^2$ is continuous, so the set is closed, and it is bounded.
2 $U_n=(\frac1n,2)$ cover $(0,1]$, but any finite subfamily has union $(\frac1N,2)$, which misses $\frac1{2N}$.
3 Tents $t_k$ of height $1$ supported in $[\frac1{k+1},\frac1k]$ lie in the ball and satisfy $d_\infty(t_k,t_l)=1$ for $k\ne l$, so no subsequence is Cauchy and the ball is not sequentially compact.
4 $f$ attains its minimum at some $x_0\in K$ (Theorem 4.10(1)), and $\min f=f(x_0)\gt0$. On $(0,1]$, $f(x)=x$ is positive with infimum $0$.
5 On $[0,10]$, $|x^2-y^2|=|x+y|\,|x-y|\le20|x-y|$ (Lipschitz). On $\mathbb{R}$, $x_n=n+\frac1n$ and $y_n=n$ are closer and closer, but $x_n^2-y_n^2=2+\frac1{n^2}\gt2$. For $\frac1x$: $x_n=\frac1n$, $y_n=\frac1{n+1}$ have $|x_n-y_n|\to0$ and $|\frac1{x_n}-\frac1{y_n}|=1$. Heine's theorem does not apply because $\mathbb{R}$ and $(0,1]$ are not compact.
6 $(p,q)\mapsto\|p-q\|_2$ is continuous on $K\times K$, which is closed and bounded in $\mathbb{R}^{2n}$, hence compact; it attains its maximum, which is $\operatorname{diam}K$.
7 $T(K)$ is compact, hence closed. If $y\notin T(K)$, then $\varepsilon=d(y,T(K))\gt0$. For $n\gt m$, $d(T^ny,T^my)=d(T^{n-m}y,y)\ge\varepsilon$ because $T^{n-m}y\in T(K)$. So $(T^ny)$ has no Cauchy subsequence, contradicting sequential compactness. On $[0,\infty)$, $x\mapsto x+1$ is an isometry that misses $[0,1)$.
8 $T$ is increasing on $[0,1]$ ($T'=1-x\ge0$) with $T(0)=0$, $T(1)=\frac12$. $|Tx-Ty|=|x-y|\,|1-\frac{x+y}2|\lt|x-y|$ for $x\ne y$ (as $0\lt x+y\le2$, with equality $x+y=2$ only if $x=y=1$), but the factor tends to $1$ as $x,y\to0$. $[0,1]$ is compact, so by Edelstein's theorem the unique fixed point $0$ attracts all iterates (slowly: $x_n\approx\frac2n$).
9 Choose $M$ with $|f|\lt1$ outside $[-M,M]$; on $[-M,M]$, $f$ is bounded, so $f$ is bounded. For uniform continuity, given $\varepsilon$ choose $M$ with $|f|\lt\frac\varepsilon2$ outside $[-M,M]$ and use Heine on $[-M-1,M+1]$ with $\delta\le1$: two points within $\delta$ either both lie in $[-M-1,M+1]$ or both lie outside $[-M,M]$. If $f(x_1)=c\gt0$, take $M$ with $|f|\lt c$ outside $[-M,M]$; the maximum of $f$ on $[-M,M]$ is at least $c$ and is the global maximum.
IV
Connectedness.
  • 1 Find the number of components of (a) $\{(x,y):(x^2+y^2-1)(x^2+y^2-4)\ge0\}$; (b) $\{x\in\mathbb{R}:\sin x\ne0\}$; (c) $\mathbb{R}^2\setminus\{xy=1\}$.
  • 2 Prove that every continuous $f:[0,1]\to[0,1]$ has a fixed point. Is the same true for continuous $f:(0,1)\to(0,1)$?
  • 3 Is there a continuous surjection $[0,1]\to(0,1)$? $[0,1]\to\mathbb{R}$? $(0,1)\to[0,1]$?
  • 4 Show that $[0,1)$ is not homeomorphic to $(0,1)$, and that $\mathbb{R}$ is not homeomorphic to $[0,\infty)$.
  • 5 Show that the letter $\mathsf T=([-1,1]\times\{0\})\cup(\{0\}\times[-1,0])$ is not homeomorphic to $[0,1]$.
  • 6 Show that $O(2)$ is not connected and describe its components.
  • 7 Prove that if $A,B$ are connected and $A\cap B\ne\varnothing$, then $A\cup B$ is connected. Give connected $A,B$ with $A\cap B=\varnothing$ and $A\cup B$ connected.
  • 8 Show that the singular $n\times n$ real matrices form a connected subset of $M_n(\mathbb{R})$, while the invertible ones do not.
  • 9 Show that the graph $\{(x,\sin\frac1x):x\gt0\}$ is connected and find its closure in $\mathbb{R}^2$. Is the closure path-connected?
1 (a) The product is $\ge0$ when $r^2\le1$ or $r^2\ge4$ ($r^2=x^2+y^2$): a closed disc and the outside of a circle, $2$ components (a path from one to the other would pass through $1\lt r\lt2$ by the IVT applied to $r$). (b) The open intervals $(k\pi,(k+1)\pi)$, $k\in\mathbb{Z}$: countably infinitely many. (c) $3$: the region $xy\lt1$ (star-shaped about the origin, since $t^2xy\lt1$ for $0\le t\le1$), and the two regions $xy\gt1$ with $x\gt0$ or $x\lt0$ (each convex on its side).
2 $h(x)=f(x)-x$ is continuous with $h(0)=f(0)\ge0$ and $h(1)=f(1)-1\le0$; by the IVT $h$ vanishes somewhere. For $(0,1)$: no — $f(x)=\frac x2$ has no fixed point in $(0,1)$.
3 No and no: the image of the compact $[0,1]$ is compact, and $(0,1)$ and $\mathbb{R}$ are not. Yes for the third: $x\mapsto\frac12(1+\sin2\pi x)$ maps $(0,1)$ onto $[0,1]$ (the values $1$ and $0$ are taken at $x=\frac14$ and $\frac34$).
4 Removing $0$ leaves $(0,1)$ connected; removing any point of $(0,1)$ disconnects it. Likewise $[0,\infty)\setminus\{0\}$ is connected, while $\mathbb{R}$ minus any point is not (Theorem 4.12(1)).
5 Removing the junction point $(0,0)$ leaves $3$ components; removing a point of $[0,1]$ leaves at most $2$.
6 $\det:O(2)\to\{1,-1\}$ is continuous and onto, so $O(2)$ is disconnected. The components are $SO(2)$ (rotations $R_\theta$, the image of the circle under $\theta\mapsto R_\theta$) and the reflections $R_\theta\operatorname{diag}(1,-1)$, each connected.
7 Theorem 4.11(5) with the common point. Example: $A=[0,1)$, $B=[1,2]$, union $[0,2]$.
8 If $A$ is singular, $tA$ is singular for $t\in[0,1]$, so every singular matrix is joined to $0$ by a path of singular matrices: path-connected. The invertible matrices are separated by the sign of $\det$ (Theorem 4.12(4)).
9 The graph is the continuous image of the interval $(0,\infty)$, hence connected. Its closure adds the segment $\{0\}\times[-1,1]$ (every $y\in[-1,1]$ equals $\sin\frac1x$ for arbitrarily small $x$). The closure is connected (Theorem 4.11(5)) but not path-connected, by the argument for the topologist's sine curve.
🎯 GATE corner GATE MA · MCQGATE MA · MSQGATE MA · NAT

E1. GATE MA · MCQ Which one of the following metric spaces is complete? (A) $[1,\infty)$ with $d(x,y)=\left|\frac1x-\frac1y\right|$; (B) $\mathbb{Z}$ with $d(m,n)=|e^m-e^n|$; (C) $\mathbb{R}$ with $d(x,y)=|x^3-y^3|$; (D) $\{\frac1n:n\in\mathbb{N}\}$ with $d(x,y)=|x-y|$.

Idea Each metric is $|\varphi(x)-\varphi(y)|$ for an injective $\varphi$, so the space is isometric to $\varphi(X)\subseteq\mathbb{R}$ with the usual metric, and it is complete exactly when $\varphi(X)$ is closed in $\mathbb{R}$ (Theorem 4.4(2)).
Options (A) $\varphi(x)=\frac1x$ maps $[1,\infty)$ onto $(0,1]$, not closed ($x_n=n$ is Cauchy, no limit). (B) $\{e^n:n\in\mathbb{Z}\}$ has the limit point $0$ ($e^{-n}\to0$), which is missing. (C) $x\mapsto x^3$ maps $\mathbb{R}$ onto $\mathbb{R}$: complete. (D) $\{\frac1n\}$ misses its limit point $0$.
Answer (C).

E2. GATE MA · MCQ Let $T:[1,\infty)\to[1,\infty)$, $T(x)=\dfrac{x+3}{x+1}$. Then (A) $T$ has no fixed point in $[1,\infty)$; (B) $T$ has a unique fixed point, and $T^nx_0$ converges to it for every $x_0\ge1$; (C) $T$ has two fixed points in $[1,\infty)$; (D) $T$ has a unique fixed point, but $T^nx_0$ diverges for some $x_0\ge1$.

Into itself $T(x)=1+\frac2{x+1}\in(1,2]$ for $x\ge1$.
Contraction $T'(x)=-\frac2{(x+1)^2}$, so $|T'|\le\frac24=\frac12$ on $[1,\infty)$, a closed (complete) set. By Theorem 4.7(1), a unique fixed point attracting every orbit.
Answer (B). The fixed point solves $x(x+1)=x+3$, $x^2=3$: $x^*=\sqrt3$ (the root $-\sqrt3$ is outside the domain, which rules out (C)).

E3. GATE MA · MSQ Which of the following subsets of $\mathbb{R}^2$ is/are compact? (One or more options may be correct.) (A) $\{(x,y):e^x+e^y\le2\}$; (B) $\{(x,y):x^2y^2\le1,\ x^2+y^2\le5\}$; (C) $\{(x,y):\sin(x^2+y^2)=0,\ x^2+y^2\le10\}$; (D) $\{(x,y):0\lt x^2+y^2\le1\}$.

(A) No Closed but unbounded: $(-t,0)$ satisfies $e^{-t}+1\le2$ for all $t\ge0$.
(B) Yes An intersection of two closed sets (preimages of closed sets under continuous functions), inside the disc of radius $\sqrt5$. Heine–Borel.
(C) Yes Closed (preimage of $\{0\}$ intersected with a closed disc) and bounded. It is the origin together with the circles $x^2+y^2=\pi,2\pi,3\pi$ ($3\pi\approx9.42\le10$).
(D) No Bounded but not closed: $(\frac1n,0)\to(0,0)\notin$ the set.
Answer (B) and (C).

E4. GATE MA · MSQ Which of the following is/are connected? (One or more options may be correct.) (A) $GL_2(\mathbb{R})$, the invertible real $2\times2$ matrices, as a subset of $\mathbb{R}^4$; (B) the hyperbola $\{(x,y):x^2-y^2=1\}$; (C) $\mathbb{R}^2$ with finitely many points removed; (D) $SO(2)=\{A\in M_2(\mathbb{R}):A^{\mathsf T}A=I,\ \det A=1\}$.

(A) No $\det$ maps it continuously onto $\mathbb{R}\setminus\{0\}$, which is disconnected.
(B) No It lies in $\{x\ge1\}\cup\{x\le-1\}$ and meets both; $\{x\gt0\}$ and $\{x\lt0\}$ separate it.
(C) Yes It is even path-connected (Example 7(b): a countable set may be removed).
(D) Yes $SO(2)=\left\{\begin{pmatrix}\cos\theta&-\sin\theta\\\sin\theta&\cos\theta\end{pmatrix}\right\}$ is a continuous image of $[0,2\pi]$.
Answer (C) and (D).

E5. GATE MA · NAT Let $T:C[0,1]\to C[0,1]$, $(Tf)(x)=x^2+\dfrac12\displaystyle\int_0^1x\,f(t)\,dt$, with the sup metric. $T$ has a unique fixed point $f^*$. The value $f^*(1)$, correct to two decimal places, is ______.

Why unique $|(Tf-Tg)(x)|\le\frac12x\int_0^1|f-g|\le\frac12d_\infty(f,g)$: a contraction of a complete space.
Solve $f^*(x)=x^2+\frac c2x$ with $c=\int_0^1f^*=\frac13+\frac c4$, so $\frac34c=\frac13$, $c=\frac49$ and $f^*(x)=x^2+\frac29x$.
Answer $f^*(1)=\frac{11}9\approx1.22$ (accept $1.21$ to $1.23$).

E6. GATE MA · NAT The number of connected components of $\{(x,y)\in\mathbb{R}^2:(x^2-1)(y^2-4)\ne0\}$ is ______.

Idea The set is the plane minus the four lines $x=\pm1$, $y=\pm2$.
Count The vertical lines cut the $x$-direction into $3$ open intervals and the horizontal lines cut the $y$-direction into $3$; the set is the union of the $3\times3$ open rectangles (some unbounded) $I\times J$. Each is convex, hence connected, and no path joins two of them (along the path, $x^2-1$ or $y^2-4$ would change sign and so vanish, by the IVT).
Answer $9$ (an integer; accept exactly $9$).
🧑‍🏫 For the teacher

Suggested plan — 3 lectures × 60 min.

  1. Metrics and completeness. Definitions 4.1–4.4 with the standard examples; Theorem 4.1(3) (closed = contains its limits) and Theorem 4.3 with the tent functions on the board. Example 1 as a class vote. Then Definition 4.5, Theorem 4.4 — prove that $(C[a,b],d_\infty)$ is complete and $(C[0,1],d_1)$ is not, projecting Interactive 2 (ramps and tents) — and Example 2.
  2. The contraction principle. Theorem 4.6 with the complete proof and both error bounds, Theorem 4.7 and the strategy box. Project Interactive 1: run $\cos x$, then the three failing maps, and ask which hypothesis each one breaks. Examples 3 and 4; mention the Picard iteration (§6.1) and the implicit function theorem (§1.1). GATE corner E2 and E5.
  3. Compactness and connectedness. Definition 4.7, Theorem 4.8 (do (2)⇒(3) and the Lebesgue number lemma in full, sketch the rest), Theorems 4.9 and 4.10 with Example 6. Then Definition 4.8, Theorem 4.11(2) with its proof, the topologist's sine curve, Theorem 4.12 and Example 7. Finish with E3, E4 and E6 under a timer.

Discussion questions. (1) $(0,1)$ and $\mathbb{R}$ are homeomorphic but only one is complete. Which properties in this section are preserved by homeomorphisms (open sets, compactness, connectedness) and which are not (completeness, boundedness, being a contraction)? (2) In Example 4 the sup-metric estimate gives $|\lambda|\lt2$ but the iteration converges for $|\lambda|\lt3$. Can you find a metric on $C[0,1]$ in which $T$ is a contraction for every $|\lambda|\lt3$? (3) Why does the proof of Edelstein's theorem need compactness exactly once, and where does $x+\frac1x$ on $[1,\infty)$ escape?

Misconceptions to watch for. "Closed and bounded means compact" in every metric space; "contractive means contraction"; forgetting to check that the map sends the set into itself before applying the contraction principle; treating completeness as a property of the set rather than of the metric; confusing "not open" with "closed"; assuming connected sets are path-connected; using the a priori bound as a prediction of the actual number of iterations.

Suggested homework. I(2, 4, 6, 9), II(1, 3, 4, 7, 9, 10), III(1, 2, 5, 7, 8), IV(1, 3, 5, 8); GATE corner E1, E3, E6.

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

Research question. A web search engine ranks pages by the "PageRank" vector, the fixed point of a map built from the link structure of the web. Why does the computation always converge, and what decides how fast?

Why it matters. Ranking by fixed points is used far beyond web search: for citation networks, protein-interaction networks, road and airline networks and recommendation systems. With $N$ pages, let $P$ be the $N\times N$ matrix with $P_{ij}=\frac1{\text{(number of links out of }j)}$ if page $j$ links to page $i$ (and $P_{ij}=\frac1N$ for all $i$ if page $j$ has no links). The ranking is the fixed point of $G(x)=\alpha Px+\frac{1-\alpha}N\mathbf{1}$ on the set $\Delta$ of probability vectors, where $\alpha\in(0,1)$ is the "damping factor" (classically $\alpha=0.85$): a random surfer follows a link with probability $\alpha$ and jumps to a random page otherwise.

What to do.

  1. Show that $P$ has non-negative entries and column sums $1$, and deduce $\|Pv\|_1\le\|v\|_1$. Conclude that $G$ maps $\Delta$ into itself and is a contraction of $(\Delta,d_1)$ with constant $\alpha$. Why is $\Delta$ complete?
  2. Draw a small web of $6$ pages with at least one page without outgoing links, write $P$, and compute the iterates $x_{n+1}=G(x_n)$ from $x_0=\frac1N\mathbf{1}$ until $d_1(x_{n+1},x_n)\lt10^{-8}$. Report the ranking.
  3. Compare the number of iterations with the a priori bound of Theorem 4.6 and with the a posteriori bound. Repeat for $\alpha=0.5,\ 0.85,\ 0.99$ and plot the number of iterations against $\alpha$.
  4. For $\alpha$ close to $1$ the convergence slows down. Explain this with the a priori bound, and find an example web in which the ranking changes dramatically between $\alpha=0.85$ and $\alpha=0.99$.

Tools: pen and paper for step 1; Python (numpy) or a spreadsheet for steps 2–4.

Hand in: the contraction proof; your web graph, matrix and ranking; a table and plot of iteration counts and both bounds; one paragraph on the role of $\alpha$.

Going further. The fixed point is the eigenvector of the "Google matrix" $\alpha P+\frac{1-\alpha}N\mathbf{1}\mathbf{1}^{\mathsf T}$ for the eigenvalue $1$, and the iteration is the power method; its second eigenvalue has modulus at most $\alpha$. Read about the Perron–Frobenius theorem for positive matrices, which explains why the fixed point has all entries positive.

Instructor note: for $x,y\in\Delta$, $G(x)-G(y)=\alpha P(x-y)$ and $\|Pv\|_1\le\sum_j|v_j|\sum_iP_{ij}=\|v\|_1$, so the contraction constant is $\alpha$; $\Delta$ is closed in $\mathbb{R}^N$, hence complete. The a priori bound $\frac{\alpha^n}{1-\alpha}d_1(x_1,x_0)$ predicts about $\log(10^{-8})/\log\alpha\approx113$ iterations for $\alpha=0.85$, roughly $27$ for $\alpha=0.5$ and over $1800$ for $\alpha=0.99$; on small graphs the actual counts are usually smaller. The handling of pages without links ("dangling nodes") is what keeps $P$ column-stochastic — a good point for discussion.

🧪 Self-check quiz

0/5 correct

Q1. Which of the following is not a metric on $\mathbb{R}$?

Q2. Which of these metric spaces is complete?

Q3. $T$ is a contraction with constant $k=\frac12$ on a complete space and $d(x_0,x_1)=1$. The a priori bound of Theorem 4.6 for $d(x_3,x^*)$ is

Q4. The closed unit ball $\{x\in\ell^2:\|x\|_2\le1\}$ is

Q5. The least constant $k$ with $\|T(v)-T(w)\|_1\le k\|v-w\|_1$ for $T(x,y)=\big(\frac{x+y}3,\frac{x-y}4\big)$ is