Definitions Flashcards
A metric space (X, d)
Consists of a non-empty set X and a non-negative real valued metric d: X × X → R>
Satisifes the axioms:
- d(x, y) = 0 ⇐⇒ x = y for all x, y ∈ X
- d(x, y) = d(y, x) for all x, y ∈ X
- d(x, z) ≤ d(x, y) + d(y, z) for all x, y, z ∈ X (triangle inequality)
Known informally as a distance function .
Subspace
Given any subset W ⊆ X, the restriction of d to W determines the subspace (W, d := d|W ) of (X, d)
Open and closed balls
For any metric space (X, d), the open ball and closed ball of radius r > 0 around a point x ∈ X are the subspaces:
Br(x) := {y : d(y, x) < r} and
_
Br(x) := {y : d(y, x) ≤ r} ⊆ X
respectively.
Euclidean n-space (R^n, d2)
Euclidean n-space (R^n, d2) consists of all real n-dimensional vectors:
x = (x1, . . . , xn)
Isometry
For any two metric spaces (X, dX) and (Y, dY ), a Bijection
f : X → Y is an isometry whenever:
dX(x, y) = dY (f(x), f(y)) for all x, y ∈ X
A graph Γ := (V, E)
A graph Γ := (V, E) consists of a set V of vertices , and a set E of edges.
Each edge vw ∈ E may be interpreted as joining two vertices v, w ∈ V
A path in Γ
The length of a path
A path in Γ from u to w is a finite sequence of edges:
π(u, w) = (uv_1, v_1v_2, . . . , v_(n−2)v_(n−1), v_(n−1)w)
Such a path has length `(π(u, w)) = n
Path connected
A graph is path connected whenever there is a path joining any pair of vertices
Edge metric e
The edge metric e on the vertex set V of a path connected graph is defined by:
e(u, w) = min_(π(u,w)) L(π(u, w))
Alphabet
An alphabet is a finite set A of letters
Word
A finite sequence of letters is a word in A; if A := {a, b, c, o, t}, then words include act, boat, and obbbt
Word graph
The vertex set W of the associated word graph Γ(A)
consists of all possible words in A.
Words w1 and w2 are joined by an edge iff they differ by one of:
- inserting or deleting a letter
- swapping two adjacent letters
- replacing one letter with another
Word Metric
The word metric dw on W is the edge metric on the associated word graph.
ex:
dw(act,boat) = 3
act, bact, baot, boat
Binary sequences
X = {0, 1}^∞ is the set of all infinite binary sequences x = x_0x_1 . . . ,
x_n = 0 or 1 for all n ≥ 0
x = 1100010 . . . is a typical element
Bounded
A real-valued function f on a closed interval [a, b] ⊂ R is bounded whenever
there exists a constant K such that |f(x)| ≤ K for every x ∈ [a, b]
Real polynomial of degree n
a(x) = a_nx^n + · · · + a_1x + a_0
Cartesian product of two metric spaces (X, d) and (X’,d’)
The cartesian product of two metric spaces (X, d) and (X’,d’) is the set X × X’
equipped with one of the metrics:
- d_a((x, x’),(y, y’)) = d(x, y) + d’(x’, y’)
- d_b((x, x’),(y, y’)) = [ d(x, y)^2 + d’(x’, y’)^2 ]^1/2
- d_c((x, x’),(y, y’)) = max{d(x, y), d’(x’, y’)}
for any x, y ∈ X and x’, y’ ∈ X’
.
Lipschitz equivalent
Two metrics d and e on a given set X are Lipschitz equivalent whenever there exist positive constants h, k ∈ R such that:
he(x, y) ≤ d(x, y) ≤ ke(x, y)
for every x, y in X
An interior point U ⊆ X
An interior point u ∈ U is one for which there exists e > 0 such that B_e(u) ⊆ U
The interior of U
The interior of U is the subset U◦ ⊆ U of all interior points
U is open in X
U◦ = U
A closure point of U ⊆ X
A point x ∈ X is a closure point of U ⊆ X if B_e(x) ∩ U is
non-empty for every u > 0; If U = U, then U is closed in X
The closure of U
The closure of U is the superset:
_
U ⊇ U of all closure points
U is closed in X
_
U = U
A partially open ball in X
A set Pr(x):= Br(x) ∪ P, where P is a proper subset of {p : d(x, p) = r}
A sequence (x_n) converges
A sequence (x_n) converges to the point x ∈ X whenever
∀e > 0, ∃N ∈ N such that n ≥ N ⇒ d(x, x_n) < e;
in this situation, x is known as the limit of (x_n)
∀e > 0, ∃N ∈ N such that n ≥ N ⇒ x_n ∈ B_e(x).
Cauchy sequence
In any metric space (X, d), a Cauchy sequence (x_n) satisfies ∀e > 0, ∃N ∈ N such that m, n ≥ N ⇒ d(x_m, x_n) < e
Dense
A subset Y is dense in (X, d) whenever Y = X
Bounded
A subset A of a metric space (X, d) is bounded whenever there exists x_0 ∈ X and M ∈ R such that d(x, x_0) ≤ M for every x ∈ A
A function f : S → X is bounded whenever its image f(S) ⊂ X is a bounded, for any set S
Diameter
The diameter diam(A) of a bounded non-empty subset A ⊆ X is the real number sup{d(x, y) : x, y ∈ A}
Boundary point
A boundary point x ∈ X of A is one for which every open ball B_e(x) meets both A and X \ A; the boundary ∂A of A is the set of all such boundary points
The boundary
The boundary ∂A of A is the set of all such boundary points
