Computable functors and effective interpretations
City University of New York
We give an overview of a number of recent results in computable model theory, by various researchers (not necessarily including the speaker). The results are not all directly connected to each other, but they serve to illustrate the principle that much of the work in this discipline can be viewed through the prism of functors, on categories C and D whose elements are countable (or computable) structures and whose morphisms are isomorphisms (not necessarily computable). Ideally, such a functor F from C to D should be effective: given a structure M from C as an oracle, it should compute the structure F(M) in D, and given a C-morphism g from M to N as an oracle, it should compute the D-morphism F(g) from F(M) to F(N). Moreover, one would hope for F to be full and faithful, as a functor, and to have a computable inverse functor. In practice, it is unusual for an F to have all of these properties, and for particular applications in computable model theory, only certain of the properties are needed. Many familiar examples will be included to help make these concepts clear.
Recent joint work by Harrison-Trainor, Melnikov, Montalbán, and the speaker has established that computable functors are closely connected to Montalban’s notion of effective interpretation of one class C of countable structures in another class D. We will explain the connections and discuss the extent to which they realize the model-theorist’s suspicion that functors are really just another version of interpretations.
Russell Miller is professor of mathematics at Queens College of CUNY and also at the CUNY Graduate Center. He conducts research in mathematical logic, especially computability theory and its interaction with other areas of mathematics, as in computable model theory. He received his doctorate from the University of Chicago in 2000, as a student of Robert Soare, and subsequently held a postdoctoral position at Cornell University until 2003, when he came to CUNY.