4.1 Metric and normed spaces; open and closed sets

Every ε-proof of Unit 1 used the distance |x − y| through only four properties. Any rule of distance with those four properties gives a metric space, and then open balls, open and closed sets, interior, closure and boundary make sense for vectors, functions and bit strings with the same proofs.

In 1.2 and 1.3 every proof about closeness used the number $|x - y|$ in a very small number of ways. It is never negative. It is zero only when $x = y$ . It is the same from $x$ to $y$ as from $y$ to $x$ . And it obeys the triangle inequality. Nothing else about the real line entered the proofs: no addition, no multiplication, no order. So any rule that measures distance and has those four properties can be put in the place of $|x - y|$ , and the same $\varepsilon$ games still work. That is a metric space. It lets us ask how close two vectors are, how close two functions are (“is $\sin x$ close to $x - \frac{x^3}{6}$ on $[0, 1]$ ?”) and how close two bit strings are, with one theory. This chapter builds the words of that theory: balls, open sets, closed sets, interior, closure, boundary. Chapter 4.2 adds convergence and completeness.

Before you start

1.2: the triangle inequality. 2.9: the norm of a vector and its properties. 0.3: unions, intersections and complements of sets, and De Morgan’s laws.

Quick checkA traveller on the number line goes from

a

c

, either directly or by way of a stop at

b

. Which statement is always true?

Quick checkFor the norm

\lVert x \rVert = \sqrt{(x, x)}

of 2.9 and a real number

c

, what is

\lVert cx \rVert

Quick checkWhat is the complement of

A \cup B

The picture: who counts as close?

On the plane there is more than one sensible way to measure how far a point is from the centre. Walking along city blocks costs $|x_1| + |x_2|$ . A straight line costs $\sqrt{x_1^2 + x_2^2}$ . A chess king moves one square in any of eight directions, so reaching $(x_1, x_2)$ takes $\max(|x_1|, |x_2|)$ moves. The set of points within distance $r$ of the centre is a diamond, a disc or a square. Three things to do in the picture:

Put $x$ on an axis. All three distances agree, because only one coordinate is non-zero.
Put $x$ near a corner of the square, such as $(0.9, 0.9)$ with $r = 1$ . It is inside the square, outside the disc and far outside the diamond. The three rules disagree about whether $x$ is “close”.
Slide $r$ and watch the nesting. The diamond stays inside the disc and the disc stays inside the square. Later we prove why, and use it to show that the three rules still agree about which sets are open.

Point $x$	$d_1 = \lvert x_1 \rvert + \lvert x_2 \rvert$	$d_2 = \sqrt{x_1^2 + x_2^2}$	$d_\infty = \max(\lvert x_1 \rvert, \lvert x_2 \rvert)$
$(3, 4)$	$7$	$5$	$4$
$(1, 1)$	$2$	$\sqrt 2 \approx 1.41$	$1$
$(5, 0)$	$5$	$5$	$5$

Where this came from· Fréchet and Hausdorff: one theory of closeness

Before 1900, “distance” meant distance on a line, in the plane or in space. Around 1900 analysts began to study sets of functions and had to say when one function is close to another, for example when a sequence of curves settles down to a limit curve. Maurice Fréchet’s doctoral thesis of 1906, Sur quelques points du calcul fonctionnel, listed the few properties of distance that the convergence proofs actually use, and studied any set that carries a distance with those properties. The name “metric space” (metrischer Raum) comes from Felix Hausdorff’s book Grundzüge der Mengenlehre (1914). The book also set out spaces defined only by which sets count as open, with no distance at all. That is the start of topology, the subject of MATH 551. The problem both men solved was to write the theory of closeness once, and have it serve numbers, vectors and functions.

The idea, in words

A distance on a set is a rule that gives every two points a number. It earns the name if it has four properties, and each property is there for a reason.

Why· Why exactly these four properties

Never negative. Distances are lengths.
Zero only for equal points. Then “the distance between $x$ and $y$ is smaller than every $\varepsilon > 0$ ” proves $x = y$ . This is the last step of the uniqueness-of-limits proof in 1.2.
Symmetric. ” $x$ is close to $y$ ” and ” $y$ is close to $x$ ” are the same statement, so a ball around $x$ and a ball around $y$ can be compared.
Triangle inequality. You can reach $z$ from $x$ by way of $y$ without saving distance. This is the property that lets you split a distance into two pieces and give each half of the budget $\varepsilon$ (the $\frac\varepsilon2$ trick). Without it, “close to something close” would not be “close”.

Notice what is not demanded: you need not be able to add points, multiply them, or order them. Bit strings and cities have distances but no sum.

A normed space adds structure: the points are vectors, and the distance comes from a length of vectors. Every normed space is a metric space, but not the other way round.

Definitions and theorems

Definition B

Metric space

A metric space is a set $X$ together with a function $d$ that gives a real number $d(x, y)$ for every pair of points $x, y \in X$ , such that for all $x, y, z \in X$ :

(M1) $d(x, y) \ge 0$ , and $d(x, y) = 0$ if and only if $x = y$ .
(M2) $d(x, y) = d(y, x)$ .
(M3) $d(x, z) \le d(x, y) + d(y, z)$ (the triangle inequality).

The function $d$ is the metric or distance. The elements of $X$ are called points, whatever they really are.

In one lineA set $X$ with a distance $d(x, y)$ for each pair of points, never negative, zero only for equal points, symmetric, and obeying the triangle inequality.

Why it existsIt keeps from $|x - y|$ exactly what the $\varepsilon$ -proofs of Unit 1 used, so those proofs work for vectors, functions and bit strings.

The real line with $d(x, y) = |x - y|$ is a metric space: (M1) and (M2) are properties of absolute value, and (M3) is the triangle inequality of 1.2 in the form $|x - z| \le |x - y| + |y - z|$ .

Quick checkOn

\mathbb R

define

d(x, y) = |x^2 - y^2|

. Which axiom fails?

Worked example

Show that

d(x, y) = (x - y)^2

is not a metric on

\mathbb R

Solution. To show a rule is not a metric, we find one violated axiom and one instance where it fails.

Check (M1) and (M2). $(x - y)^2 \ge 0$ with equality iff $x = y$ , and $(x - y)^2 = (y - x)^2$ . The first two axioms hold, so the failure, if any, is in the triangle inequality.
Look for a triangle that fails. Take $x = 0$ , $y = 1$ , $z = 2$ . Then $d(0, 2) = 4$ , while $d(0, 1) + d(1, 2) = 1 + 1 = 2$ . Squaring makes large gaps count much more than small ones, so the stop at $y = 1$ makes the journey “cheaper” than the direct trip. That is the opposite of the triangle inequality.
Conclude. $4 \le 2$ is false, so (M3) fails.

Answer. $(x - y)^2$ is not a metric. Its square root, $|x - y|$ , is. $\blacksquare$

Worked example

Prove the reverse triangle inequality in a metric space:

|d(x, z) - d(y, z)| \le d(x, y)

Solution. An absolute value $|a| \le c$ means two things at once, $a \le c$ and $-a \le c$ . So we prove both.

First half. (M3) gives $d(x, z) \le d(x, y) + d(y, z)$ . Subtract $d(y, z)$ : $d(x, z) - d(y, z) \le d(x, y)$ . The detour through $y$ is never shorter than the direct trip, so moving the term across is the same statement.
Second half. Swap the roles of $x$ and $y$ : $d(y, z) - d(x, z) \le d(y, x) = d(x, y)$ . The first half holds for any two points, so it holds with $x$ and $y$ exchanged. (M2) turns $d(y, x)$ into $d(x, y)$ .
Combine. Both $d(x, z) - d(y, z)$ and its negative are at most $d(x, y)$ . That is exactly what $|d(x, z) - d(y, z)| \le d(x, y)$ means.

Answer. The inequality holds. In words: if $x$ and $y$ are within $\varepsilon$ of each other, their distances to any third point differ by at most $\varepsilon$ . So the distance function is continuous. In a normed space, taking $z = O$ gives $\big|\,\lVert x \rVert - \lVert y \rVert\,\big| \le \lVert x - y \rVert$ . $\blacksquare$

Definition B

Normed space

A normed space is a vector space $V$ with a function $\lVert \cdot \rVert$ that gives a real number $\lVert x \rVert$ for each $x \in V$ , such that for all $x, y \in V$ and every real $c$ :

(N1) $\lVert x \rVert \ge 0$ , and $\lVert x \rVert = 0$ if and only if $x = O$ .
(N2) $\lVert cx \rVert = |c|\,\lVert x \rVert$ .
(N3) $\lVert x + y \rVert \le \lVert x \rVert + \lVert y \rVert$ .

The function is a norm. In 2.9 the norm $\sqrt{(x, x)}$ came from an inner product, and the theorem “Properties of the norm” proved (N1) to (N3) for it. Here we turn those three properties into the definition, so norms need not come from inner products.

In one lineA vector space with a length $\lVert x \rVert$ for every vector that is never negative, zero only for $O$ , scales by $\lvert c \rvert$ , and obeys the triangle inequality.

Why it existsIt is the setting where distance and the vector operations fit together, so that distance is unchanged by sliding and scales by $|c|$ under stretching.

Theorem B Abbott Sec. 3.1; Rudin ch. 2

A norm gives a metric

Let $V$ be a normed space. Then $d(x, y) = \lVert x - y \rVert$ satisfies (M1), (M2) and (M3).

