Some theorems on classes of recursively enumerable sets

Authors:
J. C. E. Dekker and J. Myhill

Journal:
Trans. Amer. Math. Soc. **89** (1958), 25-59

MSC:
Primary 02.00

DOI:
https://doi.org/10.1090/S0002-9947-1958-0097310-7

MathSciNet review:
0097310

Full-text PDF

References | Similar Articles | Additional Information

**[1]**Martin Davis,*Computability and unsolvability*, McGraw-Hill Series in Information Processing and Computers, McGraw-Hill Book Co., Inc., New York-Toronto-London, 1958. MR**0124208****[2]**J. C. E. Dekker,*The constructivity of maximal dual ideals in certain Boolean algebras*, Pacific J. Math.**3**(1953), 73–101. MR**0053910****[3]**J. C. E. Dekker,*Two notes on recursively enumerable sets*, Proc. Amer. Math. Soc.**4**(1953), 495–501. MR**0058533**, https://doi.org/10.1090/S0002-9939-1953-0058533-7**[4]**J. C. E. Dekker,*Productive sets*, Trans. Amer. Math. Soc.**78**(1955), 129–149. MR**0067049**, https://doi.org/10.1090/S0002-9947-1955-0067049-X**[5]**J. C. E. Dekker and J. Myhill,*Recursion theory*, to be published by the North Holland Pub. Co., Amsterdam.**[6]**R. M. Friedberg,*The solution of Post's problem by the construction of two recursively enumerable sets of incomparable degree of unsolvability*, Bull. Amer. Math. Soc. Abstract 62-3-362.**[7]**Stephen Cole Kleene,*Introduction to metamathematics*, D. Van Nostrand Co., Inc., New York, N. Y., 1952. MR**0051790****[8]**S. C. Kleene and Emil L. Post,*The upper semi-lattice of degrees of recursive unsolvability*, Ann. of Math. (2)**59**(1954), 379–407. MR**0061078**, https://doi.org/10.2307/1969708**[9]**R. McNaughton,*On the effective distinguishability of classes of theories*, abstract, J. Symbolic Logic vol. 19 (1954) p. 157.**[10]**Andrzej Mostowski,*On definable sets of positive integers*, Fund. Math.**34**(1947), 81–112. MR**0021923**, https://doi.org/10.4064/fm-34-1-81-112**[11]**Andrzej Mostowski,*On a set of integers not definable by means of one-quantifier predicates*, Ann. Soc. Polon. Math.**21**(1948), 114–119. MR**0026622****[12]**A. A. Muchnik,*Negative answer to the problem of reducibility of the theory of algorithms*, C. R. (Doklady) Acad. Sci. URSS vol. 108 (1956) pp. 194-197.**[13]**John Myhill,*Creative sets*, Z. Math. Logik Grundlagen Math.**1**(1955), 97–108. MR**0071379****[14]**J. Myhill and J. C. Shepherdson,*Effective operations on partial recursive functions*, Z. Math. Logik Grundlagen Math.**1**(1955), 310–317. MR**0077475****[15]**Emil L. Post,*Recursively enumerable sets of positive integers and their decision problems*, Bull. Amer. Math. Soc.**50**(1944), 284–316. MR**0010514**, https://doi.org/10.1090/S0002-9904-1944-08111-1**[16]**H. G. Rice,*Classes of recursively enumerable sets and their decision problems*, Trans. Amer. Math. Soc.**74**(1953), 358–366. MR**0053041**, https://doi.org/10.1090/S0002-9947-1953-0053041-6**[17]**H. G. Rice,*On completely recursively enumerable classes and their key arrays*, J. Symb. Logic**21**(1956), 304–308. MR**0081243****[18]**Norman Shapiro,*Degrees of computability*, Trans. Amer. Math. Soc.**82**(1956), 281–299. MR**0085187**, https://doi.org/10.1090/S0002-9947-1956-0085187-3

Retrieve articles in *Transactions of the American Mathematical Society*
with MSC:
02.00

Retrieve articles in all journals with MSC: 02.00

Additional Information

DOI:
https://doi.org/10.1090/S0002-9947-1958-0097310-7

Article copyright:
© Copyright 1958
American Mathematical Society