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 \mathcal{Z} of nonempty sets there exists a function f: \mathcal{Z} \rightarrow \bigcup \mathcal{Z} such that f(X) \in X, 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 \mathbb{R} 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 imply 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 (S, d_S) and (T, d_T) are metric spaces, a function f:S \rightarrow T is a quasi-isometry if there exists N\in \omega such that B(f(S), N) = T and for all x,y\in S we have \frac{1}{N}d_S(x, y) - N \leq d_T(f(x), f(y)) \leq Nd_S(x, y) +N, where B(J, p) is the closed neighborhood \{x\in T: d_T(x, J) \leq p\}.  Metric space (S, d_S) is accordingly quasi-isometric to (T, d_T) 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 S is geodesic if for any two points x,y\in S there is an isometric embedding \rho:[0, d_S(x,y)] \rightarrow S with \rho(0) = x and \rho( d_S(x,y)) = y (the image of which is a geodesic segment). Geodesic segments need not be unique, but a choice of geodesic segment for points x, y \in S will be denoted [x,y].  A geodesic space S is \deltahyperbolic if for any x,y,z\in S we have [x,y]\subseteq B([x,z]\cup[y,z], \delta) and is hyperbolic if it is \delta-hyperbolic for some \delta.  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 0-hyperbolic (that is, are \mathbb{R}-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 \mathcal{Z} of nonempty sets one can produce a tree-like graph \Gamma having at most two edges between vertices and no loop (edge from a vertex to itself).  The graph \Gamma is 2-hyperbolic, has a root and one infinite “arm” protruding from the root for each X\in \mathcal{Z}.  If f: T \rightarrow \Gamma is a quasi-isometry from a simplicial tree T to \Gamma then one can prune T to a subtree T' \subseteq T from which the restriction f \upharpoonright T' can be used to define a choice function.  The main difficulty in the proof lies in showing that the pruned T' satisfies key properties which make a selection from each X\in \mathcal{Z} unique.  Chasing natural number parameters is required.

Limiting theories

First order logic has provided useful tools to mathematicians over the last several decades.  We give some general motivation for interest in the first order theory of a structure, give some illuminating examples, and discuss some new results which are spelled out in Limiting theories of substructures.

One of the overarching themes in mathematics is to understand when two mathematical structures are essentially “the same.”  This sameness is often characterized by the existence of a bijection between the elements of the structures which preserves the essential characteristics of the structures.  Homeomorphisms of topological spaces, isometries of metric spaces, isomorphisms of groups (rings, fields, algebras, etc.), and order preserving bijections between ordered spaces are examples.  It is useful to produce characteristics (invariants) of a structure which are preserved under a map which witnesses sameness.  Invariants give sufficient conditions from which one may assert that two structures are not the same.  For example, a topological space with two path components cannot be homeomorphic to a space which has one.  Having a point named x is not a homeomorphism invariant.  The most naïve invariant of a structure is its cardinality, for if sameness is characterized via a bijection then structures of differing cardinality cannot be the same.

Another invariant of a structure is its first order theory.  Without getting into the gory details of languages, well-formed formulas and sentences, the first order theory of a structure is essentially the set of finitary logical sentences which are true of the structure.  It will hopefully suffice to give some examples of structures and first order sentences satisfied by them.  We let Th(\mathcal{S}) denote the first order theory of a structure \mathcal{S}.

We consider a group G as a set with binary operation *, unary inverse operation ^{-1}, and nullary operation 1 which satisfies the standard requirements that define groups: (\forall x)[x*1 = 1*x = x] , (\forall x)[x*x^{-1} = x^{-1}*x = 1] , and (\forall x)(\forall y)(\forall z)[x*(y*z) = (x*y)*z] .  For abelian groups the binary operation is often denoted + and the nullary operation is often denoted 0.  The two element abelian group \mathbb{Z}/2\mathbb{Z} satisfies the requirements for a group as well as the sentences

  1. (\forall x)[x+x = 0]
  2. (\exists x)(\exists y)[x\neq y]
  3. \neg (\exists x)(\exists y)(\exists z)[x\neq y \wedge x\neq z\wedge y\neq z]

Sentence 1 states that all elements have order at most two, sentence 2 states that there are at least two elements, and sentence 3 states that there are not three elements.  Any group of exactly two elements is isomorphic to \mathbb{Z}/2\mathbb{Z}.  More generally the first order theory of a finite group totally determines its isomorphism class: if G is a finite group and Th(G) = Th(H) then G is isomorphic to H.  This is because one can spell out the multiplication table of a group using a finitary sentence.  Letting G = \{g_0, g_2, \ldots, g_{n-1}\} and f: n\times n \rightarrow n be defined by g_i*g_j = g_{f(i, j)}, the following sentence totally determines G up to group isomorphism:

(\exists x_0)(\exists x_1) \cdots (\exists x_{n-1})[\bigwedge_{0\leq i, j<n}x_i*x_j = x_{f(i, j)}]\wedge \neg (\exists x_0)(\exists x_1) \cdots (\exists x_n)[\bigwedge_{0\leq i<j<n+1}x_i \neq x_j]

We have seen that first order logical sentences can express ideas like “there exist n elements” or “there do not exist n elements.”  Some other concepts that can be expressed using first order logic are: “every element is twice an element” (which would allow you to distinguish the group \mathbb{Q} from \mathbb{Z}), “there exists a non trivial element of order two” (which allows you to distinguish \mathbb{Z} \oplus (\mathbb{Z}/2\mathbb{Z}) from \mathbb{Z}), and “the group is nilpotent of height n.”  Thus, many algebraic properties may be expressed using first order logic and it might seem that first order logic can be used to distinguish any two nonisomorphic groups.  It turns out that this latter sentiment is not only false but extraordinarily false.  We’ll state a corollary to what is called the Upward Löwenheim-Skolem Theorem:

Corollary If a structure \mathcal{S} utilizes only countably many non-logical symbols and has countably-infinitely many elements then for every infinite cardinal number \kappa there exists a structure \mathcal{S}' having exactly \kappa elements such that Th(\mathcal{S}) = Th(\mathcal{S}').

