Hostname: page-component-586b7cd67f-t8hqh Total loading time: 0 Render date: 2024-11-30T18:56:57.680Z Has data issue: false hasContentIssue false
  • English
  • Français

Mitotic recursively enumerable sets

Published online by Cambridge University Press:  12 March 2014

Richard E. Ladner
Richard E. Ladner*
Affiliation:
Simon Fraser University, Burnaby 2, British Columbia, Canada University of California, Berkeley, California 94720
Get access Rights & Permissions [Opens in a new window]

Extract

A recursively enumerable (r.e.) set is mitotic if it is the disjoint union of two r.e. sets both of the same degree of unsolvability. A. H. Lachlan has shown in [3] that there exists a nonmitotic r.e. set. In this paper we make an initial investigation into the class of mitotic sets.

The following results are proved, (i) An r.e. set is mitotic if and only if it is auto-reducible, (ii) There is a nonmitotic r.e. set of degree 0′, (iii) If d is an arbitrary non-recursive r.e. degree then there exists a nonmitotic r.e. set of degree ≤d. (iv) There exists a maximal set which is mitotic and a maximal set which is nonmitotic.

Albert R. Meyer had independently proved (ii) and (iii) for nonautoreducible sets before (i) was known.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 38 , Issue 2 , June 1973 , pp. 199 - 211
Copyright
Copyright © Association for Symbolic Logic 1973

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]Friedberg, R. M., A criterion for completeness of degrees of unsolvability, this Journal, vol. 22 (1957), pp. 159–160.Google Scholar
[2]Friedberg, R. M., Three theorems on recursive enumeration. I. Decomposition: II. Maximal set: III. Enumeration without duplication, this Journal, vol. 23 (1958), pp. 309–316.Google Scholar
[3]Lachlan, A. H., The priority method. I, Zeitschrift für mathematische Logik und Grundlagen der Mathematik, vol. 13 (1967), pp. 1–10.CrossRefGoogle Scholar
[4]Rogers, H. Jr., Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967.Google Scholar
[5]Sacks, G. E., Degrees of unsolvability, Annals of Mathematics Studies, no. 55, Princeton, N.J., 1963.Google Scholar
[6]Sacks, G. E., A maximal set which is not complete, Michigan Mathematical Journal, vol. 2 (1964), pp. 193–205.Google Scholar
[7]Shoenfield, J. R., Degrees of unsolvability, North-Holland Mathematics Studies, no. 2, London, 1971.Google Scholar
[8]Trahtenbrot, B. A., On autoreducibility, Soviet Mathematics, Doklady, vol. 11 (1970), no. 3, pp. 814–817.Google Scholar
[9]Yates, C. E. M., Three theorems on the degree of recursively enumerable sets, Duke Mathematical Journal, vol. 32 (1965), pp. 461–468.CrossRefGoogle Scholar
[10]Ladner, R. E., A completely mitotic nonrecursive r.e. degree (to appear).Google Scholar