Hostname: page-component-78c5997874-ndw9j Total loading time: 0 Render date: 2024-11-16T16:16:07.133Z Has data issue: false hasContentIssue false

Hyperhypersimple supersets in admissible recursion theory

Published online by Cambridge University Press:  12 March 2014

C. T. Chong*
Affiliation:
Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
*
Current address: National University of Singapore, Singapore 0511, Republic of Singapore

Extract

Let α be an admissible ordinal. An α-recursively enumerable set H is hyper-hypersimple (hh-simple) if its lattice of α-r.e. supersets forms a Boolean algebra. In [3], Chong and Lerman characterized the class () of hh-simple -r.e. sets as precisely those -r.e. sets whose complements are unbounded and of order type less than . Perhaps a nice example of such a set is {σσ is not for any n < ω}. It follows that all hh-simple sets in are nonhyperregular and therefore of degree 0′. That () is a natural class to study can be seen from the role played by its ω-counterpart in the study of decision problems and automorphisms of *(ω), the lattice of ω-r.e. sets modulo finite sets (Soare [13] gives an extensive literature on these topics). In α-recursion theory the existence of hh-simple sets is not an all pervasive phenomenon, and there is as yet no complete characterization of the admissible ordinal α for which (α) is nonempty. While this situation is admittedly unsatisfactory, we feel that the lattice *(α) of α-r.e. sets modulo α*-finite sets for which (α) ≠ ∅ deserves a careful study. Indeed armed with some understanding over the last few years of the general theory of admissible ordinals, it is tempting to focus one's attention on some specific ordinals whose characteristics admit a more detailed analysis of the fine structure of sets and degrees. From this point of view, and () are natural objects of study since the former is a typical example of a non-Σ2-projectible, Σ2-inadmissible ordinal, while the latter is important for the investigations of automorphisms over *().

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 1983

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1]Chong, C. T., Σn-cofinalities of Jα, fundamenta Mathematicae, vol. 102 (1978), pp. 101107.CrossRefGoogle Scholar
[2]Chong, C. T., Major subsets of α-recursively enumerable sets, Israel Journal of Mathematics, vol. 34 (1979), pp. 106114.CrossRefGoogle Scholar
[3]Chong, C. T. and Lerman, M., Hyperhypersimple α-r.e. sets, Annals of Mathematical Logic, vol. 9 (1976), pp. 148.CrossRefGoogle Scholar
[4]Lachlan, A. H., Degrees of recursively enumerable sets which have no maximal superset, this Journal, vol. 33 (1968), pp. 431443.Google Scholar
[5]Leggett, A., α-degrees of maximal α-r.e. sets, this Journal, vol. 43 (1978), pp. 456474.Google Scholar
[6]Lerman, M. and Sacks, G.E., some minimal pairs of α-recursively enumerable degrees, Annals of Mathematical Logic, vol. 4 (1972), pp. 415442.CrossRefGoogle Scholar
[7]Lerman, M. and Simpson, S.G., Maximal sets in α-recursion theory, Israel Journal of Mathematics, vol. 14 (1973), pp. 236247.CrossRefGoogle Scholar
[8]Maass, W., High α-recursively enumerable degrees, Generalized recursion theory. II, North-Holland, Amsterdam, 1978, pp. 239270.Google Scholar
[9]Shoenfield, J.R., Degrees of classes of r.e. sets, this Journal, vol. 41 (1976), pp. 695696.Google Scholar
[10]Shore, R.A., On the jump of an α-recursively enumerable set, Transactions of the American Mathematical Society, vol. 217 (1976), pp. 351363.Google Scholar
[11]Shore, R.A., Determining automorphisms of the recursively enumerable sets, Proceedings of the American Mathematical Society, vol. 65 (1977), pp. 318325.CrossRefGoogle Scholar
[12]Shore, R.A., Splitting an α-recursively enumerable set, Transactions of the American Mathematical Society, vol. 204 (1975), pp. 6577.Google Scholar
[13]Soare, R.I., Recursive enumerability, Proceedings of the International Congress of Mathematicians, Helsinki, 1978, Academia Scientiarum Fennica, 1980, pp. 275280.Google Scholar