Is there a class of mathematical structures with non-isomorphic natural representations as a standard Borel space?

Question

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.

Answer 1

Perhaps I am misunderstanding the question, but here is what seems to be a counterexample (Lemma 9.2.2 from Su Gao Invariant Descriptive Set Theory):

Let $H$ be the class of countable well-orders. The first Borel representation will be $(\mathbb{R}, F_{\omega_1})$ where $a F_{\omega_1} b$ iff $\omega_1^{CK(a)} = \omega_1^{CK(b)}$. The second is $(LO, E_{\omega_1})$, where $LO$ is the subset of $\mathcal{P}(\omega \times \omega)$ that encode linear orders of $\omega$, and $\phi E_{\omega_1} \psi$ iff either they are both non-wellordered, or they are both well-ordered of the same rank.

Both of these have $\omega_1$-many classes, so can be used to represent classes of $H$ (for $E_{\omega_1}$, we have an extra class, which we let represent $0$, and we let the linear orders $\phi \in LO$ of rank $n+1$ represent well-orders of rank $n$.)

But there is no Borel reduction at all from $E_{\omega_1}$ to $F_{\omega_1}$, or conversely. (Addendum: they are $\Delta^1_2$-bireducible, as described in Section 9.2.)

Discussion Su Gao gives this as an example of the fact that when the equivalence classes involved are not Borel, then Borel reducibility often seems inadequate to capture the notion of "definable reduction." Some weaker notions of reduction are "provably $\Delta^1_2$," or "$\Delta^1_2"$. See Section 9.2 of Su Gao.

Note that in general, when given two Borel representations $(\mathbb{R}, F)$ and $(\mathbb{R}, E)$ of the class of structures $H$, then presuming the maps $H / \cong \to \mathbb{R}/F$ and $H/ \cong \to \mathbb{R}/E$ are sufficiently definable in some sense, then there is a sufficiently definable bijection $\mathbb{R}/F \to \mathbb{R}/E$. So if there is no Borel such map, then no worries, we just figure out in what sense the representation is definable.

One can ask: what is the least restrictive notion of reduction that still allows a good theory? I'll put forward $HC$-reduction, defined in the paper A New Notion of Cardinality for Countable First Order Theories, by myself, Richard Rast, and Chris Laskowski. (Here $HC$ is the set of hereditarily countable sets.)