How does Borelness overlap with definability, computability, or constructiveness?

Question

Background: I am writing a short paper aimed at math undergrads and focused as narrowly as possible on Borel equivalence relations. So, e.g., I am not assuming familiarity with recursion theory and am likely not mentioning the Borel or analytic hierarchies. I want to write a paragraph to motivate the restriction to Borel functions on standard Borel spaces.

I am giving as motivation the idea of investigating the natural, intuitive notion that we have of what counts as a satisfactorily-detailed description of a mathematical object or a constructive proof. The problem is that I don't know precisely what Borelness has to do with this notion and see it touched on only in snippets about the development of the field (e.g., talk about Lebesgue 1905). (I needn't mention the history unless it is relevant.) I will have already said something about AC and its equivalents. So I am presenting this question as interesting in itself: which functions (and relations) do we lose when we don't assume (full) AC? And I need to say why we are going to look at Borel functions to help answer this question. The real reason that we are looking at Borel functions is that this is what I worked on over the summer, so it's all that I'm writing about.

I also have no idea what this has to do with topology, i.e., why Borel sets are constructed from open sets of topological spaces.

My question precisely: Are Borel functions on standard Borel spaces exactly the functions that mathematicians would intuitively consider the definable, constructible, or computable ones? If not, where do they fit within this class, i.e., are they some of the simplest, oldest, first studied, most popular, etc.?

Answer 1

Are Borel functions on standard Borel spaces exactly the functions that mathematicians would intuitively consider the definable, constructible, or computable ones?

The Borel functions on the standard pointclasses $2^\omega$ and $\omega^\omega$ are the ones that are $\Delta^1_1$ definable relative to parameters from the spaces. This includes more than just the computable functions; the computable functions are the $\Delta^0_1$ ones (without parameters). In particular, every computable function is continuous, but there are many discontinuous Borel functions.

However, the Borel functions do not include all the functions definable in second-order arithmetic (for example, they do not include all $\Pi^1_1$ functions, not even all the ones defined without parameters), much less all the functions definable in set theory.

The word "constructible" can mean many things. The constructible hierarchy in set theory, $L$, includes many functions that are not Borel. For example, it also includes every $\Pi^1_1$-definable function and more generally every function definable in second-order arithmetic.

So it would not be very accurate to say that the Borel functions are the definable, constructible, or computable ones.

The point of the Boral functions is that they preserve Borel sets under pre-image, just as continuous functions preserve open sets under pre-image. The reason the Borel functions are worth looking at is that many of the sets that are constructed in topology are Borel, without necessarily being open or closed. For example, many $G_\delta$ sets that appear in topological constructions. By generalizing all the way to Borel functions, we get all these "low level Borel sets" for free.

If we restrict our notion of topology even more, we can end up with "tame topology", as in the book Tame topology and $o$-minimal structures by van den Dries. In that context there are lots of very pretty geometric results, and most of the pathologies of point-set topology (with or without the axiom of choice) are eliminated. Of course the cost is that the possible constructions are more restricted, as is the class of spaces that can be studied.

---

Part 2

Why are Borel equivalence relations special?

Very often in mathematics we define when two structures are equivalent in some way, for example "isomorphic" in some sense. The problem of telling whether two structures are equivalent can be difficult, so we look for "invariants" that we can use to help decide. For example, the homotopy groups of a topological space, and the characteristic of a ring, are invariant under isomorphism and so can be used to detect non-equivalence. Sometimes, we obtain a deep result such as Ornstein's theorem that completely reduces the problem of isomorphism to a single invariant. Call this sort of result a "complete classification". The classification of finite abelian groups is another example of a complete classification, which uses a finite sequence of natural numbers as the complete invariant for group isomorphism.

One way to motivate the study of equivalence relations in general is that it can obtain results about ''all possible'' kinds of complete classifications. Many "natural" equivalence relations are $\Sigma^1_1$, but Borel equivalence relations are nevertheless interesting for two reasons:

• They are general enough to cover many interesting mathematical phenomena. For example, the orbit equivalence relation of a continuous dynamical system (a continuous $\mathbb{Z}$-action on a Polish space) will be Borel. This is one place where the connection to topology occurs: people already have a put a great deal of effort into studying continuous dynamical systems,.

• The restriction to Borel relations allows more detailed results than would be possible otherwise. If we look at arbitrary equivalence relations, there will be no reasonable structure theory because all sorts of set-theoretic pathologies can creep in. But for Borel relations, these pathologies are kept at bay. This allows for results like those described in the first pages of this talk by Hjorth.

One particular way to get a Borel equivalence relation is to make a Borel map that assigns an invariant to each point, so that two points are equivalent if and only if they are sent to the same invariant. The Borelness of the map means that the invariant is, in a certain sense, "concretely obtained" from the point itself. A selection function on the set of equivalence classes, obtained from the axiom of choice, would be one way to obtain a complete invariant, but this invariant can be "arbitrary" in a sense that a Borel-obtained invariant is not.

Theorem 2.2 in the talk I linked above, proved by Silver, is a typical example of a result. It shows that for a Borel equivalence relation, there are two options:

1. There is a Borel way to assign a single natural number invariant $n_x$ to each point $x$, so that two points $x,y$ are equivalent if and only if $n_x = n_y$. This is a pretty nice property of the equivalence relation.
2. There is a Borel map $f$ of real numbers into the space such that for all reals $s$ and $t$, $s = t$ if and only if $f(s)$ is equivalent to $f(t)$. These relations are, in some sense, "complicated".

