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 newcases 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 0
2 -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) 2025
This is an open access article distributed under the terms of the Creative Commons CC BY license, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Keywords
Immunities in computability, Constructivities
Citation
Case, J. Constructivity conditions on immune sets. Arch. Math. Logic 64, 819–841 (2025). https://doi.org/10.1007/s00153-024-00958-x