Continuing our group theory examples, we note that groups have only finitely many non-logical symbols- the binary operation symbol, the inverse symbol, and the group identity symbol.  Thus by this corollary, for any countably infinite group G there exist groups of all infinite cardinalities which have the same first order theory (most of which are clearly not isomorphic to G.)  For example, there exist uncountable groups which have the same first order theory as the infinite cyclic group \mathbb{Z}.  This highlights that the property “being infinite cyclic” cannot be expressed using first order logic, since cyclic groups must be countable.

We move to a discussion of direct limits and of how the theories of a system of substructures can limit to the theory of the large structure.  Recall that a directed set I is a partially ordered set such that for any i_0, i_1\in I there exists i_2\in I with i_2 \geq i_0, i_1.  Let \mathcal{S} = (S, F, R) be a structure (S is the set of elements, F is the set of functions and R is the set of relations).  We’ll say for the purposes of this discussion that a collection \{\mathcal{S}_i\}_{i\in I} of substructures of \mathcal{S} has direct limit \mathcal{S} if \bigcup_{i\in I}S_i = S and i_0 \leq i_1 implies S_{i_0} \subseteq S_{i_1}.  In such a situation, since the non-logical symbols in F \cup R are the same for \mathcal{S} as for its distinguished substructures \mathcal{S}_i, it is natural to compare Th(\mathcal{S}) to Th(\mathcal{S}_i) for each i\in I.  It might be that Th(\mathcal{S}) is precisely the same as each Th(\mathcal{S}_i), but it is often the case that the theory of the large structure is different from that of each of the substructures.  For example, if \mathcal{S} has infinitely many elements and each of the \mathcal{S}_i has only finitely many elements, then Th(\mathcal{S}) \neq Th(\mathcal{S}_i) since first order sentences can distinguish a finite structure from an infinite.  Even so, it may be that the theories Th(\mathcal{S}_i) get closer and closer to Th(\mathcal{S}) in a way that we make explicit.

Let Sent(F\cup R) be the set of all first order sentences which can be made using functions in F and/or relations in R.  Thus Th(\mathcal{S}) \subseteq Sent(F \cup R) and for any \theta\in Sent(F\cup R) it is either the case that \theta\in Th(\mathcal{S}) or that \neg \theta \in Th(\mathcal{S}), and similar statements hold for Th(\mathcal{S}_i).  Let

\limsup_I Th(\mathcal{S}_i) = \{\theta \in Sent(F\cup R): (\forall j\in I)(\exists i \geq j)[\theta \in Th(\mathcal{S}_i)]\}

\liminf_I Th(\mathcal{S}_i) = \{\theta \in Sent(F\cup R): (\exists j\in I)(\forall i \geq j)[\theta \in Th(\mathcal{S}_i)]\}

Clearly the inclusion \liminf_I Th(\mathcal{S}_i) \subseteq \limsup_I Th(\mathcal{S}_i) holds, and if \liminf_I Th(\mathcal{S}_i) =\limsup_I Th(\mathcal{S}_i) we write \lim_I Th(\mathcal{S}_i)  = \liminf_I Th(\mathcal{S}_i) =\limsup_I Th(\mathcal{S}_i) and say that the limit \lim_I Th(\mathcal{S}_i) exists.  We illustrate with some examples.

