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](https://en.wikipedia.org/wiki/Descriptive_set_theory#Borel_hierarchy) and the [Polynomial hierarchy](https://en.wikipedia.org/wiki/Polynomial_hierarchy) for one, and the relationship between [topology and computability](https://www.sciencedirect.com/science/article/pii/S1571066104051357).


I would like to understand things such as:


* What is forcing, and how does one use it to prove the independence of the Continuum Hypothesis?
* What precisely is an [inner model](https://en.wikipedia.org/wiki/Inner_model)?
* [Why are Polish spaces an important setting for descriptive set theory](https://en.wikipedia.org/wiki/Polish_space)?


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](http://math.andrej.com/2007/09/28/seemingly-impossible-functional-programs/), 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.



Descriptive set theory for computer scientists?
For the last point, besides texts explicitly on computability-theoretic descriptive set theory (e.g. the hard-to-find [Mansfield-Weitkampf](https://rads.stackoverflow.com/amzn/click/com/0195036026), the freely-accessible [section $3$ of Moschovakis' book](https://www.math.ucla.edu/%7Eynm/lectures/dst2009/dst2009.pdf), or [these brief notes of Hjorth](http://www.math.uni-bonn.de/ag/logik/events/young-set-theory-2010/Hjorth.pdf)) I think the literature on **represented spaces** will be useful. There is a lot written about this; I recommend [this recent survey of Schroeder](https://arxiv.org/pdf/2004.09450.pdf) (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](https://www2.karlin.mff.cuni.cz/%7Ekrajicek/scott67.pdf)) 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](https://www.jstor.org/stable/2273183?seq=1)).


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**](https://www.cambridge.org/core/books/higher-recursion-theory/93B0D8F4DEEE99273FFF7538446E3C1B) *(it should be available via [ProjectEuclid](https://projecteuclid.org/euclid.pl/1235422631), but that link doesn't work at the moment)*.


*Now granted, [in a precise sense](http://jdh.hamkins.org/forcing-as-a-computational-process/) 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**](https://deepblue.lib.umich.edu/handle/2027.42/77915). 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](https://arxiv.org/abs/1801.09837), and the computability-theoretic result is [joint between Ivan and myself](https://arxiv.org/abs/1804.05041).


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.


