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.

  • $\begingroup$ It seems to me that one might make a counterexample for which there is no isomorphism between $B_1$ and $B_2$ as desired, but where there is a Borel multi-function providing the desired association. $\endgroup$ Mar 26 '16 at 23:25
  • $\begingroup$ Would you be able to briefly describe an example or two of the kind of isomorphism that Gao's thesis is talking about? $\endgroup$ Mar 26 '16 at 23:44
  • 2
    $\begingroup$ @NateEldredge: One example that actually was in my thesis is the following. A minimal subshift is a pair of the form $(O,\sigma)$ where $O$ is an infinite closed $\sigma$-invariant subset of $2^{\mathbb{Z}}$, $\sigma$ is the left-shif map and $\sigma$-orbit of every point is dense. You can form the standard Borel space of such $O$'s as a subspace of the Polish space $K(2^{\mathbb{Z}})$ consisting of compact subsets of $2^{\mathbb{Z}}$ (where the standard Borel structure is coming from the Hausdorff metric). On the other hand, each such $O$ has to be homeomorphic to the Cantor set++ $\endgroup$
    – Burak
    Mar 27 '16 at 0:11
  • 2
    $\begingroup$ @NateEldredge: ++ and after forming a topologically conjugate system $(2^{\mathbb{N}}, \varphi)$, we can code this system by an automorphism of $\mathbb{B}$, where $\mathbb{B}$ denotes the Boolean algebra of clopen subsets of $2^{\mathbb{N}}$. This means that you can also form the space of (infinite) minimal subshifts as a subspace of $\mathbb{B}^{\mathbb{B}}$. On the other hand, there exist Borel maps between these spaces that map objects to objects coding isomorphic structures. $\endgroup$
    – Burak
    Mar 27 '16 at 0:14
  • 2
    $\begingroup$ Another example: shall we think of a countable linear order as a binary relation on $\mathbb{N}$, or as a suborder of $\mathbb{Q}$? These are two different ways to think about how to put a standard Borel structure on the collection of countable linear orders. $\endgroup$ Mar 27 '16 at 0:49

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.)

  • $\begingroup$ This is very nice. Since as you noted your relations are not Borel, one naturally wonders whether there are such examples with Borel relations. $\endgroup$ Apr 5 '16 at 23:05
  • $\begingroup$ This is quite nice. Perhaps, one should add that Gao points out that there exists a $\Delta^1_2$ reduction from $F_{\omega_1}$ to $E_{\omega_1}$ (which is described in $\S 9.2$). It seems that $F_{\omega_1}$ codes countable linear orders in an "unnatural" way that obtaining the well order back in the other coding requires a non-Borel reduction. (Of course, one might argue that this coding is "natural" enough so that we should not believe in the proposed thesis.) $\endgroup$
    – Burak
    Apr 5 '16 at 23:12
  • $\begingroup$ I edited the post to add that there is a $\Delta^1_2$ reduction $\endgroup$ Apr 5 '16 at 23:18
  • 1
    $\begingroup$ In my opinion, $\Delta^1_2$ is a far more powerful class than Borel. After all, the least transitive model of ZFC is $\Delta^1_2$ definable (if it exists), and so one has much more powerful methods in that class. Basically, $\Delta^1_2$ is huge. $\endgroup$ Apr 6 '16 at 0:17
  • $\begingroup$ I agree that $\Delta^1_2$ is huge... I guess in my mind the question of what reductions should be permitted is context-sensitive, with Borel being the most restrictive option (used in particular when the equivalence relations are Borel), and with provably $\Delta^1_2$ (and related things, like $HC$-reduction) being the least restrictive option. $\Delta^1_2$ is too big to be useful in $ZFC$--consistently (if $V=L$ say), there are $\Delta^1_2$ reductions from $(\mathbb{R}, E_{\omega_1})$ to $(\mathbb{R}, =)$, which is bad. $\endgroup$ Apr 6 '16 at 1:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.