Example 1  Consider the structure \mathcal{S} = (\mathbb{N}, \leq, E) where \leq is the standard ordering on \mathbb{N} and Ex if and only if x is even.  The finite substructure \mathcal{S}_n whose set of elements is \{0, 1, \ldots, n\} satisfies the sentence (\exists x)[Ex\wedge (\forall y)[y\leq x]] if and only if n is even.  Letting I = \mathbb{N} under the natural ordering it is clear that \mathcal{S} is the direct limit of the \mathcal{S}_n.  We see that \liminf_I Th(\mathcal{S}_i) is strictly included in \limsup_I Th(\mathcal{S}_i) and the limit \lim_I Th(\mathcal{S}_i) does not exist.

Example 2  Consider the abelian group structure \mathcal{S} = (\mathbb{Q}, +, -, 0).  Let \{p_0, p_1, \ldots\} be an enumeration of the prime numbers and for each n\in \mathbb{N} let \mathcal{S}_n be the subgroup generated by \frac{1}{(p_0p_1\cdots p_n)^n}.  Again \mathcal{S} is the direct limit of the \mathcal{S}_n.  Each \mathcal{S}_n is isomorphic to the group \mathbb{Z} and so certainly the limit \lim_I Th(\mathcal{S}_i) exists since Th(\mathcal{S}_n) is constant.

Example 3  Consider the structure \mathcal{S} = (\mathbb{R}, \leq) where \leq is the standard ordering on \mathbb{R}.  Let I = \{A \subseteq \mathbb{R}: \mathbb{Q} \subseteq A, |A|= \aleph_0\}.  Clearly I is a directed set under set inclusion, and letting \mathcal{S}_A be the substructure having A as its elements it is clear that \mathcal{S} is the direct limit of \{\mathcal{S}_A\}_{A\in I}.  Each structure \mathcal{S}_A, and also \mathcal{S}, is a nonempty dense linear order with no first or last point, and it is classically known that all such structures have the same first order theory.  Thus \lim_I Th(\mathcal{S}_A) exists.

So far we have seen an example where the first order theory of the substructures did not have a limit, an example where the first order theory of the substructures did have a limit which was not equal to the theory of the large structure (since Th((\mathbb{Q}, +. -, 0)) \neq Th((\mathbb{Z}, +, -, 0)) ), and an example where the first order theories of the substructures have a limit which is equal to the theory of the large structure.  We give a theorem which gives sufficient conditions under which the theories of substructures has a limit, and under which the limit of their theories is equal to the theory of the large structure (see Theorem A in Limiting theories of substructures):

Theorem  Suppose \{\mathcal{S}_i\}_{i\in I} is a collection of substructures of \mathcal{S} such that \mathcal{S} is the direct limit of \{\mathcal{S}_i\}_{i\in I}.

(1) If for each finite set of constants a_1, \ldots, a_m\in S there exists an i\in I such that for j \geq i and b_1, \ldots, b_m \in S_j there exists an automorphism f:\mathcal{S}_j \rightarrow \mathcal{S}_j fixing each a_l and such that f(\{a_1, \ldots, a_m, b_1, \ldots, b_m\}) \subseteq S_i the limit \lim_I Th(\mathcal{S}_i) exists.

(2) If in addition to (1) for each finite set of constants a_1, \ldots, a_m\in S there exists an i\in I such that for b_1, \ldots, b_m \in S there exists an automorphism f:\mathcal{S} \rightarrow \mathcal{S} fixing each a_l and such that f(\{a_1, \ldots, a_m, b_1, \ldots, b_m\}) \subseteq S_i then \lim_I Th(\mathcal{S}_i) = Th(\mathcal{S}).

What we have stated is a bit weaker than the statement of Theorem A in Limiting theories, but it is sufficient for our discussion.  The theorem is proved in a more general setting, by induction on the number of quantifiers used in a sentence.  This result can obviously be applied only in settings where structures have many automorphisms, that is, structures where there are automorphisms which can fix some prescribed finite subset and move some other finite subset into a designated structure.  For example, in a structure which is simply an infinite set (no non-logical symbols), the hypotheses of both conditions (1) and (2) apply to the substructure net of finite subsets and we get that the theory of an infinite set is the limit of the theories of increasingly large finite sets.  Similar conclusions regarding infinite abelian groups of prime exponent p and infinite rank free abelian groups can be made.  Moreover, the fact that the theory of a finite set is never equal to that of an infinite yields a new proof of the classical result that the theory of an infinite set is not finitely axiomatizable (this can otherwise be proved using either the Compactness Theorem or quantifier elimination).  Similarly, the first order theory of an infinite abelian group of prime exponent p and the first order theory of an infinite rank free abelian group are not finitely axiomatizable.

