Hostname: page-component-7b7567c8c-wxvwp Total loading time: 0 Render date: 2026-11-18T14:53:31.907Z Has data issue: false hasContentIssue false

Mitotic recursively enumerable sets

Published online by Cambridge University Press:  12 March 2014

Richard E. Ladner*
Affiliation:
Simon Fraser University, Burnaby 2, British Columbia, CanadaUniversity of California, Berkeley, California 94720

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.

Information

Type
Research Article
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.)

Article purchase

Temporarily unavailable