MAXIMAL TOWERS AND ULTRAFILTER BASES IN COMPUTABILITY THEORY

DOI10.1017/JSL.2022.60MaRDI QIDQ6095978zbMATH OpenFDO

Authors Steffen Lempp, Joseph S. Miller, André Nies, Mariya I. Soskova

Publication date 11 September 2023

Published in Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2106.00312

zbMATH Keywords

cardinal characteristicshighnessmass problemsMedvedev reducibilitysequences of computable setsultrafilters

Mathematics Subject Classification ID

Other degrees and reducibilities in computability and recursion theory (03D30)

Abstract: The tower number $mathfrakt$ and the ultrafilter number $mathfraku$ are cardinal characteristics from set theory. They are based on combinatorial properties of classes of subsets of~$omega$ and the almost inclusion relation $subsete{q}^{\ast }$ between such subsets. We consider analogs of these cardinal characteristics in computability theory. We show that the mass problem of ultrafilter bases is equivalent to the mass problem of computing a function that dominates all computable functions, and hence, by Martin's characterization, it captures highness. On the other hand, the mass problem for maximal towers is below the mass problem of computing a non-low set. We also show that some, but not all, noncomputable low sets compute maximal towers: Every noncomputable (low) c.e. set computes a maximal tower but no 1-generic $Delt{a}_2^0$-set does so. We finally consider the mass problems of maximal almost disjoint, and of maximal independent families. We show that they are Medvedev equivalent to maximal towers, and to ultrafilter bases, respectively.

Recommendations

• Maximal computability structures
• Limit computability and ultrafilters
• Computable structures and the hyperarithmetical hierarchy
• Ultrafilter and Non-standard Turing Machines
• Towers and maximal chains in Boolean algebras
• Dense computability, upper cones, and minimal pairs
• scientific article; zbMATH DE number 4021127
• scientific article; zbMATH DE number 2047478
• Lawvere-Tierney topologies for computability theorists
• Upper bounds on ideals in the computably enumerable Turing degrees

Cites work

• A cohesive set which is not high
• Algorithmic randomness and complexity.
• An analogy between cardinal characteristics and highness properties of oracles
• Cardinal invariants, non-lowness classes, and Weihrauch reducibility
• Combinatorial Cardinal Characteristics of the Continuum
• Computability and randomness
• Definable maximal independent families
• Degrees in Which the Recursive Sets are Uniformly Recursive
• General topology meets model theory, on 𝔭 and 𝔱
• scientific article; zbMATH DE number 194103 (Why is no real title available?)
• scientific article; zbMATH DE number 2063218 (Why is no real title available?)
• Low upper bounds of ideals
• On the filter of computably enumerable supersets of an r-maximal set
• Relativized Schnorr tests with universal behavior
• The degrees below a 1-generic degree < 0′
• The Shelah P-point independence theorem

This page was built for publication: MAXIMAL TOWERS AND ULTRAFILTER BASES IN COMPUTABILITY THEORY

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6095978)