Hostname: page-component-78c5997874-94fs2 Total loading time: 0 Render date: 2024-11-05T16:34:59.142Z Has data issue: false hasContentIssue false
  • English
  • Français

Maximal r.e. equivalence relations

Published online by Cambridge University Press:  12 March 2014

Jeffrey S. Carroll
Jeffrey S. Carroll*
Affiliation:
Department of Mathematics, Ithaca College, Ithaca, New York 14850
Get access Rights & Permissions [Opens in a new window]

Abstract

The lattice of r.e. equivalence relations has not been carefully examined even though r.e. equivalence relations have proved useful in logic. A maximal r.e. equivalence relation has the expected lattice theoretic definition. It is proved that, in every pair of r.e. nonrecursive Turing degrees, there exist maximal r.e. equivalence relations which intersect trivially. This is, so far, unique among r.e. submodel lattices.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 55 , Issue 3 , September 1990 , pp. 1048 - 1058
Copyright
Copyright © Association for Symbolic Logic 1990

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[Be]Bernardi, C., On the relation provable equivalence and on partitions in effectively inseparable sets, Studia Logica, vol. 40 (1981), pp. 29–37.CrossRefGoogle Scholar
[BS]Bernardi, C. and Sorbi, A., Classifying positive equivalence relations, this Journal, vol. 48(1983), pp. 529–538.Google Scholar
[Ca]Carroll, J., Some undecidability results for lattices in recursion theory, Pacific Journal of Mathematics, vol. 122 (1986), pp. 319–331.CrossRefGoogle Scholar
[De]Degtev, A. N., tt- and m-degrees, Algebra and Logic, vol. 12 (1973), pp. 26–41.CrossRefGoogle Scholar
[Er]Ershov, Yu. L., Positive equivalences, Algebra and Logic, vol. 10 (1971), pp. 378–394.CrossRefGoogle Scholar
[Jo]Jockusch, C. G. Jr., Relationships between reducibilities, Transactions of the American Mathematical Society, vol. 142 (1969), pp. 229–237.CrossRefGoogle Scholar
[MN]Metakides, G. and Nerode, A., Recursively enumerable vector spaces, Annals of Mathematical Logic, vol. 11 (1977), pp. 147–171.CrossRefGoogle Scholar
[NR]Nerode, A. and Remmel, J., A survey of lattices of r.e. substructures, Recursion theory, Proceedings of Symposia in Pure Mathematics, vol. 42, American Mathematical Society, Providence, Rhode Island, 1985, pp. 323–375.CrossRefGoogle Scholar
[Od]Odifreddi, P., Strong reducibilities, Bulletin (New Series) of the American Mathematical Society, vol. 4 (1981), pp. 37–86.CrossRefGoogle Scholar
[Re]Remmel, J., On r.e. and co-r.e. vector spaces with nonextendible bases, this Journal, vol. 45 (1980), pp. 20–34.Google Scholar
[Ro]Rogers, H. Jr., Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967.Google Scholar
[So]Soare, R., Recursively enumerable sets and degrees, Springer-Verlag, Berlin, 1987.CrossRefGoogle Scholar
[Vi]Visser, A., Numerations, λ-calculus and arithmetic, To H. B. Curry: essays on combinatory logic, lambda calculus and formalism, Academic Press, New York, 1980, pp. 259–284.Google Scholar
[Yo]Young, P., A theorem on recursively enumerable classes and splinters, Proceedings of the American Mathematical Society, vol. 17 (1966), pp. 1050–1056.CrossRefGoogle Scholar