Metric Spaces

Wikipedia (Metric space) · CC BY-SA 4.0

A metric space is a set X equipped with a function d : X × X → [0, ∞) that measures distance. Four axioms: d(x,y) ≥ 0 (non-negativity), d(x,y) = 0 iff x = y (identity of indiscernibles), d(x,y) = d(y,x) (symmetry), and d(x,z) ≤ d(x,y) + d(y,z) (triangle inequality). Every geometry you know is a special case.

The four axioms

A distance function (or metric) must satisfy four properties. These are not optional: drop any one and you get a different, weaker structure (pseudometric, quasimetric, semimetric). The triangle inequality is the one that does the most work. It says detours never shorten the trip.

Scheme

; A metric d must satisfy:
; 1. d(x,y) >= 0           (non-negativity)
; 2. d(x,y) = 0 iff x = y  (identity)
; 3. d(x,y) = d(y,x)       (symmetry)
; 4. d(x,z) <= d(x,y) + d(y,z) (triangle inequality)

; Euclidean distance in 2D
(define (euclidean p q)
  (let ((dx (- (car p) (car q)))
        (dy (- (cadr p) (cadr q))))
    (sqrt (+ (* dx dx) (* dy dy)))))

(define a (list 0 0))
(define b (list 3 4))
(define c (list 6 0))

(display "d(a,b) = ") (display (euclidean a b)) (newline)
(display "d(b,c) = ") (display (euclidean b c)) (newline)
(display "d(a,c) = ") (display (euclidean a c)) (newline)
(display "triangle: d(a,c) <= d(a,b) + d(b,c)? ")
(display (<= (euclidean a c)
             (+ (euclidean a b) (euclidean b c))))

Open balls

The open ball B(x, r) is the set of all points within distance r of x. Open balls are the building blocks of the topology induced by the metric. In Euclidean space they are circles. In taxicab space they are diamonds. The metric determines the shape of "nearness."

Four metrics on the same set

The same set of points can carry different metrics. Each metric defines a different notion of distance, different open balls, and different convergent sequences. The set does not change. The structure does.

Scheme

; Four metrics on pairs of real numbers

; 1. Euclidean: sqrt(dx^2 + dy^2)
(define (d-euclidean p q)
  (let ((dx (- (car p) (car q)))
        (dy (- (cadr p) (cadr q))))
    (sqrt (+ (* dx dx) (* dy dy)))))

; 2. Taxicab (Manhattan): |dx| + |dy|
(define (d-taxicab p q)
  (+ (abs (- (car p) (car q)))
     (abs (- (cadr p) (cadr q)))))

; 3. Chebyshev (L-infinity): max(|dx|, |dy|)
(define (d-chebyshev p q)
  (max (abs (- (car p) (car q)))
       (abs (- (cadr p) (cadr q)))))

; 4. Discrete: 0 if same, 1 otherwise
(define (d-discrete p q)
  (if (equal? p q) 0 1))

(define a (list 0 0))
(define b (list 3 4))

(display "Euclidean:  ") (display (d-euclidean a b)) (newline)
(display "Taxicab:    ") (display (d-taxicab a b)) (newline)
(display "Chebyshev:  ") (display (d-chebyshev a b)) (newline)
(display "Discrete:   ") (display (d-discrete a b))

Hausdorff distance

The Hausdorff distance measures how far apart two sets are. It is the greatest distance any point in one set has to travel to reach the other set. If H(A, B) = 0, the closures of A and B are equal. Hausdorff distance turns the collection of compact subsets of a metric space into a metric space itself.

Scheme

; Hausdorff distance between two finite point sets
; H(A,B) = max(sup_a inf_b d(a,b), sup_b inf_a d(a,b))

(define (d-euclidean p q)
  (let ((dx (- (car p) (car q)))
        (dy (- (cadr p) (cadr q))))
    (sqrt (+ (* dx dx) (* dy dy)))))

(define (min-dist point set)
  (apply min (map (lambda (q) (d-euclidean point q)) set)))

(define (directed-hausdorff A B)
  (apply max (map (lambda (a) (min-dist a B)) A)))

(define (hausdorff A B)
  (max (directed-hausdorff A B)
       (directed-hausdorff B A)))

; Two small sets
(define set-A (list (list 0 0) (list 1 0) (list 0 1)))
(define set-B (list (list 2 0) (list 3 0) (list 2 1)))

(display "H(A, B) = ") (display (hausdorff set-A set-B))
; Furthest any point in A must travel to reach B

Metric space as enriched category

A metric space is a category enriched over ([0, ∞], ≥, +). Objects are points. The hom-value from x to y is d(x, y). Identity says d(x, x) = 0. Composition says d(x, z) ≤ d(x, y) + d(y, z), which is exactly the triangle inequality. Lawvere noticed this in 1973: a metric space is what you get when you replace "arrows exist or not" (Bool-enriched) with "arrows have a cost" ([0, ∞]-enriched).

Scheme

; Metric space as enriched category:
; - Objects: points
; - hom(x,y) = d(x,y) in [0, inf]
; - Identity: d(x,x) = 0
; - Composition: d(x,z) <= d(x,y) + d(y,z)
;
; Compare with a Bool-enriched category (preorder):
; - hom(x,y) = #t or #f
; - Identity: hom(x,x) = #t
; - Composition: hom(x,y) AND hom(y,z) => hom(x,z)
;
; Replacing Bool with [0,inf] and AND with +
; and TRUE with 0, turns a preorder into a metric space.

(define (d p q)
  (let ((dx (- (car p) (car q)))
        (dy (- (cadr p) (cadr q))))
    (sqrt (+ (* dx dx) (* dy dy)))))

(define x (list 0 0))
(define y (list 1 1))
(define z (list 3 0))

; Identity law: d(x,x) = 0
(display "d(x,x) = ") (display (d x x)) (newline)

; Triangle inequality = composition law
(display "d(x,z) = ") (display (d x z)) (newline)
(display "d(x,y) + d(y,z) = ")
(display (+ (d x y) (d y z))) (newline)
(display "composition holds? ")
(display (<= (d x z) (+ (d x y) (d y z))))

Neighbors

Geometry chapters

△ Chapter 6 — Differential Geometry
△ Chapter 8 — Convex Geometry
∞ Real Analysis Ch.8 — metric spaces are the same objects, analyzed rather than visualized
🤖 ML Ch.5 — kernel methods use distance functions in feature space
⚙ Algorithms Ch.7 — shortest paths generalize Euclidean distance to discrete graphs

Cross-references

△ Analysis Ch.8 — metric spaces from the analysis side
△ Milewski Ch.22 — enriched categories (metric spaces are [0,∞]-enriched)

Foundations (Wikipedia)

Translation notes

The enriched-category perspective comes from Lawvere's 1973 paper "Metric spaces, generalized logic, and closed categories." Milewski covers enriched categories in chapter 22 of Category Theory for Programmers, where the running example is exactly this: Bool-enrichment gives preorders, [0,∞]-enrichment gives metric spaces. The Hausdorff distance example uses finite sets for computability; the general definition uses suprema over arbitrary sets.

← Differential Geometry by june.kim Convex Geometry →