Uniformly introreducible sets
- 1 January 1969
- journal article
- Published by Cambridge University Press (CUP) in The Journal of Symbolic Logic
- Vol. 33 (4) , 521-536
- https://doi.org/10.2307/2271359
Abstract
Retraceable sets were denned in Dekker and Myhill [5]. In that paper it was pointed out that if A is a retraceable set, then A is recursive in each of its infinite subsets, i.e. A is introreducible. We would like to know to what extent theorems on retraceable sets also hold for introreducible sets; however, we have made very little progress in this direction. On the other hand, “uniformly introreducible” sets (which will be defined in §2) are more tractable, and it turns out that some results on retraceable sets extend to uniformly introreducible sets while others fail.Keywords
This publication has 13 references indexed in Scilit:
- Semirecursive sets and positive reducibilityTransactions of the American Mathematical Society, 1968
- Some remarks on extensibility, confluence of paths, branching properties, and index sets, for certain recursively enumerable graphsIllinois Journal of Mathematics, 1967
- No recursively enumerable set is the union of finitely many immune retraceable setsProceedings of the American Mathematical Society, 1967
- Arithmetical Sets and Retracing FunctionsMathematical Logic Quarterly, 1967
- On properties of regressive setsTransactions of the American Mathematical Society, 1965
- The minimum of two regressive isolsMathematische Zeitschrift, 1964
- Infinite series of isolsProceedings of Symposia in Pure Mathematics, 1962
- Recursively Enumerable Sets and Retracing FunctionsMathematical Logic Quarterly, 1962
- The classical and the ω-complete arithmeticThe Journal of Symbolic Logic, 1958
- Retraceable SetsCanadian Journal of Mathematics, 1958