Some theorems on classes of recursively enumerable sets
Authors:
J. C. E. Dekker and J. Myhill
Journal:
Trans. Amer. Math. Soc. 89 (1958), 2559
MSC:
Primary 02.00
MathSciNet review:
0097310
Fulltext PDF Free Access
References 
Similar Articles 
Additional Information
 [1]
Martin
Davis, Computability and unsolvability, McGrawHill Series in
Information Processing and Computers, McGrawHill Book Co., Inc., New
YorkTorontoLondon, 1958. MR 0124208
(23 #A1525)
 [2]
J.
C. E. Dekker, The constructivity of maximal dual ideals in certain
Boolean algebras, Pacific J. Math. 3 (1953),
73–101. MR
0053910 (14,838e)
 [3]
J.
C. E. Dekker, Two notes on recursively enumerable
sets, Proc. Amer. Math. Soc. 4 (1953), 495–501. MR 0058533
(15,385a), http://dx.doi.org/10.1090/S00029939195300585337
 [4]
J.
C. E. Dekker, Productive sets, Trans. Amer. Math. Soc. 78 (1955), 129–149. MR 0067049
(16,663a), http://dx.doi.org/10.1090/S0002994719550067049X
 [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 623362.
 [7]
Stephen
Cole Kleene, Introduction to metamathematics, D. Van Nostrand
Co., Inc., New York, N. Y., 1952. MR 0051790
(14,525m)
 [8]
S.
C. Kleene and Emil
L. Post, The upper semilattice of degrees of recursive
unsolvability, Ann. of Math. (2) 59 (1954),
379–407. MR 0061078
(15,772a)
 [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
(9,129f)
 [11]
Andrzej
Mostowski, On a set of integers not definable by means of
onequantifier predicates, Ann. Soc. Polon. Math. 21
(1948), 114–119. MR 0026622
(10,175w)
 [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. 194197.
 [13]
John
Myhill, Creative sets, Z. Math. Logik Grundlagen Math.
1 (1955), 97–108. MR 0071379
(17,118g)
 [14]
J.
Myhill and J.
C. Shepherdson, Effective operations on partial recursive
functions, Z. Math. Logik Grundlagen Math. 1 (1955),
310–317. MR 0077475
(17,1039b)
 [15]
Emil
L. Post, Recursively enumerable sets of
positive integers and their decision problems, Bull. Amer. Math. Soc. 50 (1944), 284–316. MR 0010514
(6,29f), http://dx.doi.org/10.1090/S000299041944081111
 [16]
H.
G. Rice, Classes of recursively enumerable sets
and their decision problems, Trans. Amer. Math.
Soc. 74 (1953),
358–366. MR 0053041
(14,713c), http://dx.doi.org/10.1090/S00029947195300530416
 [17]
H.
G. Rice, On completely recursively enumerable classes and their key
arrays, J. Symb. Logic 21 (1956), 304–308. MR 0081243
(18,369e)
 [18]
Norman
Shapiro, Degrees of computability, Trans. Amer. Math. Soc. 82 (1956), 281–299. MR 0085187
(19,2d), http://dx.doi.org/10.1090/S00029947195600851873
 [1]
 M. Davis, Computability and unsolvability, McGrawHill, New York, 1958. MR 0124208 (23:A1525)
 [2]
 J. C. E. Dekker, The constructivity of maximal dual ideals in certain Boolean algebras, Pacific J. of Math. vol. 3 (1953) pp. 73101. MR 0053910 (14:838e)
 [3]
 , Two notes on recursively enumerable sets, Proc. Amer. Math. Soc. vol. 4 (1953) pp. 495501. MR 0058533 (15:385a)
 [4]
 , Productive sets, Trans. Amer. Math. Soc. vol. 78 (1955) pp. 129149. MR 0067049 (16:663a)
 [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 623362.
 [7]
 S. C. Kleene, Introduction to metamathematics, New York, Van Nostrand, Amsterdam, North Holland Pub. Co., and Groningen, Noordhoff, 1952, x+550 pp. MR 0051790 (14:525m)
 [8]
 S. C. Kleene and E. L. Post, The upper semilattice of degrees of recursive unsolvability, Ann. of Math. vol. 59 (1954) pp. 379407. MR 0061078 (15:772a)
 [9]
 R. McNaughton, On the effective distinguishability of classes of theories, abstract, J. Symbolic Logic vol. 19 (1954) p. 157.
 [10]
 A. Mostowski, On definable sets of positive integers, Fund. Math. vol. 34 (1947) pp. 81112. MR 0021923 (9:129f)
 [11]
 , On a set of integers not definable by means of one quantifier predicates, Ann. Soc. Polon. Math. vol. 21 (1948) pp. 114119. MR 0026622 (10:175w)
 [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. 194197.
 [13]
 J. R. Myhill, Creative sets, Zeitschrift fur Mathematische Logik und Grundlagen der Mathematik vol. 1 (1955) pp. 97108. MR 0071379 (17:118g)
 [14]
 J. R. Myhill and J. C. Shepherdson, Effective operations on partial recursive functions, ibid. vol. 1 (1955) pp. 310317. MR 0077475 (17:1039b)
 [15]
 E. L. Post, Recursively enumerable sets of positive integers and their decision problems, Bull. Amer. Math. Soc. vol. 50 (1944) pp. 284316. MR 0010514 (6:29f)
 [16]
 H. G. Rice, Classes of recursively enumerable sets and their decision problems, Trans. Amer. Soc. vol. 74 (1953) pp. 358366. MR 0053041 (14:713c)
 [17]
 , On completely recursively enumerable classes and their key arrays, J. Symbolic Logic vol. 21 (1956) pp. 304308. MR 0081243 (18:369e)
 [18]
 N. Shapiro, Degrees of computability, Trans. Amer. Math. Soc. vol. 82 (1956) pp. 281299. MR 0085187 (19:2d)
Similar Articles
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:
http://dx.doi.org/10.1090/S00029947195800973107
PII:
S 00029947(1958)00973107
Article copyright:
© Copyright 1958
American Mathematical Society