Analyzing a fundamental group using basic descriptive set theory (Part 3)

In this third and final installment I’ll provide some more theorems regarding the fundamental group and first homology that can be derived using descriptive set theory.  We have already seen in Part 2 that there are quick and easy dichotomies that can be drawn using either selection theorems from logic or a diagonalization using the Baire category theorem.  By working a little harder we get the following results, which can be interpreted as compactness theorems (see On definable subgroups of the fundamental group Theorem B, and On subgroups of first homology Theorem 4,  respectively):

Theorem 3.1  If X is a Peano continuum there does not exist a strictly increasing sequence of analytic normal subgroups \{G_n\}_{n\in \omega} of \pi_1(X) such that \bigcup_{n\in \omega} G_n = \pi_1(X).

Theorem 3.2  If X is a Peano continuum with H_1(X) of cardinality < 2^{\aleph_0} there exists \epsilon>0 and N\in \omega such that any loop of diameter <\epsilon is of commutator length \leq N.

Theorem 3.1 implies that for X a Peano continuum, if there is no finite subset S\subseteq \pi_1(X) such that the normal closure \langle\langle S\rangle\rangle is \pi_1(X), then for any countable S \subseteq \pi_1(X) we again have \langle\langle S\rangle\rangle \neq \pi_1(X).  There exist Peano continua with uncountable fundamental group which is normally generated by one element, and there exist Peano continua which are not finitely (ergot not countably) normally generated.  Theorem 3.1 has numerous other applications to first homology (see On subgroups of first homology).  For Theorem 3.2 we recall that the commutator length of an element g of a group G is the smallest number n such that g may be written as a  product of n commutators, and defined to be \infty provided g is not in the derived subgroup of G.  One can understand Theorem 3.2 by its contrapositive: if there are arbitrarily small loops of arbitrarily high commutator length, then first homology is of cardinality 2^{\aleph_0}.  This is a strengthening of a result of Greg Conner and myself: a Peano continuum has first homology of cardinality 2^{\aleph_0} if there exist arbitrarily small loops of infinite commutator length (see On the first homology of Peano continua).

These ideas also lend themselves to very simple characterizations of topologically defined subgroups of the fundamental group.  For example, the shape kernel of a path connected space X is the intersection of the kernels of all maps to nerves over X.  Thus, the shape kernel represents the set of loops which unavoidably perish when one maps to a simplicial complex.  One gets the following characterization of this subgroup under some mild assumptions (see Definable, Theorem 5.1):

Theorem 3.3  If X is a metric space which is path connected, locally path connected then the shape kernel is the intersection of all open normal subgroups of \pi_1(X).

This gives one a very short, clean proof of the following (ibid Theorem 5.4):

Theorem 3.4  If X is a metric space which is path connected, locally path connected then the shape kernel is equal to the Spanier group.

This is a slightly weaker result than that of Brazas and Fabel (see their work Thick Spanier groups and the first shape group), where they give the same conclusion and instead of “metric” they assume “paracompact.”

One can cook up easy examples of fundamental groups which have a “nonconstructive” decomposition into a direct sum.  For example, by taking a countably infinite product of projective places one obtains a Peano continuum X which has fundamental group isomorphic to \prod_{\omega} \mathbb{Z}/2.  It is not difficult to find subgroups G and H such that \pi_1(X) = G\oplus H and G is not Borel, analytic, or anything close to nice.  The situation with free product decompositions is much nicer (Definable, Theorem C):

Theorem 3.5  Suppose X is path connected locally path connected Polish and \pi_1(X) \simeq *_{i\in I}G_i with each G_i nontrivial.  The following hold:

  1. |I| \leq \aleph_0
  2.  Each retraction map r_j:*_{i\in I}G_i \rightarrow G_j has analytic kernel.
  3.  Each G_j is of cardinality \leq \aleph_0 or 2^{\aleph_0}.
  4.  The map *_{i\in I} G_i \rightarrow \bigoplus_{i\in I} G_i has analytic kernel.

Local path connectedness cannot be dropped from the hypotheses, else one can violate the first three conditions.

Certain decompositions into products also behave nicely.  Recall that a group G is noncommutatively slender group if for any homomorphism from the fundamental group of the Hawaiian earring \phi:  \pi_1(E) \rightarrow G there exists N\in \omega such that \phi \circ p_N = \phi (here p_N is the induced retraction to the outer N circles).  In other words, any homomorphism from the fundamental group of the Hawaiian earring to a noncommutatively slender group kills all circles of sufficiently small size.  Free groups, free abelian groups, Thompson’s group F, Baumslag-Solitar groups and torsion-free word hyperbolic groups are examples of noncommutatively slender groups (see A note on automatic continuity).  We have the following:

