Any function I can actually write down is measurable, right?

While most students of mathematics encounter measure theory at some point, the basic machinery of measure theory (such as $\sigma$-algebras) is often regarded as fussy and irrelevant in practice. In particular, the issue of measurability of sets and functions seems to be something one only encounters in the first semester of graduate real analysis and never again. The common informal explanation of this is that any function one can ‘actually write down’ will be measurable and that one needs to go looking for trouble using the axiom of choice in order to find non-measurable objects. This is certainly a true statement empirically,¹¹1It should be noted though that there are some fields, like the study of stochastic differential equations, in which $\sigma$-algebras and measurability are used more extensively as explicit bookkeeping machinery. and a fair amount of work has also been done by set theorists to explain the fact that one seems to ‘need the axiom of choice’ to build a non-measurable function or set. The two most notable works in this direction are probably Solovay’s famous construction of a model of $\mathsf{ZF}+\mathsf{DC}$ in which all subsets of $\mathbb{R}$ are measurable [28] and Shelah and Woodin’s work culminating in the thesis that ‘large cardinals imply that every reasonably definable set of reals is Lebesgue measurable’ [25]. Despite this, however, it has been known since Gödel’s seminal construction of $L$ in the 1930s that the existence of fairly ‘explicit’ non-measurable objects is consistent with $\mathsf{ZFC}$. Despite this, it seems to me²²2We will occasionally use the terms I, me, and my as convenient shorthand for ‘the author’ or ‘the author’s,’ as appropriate. that not many mathematicians are aware of just how explicit these explicit objects can be.

Most of the notation we’ll use here is standard. To avoid collision with the notation for open intervals, we’ll use angle brackets for ordered tuples in expressions like $\langle 1,2\rangle$. We will also be using the logician’s convention of representing tuples of indexed variables with a bar. For instance, $\bar{x}$ might represent $\langle x_{1},x_{2},x_{3}\rangle$. In some places these notations will be used together. For instance, if $\bar{x}=\langle x_{1},x_{2},x_{3}\rangle$, then $\langle\bar{x},n\rangle$ is the same thing as $\langle x_{1},x_{2},x_{3},n\rangle$. We’ll be representing projection maps with $\pi$, usually with a subscript. For example, an expression like $\pi_{4}$ is meant to represent a projection from some product $X\times Y\times Z\times W$ down to $X\times Y\times Z$, but this will be spelled out explicitly when it is used. Finally, we are taking $0$ to be a natural number and all suprema and infima are understood to be computed in the extended real numbers, which we will denote by $\overline{\mathbb{R}}$.

A major aspect of set theory research is independence results, proving that certain statements can neither be proven nor refuted using certain axiomatic systems. Of course one of the most famous theorems of the 20th century, Gödel’s incompleteness theorem, is of this form.³³3Although the incompleteness theorems are not uniquely set-theoretic in nature, as they apply equally well to Peano arithmetic and other relatively weak formal systems. In some sense, though, it is a little unfortunate that the incompleteness theorem is the most famous independence result, as it is a fairly subtle result to interpret semantically (involving models with non-standard natural numbers which ‘appear finite’ from within the model but are externally infinite and may code infinitely long, secretly unsound proofs). Set-theoretic forcing, originally introduced by Cohen to establish the independence of the axiom of choice from $\mathsf{ZF}$ and the continuum hypothesis from $\mathsf{ZFC}$, is likewise somewhat difficult to understand, even given the well-documented relationship between some aspects of forcing and the internal logic of certain kinds of sheaf toposes. The idea of ‘generating an entirely new real number out of thin air’ is a little hard to get accustomed to (as is the idea of the ‘space of surjections from $\mathbb{N}$ onto $\mathbb{R}$ which has no points but is nevertheless non-empty’).

Given the fact that Gödelian incompleteness and forcing are the two most famous varieties of independence proofs, it’s reasonable that these kinds of results have a certain mystique among most mathematicians. In my mind however, this is something of a shame because there are less well-known set-theoretic independence proofs that are, I would argue, more conceptually accessible than the two most famous ones. In fact, on some level, there are many ‘independence phenomena’ that are far more familiar to most mathematicians but are not usually conceived of as ‘independence results’ per se. Consider, for example, the following suggestively phrased proposition.

