Maximal Towers and Ultrafilter Bases in Computability Theory

Journal of Symbolic Logic:1-21 (forthcoming)
  Copy   BIBTEX


The tower number ${\mathfrak t}$ and the ultrafilter number $\mathfrak {u}$ are cardinal characteristics from set theory. They are based on combinatorial properties of classes of subsets of $\omega $ and the almost inclusion relation $\subseteq ^*$ between such subsets. We consider analogs of these cardinal characteristics in computability theory. We say that a sequence $(G_n)_{n \in {\mathbb N}}$ of computable sets is a tower if $G_0 = {\mathbb N}$, $G_{n+1} \subseteq ^* G_n$, and $G_n\smallsetminus G_{n+1}$ is infinite for each n. A tower is maximal if there is no infinite computable set contained in all $G_n$. A tower ${\left \langle {G_n}\right \rangle }_{n\in \omega }$ is an ultrafilter base if for each computable R, there is n such that $G_n \subseteq ^* R$ or $G_n \subseteq ^* \overline R$ ; this property implies maximality of the tower. A sequence $(G_n)_{n \in {\mathbb N}}$ of sets can be encoded as the “columns” of a set $G\subseteq \mathbb N$. Our analogs of ${\mathfrak t}$ and ${\mathfrak u}$ are the mass problems of sets encoding maximal towers, and of sets encoding towers that are ultrafilter bases, respectively. The relative position of a cardinal characteristic broadly corresponds to the relative computational complexity of the mass problem. We use Medvedev reducibility to formalize relative computational complexity, and thus to compare such mass problems to known ones. 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 $\Delta ^0_2$ -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.



    Upload a copy of this work     Papers currently archived: 77,952

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Coanalytic ultrafilter bases.Jonathan Schilhan - 2022 - Archive for Mathematical Logic 61 (3-4):567-581.
Computability and Randomness.André Nies - 2008 - Oxford, England: Oxford University Press.
Computability and Randomness.André Nies - 2008 - Oxford, England: Oxford University Press UK.
Countable ultraproducts without CH.Michael Canjar - 1988 - Annals of Pure and Applied Logic 37 (1):1-79.
Calibrating randomness.Rod Downey, Denis R. Hirschfeldt, André Nies & Sebastiaan A. Terwijn - 2006 - Bulletin of Symbolic Logic 12 (3):411-491.
Randomness and computability: Open questions.Joseph S. Miller & André Nies - 2006 - Bulletin of Symbolic Logic 12 (3):390-410.
Computability Theory.S. Barry Cooper - 2003 - Chapman & Hall.
Remarks on the development of computability.Stewart Shapiro - 1983 - History and Philosophy of Logic 4 (1-2):203-220.
Filters on Computable Posets.Steffen Lempp & Carl Mummert - 2006 - Notre Dame Journal of Formal Logic 47 (4):479-485.


Added to PP

5 (#1,179,520)

6 months
3 (#247,676)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

A cohesive set which is not high.Carl Jockusch & Frank Stephan - 1993 - Mathematical Logic Quarterly 39 (1):515-530.
Low upper bounds of ideals.Antonín Kučera & Theodore A. Slaman - 2009 - Journal of Symbolic Logic 74 (2):517-534.
The degrees below a 1-generic degree $.Christine Ann Haught - 1986 - Journal of Symbolic Logic 51 (3):770 - 777.
Relativized Schnorr tests with universal behavior.Nicholas Rupprecht - 2010 - Archive for Mathematical Logic 49 (5):555-570.

Add more references