Constructivity conditions on immune sets
Date
2025-01-29
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Archive for Mathematical Logic
Abstract
Definitionally: strongly effectively immune sets are infinite and their c.e. subsets have maximums effectively bounded in their c.e. indices; whereas, for effectively immune sets, their c.e. subsets’ cardinalities are what’re effectively bounded. This definitional difference between these two kinds of sets is very nicely paralleled by the following difference between their complements. McLaughlin: strongly effectively immune sets cannot have immune complements; whereas, the main theorem herein: effectively immune sets cannot have hyperimmune complements. Ullian: effectively immune sets can have effectively immune complements. The main theorem improves Arslanov’s, effectively hyperimmune sets cannot have effectively hyperimmune complements: the improvement omits the second ‘effectively’. Two natural examples of strongly effectively immune sets are presented with new cases of the first proved herein. The first is the set of minimal-Blum-size programs for the partial computable functions; the second, the set of Kolmogorov-random strings. A proved, natural example is presented of an effectively dense simple, not strongly effectively simple set; its complement is a set of maximal run-times. Further motivations for this study are presented. Kleene recursion theorem proofs herein emphasize how to conceptualize them. Finally, is suggested, future, related work—illustrated by a first, natural, strongly effectively -immune set—included: solution of an open problem from Rogers’ book.
Description
This article was originally published in Archive for Mathematical Logic. The version of record is available at: https://doi.org/10.1007/s00153-024-00958-x.
© The Author(s) 2024.
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
Keywords
immunities in computability, constructivities
Citation
Case, J. Constructivity conditions on immune sets. Arch. Math. Logic (2025). https://doi.org/10.1007/s00153-024-00958-x