Theorem  3.6  If X is a path connected, locally path connected \kappa-Lindelof metric space and \{G_i\}_{i\in I} is a collection of nontrivial noncommutatively slender groups with |I| >\kappa then there is no epimorphism \phi:\pi_1(X) \rightarrow \prod_{i\in I} G_i.


If one assumes the generalized continuum hypothesis then the noncommutative slenderness of the groups can be dropped, since the product \prod_{i\in I} G_i would simply be of higher cardinality than the set of all loops in the space X.  However the noncommutative slenderness cannot be dropped in general: in a universe where 2^{\aleph_0} = 2^{\aleph_1} you can take X to be the countably infinite product of projective planes and notice that \pi_1(X) \simeq \prod_{\omega} \mathbb{Z}/2 \simeq \bigoplus_{2^{\aleph_0}} \mathbb{Z}/2 \simeq \prod_{\aleph_1} \mathbb{Z}/2.

I’ll conclude by noting that extra set theoretic assumptions can enhance the results that one derives.  Hypotheses about analyticity of a subgroup of a fundamental group can be relaxed (in the statement of Theorem 3.1, for example) to be \Sigma_2^1 or \Sigma_3^1 or whatever other semi-algebra is guaranteed to be in the algebra of subsets satisfying the property of Baire.

Analyzing a fundamental group using basic descriptive set theory (Part 2)

In this installment I’ll give a brief review of some fundamental concepts of descriptive set theory.  For further information I recommend A Course on Borel Sets by Srivastava, or Classical Descriptive Set Theory by Kechris.  Some results about subgroups are then outlined.

Descriptive set theory is the study of subsets of a nice space that have a topological description.  The nice space is generally Polish (separable, completely metrizable.)  One of the initial motivating questions in descriptive set theory was the continuum hypothesis- the question of whether there exists an uncountable set of cardinality less than 2^{\aleph_0}.  Cantor was able to show that a closed subset of the real line cannot be a counterexample to the continuum hypothesis (this follows from the Cantor-Bendixson theorem).  What the proof really shows is that no Polish space can be a counterexample to the continuum hypothesis (topology hadn’t come into its own at this point, and so Polish spaces as such weren’t yet a subject of study).  To describe further results will require more definitions.

Recall that a \sigma-algebra on a set X is a subset of the powerset of X which contains X and is closed under countable unions and under complementation.  By considering the intersection of all \sigma-algebras containing a collection of subsets of X, we see that for any collection of subsets of X  there is a minimal \sigma-algebra containing that collection.  If X is a topological space we let \mathcal{B}(X) denote the class of Borel sets– the smallest \sigma-algebra containing the open subsets of X.  Thus open sets, closed sets, countable unions of closed sets, etc.,  are Borel sets.  When X is a metric space, the open sets are a countable union of closed sets and the closed sets are a countable intersection of open sets.  In this case the Borel sets can be arranged into a nice hierarchy of complexity classes.  Let \Sigma_1^0(X) denote the collection of open sets (the topology) of X, \Pi_1^0(X) denote the collection of closed subsets and \Delta_1^0(X) denote the set of clopen subsets.  For 1< \alpha< \omega_1 we let \Sigma_{\alpha}^0(X) denote the collection of countable unions of sets in \bigcup_{\beta<\alpha} \Pi_{\beta}^0(X), \Pi_{\alpha}^0(X) denote the collection of countable intersections of sets in \bigcup_{\beta<\alpha} \Sigma_{\beta}^0(X), and \Delta_{\alpha}^0(X) = \Sigma_{\alpha}^0(X) \cap \Pi_{\alpha}(X).  A transfinite induction shows that \bigcup_{\alpha< \omega_1}\Sigma_{\alpha}^0(X) = \bigcup_{\alpha<\omega_1}\Pi_{\alpha}^0(X) = \bigcup_{\alpha<\omega_1}\Delta_{\alpha}^0(X) \subseteq \mathcal{B}(X), and \mathcal{B}(X) \subseteq \bigcup_{\alpha<\omega_1} \Sigma_{\alpha}^0(X) is seen by proving that \bigcup_{\alpha<\omega_1} \Sigma_{\alpha}^0(X) is a \sigma-algebra.  These complexity classes arrange nicely into an array, with inclusions going left:


\begin{matrix} & & \Sigma_1^0(Z) & & &  \Sigma_2^0(Z) &  & \cdots & & \Sigma_{\alpha}^0(Z) \\ \\ \\ \Delta_1^0(Z) & & & &\Delta_2^0(Z)   & \cdots & & \Delta_{\alpha}^0(Z)\\ \\ \\ & & \Pi_1^0(Z) & & &  \Pi_2^0(Z)  & & \cdots & & \Pi_{\alpha}^0(Z)  \end{matrix}


