A Dialogue on Infinity

Our second case study will demonstrate an extreme case among many possible approaches to the explication of informal mathematical concepts: a hard-core mathematical treatment of the very concept of “explicitness”. It can be formulated as a remarkably compact thesis:

Explicit = Borel.

This thesis is promoted — perhaps in less explicit form — by Alexander Kechris and Greg Hjorth. A wonderful illustration and a template for the use of the thesis can be found in a recent work by Simon Thomas.

Simon Thomas looked at the following problem:

Does there exist an explicit choice of generators for each finitely generated group such that isomorphic groups are assigned isomorphic Cayley graphs?

Recall that if is a finitely generated group and is some finite generating set not containing the identity element, then the Cayley graph of with respect to is the graph with vertex set and edge set

For example, when is the additive group of integers and consists of the most canonical generator of integers, number 1, then the corresponding Cayley graph is:

However, when and , then the corresponding Cayley graph is:

Simon Thomas’ problem is very natural: is there an explicitly given canonical Cayley graph for each finitely generated group? The problem concerns the relation between two basic concepts of algebra: that of a group and its Cayley graph; it is formulated in very elementary terms.

Simon Thomas gave a negative answer to the problem. More precisely, he proved that this assignment cannot be made by a map with a Borel graph.

The underlying concepts of his proof are not that difficult; we give here only a crude description, all details can be found in Thomas’ paper.

First we note that a structure of a group on the set of natural numbers is given by its graph of multiplication, that is, a subset of the countable set . This subset is encoded as a (countable) sequence of 0’s and 1’s, hence can be viewed as a point in , the latter being equipped with the product topology. It can be shown that the space of finitely generated subgroups becomes a Borel subset of , hence a standard Borel space, that is, a complete separable metric space equipped with its -algebra of Borel subsets (recall that a Borel algebra of a topological space is the -algebra generated by its open subsets; elements of a Borel algebra are called Borel sets).

At this point one needs to recall Kuratowski’s Theorem:

Any standard Borel space is isomorphic to one of

(1) , (2) , or (3) a finite space.

In particular, the set of finite subsets of is also a standard Borel space. Further, if and are standard Borel spaces, the map is Borel if its graph is a Borel subset of the direct product .

Now I can state Simon Thomas’ Theorem:

There does not exist a Borel map such that for each group :

• generates .
• If is isomorphic to then the Cayley graph of with respect to is isomorphic to the Cayley graph of with respect to .

Is the Explicit = Borel thesis reasonable?

Indeed, a Borel subset of is any set which can be obtained from open intervals by operations of taking countable unions, countable intersections and complements. Well, this is a fairly wide class of sets; perhaps not everyone would agree that “Borel” is “explicit”; but it is easier to accept that every “explicit” construction in the real domain produces a Borel set. Being very wide and encompassing, this explication of “explicitness” is useful for proving negative results, when we want to show that some constructioncannot be made explicit.

Notice also that it is Kuratowski’s Theorem that brings the feeling of precision and universality into the Explicit = Borel thesis; without it, the thesis would be much more vague.

The Explicit = Borel thesis for the real domain is an example of an “under the microscope” approach to mathematics; it is like cytology, which treats living tissue as an ensemble of cells. Representing everything by 0’s and 1’s gives a very low level look at mathematics; it is fascinating that this approach leads to explicit “global” results.