With the majority of set-theoretic independence phenomena, the very basic core argument is the same. One exhibits models of something like $\mathsf{ZF}$ or $\mathsf{ZFC}$ both satisfying and failing to satisfy a given sentence. The primary difference is that models of $\mathsf{ZFC}$ are large and rich enough to encode the majority of mathematics. While models of set theory are obviously far harder to visualize than, say, groups with $6$ elements, sometimes the relative construction of these models can be visualized fairly clearly.

Like many mathematicians, set theorists’ intuition is often founded on cartoonishly simple mental pictures, such as the standard drawing of a model of $\mathsf{ZFC}$ (see Fig. 1). A model of $\mathsf{ZFC}$ is somewhat like a great tree, rooted at the empty set and with the ordinals forming a transfinitely tall trunk off of which the various sets coding familiar mathematical objects branch. This picture immediately gives two coordinates which describe the broad structure of the majority of constructions of one model of $\mathsf{ZF}(\mathsf{C})$ from another: One can imagine a model extending another in height, leading to the idea of large cardinals, or one can imagine a model that extends another in width, as is the case in set-theoretic forcing, or a model which is the result of pruning another to some narrower width, which is the very basic idea of inner models such as Gödel’s $L$. Many more elaborate proofs involve performing several (or even infinitely many) of these constructions in succession, such as in Cohen’s original proof of the independence of choice from $\mathsf{ZF}$, which involves forcing to widen a model and then pruning down to a narrower symmetric submodel (a kind of inner model specialized for the context of forcing) to kill the axiom of choice by carefully cutting certain choice functions out of the model.

Descriptive set theory as a field starts by asking the question ‘What can we say about regularity properties of subsets of $\mathbb{R}$ (and other metric spaces) that can be built using topologically tame sets, such as open and closed sets, using basic operations, such as (countable) unions and intersections, complements, and projections?’ It has its roots in the beginning of measure theory. Despite the fact that questions about measurability of simple-to-define sets are now largely settled, descriptive set theory continues to be an active area of research, with many applications in various areas of math (both within and outside of mathematical logic). It’s often useful in showing that classifying some family of objects up to isomorphism via ‘simply definable’ invariants is impossible.

Effective descriptive set theory grew out of a body of connections and analogies between descriptive set theory and computability theory. Within descriptive set theory more generally, it is often useful for fine-grained analysis and has applications to problems that do not overtly involve computability theory, such as work by Lutz, Qi, and Yu in [18] on the Hausdorff dimensions of Hamel bases.

Here we will review some basic definitions and facts from effective descriptive set theory which we will eventually need. We will mostly follow [19], although we will use slightly different terminology, with the biggest difference being the uniform replacement of the word ‘recursive’ (in the sense of recursion theory) with the word ‘computable.’ We should also highlight that the following term is not standard.¹⁰¹⁰10Recall that in general a Polish space is a completely metrizable separable space. Effective descriptive set theory in general deals with ‘computably presentable’ Polish spaces, which includes the vast majority of explicitly named metric spaces in mathematics.

Obviously we could add more to this list if we wanted to, but these are the only spaces we’ll need.

Let $\nu_{p}(n)$ be the $p$-adic valuation of $n$ (i.e., the highest power of $p$ that divides $n$). Let $(p_{n})_{n\in\mathbb{N}}$ be the sequence of prime numbers (i.e., $p_{0}=2$, $p_{1}=3$, etc.). For each of the spaces $\mathbb{N}$, $\mathbb{N}^{\mathbb{N}}$, $\mathbb{R}$, and $\overline{\mathbb{R}}$ we fix an explicit enumeration of a topological basis:

• •

  $N(\mathbb{N},n)=\{n\}$.

• •

  For $n>0$,

  $$N(\mathbb{N}^{\mathbb{N}},n-1)=\{\alpha\in\mathbb{N}^{\mathbb{N}}:(\forall i<\nu_{2}(n))\alpha(i)=\nu_{p_{i+1}}(n)\}.$$

