Logic Seminar

Matthew Harrison-Trainor, Victoria University of Wellington

"Introcomputability"

We say that a set A introcomputes a set B if every infinite subset of A computes B. There are two natural ways in which this can happen. First, if A consists of the finite initial segments of B, then A introcomputes B; and second, if B is hyperarithmetic and A is very sparse then every infinite subset of A computes a function dominating the modulus of B, and hence computes B. I’ll talk about a number of results attempting to understand the reasons that one set might introcompute another.

MC 5413