Skip to main content
1 of 6
Noah Schweber
  • 21.2k
  • 10
  • 110
  • 331

Below, I'll use "recursive" in the sense of construction by recursion; I'll reserve "computable" for the computability-theoretic notion.


For the last point, 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 (recursive) descriptive set theory, but there is still strong overlap.


For general set-theoretic forcing and inner models, I think the right starting point 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 is 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 non-computably-bounded reals (= 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. However, 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.

Noah Schweber
  • 21.2k
  • 10
  • 110
  • 331