| (no subject) |
[Nov. 20th, 2009|01:30 pm] |
Today I learned about a cute new variety of algebraic structure, the generalized ultrametric space, aka "gum space". It's just like an ultrametric space, (which in turn is just like a metric space with a stronger triangle inequality that says d(x,z) ≤ max(d(x,y), d(y,z)) rather than d(x,z) ≤ d(x,y) + d(y,z)) except instead of the metric d taking values in the nonnegative real numbers, you let it take values in some ol' poset-with-least-element.
A nice example of a gum space that is not trivially an ultrametric space is a collection of functions A → B whose "distance from one another" is just the subset of A on which they have different outputs. Here the powerset of A is standing in for R≥0 as the type of "how different can two things be" --- it's actually telling you how they're different, not just how much.
Formally (X, d, (P, ≤, 0)) is a gum space with underlying set X if (P, ≤, 0) is a poset with least element 0, and d : X × X → P has the properties
- (Zero) d(x,y) = 0 iff x = y
- (Symmetry) d(x,y) = d(y,x)
- (Ultrametric Inequality) if d(x,y) ≤ p and d(y,z) ≤ p, then d(x,z) ≤ p
Exercise: when P=R≥ 0 with the usual order, then the ultrametric inequality is the same thing as requiring d(x,z) ≤ max(d(x,y), d(y,z)).
However, and I think this is rather cute, there's still enough machinery in them to prove a standard contracting-map fixed point theorem.
Define a contracting map from one gum space to another to be a map f of the underlying sets such that d(f(x),f(y)) < d(x,y). Say a gum space is spherically complete if the intersection of any chain of balls in it is nonempty. (This condition is a stand-in for the usual notion of Cauchy-completeness)
Theorem (Priess-Crampe and Ribenboim '93) Any contracting map from a spherically complete gum space to itself has a unique fixed point.
Proof (I couldn't find the original paper, so I just reconstructed the following proof from some guesswork, hints in papers that cited it, and vague memories of seeing the Banach fixed point theorem in a topology class long ago) Uniqueness of the fixed point follows immediately from the contracting condition on the function, and the zero axiom of gum spaces.
For existence, make the following definitions. A pair (x,p) is a good pair if d(x,f(x)) ≤ p. We abuse notation and let a good pair (x,p) stand for the closed ball B(x,p). So for instance a set S of good pairs is a chain if the set of closed balls {B(x,p)|(x,p) ∈ S} is a chain in the usual sense. Consider the collection of all chains of good pairs in the space, ordered by inclusion. The union of any chain of chains is again a chain, so Zorn's lemma yields a maximum chain C. By spherical completeness, ∩C is nonempty. We argue by contradiction that any point in ∩C must be a fixed point. For suppose otherwise; we have x ∈∩C such that f(x) ≠ x. First of all, also f(x) ∈ ∩C. Why? Let any good pair (y,r) ∈ C be given. We know that x ∈ B(y,r) so d(x,y) ≤ r. Because f is contracting, d(f(x),f(y)) < r. Because (y,r) is a good pair, d(y,f(y)) ≤ r.
Putting these three facts together via the ultrametric inequality, d(x,f(x)) ≤ r, so f(x) ∈ B(y,r). Hence f(x) ∈ ∩C.
Now if we go just one step further iterating f on x, notice that d(f(x),f(f(x))) < d(x, f(x)) since f is contracting, so (f(x), d(f(x),f(f(x)))) is a good pair whose ball does not include x, yet is contained in every ball in C. (This claim tacitly uses the weird ultrametric-specific fact that every point in a ball is its center) We have refuted the maximality of C, QED. |
|
|
![[info]](http://l-stat.livejournal.com/img/userinfo.gif){kind=small}
jcreed's journal
