Quasi-isometry and the axiom of choice

In this post I give an inadequate review of the axiom of choice and explain the results contained in the paper On quasi-isometry and choice.

Some proofs in mathematics are nonconstructive in the sense that no obvious algorithm or pattern can be used to produce them.  When one is working with a well-ordered set then such a specified transfinite algorithm can usually be exhibited, but the production of such a well-order is itself often nonconstructive.  The axiom of choice is the assertion that given a nonempty collection of nonempty sets there exists a function such that , and is equivalent (modulo the Zermelo-Fraenkel axioms ZF) to the assertion that every set can be well-ordered.

In its earliest history (late 19th-early 20th century) the axiom was met with skepticism.  To the mathematician used to explicit constructions, the ability to create such an abstract function, or alternatively to produce a well-ordering of arbitrary sets, is a tremendous leap in intellectual certitude.  Worse still, the axiom produces objects in classical geometry which seem pathological.  For example, one can construct subsets of which are not Lebesgue measurable and do not have the property of Baire.  The Banach-Tarski paradox is another striking example of such pathology.  The axiom gained sympathy and acceptance as mathematicians realized that some earlier theorems were proved using its implicit use.  Also, many propositions which one would want to be true are demonstrably equivalent to the axiom of choice.  These include Tychonov’s Theorem (due to Kelley), every vector space has a basis (Blass), every connected simplicial graph contains a maximal tree, and Zorn’s Lemma.

A less well known statement equivalent to choice comes from coarse geometry.  If and are metric spaces, a function is a quasi-isometry if there exists such that and for all we have , where is the closed neighborhood .  Metric space is accordingly quasi-isometric to provided such a function exists.  This notion is used very frequently in geometric group theory, where selecting different finite generating sets for a finitely generated group may produce nonisometric Cayley graphs which are nevertheless quasi-isometric.  A composition of quasi-isometries is easily a quasi-isometry and the identity map is a quasi-isometry, so the relation is transitive and reflexive.

It is a standard exercise to show that quasi-isometry is also symmetric, but it is quickly realized that the axiom of choice is blatantly used in the “going backwards” map.  With some thought, one can cook up a situation in which a quasi-isometry going in the other direction produces a choice function.  Thus the symmetry of the quasi-isometry relation is equivalent (modulo ZF) to the axiom of choice.  This is somewhat harder to see if both spaces are geodesic hyperbolic.

Recall that a metric space is geodesic if for any two points there is an isometric embedding with and (the image of which is a geodesic segment). Geodesic segments need not be unique, but a choice of geodesic segment for points will be denoted .  A geodesic space is –hyperbolic if for any we have and is hyperbolic if it is -hyperbolic for some .  In the paper On quasi-isometry and choice it is shown that the claim that quasi-isometry is symmetric between geodesic hyperbolic spaces is equivalent to the axiom of choice (see Theorem 1).  This theorem is sharp since if both of the geodesic hyperbolic spaces are -hyperbolic (that is, are -trees) then symmetry follows from ZF alone, with no axiom of choice required (Theorem 3).  A so-called Bottleneck Theorem of Jason Fox Manning also implies the axiom of choice (Theorem 4).  I give a very brief sketch of how the proof goes.

Given a collection of nonempty sets one can produce a tree-like graph having at most two edges between vertices and no loop (edge from a vertex to itself).  The graph is -hyperbolic, has a root and one infinite “arm” protruding from the root for each .  If is a quasi-isometry from a simplicial tree to then one can prune to a subtree from which the restriction can be used to define a choice function.  The main difficulty in the proof lies in showing that the pruned satisfies key properties which make a selection from each unique.  Chasing natural number parameters is required.