Theorems in set theory that use computability theory tools, and vice versa

Question

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.

Answer 1

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. 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, 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, 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.

Answer 2

Effective descriptive set theory is an area that's ripe with fruitful interaction between set theory and recursion theory. Here's a thread on MO on what to read if interested: Good source for Effective Descriptive Set Theory

EDST reveals a number of deep and beautiful analogies between computability, Borelness, and hyperarithmeticity. The Introduction section before Chapter 1 in Moschovakis's Descriptive Set Theory contains a few paragraphs on these analogies. For example, the proof that prewellordering property implies the reduction property is very reminiscent of the common technique of using Turing machines to enumerate sets alternately while looking back to check the enumerated elements at each step.

The more recent field of higher randomness theory is another place where the two fields have deep engagement. Here, one looks at higher analogues of the theory of algorithmic randomness, where "algorithmic" can be generalized to mean projectively definable. Of course, this quickly runs into independence at the $\Sigma^1_2$ level, and a satisfactory development of the theory often relies on the theory of determinacy and inner models. To the best of my knowledge, the only textbooks containing a systematic treatment to this subject are Computability and Randomness by Andre Nies, and Recursion Theory by Chong Chi Tat and Yu Liang (there are quite a few good resources on "lower" randomness theory though).

Answer 3

My favorite are the results in computability theory that rely on Martin's cone theorem (if A is sufficiently definable degree invariant set (Certainly if Borel but I think more) then either A or it's complement contain a cone.

This can be used for all sorts of neat results like the existence of a cone of minimal covers (both under Turing and arithmetic reducibility...the former has a constructive proof but I'm unaware of one for the later). See Odifreddi volume 2 for the one about the arithmetic degrees and volume 1 for the Turing degree claim.

A number of other examples here

Also see this discussion where Noah answered a q of mine about 2-lubs by hitting it over head with set theoretic forcing.

Answer 4

I have another interesting example applying set theory method to prove a result in recursion theory.

Given an infinite set $E\subseteq \omega$, a question is what's cardinality of the set $A_E=\{x\in 2^{\omega}\mid \exists c\forall n\in E K^x(n)\geq K(n)-c\}$, where $K$ is the Kolmogorov complexity and $K^x$ is the Kolmogorov complexity relative to $x$?

A famous result in algorithmic randomness theory is that $A_{\omega}$ is countable. In fact, for any set $E$ having a recursive subset, $A_E$ must be countable. Then a natural question is can $A_E$ be uncountable?

Wolfgang and I (Wolfgang Merkle and Liang Yu, Being low along a sequence and elsewhere, The Journal of Symbolic Logic, Volume 84, Issue 2 June 2019 , pp. 497-516.) constructed some $E$ so that $A_E$ uncountable. The proof is by Mathias forcing together Shoenfield absoluteness.