In one lineIf $\lVert \cdot \rVert$ is a norm on $V$ , then $d(x, y) = \lVert x - y \rVert$ is a metric on $V$ .

Why it is trueEach metric axiom is one norm axiom applied to $x - y$ ; the triangle inequality comes from splitting $x - z$ as $(x - y) + (y - z)$ .

Proofstandard

The idea: Translate each axiom: M1 is N1 for the vector x − y, M2 is N2 with c = −1, M3 is N3 for the two vectors x − y and y − z, which add to x − z.

(M1)

d(x, y) = \lVert x - y \rVert \ge 0

, and it is

0

iff

x - y = O

, that is, iff

x = y

(N1) applied to the vector

x - y

. Also

x - y = O

exactly when

x = y

(M2)

d(y, x) = \lVert y - x \rVert = \lVert -(x - y) \rVert = \lVert x - y \rVert = d(x, y)

(N2) with

c = -1

\lVert -v \rVert = |-1|\,\lVert v \rVert = \lVert v \rVert

(M3)

d(x, z) = \lVert (x - y) + (y - z) \rVert \le \lVert x - y \rVert + \lVert y - z \rVert = d(x, y) + d(y, z)

\blacksquare

Write

x - z

as the sum of the two vectors

x - y

and

y - z

, then use (N3).Where the idea comes from: a detour through y is the same as adding two displacement vectors.

Now the standard examples. For $x = (x_1, \dots, x_n)$ in $\mathbb R^n$ define three lengths:

\lVert x \rVert_1 = |x_1| + \dots + |x_n|, \qquad \lVert x \rVert_2 = \sqrt{x_1^2 + \dots + x_n^2}, \qquad \lVert x \rVert_\infty = \max(|x_1|, \dots, |x_n|).

Also, on the vector space $C[a, b]$ of continuous functions on $[a, b]$ (an example of 2.1), define the sup norm $\lVert f \rVert_\infty = \max_{a \le x \le b} |f(x)|$ . The maximum exists because a continuous function on $[a, b]$ attains its maximum, by the extreme value theorem of 1.3, and $|f|$ is continuous.

Theorem B Rudin ch. 2 and ch. 7; Apostol Vol. 2 ch. 1

The standard norms are norms

(a) $\lVert \cdot \rVert_1$ , $\lVert \cdot \rVert_2$ and $\lVert \cdot \rVert_\infty$ satisfy (N1) to (N3) on $\mathbb R^n$ . (b) The sup norm satisfies (N1) to (N3) on $C[a, b]$ .

In one line $\lVert \cdot \rVert_1$ , $\lVert \cdot \rVert_2$ and $\lVert \cdot \rVert_\infty$ are norms on $\mathbb R^n$ , and the sup norm is a norm on $C[a, b]$ .

Why it is trueFor each one, (N1) and (N2) are quick computations, and (N3) reduces to the triangle inequality for single real numbers.

ProofRudin ch. 7

The idea: The 2-norm is the norm of 2.9. For the 1-norm and the max-norm, check each axiom coordinate by coordinate, using |x_i + y_i| ≤ |x_i| + |y_i| for numbers. The sup norm is the max-norm with a point x in [a, b] in place of the coordinate i.

The 2-norm is

\sqrt{x \cdot x}

from the dot product, so (N1) to (N3) hold.

The theorem 'Properties of the norm' in 2.9, which used Cauchy–Schwarz.

1-norm (N1):

\lVert x \rVert_1 \ge 0

, and

= 0

iff every

|x_i| = 0

, that is,

x = O

A sum of non-negative terms is

0

only if every term is

0

1-norm (N2):

\lVert cx \rVert_1 = \sum |c||x_i| = |c|\,\lVert x \rVert_1

|cx_i| = |c||x_i|

, then take the common factor

|c|

out of the sum.

1-norm (N3):

\sum |x_i + y_i| \le \sum (|x_i| + |y_i|) = \lVert x \rVert_1 + \lVert y \rVert_1

The triangle inequality for numbers, for each

i

, then add over

i

Max-norm (N1), (N2):

\lVert x \rVert_\infty \ge 0

, with

0

iff

x = O

, and

\lVert cx \rVert_\infty = |c|\,\lVert x \rVert_\infty

A largest of non-negative numbers is

0

only if all of them are

0

; and

\max (|c||x_i|) = |c| \max |x_i|

because

|c| \ge 0

Max-norm (N3):

\lVert x + y \rVert_\infty \le \lVert x \rVert_\infty + \lVert y \rVert_\infty

For each

i

|x_i + y_i| \le |x_i| + |y_i| \le \lVert x \rVert_\infty + \lVert y \rVert_\infty

. A number that bounds every

|x_i + y_i|

also bounds their maximum.

Sup norm (N1), (N2):

\lVert f \rVert_\infty \ge 0

, with

\lVert f \rVert_\infty = 0

iff

f(t) = 0

for every

t

, that is,

f = O

; and

\lVert cf \rVert_\infty = |c|\,\lVert f \rVert_\infty

A maximum of non-negative numbers

|f(t)|

is at least

0

, and it is

0

only if every

|f(t)| = 0

. For (N2),

|cf(t)| = |c|\,|f(t)|

for every

t

and

|c| \ge 0

, so the maximum scales by

|c|

Sup norm (N3):

\lVert f + g \rVert_\infty \le \lVert f \rVert_\infty + \lVert g \rVert_\infty

\blacksquare

Same argument as for the max-norm, with the point

t \in [a, b]

in place of the index

i

|f(t) + g(t)| \le |f(t)| + |g(t)| \le \lVert f \rVert_\infty + \lVert g \rVert_\infty

for every

t

, so the maximum of the left side obeys the same bound.

By the previous theorem each gives a metric: $d_1$ , $d_2$ , $d_\infty$ on $\mathbb R^n$ , and on $C[a, b]$ the sup metric.

Definition B

Sup metric

The sup metric on $C[a, b]$ is $d_\infty(f, g) = \lVert f - g \rVert_\infty = \max_{a \le x \le b} |f(x) - g(x)|$ . It is the largest vertical distance between the graphs of $f$ and $g$ .

In one lineOn $C[a, b]$ , $d_\infty(f, g) = \max_{a \le x \le b} |f(x) - g(x)|$ : the largest vertical gap between the graphs.

Why it existsTwo functions are close in this metric when one graph fits inside a thin tube around the other, which is exactly the picture of uniform convergence in 1.6.

Worked example

Find the distance between

f(x) = x

and

g(x) = x^2

[0, 1]

in the sup metric, and compare with the 2-distance.

Solution.

Form the gap function. $h(x) = |f(x) - g(x)| = x - x^2$ on $[0, 1]$ (it is $\ge 0$ there since $x^2 \le x$ ). The sup metric is the largest value of $h$ , so we maximize $h$ .
Find the maximum. $h'(x) = 1 - 2x = 0$ at $x = \frac12$ , where $h = \frac12 - \frac14 = \frac14$ . At the endpoints $h(0) = h(1) = 0$ . A continuous function on $[0, 1]$ attains its maximum at an endpoint or where the derivative is $0$ (1.4).
The sup distance. $d_\infty(f, g) = \frac14$ . It is the height of the widest gap between the two graphs, at $x = \frac12$ .
The 2-distance, for comparison. $\lVert f - g \rVert_2 = \sqrt{\int_0^1 (x - x^2)^2\,dx} = \sqrt{\frac13 - \frac12 + \frac15} = \sqrt{\frac1{30}} \approx 0.183$ . This is the length of 2.9 for functions: it averages the squared gap over the interval, so a narrow spike counts for little. The sup metric counts the worst point only.

Answer. $d_\infty(x, x^2) = \frac14$ , and the 2-distance is $\sqrt{1/30} \approx 0.183$ . The two ways to measure functions give different numbers. On $[0, 1]$ the 2-distance is never larger than the sup distance, but the sup distance cannot be bounded by a constant times the 2-distance, as the box on equivalent norms below shows. $\blacksquare$

Worked example

Find the 1-, 2- and ∞-distances between

(1, -2, 4)

and

(3, 1, -2)

\mathbb R^3

Solution.

Subtract. $x - y = (1 - 3,\ -2 - 1,\ 4 - (-2)) = (-2, -3, 6)$ . All three distances are the length of $x - y$ (the norm-to-metric theorem), so we compute the difference once.
1-distance. $|-2| + |-3| + |6| = 2 + 3 + 6 = 11$ . Add the sizes of the entries.
2-distance. $\sqrt{4 + 9 + 36} = \sqrt{49} = 7$ . The usual length: square, add, root.
∞-distance. $\max(2, 3, 6) = 6$ . Only the largest entry counts.

Answer. $d_1 = 11$ , $d_2 = 7$ , $d_\infty = 6$ . Note $6 \le 7 \le 11$ : the order $d_\infty \le d_2 \le d_1$ is a theorem, proved below. $\blacksquare$

Your answerWhat is the 2-distance between

(1, -2, 4)

and

(3, 1, -2)

\mathbb R^3

Not every metric comes from a norm. The next two have no vectors to scale.

Definition B

Discrete metric

On any set $X$ , the discrete metric is $d(x, y) = 0$ when $x = y$ and $d(x, y) = 1$ when $x \ne y$ .

In one lineOn any set $X$ : $d(x, y) = 0$ if $x = y$ and $d(x, y) = 1$ if $x \ne y$ .

