Hostname: page-component-cd9895bd7-mkpzs Total loading time: 0 Render date: 2024-12-25T18:31:17.450Z Has data issue: false hasContentIssue false
  • English
  • Français

Retraceable Sets

Published online by Cambridge University Press:  20 November 2018

J. C. E. Dekker  and
J. Myhill
J. C. E. Dekker
Affiliation:
University of California at Berkeley
J. Myhill
Affiliation:
The Institute for Advanced Study
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Let us compare two properties of sets of non-negative integers: (1) the set a has property Γ, if there exists an effective procedure which when applied to any element of a different from its maximum (which α does not necessarily possess) yields the next larger element of α; (2) the set α has property Δ, if there exists an effective procedure which when applied to any element of α different from its minimum yields the next smaller element of α. It is readily seen that every recursive set has both properties.

Type
Research Article
Information
Canadian Journal of Mathematics , Volume 10 , 1958 , pp. 357 - 373
Copyright
Copyright © Canadian Mathematical Society 1958

References

1. Dekker, J. C. E., Two notes on recursively enumerable sets, Proc. Amer. Math. Soc, 4 (1953), 495-501.Google Scholar
2. Dekker, J. C. E., A theorem on hypersimple sets, Proc. Amer. Math. Soc, 5 (1954), 791–796.Google Scholar
3. Heyting, A., Intuitionism, an introduction (Amsterdam, 1956).Google Scholar
4. König, D., Ueber eine Schlussweise aus dem Endlichen ins Unendliche, Acta Litterarum ac Scientiarum (Sectio Scientiarum Mathematicarum) Szeged, 3 (1927), 121-130.Google Scholar
5. König, D., Theorie der endlichen und unendlichen Graphen (Leipzig, 1936).Google Scholar
6. Rice, H. G., On completely recursively enumerable classes and their key arrays, J. Symbolic Logic, 21 (1956), 304-308.Google Scholar
7. König, D., Recursive and recursively enumerable orders, Trans. Amer. Math. Soc, 83 (1956), 277-300.Google Scholar
8. Sierpinski, W., General topology (2nd ed.; Toronto, 1956).Google Scholar
9. Symbolic Logic, J., 21 (1956).Google Scholar