Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



A completely mitotic nonrecursive r.e. degree

Author: Richard E. Ladner
Journal: Trans. Amer. Math. Soc. 184 (1973), 479-507
MSC: Primary 02F25
MathSciNet review: 0398805
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: A nonrecursive r.e. degree d is constructed that has the property that every r.e. set of degree d is mitotic. The degree d has several other interesting properties including the property that any two r.e. sets of degree d are weak truth table equivalent.

References [Enhancements On Off] (What's this?)

  • [1] C. G. Jockusch, Jr., Degrees in which the recursive sets are uniformly recursive, Canad. J. Math. (to appear). MR 0321716 (48:83)
  • [2] R. E. Ladner, Mitotic recursively enumerable sets, J. Symbolic Logic 38 (1973). MR 0342381 (49:7127)
  • [3] H. Rogers, Jr., Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967. MR 37 #61. MR 0224462 (37:61)
  • [4] L. P. Sasso, Jr., Deficiency sets and bounded information reducibilities, Trans. Amer. Math. Soc. (to appear). MR 0469729 (57:9510)
  • [5] C. E. M. Yates, Three theorems on the degrees of recursively enumerable sets, Duke Math. J. 32 (1965), 461-468. MR 31 #4721. MR 0180486 (31:4721)
  • [6] -, On the degrees of index sets. II, Trans. Amer. Math. Soc. 135 (1969), 249-266. MR 39 #2637. MR 0241295 (39:2637)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 02F25

Retrieve articles in all journals with MSC: 02F25

Additional Information

Keywords: Recursively enumerable, degree, mitotic, strongly mitotic, weak truth table reducibility
Article copyright: © Copyright 1973 American Mathematical Society

American Mathematical Society