Maximal Towers and Ultrafilter Bases in Computability Theory

Show simple item record Lempp, S en Miller, JS en Nies, A. en Soskova, MI en 2022-01-14T03:42:10Z 2022-01-14T03:42:10Z 2020 en
dc.identifier.citation CDMTCS Research Reports CDMTCS-547 (2020) en
dc.identifier.issn 1178-3540 en
dc.description.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.
dc.publisher Department of Computer Science, The University of Auckland, New Zealand en
dc.relation.ispartofseries CDMTCS Research Report Series en
dc.rights Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated. Previously published items are made available in accordance with the copyright policy of the publisher. en
dc.rights.uri en
dc.source.uri en
dc.title Maximal Towers and Ultrafilter Bases in Computability Theory en
dc.type Technical Report en
dc.subject.marsden Fields of Research en
dc.rights.holder Copyright: The author(s) en
dc.rights.accessrights en

Files in this item

Find Full text

This item appears in the following Collection(s)

Show simple item record


Search ResearchSpace