Generic Muchnik reducibility

Joseph Miller (U of Wisconsin-Madison)

Jul 04. 2025, 11:30 — 12:15

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. Schweber suggested a natural extension of Muchnik reducibility 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 both A and B countable, A is Muchnik reducible to B. I will discuss what we know about generic Muchnik reducibility, especially as it pertains to expansions of Cantor space, Baire space, and the real numbers. The proofs mix descriptive set theory with injury and forcing constructions native to computable model theory.

Further Information
Venue:
ESI Schrödinger and Boltzmann Lecture Hall
Associated Event:
Reverse Mathematics (Thematic Programme)
Organizer(s):
Juan Aguilera (TU Vienna)
Linda Brown Westrick (Penn State U)
Noam Greenberg (Victoria U of Wellington)
Denis Hirschfeldt (U of Chicago)