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.