Why it existsIt is the extreme case where no two points are close, which makes it a test case for every definition: it shows what each idea means when nothing is near anything.

Definition B

Hamming distance

For two strings $a = a_1 \dots a_n$ and $b = b_1 \dots b_n$ of bits (each $0$ or $1$ ), the Hamming distance $d_H(a, b)$ is the number of positions $i$ where $a_i \ne b_i$ . For example $d_H(10110, 11100) = 2$ : they differ in positions $2$ and $4$ .

In one lineFor two bit strings of the same length, the number of positions where they differ.

Why it existsFlipping a bit is the basic error in a message, so the number of positions that differ counts how many errors turn one string into the other.

Theorem B Hamming 1950; standard

The discrete metric and the Hamming distance are metrics

(a) The discrete metric on a set $X$ is a metric. (b) The Hamming distance is a metric on the set of bit strings of length $n$ .

In one lineThe discrete metric on any set, and $d_H$ on bit strings of length $n$ , satisfy (M1), (M2) and (M3).

Why it is trueFor both, a detour through a third point cannot make two different points closer, because the third point cannot agree with both.

Proofstandard

The idea: (M1) and (M2) are read off the definitions. For (M3) in both cases: if a and c differ somewhere, the middle point b cannot agree with both of them there, so b differs from a or from c at that place.

(a) (M1), (M2): immediate.

By definition

d \ge 0

and

d(x, y) = 0

exactly when

x = y

. The definition does not mention the order of

x

and

y

(a) (M3), case

x = z

d(x, z) = 0 \le d(x, y) + d(y, z)

x = z

, the left side is

0

, and the right side is non-negative.

(a) (M3), case

x \ne z

d(x, z) = 1 \le d(x, y) + d(y, z)

\blacksquare

y

were equal to both

x

and

z

, then

x = y = z

, contradicting

x \ne z

. So

y \ne x

y \ne z

, and at least one term on the right is

1

(b) (M1), (M2): immediate.

The count is a number of positions, so it is a whole number at least

0

; it is

0

iff no position differs iff

a = b

. 'Differs' is a symmetric relation.

(b) (M3):

D(a, c) \subseteq D(a, b) \cup D(b, c)

Let

D(a, b)

be the set of positions where

a

and

b

differ. If

a_i \ne c_i

, then

b_i

cannot equal both

a_i

and

c_i

, so

i \in D(a, b)

i \in D(b, c)

.Where the idea comes from: this is the same 'cannot agree with both' as the discrete metric, now once per position.

d_H(a, c) = |D(a, c)| \le |D(a, b)| + |D(b, c)| = d_H(a, b) + d_H(b, c)

\blacksquare

A set inside a union has at most as many elements as the union, and a union has at most as many elements as the sum of the sizes.

(If you read a bit string as a vector in $\mathbb R^n$ with entries $0$ and $1$ , then $d_H(a, b) = \lVert a - b \rVert_1$ . The 1-distance counts the same positions.)

Quick checkIs the discrete metric on

\mathbb R

given by a norm, that is, is

d(x, y) = \lVert x - y \rVert

for some norm on

\mathbb R

Open balls, open sets, closed sets

Definition T

Open ball

In a metric space, the open ball of radius $r > 0$ about $x$ is $B(x, r) = \{y \in X : d(x, y) < r\}$ . (The strict inequality matters: the points at distance exactly $r$ are not in it.)

In one line $B(x, r)$ is the set of all points whose distance from $x$ is less than $r$ : the points strictly within $r$ of $x$ .

Why it existsThe ball is the unit of 'nearby'. Every later definition says that a ball around a point fits in, or touches, a set.

In $\mathbb R$ with $|x - y|$ , $B(x, r)$ is the interval $(x - r, x + r)$ . In $\mathbb R^2$ with $d_2$ it is a disc without its rim, with $d_1$ a diamond without its edge, with $d_\infty$ a square without its edge. In the discrete metric, $B(x, r) = \{x\}$ when $r \le 1$ and $B(x, r) = X$ when $r > 1$ . In Hamming distance the balls are sets of strings.

Worked example

List the open balls

B(000, r)

in the Hamming distance on bit strings of length 3, for

r = 1, 2, 3, 4

Solution.

Distances from $000$ . $d_H(000, s)$ is the number of $1$ s in $s$ . $000$ differs from $s$ exactly where $s$ has a $1$ .
Sort the 8 strings by distance. Distance $0$ : $000$ . Distance $1$ : $100, 010, 001$ . Distance $2$ : $110, 101, 011$ . Distance $3$ : $111$ . There are $\binom3k$ strings with $k$ ones.
Apply “strictly less than $r$ ”. $r = 1$ : distance $< 1$ , so only $000$ . $r = 2$ : distance $\le 1$ , so $000, 100, 010, 001$ . $r = 3$ : distance $\le 2$ , so 7 strings (all but $111$ ). $r = 4$ : all 8 strings.

Answer. $B(000, 1) = \{000\}$ , $B(000, 2)$ has 4 strings, $B(000, 3)$ has 7, $B(000, 4)$ has 8. $\blacksquare$

Your answerIn Hamming distance on bit strings of length 5, how many strings lie in the open ball

B(00000, 3)

