# Descriptive set theory for computer scientists?

It seems to me that there are scattered references of deep relationships between descriptive set theory and computability theory. For one, the relationship between the Borel hierarchy and the Polynomial hierarchy for one, and the relationship between topology and computability.

I would like to understand things such as:

It would be fantastic if these could be answered from the perspective of computability. For example, I know that the Cantor set has good computability properties, and I (possibly very incorrect) believe that this is related to descriptive set theory.

I'd greatly appreciate references to lecture notes, talks, video lectures, textbooks. Pretty much anything where I can study descriptive set theory with a computational bent would be great.

• This may be interesting: jdh.hamkins.org/tag/computability . And this: mathoverflow.net/questions/255990/… – Goldstern Apr 7 at 14:07
• There's also jstor.org/stable/1578739 – Gabe Goldberg Apr 7 at 15:01
• I agree with Noah Schweber that, given your interests, it probably doesn't make sense to try to learn forcing and inner models via computability theory rather than via a more conventional approach. Having said that, let me suggest that you may want to take a look at the book Computability Theory by S. Barry Cooper. (Another person who has written about the connection between computability and forcing is Jan Krajíček, but to be honest, I find him hard to read.) – Timothy Chow Apr 7 at 15:45
• One conceptual hurdle for learning forcing is ordinals. There was nothing at all in my computer science education about them. The point is that in forcing, the ordinals stay where they are, and other sets move up and down them like putting clothes on a clothesline. It is also important to understand that e.g. a countable ordinal is both a particular kind of poset structure imposed on $\mathbb{N}$ also a specific kind of set ordered by $\in$. The absoluteness of ordinals vs. non-absoluteness of cardinals is also a good, very basic, example of how to use the Lévy hierarchy. – Robert Furber Apr 8 at 1:43
• 1) It is incomprehensible near "where I can descriptive set theory" (e.g., is a word missing?) 2) What is abbr. "CH"? Computability hierarchy? Is "CH" a typo (e.g., of "CT" (computability theory))? – Peter Mortensen Apr 8 at 8:50

## 1 Answer

