**Background.** The field of Borel equivalence relation theory
provides a robust, unifying theory that organizes most of the
classification problems of classical mathematics into a hierarchy,
allowing us precisely to compare their relative difficulty.
Namely, every such classification problem amounts to an
equivalence relation on a class of mathematical structures, and
one can generally present the class of structures as a standard
Borel space. An equivalence relation $E$ on such a space *reduces*
to another $F$, if there is a Borel function $f$ for which
$$x\mathrel{E}y\quad\iff\quad f(x)\mathrel{F} f(y).$$ Thus, the classification problem of $E$ is reduced to that of $F$, and a rich hierarchy has emerged. Anyone with a classification problem in any part of
mathematics should seek to situate it into this hierarchy. The
subject is a pleasing mix of ideas from many parts of mathematics.

**The issue.** Since the hierarchy works essentially on coded versions of the classification problems as standard Borel spaces, it is important for the subject that these encodings are authentic. Su Gao discussed the importance of this issue in his
book,
Invariant descriptive set theory (p. 328),
where he proposed the following principle:

Gao's thesis.For any collection $H$ of mathematical structures and natural standard Borel structures $B_1$ and $B_2$ on $H$, there is a Borel isomorphism $\psi:\langle H,B_1\rangle\cong\langle H,B_2\rangle$ for which $\psi(x)$ is isomorphic to $x$ for every $x\in H$.

In other words, all natural presentations of a given class of mathematical structures as a standard Borel space are the same up to Borel isomorphism. Many instances of such isomorphisms have been observed, and empirical evidence is accumulating in support of the thesis.

In his dissertation, Burak Kaya formulates the principle as asserting: for any class $H$ of mathematical structures, if $\langle X,B_1\rangle$ and $\langle Y,B_2\rangle$ are two standard Borel spaces naturally encoding the structures of $H$, then there is a Borel isomorphism $\psi:X\to Y$ such that the structures in $H$ coded by $x$ and by $\psi(x)$ are isomorphic. It is this formulation of the thesis that seems to arise more often in practice, as researchers give different encodings of their class of structures.

Gao discusses the philosophical nature of his thesis, citing specifically the difficulty of the issue of what counts as natural. He describes the thesis as an analogue of the Church/Turing thesis in computability theory.

**The questions.** My view is that Gao's thesis is critically
important for the subject, because if as we desire we are to view
the results of Borel equivalence relation theory as being about
the actual classification problems arising in mathematics, we need
to know that we have successfully captured those problems in our
presentations of them as standard Borel spaces.

In the case of computability theory, Turing in his famous paper gave a forceful philosophical argument that in principle any effective means of computation can be simulated by Turing machines. In the case of Gao's thesis, however, we seem to lack comparable forceful philosophical grounds. So are the two theses analogous?

I'd like to get a grasp on the nature of possible counterexamples
to Gao's thesis, if there might be any. Presumably, if we weaken
the naturality requirement, we can find counterexamples to the
thesis. How unnatural do the counterexamples have to be? Can anyone provide me with *unnatural* counterexamples?

**Question 1.** What are examples of collections $H$ of
mathematical structures that have almost-natural standard Borel
structures $B_1$ and $B_2$ on $H$, with no Borel isomorphism
respecting isomorphism of structures in $H$?

In other words, how close to natural can we get while violating the conclusion of Gao's thesis? It seems important for us to be aware of the range of possibility when discussing this thesis.

**Question 2.** What are the philosophical grounds that we have in
support of Gao's thesis?

I became interested in the issue of Gao's thesis because it arose in the recent dissertation and dissertation defense of Burak Kaya, where we had an interesting discussion about it during the question session.

7more comments