Theorem 2.3 in Hjorth's paper, by Harrison, Kechris, and Louveau, is a significant extension of Silver's result, which divides case 2 into two subcases. Theorems such as these would not be possible in the "general equivalence relation" case - the restriction to Borel equivalence relations is vital.

This paper by Louveau and this paper by Hjorth also have quite a bit of motivation at the beginning.

The other reason that Borel, analytic, and coanalytic relations are so well studied is that they can be attacked by "effective" methods, which use theorems and methods of computability theory to obtain results in descriptive set theory. The computability methods quickly break down at higher levels of the projective hierarchy (where they must be replaced with set-theoretic methods, when possible).

Answer 2

The Borel pointclass are very well-behaved and simple sets; however, in my opinion, I would not called them the intuitively "definable, constructible, or computable" subsets of Polish Spaces.

A set is definable usually means the set is defined or "carved out" by some formula. Borel subsets are definable, but they are not all the definable sets.

In descriptive set theory, the bold-faced $\Sigma_1^0$ sets are all the open subsets of any polish space. If $U$ is an open subset of a polish space $X$, let $U(x)$ be the unary predicate such that $U(x) \Leftrightarrow x \in U$. A set $F$ of a Polish Space $X$ is Boldface $\Pi_1^0$ if and only if there exists a $\Sigma_1^0$ $U$ such that $F = \{x \in X : \neg U(x)\}$. In general, a subset $W$ of a perfect polish space $X$ is boldface $\Sigma_{n + 1}^0$ if there is a $\Pi_1^n$ subset $V$ of $X \times \omega$, such that $W = \{x \in X : (\exists k)(V(x,k))\}$. $W$ is boldface $\Pi_{n + 1}^0$ if and only if there is a $\Sigma_{n + 1}^0$ set $V$ such that $W = \{x : \neg V(x)\}$. In the usual way, you can extend the indices through the countable ordinals. Then the Borel pointclass is $\bigcup_{\eta < \omega_1} \Sigma_{\eta}^0$. Using some basic logic, you can see that the $\Sigma$ and $\Pi$ hierarchy come from the certain number of alternation of quantifiers on $\omega$.

However, if you think of quantifiers on $\omega$ as number quantifers, then you may consider set quantifiers next. Let $\omega^\omega$ denote Baire Space. $W$ subset of a polish space $X$ is analytic if there exists a closed subset $F$ of $X \times \omega^\omega$ such that $W = \{x \in X: (\exists \alpha)(F(x,\alpha))\}$, where $\alpha$ ranges over $\omega^\omega$. Let $\Sigma_1^1$ denote the collection of analytic subsets of polish spaces. In a similar way as to the Borel Collection, you can define $\Pi_\eta^1$ and $\Sigma_\eta^1$. These form the projective sets. Clearly these are also definable; and, by some basic logics results, they correspond to alternations of function quantifers.

So the Borel class does not really correspond to all definable subsets. The Projective set are also definable. The projective sets play a very important of descriptive set theory, especially determinacy.

I would not say that the Borel Pointclass correspond to the computable ones either. Effective Descriptive Set Theory study some aspect of recursively presented perfect polish spaces. For the full definition of these concepts, you should Moschovakis' Book. Here $\Sigma_1^0$ (no boldface) refer to the semirecursive pointsets. In computability theory, these sort of resemble the computably enumerable sets. As in computability theory, the computable set would be the $\Delta_1^0 = \Sigma_1^0 \cap \Pi_1^0$ sets. Similarly to the above, you can define other the non-boldface borel and projective set. Even the $\Sigma_1^0$ sets would not be considered computable. For instance, $\Sigma_1^0$ subsets of $\omega$ (discrete metric) correspond exactly to the computably enumerable subsets of $\omega$. It is well known that $\emptyset'$ is a c.e. non computable subset of $\omega$.

Finally, as you mentioned you are interested in Borel Equivalence Relations. I don't know much about this, but there are some interested results and questions in countable Borel Equivalence Relation Theory and Computability Theory. For instance, Turing Equivalence $\equiv_T$ is a countable Borel Equivalence Relation. So is computable isomorphism and arithmetic equivalence. One important question is whether these are universal countable Borel Equivalence Relations. I believe that it has been shown that arithmetic equivalence is universal. Recursive isomorphism on $\omega^\omega$ and $5^\omega$ are also universal. Recursive Isomorphism on $2^\omega$ and Turing Equivalence are still open. The last one has connection to Martin Conjecture on Turing Invariant functions.

---

Many theorems in descriptive set theory do not use the full axiom of choice. Usually the dependent choice may be used. Interestingly, some of the open question of descriptive set theory relating to computability theory such as Martin's Conjecture are framed ZF + Dependent Choice + the Axiom of Determinacy.

Answer 3

Regarding the stem question

Are Borel functions on standard Borel spaces exactly the functions that mathematicians would intuitively consider the definable, constructible, or computable ones?

If not, where do they fit within this class, i.e., are they some of the simplest, oldest, first studied, most popular, etc.?

it happens that the first example of a concrete (not obtained with the help of AC) non-Borel pointset belongs to Lebesgue (1905), it is more or less equal to the $\Pi^1_1$ set of all reals which code ordinals. Also it looks like its non-Borelness was actually established near 10 years after by members of Luzin's group of students of descriptive set theory.