I recently learnt that the proof of the classical theorem "$\mathsf{AD}$ $\implies$ $\aleph\_1$ is measurable" uses computability theory tools (or at least one of its proofs does so). I'm interested in more examples of this. More precisely:


1. What are some other well-known results in set theory that use non-trivial tools from computability theory to prove?
2. What are some well-known results in computability theory that use non-trivial tools in set theory to prove?


I'm more interested in classical results, but modern examples of such are also welcome. If possible, I would also like a reference (textbook/paper) for each example.



Theorems in set theory that use computability theory tools, and vice versa
Here are several examples.


* There is a natural affinity between forcing and many constructions in the Turing degrees. Specifically, many constructions of degrees by meeting requirements in succession can be seen as meeting dense sets in a suitable forcing notion, with the result that the computability construction amounts to a genericity argument. For example, to prove there are incomparable degrees, one should build the oracles by initial segment (so, Cohen forcing), and extend them generically in such a manner that neither is computable relative to the other as oracle. There are dozens of examples like this, and I recommend the forcing manner of understanding such constructions in computability. This is similar to the forcing genericity way of looking at the Fraïssé limit of a class of finite structures.
* Another example of this type: there must be strongly independent antichains in the degrees (no element is computable from the sum of all the others), since if you add infinitely many Cohen reals, they are like that, and the assertion that it exists is $\Sigma^1\_1$, hence absolute. From such an antichain, you get universality as an easy consequence — every countable order embeds into the degrees.
* The previous analogy is very strong in certain cases, and was historically the way the results were proved. For example, Sacks construction of a minimal degree in the Turing degrees translates directly to the proof of the minimality feature of Sacks forcing.
* The concept of Turing degrees is directly analogous to many other degree notions in set theory. For example, many arguments translate to the degrees of constructibility, where $x\sim y$ iff $L[x]=L[y]$. For example, the role of iterated Sacks forcing has been used (especially in work of Marcia Groszek and others) to produce models of set theory realizing a specified structure for the degrees of constructibility. This method also appears in my paper with Groszek on the [Implicitly constructible universe](https://arxiv.org/abs/1702.07947). And similarly with the arithmetic and hyperarithmetic degrees.
* The notion of computability is generalized to hypercomputation and E-recursion, in a way that is deeply connected with descriptive set theory.
* The notion of computability is also generalized by [Infinite time Turing machines](https://www.jstor.org/stable/2586556), which is also deeply connected with descriptive set theory. That notion in turn is generalized by ordinal computation, which provides an alternative presentation of the L-hierarchy in computability-theoretic terms.
* In my paper, [Forcing as a computational process](https://arxiv.org/abs/2007.00418), my co-authors and I investigate the computable model theory of forcing, looking into how one can compute a forcing extension from an oracle for a given model.
* There is a fun argument of mine for the nonlinearity of Turing degrees using set theory: if the degrees are linear, then since every initial segment is countable, the cofinality would have to be $\omega\_1$, but since there are continuum many degrees, this implies CH. But CH fails in a forcing extension. The assertion that there are incomparable degrees is $\Sigma^1\_1$, hence absolute. So there must be incomparable degrees in the ground model.
* Another argument, which I was just reminded of by Jason Chen (but I think it appears elsewhere here on MO): the Turing degree relation $x\leq\_T y$ is arithmetically definable and hence Borel, and since it has countable sections, it must have measure 0. The inverse relation also therefore has measure 0. So there is a measure one set of pairs $(x,y)$ not related by relative computability. So the degrees are nonlinear.