• •

  For $n>0$, $N(\mathbb{R},n-1)$ is the open interval

  $$\left(\frac{\nu_{3}(n)-\nu_{5}(n)}{1+\nu_{2}(n)},\frac{\nu_{3}(n)-\nu_{5}(n)+\nu_{7}(n)+1}{1+\nu_{2}(n)}\right).$$

• •

  $N(\overline{\mathbb{R}},3n)=N(\mathbb{R},n)$, $N(\overline{\mathbb{R}},3n+1)=(n,\infty]$, and $N(\overline{\mathbb{R}},3n+2)=[-\infty,-n)$.

• •

  For any product $X\times Y$ of basic Polish spaces, for $n>0$, $N(X\times Y,n-1)=N(X,\nu_{2}(n))\times N(Y,\nu_{3}(n))$.

The fact that we have many redundant entries in these enumerations doesn’t really matter. Moreover, the particular choices of basic open neighborhoods do not matter that much. All that matters is that these actually are open bases and that basic facts about sets in each basis (such as inclusion of one set in another, emptiness of intersection, etc.) are computably decidable, which is easy to verify about our choices here. We will not actually be specifically referencing these enumerations at all; we’ve provided them more for the thematic purpose of explicitness (and for the sake of fun).

Beyond this though it also gives a good example of how computability theorists (and other logicians for that matter) think. Most mathematicians engage with the natural numbers combinatorially or in an algebraic or analytic capacity. To a computability theorist, by contrast, a natural number is often just data. Any finite, possibly heterogeneous, bundle of data can be coded as a single natural number, as in our coding of $N(\mathbb{N}^{\mathbb{N}},n)$. Here we’re using $\nu_{2}$ in a fundamentally different way than the other $p$-adic valuations, in that it codes the length of initial segment of an element of $\mathbb{N}^{\mathbb{N}}$ that needs to be checked to verify membership in $N(\mathbb{N}^{\mathbb{N}},n)$. All of this is fairly unnatural from the point of view of number theory, but it doesn’t matter here. All that matters at the moment is that we can do it, just like with the definable well-order $<_{L}$ of $L$.

Recall that a set $W$ of natural numbers is computably enumerable if, informally speaking, there is a computer program that lists the elements of $W$ in some order. This can be formalized of course, but all reasonable formalizations of this notion result in an equivalent theory of computation. (This is the phenomenon of Turing completeness.) $W$ is computable or decidable if there is a computer program that can decide membership of $W$. A basic exercise in computability theory is showing that $W$ is computable if and only if both $W$ and $\mathbb{N}\setminus W$ are computably enumerable. Famously Turing showed that there are computably enumerable sets that are not computable (specifically sets coding the solution to the halting problem), but there are also many examples in mathematics of sets that are known to be computably enumerable but not know to be computable, such as the set $\{|p-q|:p,q~{}\text{prime}\}$.

Computably enumerable sets have a familial resemblance to open sets in the context of topology. Membership in either a computably enumerable or open set is witnessed by some ‘finite amount of data.’ This family resemblance makes the following notion fairly natural.

It is immediate that a set $U\subseteq\mathbb{N}$ is semicomputable if and only if it is computably enumerable.

Descriptive set theory deals with regularity properties of various classes of subsets of Polish spaces, called pointclasses. The most familiar examples of pointclasses are probably the classes of open and closed sets, but the classes of $G_{\delta}$ and $F_{\sigma}$ sets are also fairly common. $G_{\delta}$ and $F_{\sigma}$ are remnants of an older notation which was abandoned by descriptive set theorists as it does not scale well to more complicated sets. The following definition features some of the notation adopted by descriptive set theorists (although note that none of the pointclasses in this definition are directly comparable to the open, $G_{\delta}$, or $F_{\sigma}$ sets). More generally we of course have the pointclass of Borel sets. A big topic of descriptive set theory (and in particular of the interaction between it and set theory) is the projective hierarchy (see Fig. 4), which is built out of Borel sets by successive applications of the operations of projections and complements.

Suslin’s theorem (later generalized by Lusin’s separation theorem) is a particularly important structural fact about the projective hierarchy.