For example \Pi_{\alpha}^0(Z)\subseteq \Delta_{\alpha+1}^0(Z).

Polish spaces are either finite (and therefore discrete), countable, or of cardinality 2^{\aleph_0}.  In case a Polish space is countable we know that every subset is a \Sigma_2^0 as a countable union of singletons, and thus the Borel hierarchy stabilizes and is not especially interesting.  In case a Polish space is uncountable we get a non-stabilizing hierarchy, with strict containments going left (i.e. \Pi_{\alpha}^0\subsetneq \Delta_{\alpha+1}^0.)  In a Polish space, all Borel sets are either countable (including finite) or contain a homeomorph of the Cantor set.  For example, no Borel subset of \mathbb{R} can violate the continuum hypothesis.

While Borel sets are closed under many set-theoretic operations, they are not closed under continuous images.  There exist Polish spaces X, Y, a closed subset Z \subseteq X, and a continuous function f: X \rightarrow Y such that f(Z) is not Borel in Y.  Such a set is called analytic, and the class of analytic sets is denoted \Sigma_1^1.  The class consisting of complements of analytic sets is denoted \Pi_1^1, and we denote \Delta_1^1 = \Sigma_1^1\cap\Pi_1^1.  Since the identity map is continuous we see that every Borel set in a Polish space is \Delta_1^1.  That all \Delta_1^1 sets are Borel is a theorem of Souslin (Sur une definition des ensembles B sans nombres transfinis, C. R. Acad. Sciences, Paris, 164 (1917), 88-91.)  The notation suggests that we will define a hierarchy, in this case we shall only use subscripts in the natural numbers and not in all of \omega_1.  If \Delta_n^1, \Sigma_n^1, \Pi_n^1 have been defined for all n<m we let \Sigma_m^1 denote the class of continuous images of sets in \Pi_{m-1}^1, \Pi_m^1 is the class of complements of sets in \Sigma_m^1 and \Delta_m^1 = \Sigma_m^1 \cap \Pi_m^1.  A similar arrangement, with strict inclusions in case the Polish space is uncountable, holds for these so called projective pointclasses:


\begin{matrix} & & \Sigma_1^1 & & & & \Sigma_2^1 & & \cdots\\ \\ \\ \Delta_1^1 & & & &\Delta_2^1 & & \cdots\\ \\ \\ & & \Pi_1^1 & & & & \Pi_2^1 & & \cdots  \end{matrix}

As some points of interest, \Sigma_1^1 sets are either countable or include a homeomorph of the Cantor set, and so are never a counterexample to the continuum hypothesis.  The \Sigma_1^1, and therefore also the \Pi_1^1, subsets of \mathbb{R} are always Lebesgue measurable.  The \Pi_1^1 sets may be countable, of cardinality \aleph_1, or of cardinality 2^{\aleph_0} and there exist models of ZFC modelling \aleph_1< 2^{\aleph_0} in which there exists a \Pi_1^1 set of cardinality \aleph_1.  Other strange phenomena happen further up the hierarchy in various models of ZFC.

Let’s move on to some information on subgroups.  We shall assume X is a path connected Polish space for what follows and sometimes add additional hypotheses when stating theorems.  Recall that a subgroup G\leq \pi_1(X, x) is open, closed, Borel, etc. provided the set of loops \bigcup G is an open, closed, Borel, etc. subset of the loop space L_x under the \sup metric.  We first notice that many of the very natural subgroups of \pi_1(X, x) are analytic (we state a specialization of Theorem 3.10 in On definable subgroups of the fundamental group):

Proposition 2.1 Let f:(X, x) \rightarrow (Y, y) be a continuous function between Polish spaces.  The following hold:

  1. If H\leq \pi_1(Y, y) is \Sigma_1^1 then f_*^{-1}(H)\leq \pi_1(X, x) is \Sigma_1^1.
  2. If G\leq \pi_1(X, x) is \Sigma_1^1 then f_*(G)\leq \pi_1(Y, y) is \Sigma_1^1.
  3. The subgroups 1 and \pi_1(X, x) are analytic in \pi_1(X, x).
  4. If G_n \leq \pi_1(X, x) are \Sigma_1^1 then so are \displaystyle\bigcap_{n\in \omega} G_n and \displaystyle\langle \bigcup_{n\in \omega} G_n \rangle.
  5. Countable subgroups of \pi_1(X, x) are \Sigma_1^1.
  6. If G\leq \pi_1(X, x) is \Sigma_1^1 then so is \langle \langle G \rangle\rangle.
  7. If G\leq \pi_1(X,x) is \Sigma_1^1 then so is any conjugate of G.
  8. If w(x_0, \ldots, x_k) is a reduced word in the free group F(x_0, \ldots, x_k) and the groups G_0, \ldots, G_k \leq \pi_1(X, x) are \Sigma_1^1 then so is the subgroup \langle \{w(g_0, g_1, \ldots, g_k)\}_{g_i \in G_i}\rangle.
  9. If G, H \leq \pi_1(X, x) are \Sigma_1^1 then so is the subgroup [G, H].
  10. If G\leq \pi_1(X, x) is \Sigma_1^1 then each countable index term of the derived series G^{(\alpha)} and each term of the lower central series G_n is \Sigma_1^1.

