Computability Seminar MSRI program on DDC-Generic Muchnik reducibility and enumerations of ideals

Organizer: V. Harizanov

For link contact [email protected]

Thursday, December 10, 12:00-1:00 ET on Zoom

Speaker: : Joseph Miller, University of Wisconsin, Madison

Title: Generic Muchnik reducibility and enumerations of ideals

Abstract: If A and B are countable structures, then A is Muchnik reducible to B if every ω-copy of B computes an ω-copy of A. This can be interpreted as saying that B is intrinsically at least as complicated as A. While this is a natural way to compare the complexity of structures, it was limited to the countable setting until Schweber introduced an extension to arbitrary structures: if A and B are (possibly uncountable) structures, then A is generically Muchnik reducible to B if in some (equivalently, any) forcing extension that makes A and B countable, A is Muchnik reducible to B.

We will discuss the fact that Cantor space is strictly below Baire space in the generic Muchnik degrees. On the other hand, Baire space is generic Muchnik equivalent to the field of reals, and in fact, any expansion of the reals by countably many continuous functions. On the other hand, if we expand Cantor space by adding jump and join, then we get a structure that is strictly more complicated than Baire space, one that is generic Muchnik above every Borel structure.