Since our goal is to analyze the complexity of projective sets in terms of computability theory, we also need the following more fine-grained notion.

The terms ‘boldface’ and ‘lightface’ are in reference to the fact that historically the two families of pointclasses were distinguished by font alone. Since this is admittedly an awful notational convention, it is now common to further distinguish the boldface pointclasses by under-tildes.¹¹¹¹11It should be noted, however, that a lot of descriptive set theory literature only considers the boldface notion and so doesn’t bother with maintaining notation for distinguishing the lightface projective sets.

The superscript $1$ is to distinguish from the notation for the levels of the (effective) Borel hierarchy (e.g., $\Sigma^{0}_{1}$ and $\Pi^{0}_{1}$). Since we won’t be needing to think about the complexity of Borel sets in this paper, we will avoid spelling out too much of this notation, but we will still need the following definitions.

Just as how semicomputable sets are ‘computably open’ sets, $\Pi^{0}_{2}$ sets are ‘computably $G_{\delta}$’ sets. 2.4 has a generalization to the lightface projective sets, which is a bit technical to state. We will use a corollary of this a few times which is that $\Sigma^{0}_{1}$, $\Pi^{0}_{1}$, $\Sigma^{0}_{2}$, and $\Pi^{0}_{2}$ sets are all $\Delta^{1}_{1}$.

The following basic fact will also be used frequently. The second part of this statement should be interpreted as saying that the lightface projective pointclasses are closed under ‘computable countable unions’ and ‘computable countable intersections’ and the boldface projective pointclasses are closed under countable unions and intersections.

Note that 2.7 immediately implies analogous results for the (boldface and lightface) $\Pi$ and $\Delta$ pointclasses.

It is also useful to define a notion of definability for functions, analogously to the preceding notions of definability for sets.

This generalizes a few other notions: A function $f:X\to Y$ is

• •

  $\undertilde{\mathbf{\Delta}}^{1}_{1}$ if and only if it is Borel,

• •

  $\undertilde{\mathbf{\Sigma}}^{0}_{1}$ if and only if it is continuous (where $\undertilde{\mathbf{\Sigma}}^{0}_{1}$ is the pointclass of open sets), and

• •

  $\Sigma^{0}_{1}$ if and only if it is computable in the sense of computable analysis.

Moreover a function $f:\mathbb{N}^{k}\to\mathbb{N}$ is computable in the sense of computability theory if and only if it is a $\Sigma^{0}_{1}$ function. The fact regarding $\undertilde{\mathbf{\Delta}}^{1}_{1}$ functions follows from 2.4.

We will be using the following facts in several places.

This is extremely useful because the class of $\Delta^{1}_{1}$ functions includes all computable functions and is closed under basic operations such as composition. The second part of 2.9 (as well as its boldface analog) is part of the reason why so much descriptive set theory literature is phrased explicitly in terms of Baire space, $\mathbb{N}^{\mathbb{N}}$, rather than $\mathbb{R}$, despite the historical origins of the field. All uncountable Polish spaces are ‘isomorphic’ in terms of most of the structure relevant to descriptive set theory, and this fact is essentially true in the sense of effective descriptive set theory as well. There is a clear analogy here to computability theory. One naturally encounters many different countable sets in computability theory, such as $\mathbb{N}$, $\mathbb{N}^{n}$, $\mathbb{Z}$, and $\mathbb{Q}$, but these are all ‘the same’ in the sense that there are computable bijections between them.

That said, there are of course meaningful differences between different uncountable Polish spaces (e.g., $\overline{\mathbb{R}}$ is compact, $\mathbb{R}$ is locally compact, and $\mathbb{N}^{\mathbb{N}}$ is not even $\sigma$-compact), but in terms of descriptive set theory we only really see these differences near the low end of the Borel hierarchy (as we will see later in Section 5.2). For instance, we cannot replace $\Pi^{0}_{2}$ with $\Pi^{0}_{1}$ in the following fact.