Here are some more theorems (also from On definable subgroups of the fundamental group):

Proposition 2.2 Let G \leq \pi_1(X,x).

  1. If G is \Pi_1^1 then the index [\pi_1(X,x):G] is either \leq \aleph_0 or 2^{\aleph_0}.
  2. If G is \Sigma_1^1 then the index [\pi_1(X, x):G] is either \leq \aleph_1 or 2^{\aleph_0}.

Theorem 2.3 Suppose X is locally path connected. The following groups are of cardinality 2^{\aleph_0} or \leq \aleph_0, and in case X is compact they are of cardinality 2^{\aleph_0} or are finitely generated:

  1. \pi_1(X)
  2. \pi_1(X)/(\pi_1(X))^{(\alpha)} for any \alpha<\omega_1 (derived series)
  3. \pi_1(X)/(\pi_1(X))_n for any n\in \omega (lower central series)
  4. \pi_1(X)/N where N is the normal subgroup generated by squares of elements, cubes of elements, or n-th powers of elements, or is simply any \Sigma_1^1 normal subgroup

In case X is compact then countability of the fundamental group is equivalent to being finitely presented.

Some general remarks about these results are in order.  Proposition 2.1 is verified using direct computation of topological complexity.  Proposition 2.2 follows from a theorem of Burgess and a theorem of Silver.  Theorem 2.3 is proved using Baire category.  I give an example in Definable subgroups of a compact path connected subspace F of \mathbb{R}^2 for which there exists a model of ZFC which has \aleph_1 <2^{\aleph_0} and normal subgroup G \unlhd \pi_1(F, x) which is \Sigma_1^1 and for which \pi_1(F, x)/G is of cardinality \aleph_1.  Thus in an appropriate model an intermediate cardinality \aleph_1<2^{\aleph_0} can obtain and the hypothesis “locally path connected” in Theorem 2.3 (4 ) cannot be relaxed.  The quotients in Theorem 2.3 are countable precisely when the normal subgroup is open, or in other words, when the subgroup has a covering space.

I’ll mention one more result (Theorem C from On subgroups of first homology).  Recall that the Hawaiian earring is the subspace E=\bigcup_{n\in \omega} C((0, \frac{1}{n+2}),\frac{1}{n+2})\subseteq \mathbb{R}^2, with C(p,r) the circle centered at point p of radius r.  We’ll say a set is true \Sigma_{\alpha}^0 (respectively \Pi_{\alpha}^0) provided it is not \Pi_{\alpha}^0 (resp. \Sigma_{\alpha}^0) and that a set is true \Sigma_1^1 provided it is not Borel.

Theorem 2.4   The fundamental group \pi_1(E) has normal subgroups of the following types:

  1. true \Sigma_{\gamma}^0 for \omega_1>\gamma \geq 2
  2. true \Pi_{\gamma}^0 for each \omega_1 > \gamma \neq 2
  3. true \Sigma_1^1

These normal subgroups can be selected so that the quotient groups are of exponent 2.



Analyzing a fundamental group using basic descriptive set theory (Part 1)

The fundamental group is a useful tool in understanding a topological space.  In this installment I’ll present a very brief review of the concept of fundamental group, review the sup metric on the space of loops and introduce the notion of topological descriptions of subgroups of the fundamental group.

Recall that the fundamental group of a space X with distinguished point x, denoted \pi_1(X, x), is the set of all loops based at x modulo homotopy rel the endpoints.  The binary operation is defined by loop concatenation, the trivial element is the homotopy class of the constant loop at x, and inverses are given by taking the “backwards” loop.  As any loop based at x must stay within the path component of x, fundamental groups are most frequently used in path connected spaces.  For the remainder of this discussion I shall assume path connectedness of all spaces mentioned for which a fundamental group is computed, unless stated otherwise.  Given a path \rho in X from x to x' one obtains a natural isomorphism between \pi_1(X, x) and \pi_1(X, y), and thus one often drops the distinguished point x and speaks of the fundamental group \pi_1(X), which is well defined up to isomorphism.  A continuous map f: (X, x) \rightarrow (Y, y) induces a homomorphism f_*: \pi_1(X, x) \rightarrow \pi_1(Y, y) defined by letting f_*([l]) = [f\circ l].  The fundamental group is a homotopy invariant and so if spaces X and Y are homotopy equivalent there is an isomorphism \pi_1(X) \simeq \pi_1(Y) given by the functions witnessing homotopy equivalence.

