2025/03/06 by Logan McDonald, McDonald, Logan
Computer Science · Mathematics · #Advanced Topology and Set Theory #Computability, Logic, AI Algorithms #FOS: Mathematics #Logic (math.LO) #Logic, programming, and type systems
paper · pdf · doi:10.48550/arxiv.2503.04192
openalex publication_date 2025/03/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Cardinal characteristics of the continuum represent the boundaries in size between the countable and the continuum with respect to certain properties of sets. They are often defined as the minimum sizes of families of reals that meet some criteria. Taking these families and considering their analogues in the setting of computability theory provides a rich hierarchy of properties of oracles, which can be studied in terms of the Muchnik/Medvedev lattices of mass problems. We provide more detail to the proof of the Medvedev equivalence between dominating functions and maximal independent families given by Lempp et al. (2023) and adapt their construction of maximal almost disjoint families to the setting of ω-computably approximable sets. We then extend the theory to include correspondents of maximal ideal independent families and show they behave similarly to the maximal independent families.