For the last point, besides texts explicitly on computability-theoretic descriptive set theory (e.g. the hard-to-find Mansfield-Weitkampf, the freely-accessible section $$3$$ of Moschovakis' book, or these brief notes of Hjorth) I think the literature on represented spaces will be useful. There is a lot written about this; I recommend this recent survey of Schroeder (and the sources in its bibliography). Granted, this is somewhat more geared towards computable analysis than (effective) descriptive set theory, but there is still strong overlap.

Roughly speaking, suppose we have a topological space $$\mathcal{X}$$ equipped with a canonical basis. Each point in $$\mathcal{X}$$ can be described by a set of basis elements, and examples like $$\mathbb{R}, 2^\mathbb{N}$$, and $$\mathbb{N}^\mathbb{N}$$ suggest that with "naturally-occuring" spaces it is often the case that such representations yield a good computability theory (we have notions of "computable elements" of each of those spaces). Polish spaces arise as a natural generalization of this setting; note that completeness can be thought of as the analogue of "every infinite sequence of decimal digits corresponds to a real number." Of course the situation is a bit more complicated than this, as the theory of represented spaces indicates, but this is still a good starting point.

Moreover, since all "nontrivial" Polish spaces are Borel-isomorphic, we get a general independence principle for "high-level" descriptive set theoretic questions. This helps motivate them on the classical side.

However, I don't really think that (set-theoretic) forcing and inner models are best approached via computability theory, even for a computability theorist; while they do have computability-theoretic aspects, focusing too much on this will obscure the fundamentally set-theoretic nature of the topic which is necessary to any deep understanding. In particular, while there is a notion of forcing in classical computability theory, in my opinion it's far too weak to yield a good bridge to set-theoretic forcing.

I think to a large extent there's nothing to do but grab the bull by the horns. Certainly not all expositions of forcing are equally clear, but in my experience ones which attempt a significantly simplified presentation (e.g. this "analytic" approach of Scott) don't really serve well as introductions to the fully general theory. The two standard approaches to forcing are via posets and Boolean-valued models, and I would just pick one and study it directly. In my experience the poset-based approach is far simpler, and it's what I learned; however, the Boolean-valued approach avoids any need to talk about generic objects directly, which may be a significant intuitive benefit if one is uncomfortable with model theory.

For general set-theoretic forcing and inner models, I think the right starting point (overlooking the concern of the paragraph above) is hyperarithmetic theory. Not only is this a "lightface" analogue of the Borel hierarchy (so it's relevant to the previous point too), it is tightly connected to the construction of $$L$$: in a very strong sense, $$L$$ is what you get when you "continue the hyperarithmetic hierarchy through the ordinals" (the relevant term here is "master codes" - see here).

Hyperarithmetic theory is also useful for understanding set-theoretic forcing. Forcing in classical computability theory (e.g. Jockusch-Soare forcing) is a bit too simple to provide a good starting point for set-theoretic forcing in my opinion. One wants to shift from classical computability theoretic forcing to forcing over some "set theory flavored" structure. It turns out that forcing over levels of $$L$$ is a very good context for doing this. For example, consider the proof that a comeager set of reals $$x$$ satisfy $$\omega_1^{CK}(x)=\omega_1^{CK}$$; this is basically "Cohen forcing over $$L_{\omega_1^{CK}}$$." In general, there's a rich theory of forcing over admissible sets.

My personal favorite treatment of the hyperarithmetic hierarchy and related notions is (the first few parts of) Sacks' book Higher recursion theory (it should be available via ProjectEuclid, but that link doesn't work at the moment).

Now granted, in a precise sense we can make sense of forcing "computably" rather than "hyperarithmetically;" however, while it's a very nice result I don't think this is a good way to approach the subject as a beginner from computability theory.

One final topic worth mentioning re: forcing, specifically connected with combinatorial topics like $$\mathsf{CH}$$, is the theory of effective cardinal characteristics of the continuum. This amounts to a "computable analogue" of the analysis of the interval $$[\aleph_1,2^{\aleph_0}]$$ via forcing, with set-theoretic forcing notions usually having corresponding computability-theoretic ones which yield analogous results. For example, we have a direct connection between the following two facts:

• It is (relatively) consistent with $$\mathsf{ZFC}$$ that there is a cardinal $$\kappa$$ such that $$(i)$$ there is a set $$F$$ of functions $$\mathbb{N}\rightarrow\mathbb{N}$$ such that every $$g:\mathbb{N}\rightarrow\mathbb{N}$$ is escaped by some $$f\in F$$, but $$(ii)$$ there is a set $$F$$ of functions $$\mathbb{N}\rightarrow\mathbb{N}$$ such that every $$g:\mathbb{N}\rightarrow\mathbb{N}$$ is dominated by some $$f\in F$$.

• There are hyperimmune degrees (= compute a function escaping all computable functions) which are not high (= compute a function dominating all computable functions).

Note that a consistency result is replaced by an outright fact.

Here the idea is to shift from cardinality on the set-theoretic side to lowness/highness notions on the computability-theoretic side. Moreover, while the applications generally go from the set-theoretic version to the computability-theoretic version, there is at least one case where we get a result on the set-theoretic side building on an initial result on the computability-theoretic side; the set-theoretic result (which was much harder) was gotten by Ivan Ongay-Valverde, and the computability-theoretic result is joint between Ivan and myself.

However, I think that this is a bit of a double-edged sword: while much more accessible to the classical computability theorist than hyperarithmetic theory, the conceptual shift in the previous sentence does lose a lot of the set-theoretic "spirit." I'm not sure how much I recommend it as a pedagogical starting point.

• @NoahSchweber "Set Theory and the Continuum Problem" by Fitting and Smullyan uses modal logic for forcing. I think their approach is taken from Fitting's book "Intuitionistic Logic, Model Theory and Forcing", but I haven't seen the latter book. – Michael Greinecker Apr 7 at 18:19
• @MichaelGreinecker Hm, I can't find a copy of either book but Fitting has an article where he sketches some of the idea. It seems to me that, even if it's more intuitive for a CSist in the specific case of $\mathsf{CH}$ (and I'm not at all sure I buy that) it's likely to add tons of overhead difficulty to more complicated forcing arguments. But I could be wrong; I'll definitely read through it as soon as I can get my hands on a copy! – Noah Schweber Apr 7 at 18:57
• I think Fitting and Smullyan sell it as a didactic improvement in their book. Indeed, interpreting consistency as holding in some possible world is at least intuitive. But for the working mathematician, there is probably no advantage. – Michael Greinecker Apr 7 at 19:04
• @StevenStadnicki In my beginner's guide I focus on the Boolean-valued models approach, which I think is more intuitive than generic filters in an arbitrary poset. Scott Aaronson, a computer scientist, didn't care much for either approach, and is trying to develop his own explanation. Since computer scientists tend to be more familiar with randomness than genericity, he was attracted to Dana Scott's A proof of the independence of the continuum hypothesis, so you might give that a try. – Timothy Chow Apr 7 at 22:08
• I don't think that the modal logic approach is going to be too helpful unless you're already familiar with modal logic. – Timothy Chow Apr 7 at 22:08