Metric Spaces

Question 1

d is Metric on X

Answer 1

Let X be a set and d:X×X→R a function. Then d is called a metric on X if, for all x,y,z∈X, we have
* positivity
* symmetry
* triangle inequality
* nondegenerate
If d is a metric on X, then the pair (X,d) is called a metric space. If it is clear what is the metric d, then one also calls X a metric space.

Question 2

Positivity

Answer 2

d(x,y)≥0

Question 3

Symmetry

Answer 3

d(x,y) = d(y,x)

Question 4

Triangle Inequality

Answer 4

d(x,z)≤ d(x,y)+d(y,z)

Question 5

Nondegenerate

Answer 5

d(x,y) = 0⇔x=y

Question 6

Reverse Triangle Inequality

Answer 6

|d(x,z)-d(y,z)|≤d(x,y) for all x,y,z∈X.

Question 7

The Discrete Metric

Answer 7

The discrete (or point metric) measures the distance between x and y by checking if x = y. Let X be a set. Define d: X×X→R by
d(x,y){█(1 if x≠y,@0 if x=y)┤

Question 8

The p-metrics

Answer 8

The p-metrics measure distance on R^n in a similar fashion to the Euclidean distance but use a different power. That is for 1 p<n<∞:

d_p (x,y)=(∑(k=1)^n▒|x_k-y_k |^p )^(1/p)
For p=∞ we define d∞ (xy)=max_(1≤k≤n)⁡〖|x_k-y_k |^p 〗

The idea is that for higher values of p more weighting is put on the largest |x_k-y_k | with the extreme at p = where only the largest |x_k-y_k | contributes to the distance at all.

Question 9

Minkowski’s Inequality

Answer 9

Let x∈R^n and p<n<∞. If
|x|p=(∑(k=1)^n▒|x_k |^p )^(1/p)
Then
|x+y|_p≤|x|_p+|y|_p

Question 10

Path

Answer 10

A path, γ= (e_1,…,e_k ), between the vertices v and u on a graph is a sequence of distinct edges so that there is a sequence of distinct vertices (v_1,…,v_(k-1) ) with e_1 connecting v and v_1, e_k connecting v_(k-1) and u and e_i connecting v_(i-1) and v_i for i = 2,…,k-1. The length of the path is denoted |γ| and is equal to k (the number of edges).

We say that a graph is connected if for every pair (v,u) there is a path joining them.

Let v and u be vertices on a graph. Then
d_G (v,u)=min⁡{|γ|│γ is a path joining v and u}

Question 11

Hamming Metric

Answer 11

The Hamming metric allows us to measure the difference between two words (or two codes)

Let X be the set of words of length n (with letters drawn from any alphabet). Then d_H (w_1,w_2 )= the number of sites at which w_1 differs from w_2 By definition d_H is non-negative (and also ≤n)

Question 12

Induced Metrics

Answer 12

Let (X,d) be a metric space and let Y⊆X. Define

d_Y ∶ Y×Y∈R by d,Y(y,y ̅) = d(y,y ̅) .

Then (Y,d_Y) is a metric space. Note that if we think of the distance as a function from X×X to R the induced metric d_Y is the distance function restricted to the subset Y×Y⊆X×X. This is denoted d_Y= d|_(Y×Y).

Question 13

Triangle Inequality (Induced Metrics)

Answer 13

Let (X,d) be a metric space and let Z⊆Y⊆X. Let d_Y be the induced metric on Y from the metric d on X. Let d_(Z,Y) be the induced metric on Z from the metric d_Y on Y.

Let d(Z,X) be the induced metric on Z from the metric d on X. Then d_(Z,X) = d_(Z,Y).

Question 14

Sequence in a Set

Answer 14

A sequence in a set X is a map x∶ N→X. As a matter of notation we usually write x_n =x(n) and denote the sequence itself by (x_n) or (x_n)_(n∈N).

Question 15

Convergence of a Sequence

Answer 15

a_n→a if a_n becomes arbitrarily close to a as n tends to heuristic notion is that a_n . The mathematical formalisation of this is that a_n→a for every ϵ> 0 there is an N so that when n≥N then |a_n-a|≤ϵ .

1. An error tolerance ϵ> 0, “arbitrarily close” means any error tolerance so long as it is positive.
2. A way of measuring whether we are within the error tolerance. We are within the error tolerance if the distance|a_n-a|≤ϵ.
3. A threshold past which we must be within the error tolerance n≥N. Once we have met this threshold condition we must be within the error tolerance.

Question 16

Limit on a Metric Space

Answer 16

To define a limit on a metric. We will replace the a_n→a with d(a_n,a) and say that we have within the error tolerance if d(a_n,a)≤ϵ .

Question 17

d-convergence

Answer 17

1. The threshold N usually depends on ϵ. We sometimes denote that dependence by writing N_ϵ. This notation can be particularly useful in a complicated proof where we are tracking multiple dependencies.
2. To show convergence of a sequence it is not necessary to locate the smallest threshold N_ϵ for which n∈N implies d(x_n,x) . You need to find a threshold and show that it works.
3. It is not enough to show that you can find an N so that d(x_N,x)≤ϵ . You need to show that d(x_n,x)≤ϵ for any n∈N.

When talking about convergent sequences of real numbers we talk about the limit of (x_n). That is the limit is unique, the same is true for limits on metric spaces.

Question 18

Uniqueness of a Limit

Answer 18

Suppose that (x_n) is a convergent sequence on a metric space (X,d) then the limit of (x_n) is unique.
If
d(x,x_n ),d(y,x_n )≤ϵ/2
for N_1,N_2 respectively
N=max(N_1,N_2 )

d(x,y)≤d(x,x_n )+d(y,x_n )≤ϵ
x=y or d(x,y)=0

Question 19

Proof a Quantity is 0

Answer 19

If z∈R, z≥0 and z≤ϵ for every ϵ>0 then z =0

Question 20

d-convergence to 0

Answer 20

A sequence (x_n) is d-convergent to x in a metric space (X,d) if and only if y_n = d(x_n,x) converges to zero as sequence of real numbers.

Question 21

Convergence of a Finite Sequence

Answer 21

Suppose (X,d) is a metric space where X is finite(in the sense that X is a set of K<∞ elements). Let (x_n) be a sequence on (X,d) that d-converges to a point x∈X. Then there is an N∈N so that for n≥N, x_n=x.

Question 22

Cauchy Sequences

Answer 22

A sequence (x_n) on a metric space (X,d) is said to be Cauchy if, for every ϵ> 0 there is an N∈N so that if n,m∈N then
d(x_n,x_m)≤ϵ

Question 23

Sequential Completeness

Answer 23

All d-convergent sequences are cauchy, but not all cauchy sequnces a d-convergent.

Cauchy sequences that converge are sequentially complete metric spaces.

Question 24

Sequential Completeness of R

Answer 24

If (R,d_R) is sequentially complete then for any n∈N, (R^n,d_(R^n )) is sequentially complete.

Question 25

Open and Closed Sets

Answer 25

Open intervals do not contain their endpoints and closed intervals do contain their endpoints.

If the metric space is (R,d_R) and the subsets are intervals this extended concept of open/closed agrees with our the above understanding of open/closed intervals.

Question 26

Open Balls(Intervals)

Answer 26

Let (X,d)be a metric space. For r∈(0,∞) and x∈X we say that the open ball about x of radius r, B_r(x) is given by
B_r(x)= {z∈X│d(x,z) }

Question 27

Open Ball on a Metric Space

Answer 27

From open balls we progress to open sets by defining a set to be open if we can fit a ball around any point.

Let (X,d)be a metric space and Y⊆X.We say that Y is open in X if, for every y∈Y there is an ϵ>0 so that
B_ϵ (y)⊆Y.

The value of ϵ may (and usually does) depend on y∈Y.

Question 28

Complement of an Interval

Answer 28

For intervals I = (a,b) if we take the complement R\I of I we get a union of two closed intervals.

Conversely the complement of the closed interval [a,b] is a union of two open intervals.

Question 29

Closed Set on a Metric Space

Answer 29

Let (X,d) be a metric space and Y⊆X we say that Y is closed in X if X\Y is open in X.

Question 30

Properties of Openness and Closure

Answer 30

Let (X,d) be a metric space:

1. Any finite intersection of open sets is open.
2. Any arbitrary union of open sets is open.
3. Any arbitrary intersection of closed sets is closed.
4. Any finite union of closed sets is closed.

Question 31

Subsets of Finite Metric Spaces

Answer 31

Suppose (X,d) is a finite metric space (in the sense that X is a finite set). Then all subsets are open (and closed).

Question 32

Convergent Sequences in Subsets of Closed Sets

Answer 32

Let (X,d) be a metric space and Y⊆X. Then the following are equivalent:
1. Y is closed.
2. If (x_n) is a convergent sequence in X with all x_n∈ Y then lim┬(n→∞)⁡〖x_n 〗=x∈Y.

Question 33

Bounded Sets

Answer 33

|x|≤M for all x∈X
This cannot directly be translated to metric spaces.

Convergent (and Cauchy)
sequences give rise to bounded sets.

Question 34

Bounded Sets in Metric Spaces

Answer 34

Let (X,d) be a metric space. We say that Y⊆X is bounded if there exists an D∈R so that for all
x,y∈Y, d(x,y)≤D

We then say that D is a bound for Y. An equivalent way of defining a bounded set is to say that Y is bounded if the set {d(x,y)┤|x,y∈Y} is a bounded set in R.

Bounds are not unique.

Question 35

Bounded Sets and Cauchy Sequences

Answer 35

Let (x_n) be a Cauchy sequence. Define X = {x_n} (that is X is the set of points in the sequence). Then X is a bounded set.