{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,13]],"date-time":"2025-05-13T21:50:22Z","timestamp":1747173022770,"version":"3.40.5"},"reference-count":20,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2022,8,15]],"date-time":"2022-08-15T00:00:00Z","timestamp":1660521600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[2023,9]]},"abstract":"Abstract<\/jats:title>The tower number \n${\\mathfrak t}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> and the ultrafilter number \n$\\mathfrak {u}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> are cardinal characteristics from set theory. They are based on combinatorial properties of classes of subsets of \n$\\omega $\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> and the almost inclusion relation \n$\\subseteq ^*$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> between such subsets. We consider analogs of these cardinal characteristics in computability theory.<\/jats:p>We say that a sequence \n$(G_n)_{n \\in {\\mathbb N}}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> of computable sets is a tower<\/jats:italic> if \n$G_0 = {\\mathbb N}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, \n$G_{n+1} \\subseteq ^* G_n$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, and \n$G_n\\smallsetminus G_{n+1}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> is infinite for each n<\/jats:italic>. A tower is maximal<\/jats:italic> if there is no infinite computable set contained in all \n$G_n$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. A tower \n${\\left \\langle {G_n}\\right \\rangle }_{n\\in \\omega }$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> is an ultrafilter base<\/jats:italic> if for each computable R<\/jats:italic>, there is n<\/jats:italic> such that \n$G_n \\subseteq ^* R$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> or \n$G_n \\subseteq ^* \\overline R$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>; this property implies maximality of the tower. A sequence \n$(G_n)_{n \\in {\\mathbb N}}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> of sets can be encoded as the \u201ccolumns\u201d of a set \n$G\\subseteq \\mathbb N$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. Our analogs of \n${\\mathfrak t}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> and \n${\\mathfrak u}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> 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.<\/jats:p>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\u2019s 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 \n$\\Delta ^0_2$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-set does so.<\/jats:p>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.<\/jats:p>","DOI":"10.1017\/jsl.2022.60","type":"journal-article","created":{"date-parts":[[2022,8,15]],"date-time":"2022-08-15T11:45:04Z","timestamp":1660563904000},"page":"1170-1190","update-policy":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":0,"title":["MAXIMAL TOWERS AND ULTRAFILTER BASES IN COMPUTABILITY THEORY"],"prefix":"10.1017","volume":"88","author":[{"ORCID":"https:\/\/2.zoppoz.workers.dev:443\/https\/orcid.org\/0000-0002-2958-4017","authenticated-orcid":false,"given":"STEFFEN","family":"LEMPP","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/2.zoppoz.workers.dev:443\/https\/orcid.org\/0000-0002-6411-5670","authenticated-orcid":false,"given":"JOSEPH S.","family":"MILLER","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/2.zoppoz.workers.dev:443\/https\/orcid.org\/0000-0002-0666-5180","authenticated-orcid":false,"given":"ANDR\u00c9","family":"NIES","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/2.zoppoz.workers.dev:443\/https\/orcid.org\/0000-0003-4505-8006","authenticated-orcid":false,"given":"MARIYA I.","family":"SOSKOVA","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2022,8,15]]},"reference":[{"key":"S0022481222000603_r14","unstructured":"[14] Nies, A. (ed.), Logic blog 2019, preprint, 2019, arXiv:2003.03361."},{"key":"S0022481222000603_r18","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-02460-7"},{"key":"S0022481222000603_r19","unstructured":"[19] Soukup, D. T. , Two infinite quantities and their surprising relationship, preprint, 2018, arXiv:1803.04331."},{"key":"S0022481222000603_r17","first-page":"379","volume-title":"Proceedings of the Fourth Annual Workshop on Computational Learning Theory","author":"Slaman","year":"1991"},{"key":"S0022481222000603_r11","doi-asserted-by":"publisher","DOI":"10.1007\/PL00003846"},{"key":"S0022481222000603_r20","doi-asserted-by":"publisher","DOI":"10.1007\/BF02761683"},{"key":"S0022481222000603_r7","doi-asserted-by":"crossref","unstructured":"[7] Haught, C. A. , The degrees below a 1-generic degree <0 \u2032, this Journal, vol. 51(1986), pp. 770\u2013777.","DOI":"10.2307\/2274030"},{"key":"S0022481222000603_r15","unstructured":"[15] Rupprecht, N. A. , Effective correspondents to cardinal characteristics in Cicho\u0144\u2019s diagram , Ph.D. thesis, University of Michigan, 2010."},{"key":"S0022481222000603_r10","doi-asserted-by":"crossref","unstructured":"[10] Ku\u010dera, A. and Slaman, T. A. , Low upper bounds of ideals, this Journal, vol. 74 (2009), pp. 517\u2013534.","DOI":"10.2178\/jsl\/1243948325"},{"key":"S0022481222000603_r3","doi-asserted-by":"publisher","DOI":"10.1090\/proc\/14497"},{"key":"S0022481222000603_r16","doi-asserted-by":"publisher","DOI":"10.1007\/s00153-010-0187-6"},{"key":"S0022481222000603_r5","doi-asserted-by":"publisher","DOI":"10.1142\/9789812705815_0005"},{"key":"S0022481222000603_r4","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-68441-3"},{"key":"S0022481222000603_r9","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19930390153"},{"key":"S0022481222000603_r1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4020-5764-9_7"},{"first-page":"1","volume-title":"Proceedings of the 13th Asian Logic Conference: Guangzhou, China","author":"Brendle","key":"S0022481222000603_r2"},{"key":"S0022481222000603_r12","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1306114110"},{"key":"S0022481222000603_r6","doi-asserted-by":"publisher","DOI":"10.3233\/COM-180219"},{"key":"S0022481222000603_r13","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780199230761.001.0001"},{"key":"S0022481222000603_r8","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1972-113-9"}],"container-title":["The Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481222000603","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,4]],"date-time":"2023-09-04T11:47:13Z","timestamp":1693828033000},"score":1,"resource":{"primary":{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/www.cambridge.org\/core\/product\/identifier\/S0022481222000603\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,15]]},"references-count":20,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,9]]}},"alternative-id":["S0022481222000603"],"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1017\/jsl.2022.60","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"type":"print","value":"0022-4812"},{"type":"electronic","value":"1943-5886"}],"subject":[],"published":{"date-parts":[[2022,8,15]]},"assertion":[{"value":"\u00a9 The Author(s), 2022. Published by Cambridge University Press on behalf of The Association for Symbolic Logic","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}