Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2021
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2106.00312 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916422392741888 |
|---|---|
| author | Lempp, Steffen Miller, Joseph S. Nies, Andre Soskova, Mariya |
| author_facet | Lempp, Steffen Miller, Joseph S. Nies, Andre Soskova, Mariya |
| contents | 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~$ω$ and the almost inclusion relation $\subseteq^*$ 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 $Δ^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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2106_00312 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Maximal towers and ultrafilter bases in computability Lempp, Steffen Miller, Joseph S. Nies, Andre Soskova, Mariya Logic 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~$ω$ and the almost inclusion relation $\subseteq^*$ 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 $Δ^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. |
| title | Maximal towers and ultrafilter bases in computability |
| topic | Logic |
| url | https://arxiv.org/abs/2106.00312 |