Hostname: page-component-78c5997874-t5tsf Total loading time: 0 Render date: 2024-11-16T20:16:05.856Z Has data issue: false hasContentIssue false
  • English
  • Français

Monotone and 1–1 sets

Part of: Computability and recursion theory

Published online by Cambridge University Press:  09 April 2009

D. B. Madan  and
R. W. Robinson
D. B. Madan
Affiliation:
Department of Economic Statistics University of SydneySydney, N.S.W. 2006, Australia
R. W. Robinson
Affiliation:
Mathematics Department University of NewcastleNewcastle, N.S.W. 2308, Australia
Rights & Permissions [Opens in a new window]

Abstract

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.

An infinite subset of ω is monotone (1–1) if every recursive function is eventually monotone on it (eventually constant on it or eventually 1–1 on it). A recursively enumerable set is co-monotone (co-1–1) just if its complement is monotone (1–1). It is shown that no implications hold among the properties of being cohesive, monotone, or 1–1, though each implies r-cohesiveness and dense immunity. However it is also shown that co-monotone and co-1–1 are equivalent, that they are properly stronger than the conjunction of r-maximality and dense simplicity, and that they do not imply maximality.

MSC classification

Secondary: 03D25: Recursively (computably) enumerable sets and degrees
Type
Research Article
Information
Journal of the Australian Mathematical Society , Volume 33 , Issue 1 , August 1982 , pp. 62 - 75
Copyright
Copyright © Australian Mathematical Society 1982

References

Lachlan, A. H. (1968), ‘On the lattice of recursively enumerable sets’, Trans. Amer. Math. Soc. 130, 1–37.CrossRefGoogle Scholar
Lerman, M. and Soare, R. I. (1980), ‘A decidable fragment of the elementary theory of the lattice of recursively enumerable sets’, Trans. Amer. Math. Soc. 267, 1–37.CrossRefGoogle Scholar
Madan, D. B. (1975), Simplicity notions in recursion theory (Ph. D. Thesis, University of Maryland, College Park, Md.).Google Scholar
Owings, J. C. (1966), Topics in metarecursion theory (Ph. D. Thesis, Cornell University, Ithaca, N. Y.).Google Scholar
Robinson, R. W., ‘Simplicity of recursively enumerable sets’, J. Symbolic Logic 32, 162–172.CrossRefGoogle Scholar
Rogers, H. (1967), The theory of recursive functions and effective computability (McGraw-Hill, New York).Google Scholar