Lusin and Sierpiński independently showed that one can build ‘universal $\undertilde{\mathbf{\Sigma}}^{1}_{n}$ sets.’ In other words, for any uncountable Polish space $X$, there is a $\undertilde{\mathbf{\Sigma}}^{1}_{n}$ set $A\subseteq X\times X$ such that for every $\undertilde{\mathbf{\Sigma}}^{1}_{n}$ set $W\subseteq X$, there is an $e\in X$ such that $W=A(e)\coloneq\{x\in X:\langle x,e\rangle\in A\}$. This can be used to show that the (boldface and lightface) projective hierarchies are strict (see Fig. 4) via a diagonalization argument that is reminiscent of Turing’s proof of the unsolvability of the halting problem (which we can rephrase in our language here as the statement that there is a $\Sigma^{0}_{1}$ subset of $\mathbb{N}$ that is not $\Delta^{0}_{1}$).

Effective descriptive set theory had not been developed yet at the time of Lusin and Sierpiński’s result, but the proof of the result is so explicit that the resulting universal set is actually lightface projective, even though it indexes all boldface sets of the same complexity.

Note that the complement of any universal $\undertilde{\mathbf{\Sigma}}^{1}_{n}$ set is a universal $\undertilde{\mathbf{\Pi}}^{1}_{n}$ set.

Now that we have introduced some of the basic ideas of effective descriptive set theory, we are in a position to answer the question posed at the end of Section 1.3. Just as with the universal $\undertilde{\mathbf{\Sigma}}^{1}_{n}$ sets in 2.12, Gödel’s definition is explicit enough that it is possible to show that it is actually $\Delta^{1}_{2}$ rather than just $\undertilde{\mathbf{\Delta}}^{1}_{2}$.

2.9 immediately gives the following corollary.

Note that for powers of $\mathbb{R}$ in particular, we could also use the lexicographic order induced by $<^{L}$ restricted to $\mathbb{R}$. For example, we could take $\langle x,y\rangle<^{L}_{\mathbb{R}^{2}}\langle a,b\rangle$ to mean $x<^{L}a\vee(x=a\wedge y<^{L}b)$. The specifics do not matter too much.

Given a low complexity well-ordering on a Polish space, we now have a low complexity choice function on subsets thereof and can use this to produce low complexity versions of various choicy constructions. Recall that given an equivalence relation $E$ on a set $A$, a transversal is a set $B\subseteq A$ such that each equivalence class of $E$ contains exactly one element of $B$.

It should be noted that 3.5 is constructive in the sense that there is a specific computer program enumerating the basic open neighborhoods of $U$. Moreover, the set $\mathbb{R}\setminus\pi_{2}\left(\mathbb{R}^{2}\setminus\pi_{3}\left(\mathbb{R}^{3}\setminus\pi_{4}\left(\mathbb{R}^{3}\times\mathbb{N}\setminus U\right)\right)\right)$ exists in any model of $\mathsf{ZFC}$,¹³¹³13Or perhaps it would be more accurate to say that in any model of $\mathsf{ZFC}$ there is a set that can be built according to those instructions. but the next fact implies that it is independent of $\mathsf{ZFC}$ whether it actually is a Vitali set.

In particular, this statement in 3.6 implies that any set defined in the same manner as the set in 3.5 is measurable.

The word ‘lightface’ is essential in this statement, however. Solovay famously showed that, assuming the existence of an inaccessible cardinal, there is a model of $\mathsf{ZF}+\mathsf{DC}$ in which all sets of reals are Lebesgue measurable. As an intermediate step in his proof, Solovay also built a model of $\mathsf{ZFC}$ in which all (boldface) projective sets of reals are measure [28]. It was later shown by Shelah that it is not possible to remove the assumption of an inaccessible cardinal from this proof [24]. This is part of a general theme in set theory, namely that regularity properties of more complicated explicitly definable sets are intimately linked with larger scale large cardinal phenomena.

As noted by Shelah in [24], 3.7 goes through in $\mathsf{ZF}+\mathsf{AC}_{\aleph_{0}}$ (where $\mathsf{AC}_{\aleph_{0}}$ is the axiom of countable choice). Moreover, it’s known that far less than $\mathsf{ZF}$ itself is actually required for the proof and that it goes through in $\mathsf{BZ}+\mathsf{AC}_{\aleph_{0}}$ (where $\mathsf{BZ}$ is ‘bounded Zermelo set theory’).