Example  The fundamental group of a space consisting of one point is isomorphic to the trivial group, as is the fundamental group of any contractible space.

Example  The fundamental group of the circle S^1 is isomorphic to the group \mathbb{Z}.  Intuitively, declare one of the directions around the circle to be positive and given a loop l ask the net number of times that the loop has gone around the circle in the positive direction.

The fundamental group factors through products, meaning that \pi_1(\prod_{i\in I} X_i) \simeq \prod_{i\in I}\pi_1(X_i).  Thus one can compute the fundamental group of a two dimensional torus by noting that \pi_1(S^1 \times S^1) \simeq \pi_1(S^1) \times \pi_1(S^1) \simeq \mathbb{Z} \times \mathbb{Z}.

Many of the spaces that interest topologists are metrizable, and a metric on X induces a topology on the set of loops which underlies the fundamental group.  More precisely, let d be a metric on the space X and x \in X be a distinguished point.  Let L_x denote the set of all loops based at x.  One can topologize L_x using the sup metric which defines the distance between loops l_1, l_2 \in L_x to be \sup_{s\in [0, 1]}d(l_1(s), l_2(s)).  It is important to remember that we are not topologizing \pi_1(X, x) but rather the set L_x.

Now one can define a subgroup G \leq \pi_1(X, x) to be open (respectively closed) if the set \{l\in L_x: [l]\in G\} = \bigcup G is open (resp. closed) as a subset of L_x.  Change of base point isomorphisms preserve open-ness and closed-ness.  As is the case in topological groups, all open subgroups are also closed (the complement of an open subgroup is a union of left cosets of the group, which are also open subsets of L_x.)  If X is also assumed to be separable then L_x is also separable, and so any open subgroup of \pi_1(X, x) is of at most countable index by noticing that the set of left cosets gives a partition of L_x into nonempty open sets.  We recall that a space X is semi-locally simply connected if for every x\in X and open neighborhood U of x there exists a neighborhood V of x such that the map induced by inclusion \iota_*: \pi_1(V, x) \rightarrow \pi_1(X, x) is the trivial map (here, V might not be path connected).  Among path connected, locally path connected spaces the condition of semi-local simple connectivity is equivalent to having a universal cover.  We have the following (see On definable subgroups of the fundamental group, Proposition 2.10):

Fact  If X is metric and locally path connected the following are equivalent:

  1. The trivial subgroup of \pi_1(X) is open
  2. All subgroups of \pi_1(X) are clopen
  3. X is semilocally simply connected

This shows, among other things, that if we want to find topologically fascinating subgroups in the fundamental group of a locally path connected space we need to consider a “wild” space (i.e. one that has no universal cover).  As a matter of interest, we can say something a bit stronger (see Chapter 6 in my dissertation Subgroups and quotients of fundamental groups, Theorems and

Theorem  If X is metric, locally path connected and G \unlhd \pi_1(X, x) the following are equivalent:

  1. G is open
  2. There exists a covering space p: (\tilde{X}, \tilde{x}) \rightarrow (X, x) associated to G (i.e. p_*(\pi_1(\tilde{X}, \tilde{x})) = G)

To gain information about how \bigcup G sits inside of the loop space L_x, it helps to have at least one further assumption on X.  If d was assumed to be a complete metric then the sup metric on L_x is also complete.  Thus if X is a separable completely metrizable space (a Polish space) we have an accompanying separable completely metrizable topology on L_x.  Descriptive set theory is the field concerned with understanding “topological complication” of subsets of a Polish space.  Given a description of a subgroup G \leq \pi_1(X, x) using logic and/or topology it may be possible to know something about the index [\pi_1(X, x): G], and if G is normal we might gain insight into the quotient \pi_1(X, x)/G.

Welcome to Topology and Group Theory

Thank you for visiting!  This is a website mostly for posting my math.  I received a PhD in mathematics in May 2016 from Vanderbilt University under the advisement of Mark Sapir.  I do research in topology and group theory and have side interests in (descriptive, combinatorial) set theory and logic.  I am currently a postdoctoral researcher at The University of the Basque Country.

I got hooked on mathematics when I was exposed to Cantor’s diagonalization argument in high school.