Maximal Towers and Ultrafilter Bases in Computability Theory

Abstract

The tower number t and the ultrafilter number u are cardinal characteristics from set theory based on combinatorial properties of classes of subsets of ! and the almost inclusion relation ✓⇤ between such subsets. We consider analogs of these cardinal characteristics in computability theory. We say that a sequence hGnin2! of computable sets is a tower if G0 = !, Gn+1 ✓⇤ Gn, and Gn r Gn+1 is infinite for each n. A tower is maximal if there is no infinite computable set contained in all Gn. A tower hGnin2! is an ultrafilter base if for each computable R, there is n such that Gn ✓⇤ R or Gn ✓⇤ R; this property implies maximality of the tower. A sequence hGnin2! of sets can be encoded as the “columns” of a set G ✓ !. Our analogs of t and 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 mainly use Medvedev reducibility to formalize relative computational complexity, and thus to compare such mass problems to known ones. We show that the mass problem corresponding to 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 no 1-generic 0 2- oracle computes a maximal tower. In fact, no index predictable oracle does so. Here, index predictability of an oracle captures the ability to guess in a limit-wise way a characteristic index for a computable set given by a Turing reduction to the oracle. 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.