? (That is, how many have distance less than 3 from

00000

Quick checkIn the discrete metric on a set

X

with more than one point, what is the open ball

B(x, 1)

Definition T

Open set

A subset $U$ of a metric space $X$ is open if for every $x \in U$ there is an $r > 0$ with $B(x, r) \subseteq U$ . In symbols, $\forall x \in U\ \exists r > 0:\ B(x, r) \subseteq U$ . The radius $r$ may depend on $x$ .

In one lineA set $U$ is open if every point of $U$ has an open ball around it that lies completely inside $U$ .

Why it existsOpen sets are the sets with no edge in them: every point has room to move in every direction while staying in the set. This is where derivatives, and also limits, make sense.

Definition T

Closed set

A subset $F$ of a metric space $X$ is closed if $X \setminus F$ is open. (Here $X \setminus F$ is the complement of $F$ in $X$ , the points of $X$ not in $F$ .)

In one lineA set is closed if its complement is open.

Why it existsClosed sets are the sets that contain their own edge, so a sequence inside one cannot escape through the edge. 4.2 turns this into the statement that limits of sequences in a closed set stay in it.

Proposition T Rudin Thm 2.19; Abbott Sec. 3.2

Open balls are open

For every $x$ in a metric space and every $r > 0$ , the ball $B(x, r)$ is open.

In one lineEvery open ball $B(x, r)$ is an open set.

Why it is trueA point of the ball at distance $d$ from the centre has a gap $r - d$ to the rim, and a small ball of that radius fits inside, by the triangle inequality.

ProofRudin 2.19

The idea: Take a point y in the ball. The distance from y to the rim of the ball is r − d(x, y), which is positive. A ball around y of that radius stays inside, because going from x to a point of it by way of y cannot exceed d(x, y) plus that radius.

Let

y \in B(x, r)

, so

d(x, y) < r

We must give every point of the ball a smaller ball that fits inside it. So start with an arbitrary point.

Let

s = r - d(x, y) > 0

This is positive because

d(x, y) < r

. It is the room between

y

and the rim.The idea: measure how far y is from the edge.

Let

z \in B(y, s)

, so

d(y, z) < s

Take any

z

in the small ball.

d(x, z) \le d(x, y) + d(y, z) < d(x, y) + s = r

Triangle inequality (M3) through

y

, then the choice of

s

B(y, s) \subseteq B(x, r)

, and

y

has a ball inside

B(x, r)

. Since

y

was arbitrary,

B(x, r)

is open.

\blacksquare

That says

z \in B(x, r)

. Every

z

in the small ball is in the big ball.

In the picture: the ball is a disc, the point $y$ is somewhere inside it, and the small ball around $y$ is a disc that touches the rim of the big one from inside when $s = r - d(x, y)$ . In the visualizer this is the diamond, disc or square: pick any point inside, and the shorter distance to the edge is the radius you may use.

Proof workshopRebuild the proof that open balls are open

Tap the lines in the order a proof would write them. Each line can only use what is already above it.

Worked example

Show that

(0, 1)

is open in

\mathbb R

, that

[0, 1]

is closed, and that

[0, 1)

is neither.

Solution.

$(0, 1)$ is open. Take $x \in (0, 1)$ and let $r = \min(x, 1 - x) > 0$ . Then $B(x, r) = (x - r, x + r) \subseteq (0, 1)$ , because $x - r \ge 0$ and $x + r \le 1$ . The radius is the smaller of the distances to the two ends. It depends on $x$ : near $0$ or $1$ it must be tiny.
$[0, 1]$ is closed. Its complement is $(-\infty, 0) \cup (1, \infty)$ . For $x < 0$ the ball $B(x, -x)$ stays below $0$ ; for $x > 1$ the ball $B(x, x - 1)$ stays above $1$ . So the complement is open. Closed means the complement is open, so we check the complement with the same radius trick.
$[0, 1)$ is not open. The point $0$ belongs to it, but every ball $B(0, r) = (-r, r)$ contains negative numbers, which are not in $[0, 1)$ . A single point of the set with no ball inside it is enough to show a set is not open. This is the negation of the definition.
$[0, 1)$ is not closed. Its complement $(-\infty, 0) \cup [1, \infty)$ contains $1$ , and every ball $B(1, r) = (1 - r, 1 + r)$ contains numbers less than $1$ that are in $[0, 1)$ , so not in the complement. So the complement is not open. Each end of the interval is “missing” on one side, and that spoils one of the two tests.

Answer. $(0, 1)$ is open and not closed. $[0, 1]$ is closed and not open. $[0, 1)$ is neither. A set can be neither open nor closed, so “closed” does not mean “not open”. $\blacksquare$

Worked example MATH 375 Piazza, Nov 23

Classify as open, closed, both or neither in

\mathbb R

\varnothing

\mathbb R

\{0\}

\mathbb N

\mathbb Q

Solution.

$\varnothing$ and $\mathbb R$ are both. $\varnothing$ is open because there is no point to test, so the condition “for every point of the set” holds with nothing to check. $\mathbb R$ is open because every ball is inside it. Each is the complement of the other, so each is also closed. A statement “for every $x \in \varnothing$ ” is true (0.1). These are the only two subsets of $\mathbb R$ that are both open and closed. That fact is called the connectedness of $\mathbb R$ , and we do not prove it here.
$\{0\}$ is closed, not open. Its complement is $(-\infty, 0) \cup (0, \infty)$ , which is open (each point has a ball avoiding $0$ : radius $|x|$ ). But every ball $(-r, r)$ around $0$ contains points other than $0$ . One point is closed in every metric space (a problem below), but in $\mathbb R$ it is not open.
$\mathbb N$ is closed, not open. Here $\mathbb N = \{1, 2, 3, \dots\}$ . Take a real number $y$ not in $\mathbb N$ . If $y < 1$ , the ball $B(y, 1 - y)$ stays below $1$ . If $y > 1$ , then $k < y < k + 1$ for some natural number $k$ (the naturals are spaced $1$ apart), and the ball $B(y, r)$ with $r = \min(y - k,\ k + 1 - y) > 0$ lies strictly between $k$ and $k + 1$ , so it contains no natural number. So the complement of $\mathbb N$ is open. Each point outside has a positive gap to the nearest natural number on each side, and the smaller gap is a safe radius. And $\mathbb N$ is not open: every ball around $1$ contains non-integers.
$\mathbb Q$ is neither. Every ball $(q - r, q + r)$ contains an irrational number (for example $q + \frac{\sqrt2}{n}$ with $n$ large enough that $\frac{\sqrt2}n < r$ , by the Archimedean property; it is irrational because if it were a rational $p$ , then $\sqrt 2 = n(p - q)$ would be rational), so $\mathbb Q$ is not open. Every ball around an irrational contains a rational (density, 1.1), so the complement is not open, and $\mathbb Q$ is not closed. The rationals and irrationals are tangled together at every scale.

Answer. $\varnothing$ , $\mathbb R$ : both. $\{0\}$ , $\mathbb N$ : closed only. $\mathbb Q$ : neither. $\blacksquare$

Worked example

In the discrete metric, every subset is open, and so every subset is closed.

Solution.

Pick any set $U$ and a point $x \in U$ . Take $r = \frac12$ . Any radius at most $1$ will do in the discrete metric.
The ball is a single point. $B(x, \frac12) = \{x\} \subseteq U$ . Only $x$ has distance less than $1$ from $x$ .
So $U$ is open. The complement $X \setminus U$ is also a subset of $X$ , so by the same argument it is open; hence $U$ is closed. Closed means the complement is open, and the complement is another subset of $X$ , to which the argument we just made applies.

Answer. In the discrete metric every set is both open and closed. This is why it is a good test case: it shows how much the words depend on the metric. $\blacksquare$

Unions and intersections

Theorem T Abbott Sec. 3.2; Apostol 8.3 #5; Rudin Thm 2.24

Unions and finite intersections of open sets

In a metric space $X$ : (a) $\varnothing$ and $X$ are open. (b) If $U_\alpha$ is open for every $\alpha$ in some collection (finite or infinite), then $\bigcup_\alpha U_\alpha$ is open. (c) If $U_1, \dots, U_m$ are open, then $U_1 \cap \dots \cap U_m$ is open.

In one line $\varnothing$ and $X$ are open; any union of open sets is open; the intersection of finitely many open sets is open.

Why it is trueFor a union, a point sits in one of the sets and uses its ball. For a finite intersection, take the smallest of finitely many radii, which is still positive. With infinitely many radii the smallest could be zero.

ProofAbbott Sec. 3.2

The idea: (b): a point of the union lies in one U_α, whose ball is also inside the union. (c): a point of the intersection lies in each U_i with its own radius r_i; the smallest r_i works for all of them at once, and a smallest of finitely many positive numbers is positive.

(a)

\varnothing

and

X

are open.

For

\varnothing

there is no point to check. For

X

, any ball is a subset of

X

(b) Let

x \in \bigcup U_\alpha

. Then

x \in U_\beta

for some

\beta

Choose the set in the collection that contains

x

There is

r > 0

with

B(x, r) \subseteq U_\beta \subseteq \bigcup_\alpha U_\alpha

. So the union is open.

U_\beta

is open, and

U_\beta \subseteq \bigcup U_\alpha

x \in U_1 \cap \dots \cap U_m

. For each

i

there is

r_i > 0

with

B(x, r_i) \subseteq U_i

Each

U_i

is open and contains

x

, so it gives its own radius.The radius is allowed to differ for each set; that is why we need a minimum.

Let

r = \min(r_1, \dots, r_m) > 0

A minimum of FINITELY many positive numbers is one of them, so it is positive. With infinitely many it could be

0

(or not exist).

B(x, r) \subseteq B(x, r_i) \subseteq U_i

for every

i

, so

B(x, r) \subseteq U_1 \cap \dots \cap U_m

\blacksquare

A ball of radius

r \le r_i

is inside the ball of radius

r_i

Worked example MATH 375 HW 11 (Apostol 8.3 #5)

Show that an infinite intersection of open sets need not be open:

\bigcap_{n=1}^\infty (0, 1 + \tfrac1n) = (0, 1]

Solution.

Each set is open. $(0, 1 + \frac1n)$ is an open interval. An open interval is an open ball in $\mathbb R$ .
Which numbers lie in all of them? If $0 < x \le 1$ , then $x < 1 + \frac1n$ for every $n$ , so $x$ is in every set. If $x > 1$ , pick $n$ with $\frac1n < x - 1$ (Archimedean property); then $x > 1 + \frac1n$ , so $x$ is missing from the $n$ -th set. Numbers $\le 0$ are in none. An element of the intersection must pass every test, so one failing set removes it.
The intersection is $(0, 1]$ , which is not open. The point $1$ is in it, but every ball $(1 - r, 1 + r)$ contains numbers above $1$ . The minimum trick fails: the radii that fit around $1$ in the $n$ -th set are $\frac1n$ , and $\min$ of infinitely many of those is $0$ .

Answer. The intersection is $(0, 1]$ , not open. The word “finite” in part (c) cannot be dropped. $\blacksquare$

Taking complements turns this theorem into one about closed sets. By De Morgan’s laws (0.3), $X \setminus \bigcap F_\alpha = \bigcup (X \setminus F_\alpha)$ and $X \setminus (F_1 \cup \dots \cup F_m) = \bigcap (X \setminus F_i)$ .

Corollary T Abbott Sec. 3.2; Rudin Thm 2.24

Intersections and finite unions of closed sets

In a metric space: (a) $\varnothing$ and $X$ are closed. (b) Any intersection of closed sets is closed. (c) A union of finitely many closed sets is closed.

In one line $\varnothing$ and $X$ are closed; any intersection of closed sets is closed; the union of finitely many closed sets is closed.

Why it is trueTake complements of the open-set theorem: De Morgan swaps unions with intersections.

ProofAbbott Sec. 3.2

The idea: Apply the previous theorem to the complements, and use De Morgan's laws to move complements across unions and intersections.

(a) The complements of

\varnothing

and

X

are

X

and

\varnothing

, which are open.

\varnothing = X \setminus X

and

X = X \setminus \varnothing

, and both

X

and

\varnothing

are open.

(b)

X \setminus \bigcap F_\alpha = \bigcup (X \setminus F_\alpha)

is open, so

\bigcap F_\alpha

is closed.

De Morgan: the complement of an intersection is the union of the complements. Each complement

X \setminus F_\alpha

is open, and a union of open sets is open.

(c)

X \setminus (F_1 \cup \dots \cup F_m) = \bigcap (X \setminus F_i)

is open, so the finite union is closed.

\blacksquare

De Morgan: the complement of a union is the intersection of the complements, and a FINITE intersection of open sets is open.

The word “finite” cannot be dropped here either: $\bigcup_{n=2}^\infty [\frac1n, 1] = (0, 1]$ , an infinite union of closed intervals that is not closed (its complement contains $0$ but no ball around $0$ stays out of $(0, 1]$ ).

Quick checkWhich statement is correct?

Interior, limit points, closure, boundary

Take a set $A$ and zoom in on a point $x$ of the space. A small ball around $x$ can do one of three things, and each gives a word.

Definition T

Interior

A point $x \in A$ is an interior point of $A$ if some ball $B(x, r)$ lies inside $A$ . The interior of $A$ , written $\operatorname{int} A$ , is the set of its interior points.

In one lineThe interior of $A$ is the set of points of $A$ that have a ball around them inside $A$ .

Why it existsIt strips off the edge of $A$ and keeps the part where you could wiggle in any direction without leaving $A$ .

Definition B

Limit point

A point $x$ of the space (in $A$ or not) is a limit point of $A$ if for every $r > 0$ the ball $B(x, r)$ contains a point of $A$ different from $x$ . A point of $A$ that is not a limit point of $A$ is isolated: some ball around it contains no other point of $A$ .

In one line $x$ is a limit point of $A$ if every ball around $x$ contains a point of $A$ other than $x$ itself.

Why it existsIt describes the points that $A$ crowds around. A limit point need not belong to $A$ , and a point of $A$ need not be a limit point.

Definition B

Closure

The closure of $A$ , written $\overline A$ , is the set of points $x$ such that $B(x, r)$ contains a point of $A$ for every $r > 0$ .

In one lineThe closure of $A$ is every point whose every ball touches $A$ : the set $A$ together with its edge.

Why it existsIt adds to $A$ the points it can be approached from, so it is the smallest closed set around $A$ .

Definition T

Boundary

The boundary of $A$ , written $\partial A$ , is the set of points $x$ such that every ball $B(x, r)$ contains a point of $A$ and a point of $X \setminus A$ .

In one lineThe boundary of $A$ is every point whose every ball touches both $A$ and the complement of $A$ : the edge of $A$ .

Why it existsIt is where $A$ stops. It separates the inside of $A$ from the outside, and for a closed set it is the part that makes the set closed.

Zoom in on $x$ . Either some ball around $x$ lies inside $A$ (then $x$ is in the interior of $A$ ), or some ball around $x$ lies inside the complement of $A$ (then $x$ is outside the closure), or every ball around $x$ contains points of both $A$ and its complement (then $x$ is on the boundary). Exactly one of the three happens.

Theorem B Rudin Thm 2.27; Abbott Sec. 3.2; Apostol Sec. 8.2

Interior, closure and boundary

For a subset $A$ of a metric space $X$ :

(a) $\operatorname{int} A$ is open, it is the largest open set contained in $A$ , and $A$ is open iff $A = \operatorname{int} A$ .

(b) $X \setminus \overline A = \operatorname{int}(X \setminus A)$ . Hence $\overline A$ is closed, it is the smallest closed set containing $A$ , and $A$ is closed iff $A = \overline A$ .

(d) $\partial A = \overline A \setminus \operatorname{int} A$ .

In one line $\operatorname{int} A$ is the largest open set inside $A$ ; $\overline A$ is the smallest closed set containing $A$ and equals $A$ together with its limit points; $\partial A = \overline A \setminus \operatorname{int} A$ .

Why it is trueA point is outside the closure exactly when some ball misses $A$ , that is, when some ball lies inside the complement. So closure and interior of the complement are complements of each other.

ProofRudin 2.27

The idea: Everything comes from one fact: a point is outside the closure iff some ball misses A iff some ball lies inside the complement. Open balls are open (the previous proposition) gives (a); (b), (c), (d) are rewordings of the definitions.

(a) If

x \in \operatorname{int} A

with

B(x, r) \subseteq A

, then every

y \in B(x, r)

is also an interior point of

A

. So

B(x, r) \subseteq \operatorname{int} A

and

\operatorname{int} A

is open.

Open balls are open (proved above): every

y

B(x, r)

has a ball around it inside

B(x, r) \subseteq A

U

is open and

U \subseteq A

, then

U \subseteq \operatorname{int} A

: that is why

\operatorname{int} A

is the largest. And

A

is open iff all its points are interior iff

A = \operatorname{int} A

U \subseteq A

is open, each of its points has a ball inside

U \subseteq A

, so it is an interior point of

A

(b)

x \notin \overline A \iff \exists r:\ B(x, r) \cap A = \varnothing \iff x \in \operatorname{int}(X \setminus A)

. So

X \setminus \overline A = \operatorname{int}(X \setminus A)

x \notin \overline A

means: some ball

B(x, r)

contains no point of

A

. That is the same as

B(x, r) \subseteq X \setminus A

, which is the definition of

x \in \operatorname{int}(X \setminus A)

(the point

x

is automatically in

X \setminus A

, since it is in its own ball).

\overline A

is closed and is inside every closed set containing

A

. If

A

is closed it is one of those sets, so

\overline A \subseteq A

; also

A \subseteq \overline A

(a point of

A

is in every one of its balls). Hence

A

is closed iff

A = \overline A

By (a),

\operatorname{int}(X \setminus A)

is open, so its complement

\overline A

is closed. If

F

is closed and contains

A

, then

X \setminus F

is open and inside

X \setminus A

, so inside

\operatorname{int}(X \setminus A) = X \setminus \overline A

. Taking complements,

\overline A \subseteq F

(c)

A \cup \{\text{limit points}\} \subseteq \overline A

A point

x \in A

is in

\overline A

because

x

itself is in every ball around

x

. A limit point has a point of

A

in every ball, so it is in

\overline A

Conversely, if

x \in \overline A

, then

x \in A

x

is a limit point of

A

x \in \overline A

and

x \notin A

, every ball around

x

contains a point of

A

, and that point cannot be

x

because

x \notin A

. So

x

is a limit point.

(d)

x \in \overline A \setminus \operatorname{int} A

iff every ball meets

A

and every ball meets

X \setminus A

, which is the definition of

x \in \partial A

\blacksquare

x \in \overline A

says every ball meets

A

x \notin \operatorname{int} A

says no ball lies inside

A

, that is, every ball contains a point outside

A

(this holds also for

x \notin A

, since then

x

itself is outside

A

and in every ball).

In the picture: the interior is the part of $A$ with room all around, the closure adds the edge it touches, and the boundary is the strip between them, the points where every small disc shows both the inside and the outside of $A$ .

Worked example

Find the interior, limit points, closure and boundary of

A = (0, 1] \cup \{2\}

\mathbb R

Solution.

Interior. Each point of $(0, 1)$ has a ball inside $A$ (shrink toward the nearer end). The point $1$ does not: every ball $(1 - r, 1 + r)$ contains numbers above $1$ . The point $2$ does not: every ball around it contains other numbers. So $\operatorname{int} A = (0, 1)$ . The interior throws out every point of $A$ that sits on an edge or alone.
Limit points. Every point of $[0, 1]$ is a limit point: every ball around it contains other points of $(0, 1]$ . The point $0$ qualifies although $0 \notin A$ . The point $2$ is not: $B(2, \frac12)$ contains no other point of $A$ , so $2$ is isolated. No other number is a limit point. A limit point needs other points of $A$ crowding around it.
Closure. $\overline A = A \cup \{\text{limit points}\} = [0, 1] \cup \{2\}$ (by part (c) of the theorem). Add the missing edge $0$ and keep the isolated point $2$ .
Boundary. $\partial A = \overline A \setminus \operatorname{int} A = \{0, 1, 2\}$ . Part (d). The three edge points are the places where a small ball sees both $A$ and the outside.

Answer. $\operatorname{int} A = (0, 1)$ ; limit points $[0, 1]$ ; $\overline A = [0, 1] \cup \{2\}$ ; $\partial A = \{0, 1, 2\}$ . Note that $2 \in \partial A$ though it is an isolated point of $A$ . $\blacksquare$

Quick checkLet

A = \{1, \frac12, \frac13, \frac14, \dots\}

\mathbb R

. Which points are limit points of

A

Theorem B Abbott Sec. 3.2; Rudin ch. 2

A closed set contains its limit points

A subset $A$ of a metric space is closed if and only if it contains all of its limit points.

In one lineA set $A$ is closed if and only if every limit point of $A$ belongs to $A$ .

Why it is trueA limit point outside $A$ would be a point of the complement with no room, so the complement would not be open; conversely, a point of the complement that is not a limit point has a ball that misses $A$ .

ProofAbbott Sec. 3.2

The idea: (⇒) Contrapositive-style: if a limit point x were outside a closed A, the open complement would have a ball around x missing A, contradicting that x is a limit point. (⇐) A point of the complement is not a limit point, so some ball around it has no point of A other than possibly itself, and it is not in A, so the ball misses A.

(⇒) Let

A

be closed, let

x

be a limit point of

A

, and suppose

x \notin A

Closed means the complement

X \setminus A

is open.

There is

r > 0

with

B(x, r) \subseteq X \setminus A

, so

B(x, r)

contains no point of

A

Then

x \in X \setminus A

, which is open, so

x

has a ball inside it.

Contradiction, so

x \in A

This contradicts the definition of a limit point: every ball around

x

must contain a point of

A

(⇐) Suppose

A

contains all its limit points, and let

x \in X \setminus A

To show

A

is closed we show that

X \setminus A

is open: take an arbitrary point of it.

x

is not a limit point of

A

: some ball

B(x, r)

contains no point of

A

other than

x

x

were a limit point of

A

it would be in

A

by assumption, but

x \notin A

Hence

B(x, r) \cap A = \varnothing

, that is,

B(x, r) \subseteq X \setminus A

. So

X \setminus A

is open and

A

is closed.

\blacksquare

x \notin A

, so

x

is not a point of

A

either.

Proof workshopRebuild the proof that a closed set contains its limit points (the forward direction)

Each line of the proof is shown in order. Choose the reason that justifies it, then press Check.

Let $A$ be closed and let $x$ be a limit point of $A$ . Suppose, for contradiction, that $x \notin A$ .
Then $x$ lies in the complement $X \setminus A$ .
There is $r > 0$ with $B(x, r) \subseteq X \setminus A$ .
So $B(x, r)$ contains no point of $A$ .
This contradicts that $x$ is a limit point, so $x \in A$ .

Equivalent norms: do the three distances agree?

The picture showed three shapes of ball. Do they define the same open sets? We compare the lengths with two-sided inequalities.

Definition B

Equivalent norms

Two norms $\lVert \cdot \rVert_a$ and $\lVert \cdot \rVert_b$ on a vector space $V$ are equivalent if there are constants $0 < m \le M$ with

m\,\lVert x \rVert_a \le \lVert x \rVert_b \le M\,\lVert x \rVert_a \qquad \text{for all } x \in V.

In one lineTwo norms on the same vector space are equivalent if each is at most a constant multiple of the other.

Why it existsIt is the precise condition under which two lengths measure 'close' in the same way, even though they give different numbers.

Theorem B Abbott Sec. 3.1 exercises; standard

Comparing the 1-, 2- and max-norms

For every $x \in \mathbb R^n$ ,

\lVert x \rVert_\infty \le \lVert x \rVert_2 \le \lVert x \rVert_1 \le \sqrt n\,\lVert x \rVert_2 \le n\,\lVert x \rVert_\infty.

So the three norms are equivalent, with constants depending only on $n$ .

In one lineFor every $x \in \mathbb R^n$ : $\lVert x \rVert_\infty \le \lVert x \rVert_2 \le \lVert x \rVert_1 \le \sqrt n\,\lVert x \rVert_2 \le n\,\lVert x \rVert_\infty$ .

Why it is trueThe largest term is one of the terms of the sum of squares; squaring the 1-norm adds cross terms to the sum of squares; Cauchy–Schwarz against the vector of ones gives the factor $\sqrt n$ ; and every term is at most the largest.

Proofstandard

The idea: Four small inequalities, one per link in the chain: bound a term by a sum, expand a square, use Cauchy–Schwarz with the all-ones vector, and bound every term by the largest.

(1)

\lVert x \rVert_\infty^2 = x_i^2 \le x_1^2 + \dots + x_n^2 = \lVert x \rVert_2^2

. Take square roots.

The largest of the

|x_j|

is one of them, call it

|x_i|

. Its square is one term of the sum of squares, and the other terms are

\ge 0

(2)

\lVert x \rVert_1^2 = \sum_j x_j^2 + 2\sum_{j<k} |x_j||x_k| \ge \sum_j x_j^2 = \lVert x \rVert_2^2

. Take square roots.

Expand

(|x_1| + \dots + |x_n|)^2

: the squares

x_j^2

, plus the cross terms

2|x_j||x_k|

for

j < k

, which are

\ge 0

(3)

\lVert x \rVert_1 = u \cdot v \le \lVert u \rVert_2\,\lVert v \rVert_2 = \sqrt n\,\lVert x \rVert_2

Cauchy–Schwarz (2.9) for

u = (|x_1|, \dots, |x_n|)

and

v = (1, \dots, 1)

. We have

\lVert u \rVert_2 = \lVert x \rVert_2

and

\lVert v \rVert_2 = \sqrt n

.Where the idea comes from: a sum of n numbers is the dot product with the all-ones vector.

(4)

\lVert x \rVert_2^2 \le n\,\lVert x \rVert_\infty^2

, so

\lVert x \rVert_2 \le \sqrt n\,\lVert x \rVert_\infty

and

\sqrt n\,\lVert x \rVert_2 \le n\,\lVert x \rVert_\infty

\blacksquare

Each

x_j^2 \le \lVert x \rVert_\infty^2

, and there are

n

terms.

Worked example

Check the chain of inequalities for

x = (3, -4, 12)

\mathbb R^3

, and find vectors where the ends of the chain are attained.

Solution.

Compute the three norms. $\lVert x \rVert_1 = 3 + 4 + 12 = 19$ , $\lVert x \rVert_2 = \sqrt{9 + 16 + 144} = \sqrt{169} = 13$ , $\lVert x \rVert_\infty = 12$ . Add the sizes, root of the sum of squares, largest size.
The other two links. $\sqrt n\,\lVert x \rVert_2 = \sqrt3 \cdot 13 \approx 22.5$ and $n\,\lVert x \rVert_\infty = 3 \cdot 12 = 36$ . The chain needs $\sqrt n \lVert x \rVert_2$ and $n \lVert x \rVert_\infty$ as well.
Check the chain. $12 \le 13 \le 19 \le 22.5 \le 36$ . Every link holds.
Where the chain is tight. For $x = (1, 0, 0)$ all three norms are $1$ , so the left links are equalities. For $x = (1, 1, 1)$ : $\lVert x \rVert_\infty = 1$ , $\lVert x \rVert_2 = \sqrt3$ , $\lVert x \rVert_1 = 3 = \sqrt3 \cdot \sqrt3 = n \cdot 1$ , so the right links are equalities. The constants $\sqrt n$ and $n$ cannot be improved. They are largest for vectors with all entries equal, and the gap grows with the dimension.

Answer. $12 \le 13 \le 19 \le 22.5 \le 36$ , with both ends of the chain attained by suitable vectors. $\blacksquare$

Your answerFor

x = (3, -4, 12)

, what is

\lVert x \rVert_2

Worked example

\mathbb R^2

, which of the points

(0.8, 0.5)

and

(0.5, 0.5)

lie in the open unit ball for

d_1

d_2

and

d_\infty

? What is the area of each ball?

Solution.

Compute the three distances from the origin. For $(0.8, 0.5)$ : $d_1 = 1.3$ , $d_2 = \sqrt{0.64 + 0.25} = \sqrt{0.89} \approx 0.943$ , $d_\infty = 0.8$ . For $(0.5, 0.5)$ : $d_1 = 1$ , $d_2 = \sqrt{0.5} \approx 0.707$ , $d_\infty = 0.5$ . The ball of radius $1$ about the origin is every point whose distance is below $1$ , so we need the distance in each rule.
Compare with the radius, strictly. $(0.8, 0.5)$ is in the disc and the square, not in the diamond. $(0.5, 0.5)$ is in the disc and the square, and it is NOT in the diamond, because $d_1 = 1$ is not less than $1$ : it sits on the edge. The open ball uses strict inequality, so the edge is left out.
Areas. The square $(-1, 1)^2$ has area $2 \times 2 = 4$ . The disc has area $\pi \approx 3.14$ . The diamond has vertices $(\pm 1, 0)$ , $(0, \pm 1)$ : it is two triangles of base $2$ and height $1$ , area $2 \cdot \frac12 \cdot 2 \cdot 1 = 2$ . Diamond, disc and square nest, so the areas must increase: $2 \le \pi \le 4$ .

Answer. Both points are in the disc and the square, neither is in the diamond. The areas are $2$ , $\pi$ and $4$ . $\blacksquare$

What the chain says about the balls: if $\lVert y \rVert_1 < r$ then $\lVert y \rVert_2 < r$ , and then $\lVert y \rVert_\infty < r$ . In balls, around any centre,

B_1(x, r) \subseteq B_2(x, r) \subseteq B_\infty(x, r) \subseteq B_1(x, nr).

The last inclusion uses $\lVert y \rVert_1 \le n\,\lVert y \rVert_\infty$ . In the plane, a diamond of radius $r$ is inside the disc of radius $r$ , which is inside the square of radius $r$ , which is inside the diamond of radius $2r$ . That is the nesting you saw in the visualizer.

Theorem B standard

Equivalent norms give the same open sets

Let $\lVert \cdot \rVert_a$ and $\lVert \cdot \rVert_b$ be norms on $V$ with $m\,\lVert x \rVert_a \le \lVert x \rVert_b \le M\,\lVert x \rVert_a$ . Then a set $U \subseteq V$ is open for the metric $d_a$ if and only if it is open for $d_b$ .

In one lineIf two norms on $V$ are equivalent, a set is open for one iff it is open for the other, so they also have the same closed sets, interiors, closures and boundaries.

Why it is trueA ball for one norm contains a smaller ball for the other, with the radius changed by the constants $m$ and $M$ .

Proofstandard

The idea: Show that every a-ball contains a b-ball with the same centre and the other way round. Then a ball inside U for one norm gives a ball inside U for the other.

Let

U

be open for

d_a

and

x \in U

, so

B_a(x, r) \subseteq U

for some

r > 0

Write

B_a

and

B_b

for balls in the two metrics. We show

B_b(x, mr) \subseteq B_a(x, r)

\lVert y - x \rVert_b < mr

, then

m\,\lVert y - x \rVert_a \le \lVert y - x \rVert_b < mr

, so

\lVert y - x \rVert_a < r

From

m\,\lVert y - x \rVert_a \le \lVert y - x \rVert_b

Hence

B_b(x, mr) \subseteq B_a(x, r) \subseteq U

, and

U

is open for

d_b

So the

b

-ball of radius

mr

is inside the

a

-ball of radius

r

, which is inside

U

The converse follows by swapping the two norms, with

\frac1M

in place of

m

\blacksquare

The same argument with the roles swapped, using

\lVert y - x \rVert_b \le M\,\lVert y - x \rVert_a

: if

\lVert y - x \rVert_a < \frac rM

then

\lVert y - x \rVert_b < r

, so

B_a(x, \frac rM) \subseteq B_b(x, r)

So on $\mathbb R^n$ the diamond, disc and square all give the same open sets, closed sets, interiors, closures and boundaries. We may use whichever norm makes a computation easiest. In fact every pair of norms on $\mathbb R^n$ is equivalent. The proof needs compactness (a closed bounded set of $\mathbb R^n$ contains a convergent subsequence of any sequence in it, as in Bolzano–Weierstrass). We do not prove it here.

Beyond the course: for understanding· All norms on R^n are equivalent, and all of this fails for functions

Fact (stated, not proved here). Any two norms on $\mathbb R^n$ are equivalent. The standard proof shows that every norm is a continuous function of the coordinates, and that a continuous function on the unit sphere (closed and bounded) attains a positive minimum and a finite maximum. Compactness is the tool, and MATH 521 proves it.

The statement is false for functions. On $C[0, 1]$ take $f_n(x) = x^n$ . Then $\lVert f_n \rVert_\infty = 1$ for every $n$ , but $\lVert f_n \rVert_2 = \sqrt{\int_0^1 x^{2n}\,dx} = \frac{1}{\sqrt{2n + 1}} \to 0$ . If $\lVert f \rVert_\infty \le M\,\lVert f \rVert_2$ held for a fixed $M$ , we would get $1 \le \frac{M}{\sqrt{2n+1}}$ for all $n$ , which is false for large $n$ . So the sup norm and the 2-norm are not equivalent on $C[0, 1]$ , and they give different open sets and, as 4.2 shows, different convergent sequences. In infinite dimensions the choice of norm matters.

Where it is used

Used inside maths· Inside maths: continuity, derivatives and topology all run on balls

Replace $|x - a|$ by $d(x, a)$ in the $\varepsilon$ - $\delta$ definition of 1.3 and you have continuity of a function between metric spaces: $f$ is continuous at $a$ if for every $\varepsilon > 0$ there is $\delta > 0$ with $d_Y(f(x), f(a)) < \varepsilon$ whenever $d_X(x, a) < \delta$ . The same statement says that the preimage of every open set is open, which MATH 551 takes as the definition of continuity and builds a whole subject on. The derivative in many variables (Unit 5) is defined at an interior point of a set: the ball inside the set is what lets you approach the point from every direction. Chapter 4.2 uses completeness and balls to prove that equations have solutions.

Used in the real world· Error-correcting codes: Hamming balls that do not overlap

A message is sent as a string of bits, and noise flips some of them. The Hamming distance counts how many flips separate two strings. A code is a chosen set of strings (the codewords), picked so that two codewords are at Hamming distance at least $3$ . Then the open balls $B(c, 2)$ of radius $2$ around the codewords (all strings at distance $\le 1$ ) do not overlap. If one bit is flipped in transmission, the received string is inside the ball of the sent codeword and in no other, so the receiver decodes by picking the nearest codeword and recovers the message.

The Hamming (7,4) code has 7-bit strings and $2^4 = 16$ codewords with minimum distance $3$ between any two. Each ball of radius $1$ contains $1 + 7 = 8$ strings, and $16 \times 8 = 128 = 2^7$ , so the 16 balls cover all $128$ strings of length $7$ without overlap. (We checked this by listing all 16 codewords by computer.) Every 7-bit string is a codeword or exactly one bit away from exactly one codeword.

Your answerIn Hamming distance on bit strings of length 7, how many strings are within distance 1 of a given string (the string itself included)?

Where this came from· Hamming at Bell Labs

Richard Hamming published Error detecting and error correcting codes in the Bell System Technical Journal in April 1950. He worked at Bell Telephone Laboratories, and his stated concern was large computing machines in which long calculations had to finish without a single error in the result. He measured how far apart two bit strings are by the number of positions in which they differ, and showed how to choose codewords far enough apart that one flipped bit can be both detected and corrected. The “distance” that now carries his name is the metric of this chapter, and “balls do not overlap” is the whole design principle.

Used in the real world· Machine learning: which ball is the perturbation allowed to live in?

An image classifier is attacked by changing every pixel by a small amount. The usual rule is to allow any change inside the max-norm ball of radius $\varepsilon$ around the image: no pixel moves by more than $\varepsilon$ . A common benchmark setting for $32 \times 32$ colour images (CIFAR-10), used for example by the RobustBench leaderboard, is $\varepsilon = \frac{8}{255}$ with pixel values scaled to run from $0$ to $1$ . The image has $n = 32 \cdot 32 \cdot 3 = 3072$ numbers. The corner of that cube, where every number moves by the full $\varepsilon$ , has 2-norm $\frac8{255}\sqrt{3072} \approx 1.74$ . So a change of at most about $3\%$ per number can have a Euclidean length as large as $1.74$ . That is the factor $\sqrt n \approx 55$ from the comparison theorem acting on a $3072$ -dimensional vector: the corner of the square is far from the centre in the 2-distance. The diamond tells a different story: minimizing a loss over a 1-norm ball tends to land on a corner of the diamond, where many coordinates are exactly $0$ , which is why an $\ell_1$ penalty (the lasso) produces sparse models. The three balls are three different modelling choices.

Your answerA CIFAR-10 image has

n = 3072

numbers. If every one changes by exactly

\varepsilon = \frac{8}{255}

, what is the 2-norm of the change? (Give a decimal.)

Traps

Watch out· Open is not the opposite of closed

A set can be both ( $\varnothing$ , the whole space, or any set in the discrete metric), or neither ( $[0, 1)$ and $\mathbb Q$ in $\mathbb R$ ). To prove a set is closed you show the complement is open; showing the set is “not open” proves nothing about closedness.

Watch out· Finite versus infinite intersections

Finite intersections of open sets are open; infinite ones need not be ( $\bigcap (-\frac1n, \frac1n) = \{0\}$ ). Dually, finite unions of closed sets are closed; infinite ones need not be. The proof uses a minimum of radii, and infinitely many positive radii can have minimum $0$ .

Watch out· Interior and boundary depend on the space around the set

The interval $[0, 1]$ has interior $(0, 1)$ as a subset of $\mathbb R$ . The same segment $[0, 1] \times \{0\}$ in the plane has empty interior, because no disc fits inside a segment. “Open” and “boundary” always mean “inside the metric space $X$ you are working in”. In the same way, the open interval $(0, 1)$ is open in $\mathbb R$ but, viewed as the segment $(0, 1) \times \{0\}$ of the plane, it is not open there.

Watch out· The closed ball is not always the closure of the open ball

The closed ball is $\{y : d(x, y) \le r\}$ and the open ball is $\{y : d(x, y) < r\}$ . In $\mathbb R^n$ the closure of the open ball is the closed ball, but not in every metric space. In the discrete metric on a set with at least two points, $B(x, 1) = \{x\}$ , whose closure is $\{x\}$ , while the closed ball of radius $1$ is the whole space.

Watch out· A limit point need not be in the set, and a point of the set need not be a limit point

For $A = \{\frac1n\}$ , $0$ is a limit point outside $A$ . Each $\frac1n$ is in $A$ but not a limit point. The closure is the union of the two kinds. In the proof, the phrase “other than $x$ itself” is not decoration: without it every point of $A$ would count.

Watch out· Balls are not always round

The ball of the max-distance is a square and of the 1-distance a diamond. A statement like “a ball has a smooth edge” or “a ball is convex and round” is a fact about $d_2$ only. What does hold for every metric is that balls are open sets.

Problems

check

Find $d_1$ , $d_2$ and $d_\infty$ between $(2, 0, -1)$ and $(-1, 4, -1)$ , and check $d_\infty \le d_2 \le d_1$ .

Solution

The difference is $(3, -4, 0)$ . So $d_1 = 3 + 4 + 0 = 7$ , $d_2 = \sqrt{9 + 16 + 0} = 5$ , $d_\infty = \max(3, 4, 0) = 4$ . And $4 \le 5 \le 7$ .

check

In the discrete metric on $\mathbb R$ , what are $B(3, \frac12)$ , $B(3, 1)$ and $B(3, 2)$ ?

Solution

$B(3, \frac12) = \{3\}$ and $B(3, 1) = \{3\}$ (the only distance below $1$ is $0$ ). $B(3, 2) = \mathbb R$ , because every distance is at most $1 < 2$ .

check

Is $\mathbb Z$ open in $\mathbb R$ ? Is it closed?

Solution

Not open: every ball $(n - r, n + r)$ around an integer contains non-integers. Closed: its complement is $\bigcup_n (n, n + 1)$ , a union of open intervals, hence open.

check

Write the negation of ” $U$ is open” using quantifiers.

Solution

$\exists x \in U\ \forall r > 0:\ B(x, r) \not\subseteq U$ . That is, some point of $U$ has no ball around it inside $U$ , which is what we showed for the point $0$ in $[0, 1)$ .

use

Find the interior, closure and boundary of $A = (0, 1) \cup (1, 2) \cup \{3\}$ in $\mathbb R$ .

Solution

Interior: $(0, 1) \cup (1, 2)$ (the point $3$ is isolated, so has no ball inside $A$ ). Limit points: $[0, 2]$ (the point $1$ is a limit point though not in $A$ ). Closure: $[0, 2] \cup \{3\}$ . Boundary: closure minus interior $= \{0, 1, 2, 3\}$ .

use

In $\mathbb R^2$ find the area of the open ball of radius $1$ about the origin for $d_1$ , $d_2$ , $d_\infty$ . Which of the points $(0.6, 0.6)$ and $(0.5, 0.5)$ lie in each ball?

Solution

$d_1$ : the diamond with vertices $(\pm 1, 0), (0, \pm 1)$ has area $2$ . $d_2$ : area $\pi$ . $d_\infty$ : the square $(-1, 1)^2$ has area $4$ . The point $(0.6, 0.6)$ has $d_1 = 1.2$ , $d_2 \approx 0.85$ , $d_\infty = 0.6$ , so it is in the disc and the square but not the diamond. The point $(0.5, 0.5)$ has $d_1 = 1$ exactly, so it is not in the open diamond (strict inequality) but it is in the other two.

use

How many bit strings of length 6 are in the Hamming open ball $B(a, 3)$ around a fixed string $a$ ? How many strings are at distance exactly $3$ ?

Solution

Distance less than $3$ means at most $2$ flips: $\binom60 + \binom61 + \binom62 = 1 + 6 + 15 = 22$ . Exactly $3$ flips: $\binom63 = 20$ .

use

Use the comparison theorem to show that if $\lVert x \rVert_\infty < \frac{1}{10}$ for $x \in \mathbb R^4$ , then $\lVert x \rVert_1 < 0.4$ and $\lVert x \rVert_2 < 0.2$ .

Solution

$\lVert x \rVert_1 \le n\,\lVert x \rVert_\infty = 4 \cdot \lVert x \rVert_\infty < 0.4$ . And $\lVert x \rVert_2 \le \sqrt n\,\lVert x \rVert_\infty = 2\,\lVert x \rVert_\infty < 0.2$ .

prove

Use the reverse triangle inequality to prove that for any four points $x, y, w, z$ of a metric space, $|d(x, y) - d(w, z)| \le d(x, w) + d(y, z)$ .

Solution

Plan. Move one endpoint at a time, using the reverse triangle inequality from the example above.

proveMATH 375 HW 11 (Apostol 8.3 #4a)

Prove: if $A$ is open and $x \in A$ , then $A \setminus \{x\}$ is open. (Work in any metric space.)

Solution

Plan. A point $y$ of $A \setminus \{x\}$ has a ball inside $A$ ; shrink it so that it also misses $x$ .

Let $y \in A \setminus \{x\}$ . Since $A$ is open, $B(y, r) \subseteq A$ for some $r > 0$ . Since $y \ne x$ , $d(x, y) > 0$ by (M1). Let $r' = \min(r, d(x, y))$ . Then $B(y, r') \subseteq B(y, r) \subseteq A$ , and $x \notin B(y, r')$ because $d(y, x) = d(x, y) \ge r'$ . So $B(y, r') \subseteq A \setminus \{x\}$ . $\blacksquare$

prove

Prove that the closed ball $\{y : d(x, y) \le r\}$ is a closed set.

Solution

Plan. Show the complement $\{y : d(x, y) > r\}$ is open, by the same idea as open balls are open.

Let $z$ satisfy $d(x, z) > r$ , and let $s = d(x, z) - r > 0$ . If $d(z, y) < s$ , then by (M3), $d(x, z) \le d(x, y) + d(y, z)$ , so $d(x, y) \ge d(x, z) - d(y, z) > d(x, z) - s = r$ . So $B(z, s)$ lies in the complement, which is open. Hence the closed ball is closed. $\blacksquare$

prove

Prove that every finite set in a metric space is closed.

Solution

Plan. A single point is closed; a finite union of closed sets is closed.

A single point $\{x\}$ is closed: for $y \ne x$ , the ball $B(y, d(x, y))$ does not contain $x$ (the distance from $y$ to $x$ is not less than $d(x, y)$ ), so it lies in $X \setminus \{x\}$ , which is therefore open. A finite set is a finite union of singletons, hence closed by the corollary on finite unions. $\blacksquare$

proveAbbott Sec. 3.2 style; new

Prove that $\overline A = A$ if $A$ is closed, and that $\overline A$ is always closed, using only the definition of closure (every ball around the point meets $A$ ).

Solution

Plan. Show the complement of $\overline A$ is open directly, with the open-ball proposition.

Closedness of $\overline A$ : let $x \notin \overline A$ . Some ball $B(x, r)$ misses $A$ . Every $y \in B(x, r)$ has a ball $B(y, s) \subseteq B(x, r)$ (open balls are open), and $B(y, s)$ misses $A$ too, so $y \notin \overline A$ . So $B(x, r) \subseteq X \setminus \overline A$ , which is open, and $\overline A$ is closed. If $A$ is closed and $x \notin A$ , then $X \setminus A$ is open, so some ball around $x$ misses $A$ , so $x \notin \overline A$ . Thus $\overline A \subseteq A$ , and always $A \subseteq \overline A$ . $\blacksquare$

stretch

Prove that $d(x, y) = \dfrac{|x - y|}{1 + |x - y|}$ is a metric on $\mathbb R$ . (Hint: $f(t) = \frac{t}{1 + t}$ is increasing, and $f(a + b) \le f(a) + f(b)$ for $a, b \ge 0$ .)

Solution

Plan. (M1) and (M2) are easy. For (M3), apply the increasing function $f$ to the real triangle inequality and then split.

(M1): $f(t) \ge 0$ with equality iff $t = 0$ , and $|x - y| = 0$ iff $x = y$ . (M2): $|x - y| = |y - x|$ . (M3): $f$ is increasing because $f(t) = 1 - \frac1{1 + t}$ . With $a = |x - y|$ , $b = |y - z|$ we have $|x - z| \le a + b$ , so $d(x, z) = f(|x - z|) \le f(a + b)$ . Then $f(a + b) = \frac{a + b}{1 + a + b} = \frac{a}{1 + a + b} + \frac{b}{1 + a + b} \le \frac{a}{1 + a} + \frac{b}{1 + b} = d(x, y) + d(y, z)$ , since each denominator on the left is at least as large as the one on the right. $\blacksquare$ (This metric never exceeds $1$ but has the same open sets as $|x - y|$ ; only the ball sizes change.)

stretch

Show that the open 1-ball of radius $r$ in $\mathbb R^n$ has volume $c_n r^n$ with $c_n = \frac{2^n}{n!}$ , while the max-ball has volume $2^n r^n$ . For $n = 10$ , what fraction of the cube does the diamond fill?

Solution

Plan. Slice the diamond by the last coordinate and use induction.

The volume scales as $r^n$ , so write $\operatorname{vol} = c_n r^n$ (for $n = 1$ , $c_1 = 2$ ). Slicing at height $t \in (-r, r)$ in the last coordinate leaves an $(n-1)$ -dimensional diamond of radius $r - |t|$ , of volume $c_{n-1}(r - |t|)^{n-1}$ . So $c_n r^n = 2\int_0^r c_{n-1}(r - t)^{n-1}\,dt = 2c_{n-1}\frac{r^n}{n}$ , giving $c_n = \frac{2}{n}c_{n-1}$ , hence $c_n = \frac{2^n}{n!}$ . The cube $(-r, r)^n$ has volume $(2r)^n$ . The ratio is $\frac1{n!}$ , which for $n = 10$ is $\frac{1}{3628800} \approx 2.8 \times 10^{-7}$ . In ten dimensions the diamond fills almost none of the cube it is inscribed in, so “being close” in $d_1$ is a far more demanding requirement than in $d_\infty$ .

Summary

A metric space is a set with a distance that is non-negative, zero only for equal points, symmetric, and obeys the triangle inequality. These four properties are all the $\varepsilon$ -proofs of Unit 1 used.
A norm (never negative, zero only at $O$ , scales by $|c|$ , triangle inequality) gives a metric $\lVert x - y \rVert$ . The 1-, 2- and max-norms on $\mathbb R^n$ and the sup norm on $C[a, b]$ are norms. The discrete metric and Hamming distance are metrics that come from no norm.
The open ball $B(x, r)$ is the points at distance strictly less than $r$ . It is a diamond, disc or square for $d_1$ , $d_2$ , $d_\infty$ .
Open means every point has a ball inside. Closed means the complement is open. Unions of open sets and finite intersections of open sets are open; the word “finite” is needed ( $\bigcap (-\frac1n, \frac1n) = \{0\}$ ).
Interior, closure, boundary: a ball around a point sits inside the set, touches it, or touches both it and its complement. $\overline A = A \cup \{\text{limit points}\}$ , $\partial A = \overline A \setminus \operatorname{int} A$ , and $A$ is closed iff it contains its limit points.
$\lVert x \rVert_\infty \le \lVert x \rVert_2 \le \lVert x \rVert_1 \le \sqrt n\,\lVert x \rVert_2 \le n\,\lVert x \rVert_\infty$ , so on $\mathbb R^n$ the three norms have the same open sets. On function spaces the norms need not be equivalent.
Hamming balls that do not overlap are an error-correcting code; max-norm balls are the perturbations allowed in adversarial robustness.

4.1 Metric and normed spaces; open and closed sets

The picture: who counts as close?

The idea, in words

Definitions and theorems

Metric space

Normed space

A norm gives a metric

The standard norms are norms

Sup metric

Discrete metric

Hamming distance

The discrete metric and the Hamming distance are metrics

Open balls, open sets, closed sets

Open ball

Open set

Closed set

Open balls are open

Unions and intersections

Unions and finite intersections of open sets

Intersections and finite unions of closed sets

Interior, limit points, closure, boundary

Interior

Limit point

Closure

Boundary

Interior, closure and boundary

A closed set contains its limit points

Equivalent norms: do the three distances agree?

Equivalent norms

Comparing the 1-, 2- and max-norms

Equivalent norms give the same open sets

Where it is used

Traps

Problems

Summary

Where this sits

Comes from

Leads to

Same idea elsewhere