Note that 3.7 doesn’t say that if all $\undertilde{\mathbf{\Sigma}}^{1}_{3}$ sets of reals are Lebesgue measurable, then there is an inaccessible cardinal. This is provably impossible. A statement that only quantifies over reals and sets of reals (or other collections of uniformly small objects) cannot unconditionally imply the existence of an inaccessible cardinal because such a statement will still hold in $H_{\kappa}$, where $\kappa$ is the smallest inaccessible cardinal. Note that this is essentially the same argument as in the proof of 1.4.

We will of course be needing the famous negative resolution of Hilbert’s tenth problem. This is by far the best known part of this story and is already covered by many accessible expository accounts, such as [20].

For the moment, we will adopt the convention of writing functions with a semicolon to indicate that certain variables are meant to be interpreted as parameters. For example, $p(\bar{x};n,m)$ in the following fact is strictly speaking a polynomial in the variables $\bar{x}$, $n$, and $m$, but we are thinking of $\bar{x}$ as unknowns and of $n$ and $m$ as parameters. In particular, when we talk about the ‘number of variables’ of a polynomial, were are only talking about those before the semicolon.

Polynomials with this property are called universal. We will need a very slightly more specific property which is usually guaranteed in the construction of universal polynomials. To match the convention of [11], we will also allow $m$ to be a tuple of parameters rather than a single parameter.

Obviously any universal polynomial $p$ yields a positively universal polynomial $p^{2}$ with twice the degree, but universal polynomials are typically constructed as a system of polynomials which are then combined as a sum of squares. This is almost certainly true of all known constructions of universal polynomials.

The original proof of the existence of universal polynomials, while constructive, didn’t do much to control the degree or number of unknowns of the resulting polynomial. There doesn’t even seem to be a published estimate of how big the original polynomial would be. Robinson and Matiyasevich, jointly and separately, produced a series of proofs reducing the needed number of unknowns, with Matiyasevich eventually reducing it to $9$ in an unpublished proof. Jones published this proof along with an analysis (some of which was performed by Wada) of various universal degree-unknown-number pairs, reporting the existence, for example, of a degree $4$ positively universal polynomial in $58$ unknowns and a $9$-unknown positively universal polynomial of degree $47216\cdot 5^{58}+9728\approx 1.638\times 10^{45}$ [11]. Unfortunately Jones omits a fair amount of details of these constructions and only explicitly gives the polynomial $p(x_{1},\dots,x_{28};n,m_{1},m_{2},m_{3})$ of degree $2\cdot 5^{60}$ shown in Figure 18 along with the general technique for constructing universal polynomials with $9$ variables (out of other universal polynomials¹⁶¹⁶16The occurrence of $58$ in the degree of the $9$-unknown universal polynomial is not a coincidence. This polynomial is constructed using the $58$-unknown polynomial. Given a universal polynomial with $\nu$ unknowns of degree $4$, the construction in [11] produces a $9$-unknown universal polynomial of degree $47216\cdot 5^{\nu}+9728$.). Focusing on this polynomial is reasonable, as it has the virtue of being short enough to actually write on one page, but it’s unclear how difficult it would be to fully replicated the other results reported by Jones. Using a standard technique of encoding intermediate calculations in extra variables [20, Thm. 6.2], it is possible to convert the polynomial in Figure 18 to an equivalent one of degree $4$ but with roughly $\log_{2}5^{60}$ variables.

Now we have almost all of the ingredients we need to arrive at our main results. One last fact is the observation, originally due to Cantor, that there is a polynomial pairing function on $\mathbb{N}$.

For each $n\geq 2$, let $J_{n+1}(x_{1},\dots,x_{n+1})\coloneq J_{2}(J_{n}(x_{1},\dots,x_{n}),x_{n+1})$. Note that each $J_{n}$ is a polynomial of degree $n$ with integer coefficients which moreover defines an injection from $\mathbb{N}^{n}$ to $\mathbb{N}$.