Simplicity of recursively enumerable sets
- 1 August 1967
- journal article
- Published by Cambridge University Press (CUP) in The Journal of Symbolic Logic
- Vol. 32 (2) , 162-172
- https://doi.org/10.2307/2271653
Abstract
In §1 is given a characterization of strongly hypersimple sets in terms of weak arrays which is in appearance more restrictive than the original definition. §1 also includes a new characterization of hyperhypersimple sets. This one is interesting because in §2 a characterization of dense simple sets is shown which is identical in all but the use of strong arrays instead of weak arrays. Another characterization of hyperhypersimple sets, in terms of descending sequences of sets, is given in §3. Also a theorem showing strongly contrasting behavior for simple sets is presented. In §4 a r-maximal set which is not contained in any maximal set is constructed.Keywords
This publication has 9 references indexed in Scilit:
- Classes of Recursively Enumerable Sets and Degrees of UnsolvabilityMathematical Logic Quarterly, 1966
- Three theorems on the degrees of recursively enumerable setsDuke Mathematical Journal, 1965
- A maximal set which is not complete.The Michigan Mathematical Journal, 1964
- Some observations on quasicohesive sets.The Michigan Mathematical Journal, 1964
- Approximations of functions on the integersPacific Journal of Mathematics, 1963
- Recursively Enumerable Sets and Retracing FunctionsMathematical Logic Quarterly, 1962
- Recursive and recursively enumerable ordersTransactions of the American Mathematical Society, 1956
- Introduction to Metamathematics. By S. C. Kleene. Pp. x, 550, Fl. 32.50. 1952. (Noordhoff, Groningen; North-Holland Publishing Co., Amsterdam)The Mathematical Gazette, 1954
- Recursively enumerable sets of positive integers and their decision problemsBulletin of the American Mathematical Society, 1944