15
$\begingroup$

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

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ This question is at the border of my comfort zone, and I don't have too much time these days to properly sit and work on an answer. I will point out one thing, though, there is quite a difference between not assuming full choice; and working in ZF. E.g., there are models of ZF in which the real numbers are a countable union of countable sets. In such models descriptive set theory goes insane. Every set is Borel, although not every Borel set can be coded effectively. $\endgroup$ – Asaf Karagila♦ Sep 2 '12 at 6:45
  • $\begingroup$ @AsafKaragila Can't you always prove that the Borel and projective hierarchy are proper at each level? Does this result use some very weak form of choice? $\endgroup$ – William Sep 2 '12 at 7:25
  • $\begingroup$ @AsafKaragila I see. One points sets are closed. So countable sets are $\mathbf{\Sigma}_2^0$. All subsets in this model are then $\mathbf{\Sigma}_2^0$. $\endgroup$ – William Sep 2 '12 at 7:29
  • $\begingroup$ @William: Yes. If the continuum is a countable union of countable sets then every set is the countable union of $F_\sigma$ sets, so not exactly $\Sigma^0_2$, but if you go a bit further you can cover all subsets, e.g. $\Sigma^0_3$ is enough to generate every set. $\endgroup$ – Asaf Karagila♦ Sep 2 '12 at 7:31
4
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I have read somewhere else that Borel sets were invented/defined because they are more appropriate than open sets for some questions in topology. This would be motivation enough for my introducing them except that, in ~20 pages, I mention topology only in the definition of Borel sets. When we actually go looking for Borel reductions, the topology and metric are completely useless. What matters is getting back choice in some limited way, e.g., through the group action, hyperfiniteness, or smoothness, or looking at the measures to see if what we want is possible. [cont...] $\endgroup$ – Rachel Sep 3 '12 at 19:51
  • $\begingroup$ [...cont] My interest is logic, the paper is focused narrowly on Borel reductions, and the structures that we work with are orders, groups, and measures. I think it's interesting to ask how things change when you require everything to be Borel instead of allowing arbitrary sets. But I currently know no reason for Borel equivalence relations being a field of study (and populated by logicians). Surely it is not by pure happenstance that people write papers specifically about the classification of Borel equivalence relations. These objects and their classification must be special in some way. No? $\endgroup$ – Rachel Sep 3 '12 at 19:54
  • $\begingroup$ @Rachel: I think that I understand the question better. I have written "part 2" in my answer to try to address your comments. $\endgroup$ – Carl Mummert Sep 3 '12 at 21:16
  • $\begingroup$ Thank you, that makes much sense. I also had not seen the Louveau paper, and it looks very interesting. $\endgroup$ – Rachel Sep 3 '12 at 21:56
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I should mention $\omega$ is a not a perfect Polish Space, but it usually thrown in to define the Borel pointclass. $\endgroup$ – William Sep 2 '12 at 6:00
  • $\begingroup$ I should tell you this: you can use '\mathbf over Greek letters,e.g. $\mathbf\Sigma$, instead of writing “boldface” every time. $\endgroup$ – Asaf Karagila♦ Sep 2 '12 at 6:23
  • $\begingroup$ @AsafKaragila In Descriptive Set Theory, do you actually make the letter boldface to denote the boldface hierarchy? In textbooks, the only notation I have seen is the little tilde on the bottom, but they call it "boldface". I don't know how to make that. $\endgroup$ – William Sep 2 '12 at 6:26
  • $\begingroup$ My advisor explained this to me once. In the days before $\LaTeX$ when they would write on the blackboard it's hard to make a boldface font, so an underline tilde was denoting boldface. It is in fact a boldface font in several books and papers. $\endgroup$ – Asaf Karagila♦ Sep 2 '12 at 6:27
  • $\begingroup$ @Asaf: A wavy underline was used very generally to indicate boldface, e.g., in section headings of typewritten papers. Similarly, plain underlining indicated italics. Those were the days when those of us who typed our own papers had to fill in a lot of symbols by hand (script letters, $\subseteq$, $\bigcup$, etc.). $\endgroup$ – Brian M. Scott Sep 2 '12 at 8:22
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

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.