Hostname: page-component-78c5997874-t5tsf Total loading time: 0 Render date: 2024-11-17T18:55:44.935Z Has data issue: false hasContentIssue false
  • English
  • Français

UNIVERSAL COMPUTABLY ENUMERABLE EQUIVALENCE RELATIONS

Published online by Cambridge University Press:  17 April 2014

URI ANDREWS ,
STEFFEN LEMPP ,
JOSEPH S. MILLER ,
KENG MENG NG ,
LUCA SAN MAURO  and
ANDREA SORBI
URI ANDREWS
Affiliation:
DEPARTMENT OF MATHEMATICS UNIVERSITY OF WISCONSIN MADISON, WI 53706-1388, USAE-mail: andrews@math.wisc.edu
STEFFEN LEMPP
Affiliation:
DEPARTMENT OF MATHEMATICS UNIVERSITY OF WISCONSIN MADISON, WI 53706-1388, USAE-mail: lempp@math.wisc.edu
JOSEPH S. MILLER
Affiliation:
DEPARTMENT OF MATHEMATICS UNIVERSITY OF WISCONSIN MADISON, WI 53706-1388, USAE-mail: jmiller@math.wisc.edu
KENG MENG NG
Affiliation:
DIVISION OF MATHEMATICAL SCIENCES SCHOOL OF PHYSICAL & MATHEMATICAL SCIENCES COLLEGE OF SCIENCE NANYANG TECHNOLOGICAL UNIVERSITY SINGAPOREE-mail: kmng@ntu.edu.sg
LUCA SAN MAURO
Affiliation:
SCUOLA NORMALE SUPERIORE PERFEZIONAMENTO IN DISCIPLINE FILOSOFICHE I-56126 PISA, ITALYE-mail: luca.sanmauro@sns.it
ANDREA SORBI
Affiliation:
DIPARTIMENTO DI INGEGNERIA DELL’INFORMAZIONE E SCIENZE MATEMATICHE UNIVERSITÀ DEGLI STUDI DI SIENA, VIA ROMA, 56 I-53100 SIENA, ITALYE-mail: sorbi@unisi.it
Get access Rights & Permissions [Opens in a new window]

Abstract

We study computably enumerable equivalence relations (ceers), under the reducibility $R \le S$ if there exists a computable function f such that $x\,R\,y$ if and only if $f\left( x \right)\,\,S\,f\left( y \right)$, for every $x,y$. We show that the degrees of ceers under the equivalence relation generated by $\le$ form a bounded poset that is neither a lower semilattice, nor an upper semilattice, and its first-order theory is undecidable. We then study the universal ceers. We show that 1) the uniformly effectively inseparable ceers are universal, but there are effectively inseparable ceers that are not universal; 2) a ceer R is universal if and only if $R\prime \le R$, where $R\prime$ denotes the halting jump operator introduced by Gao and Gerdes (answering an open question of Gao and Gerdes); and 3) both the index set of the universal ceers and the index set of the uniformly effectively inseparable ceers are ${\rm{\Sigma }}_3^0$-complete (the former answering an open question of Gao and Gerdes).

Keywords

03D25.Computably enumerable equivalence relationseffectively inseparable sets
Type
Articles
Information
The Journal of Symbolic Logic , Volume 79 , Issue 1 , March 2014 , pp. 60 - 88
Copyright
Copyright © Association for Symbolic Logic 2014 

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

Becker, H. and Kechris, A. S., The descriptive set theory of polish group actions . London Mathematical Society Lecture Notes Series, vol. 232, Cambridge University Press, 1996.CrossRefGoogle Scholar
Bernardi, C., On the relation provable equivalence and on partitions in effectively inseparable sets. Studia Logica, vol. 40 (1981), pp. 29–37.Google Scholar
Bernardi, C. and Montagna, F., Equivalence relations induced by extensional formulae: Classifications by means of a new fixed point property. Fundamenta Mathematicae, vol. 124 (1984),pp. 221–232.Google Scholar
Bernardi, C. and Sorbi, A., Classifying positive equivalence relations, this Journal, vol. 48 (1983), no. 3, pp. 529–538.Google Scholar
Case, J., Periodicity in generations of automata. Mathematical Systems Theory, vol. 8 (1974),pp. 15–32.Google Scholar
Cenzer, D., Harizanov, V. S., and Remmel, J. B., and equivalence structures. Annals of Pure and Applied Logic, vol. 162 (2011), no. 7, pp. 490–503.Google Scholar
Cleave, J. P., Creative functions. Zeitschrift für mathematische Logik und Grundlagen der Mathematik, vol. 7 (1961), pp. 205–212.Google Scholar
Coskey, S., Hamkins, J. D., and Miller, R., The hierarchy of equivalence relations on the natural numbers under computable reducibility. Computability, vol. 1 (2012), pp. 15–38.Google Scholar
Yu, L. Ershov, Positive equivalences. Algebra and Logic, vol. 10 (1973), no. 6, pp. 378–394.Google Scholar
Yu, L. Ershov, Theorie der Numerierungen I. Zeitschrift für mathematische Logik und Grundlagen der Mathematik, vol. 19 (1973), pp. 289–388.Google Scholar
Yu, L. Ershov, Theorie der Numerierungen II. Zeitschrift für mathematische Logik und Grundlagen der Mathematik, vol. 19 (1975), pp. 473–584.Google Scholar
Ershov, Yu. L., Theorie der Numerierungen III. Zeitschrift für mathematische Logik und Grundlagen der Mathematik, vol. 23 (1977), pp. 289–371.Google Scholar
Ershov, Yu. L., Theory of numberings. Nauka, Moscow, 1977.Google Scholar
Fokina, E. and Friedman, S. D., Equivalence relations on computable structures. In CiE 2009, Lecture Notes in Computer Science, vol. 5635, pp. 198–207, Springer-Verlag, Berlin, Heidelberg, 2009.Google Scholar
Fokina, E. and Friedman, S. D., On1 equivalence relations over the natural numbers. Mathematical Logic Quarterly, vol. 58 (2012), no. 1–2, pp. 113–124.Google Scholar
Fokina, E., Friedman, S. D., Harizanov, V., Knight, J. F., McCoy, C., and Montalban, A., Isomorphism relations on computable structures, this Journal, vol. 77 (2012), no. 1, pp. 122–132.Google Scholar
Fokina, E., Friedman, S. D., and Nies, A., Equivalence relations that are 3 -complete for computable reducibility. In Logic, Language, Information and Computation, 19th International Workshop, WoLLIC 2012, Buenos Aires, Argentina, September 3–6, 2012, Ong L. and de Queiroz, R. (editors), Lecture Notes in Computer Science, vol. 7456, pp. 26–34, Springer-Verlag, Berlin, Heidelberg, 2012. Google Scholar
Fokina, E., Friedman, S. D., and Törnquist, A., The effective theory of Borel equivalence relations. Annals of Pure and Applied Logic, vol. 161 (2010), pp. 837–850.Google Scholar
Gao, S., Invariant descriptive set theory . Pure and Applied Mathematics (Boca Raton). CRC Press, Boca Raton, Florida, 2009.Google Scholar
Gao, S. and Gerdes, P., Computably enumerable equivalence realations. Studia Logica, vol. 67 (2001), pp. 27–59.Google Scholar
Lachlan, A. H., Initial segments of one-one degrees. Pacific Journal of Mathematics, vol. 29 (1969), pp. 351–366.Google Scholar
Lachlan, A. H., A note on positive equivalence relations. Zeitschrift für mathematische Logik und Grundlagen der Mathematik, vol. 33 (1987), pp. 43–46.Google Scholar
Mal’tsev, A. I., Towards a theory of computable families of objects. Algebra i Logika, vol. 3 (1963), no. 4, pp. 5–31.Google Scholar
San Mauro, L., Forma e complessità. uno studio dei gradi delle relazioni di equivalenza ricorsivamente enumerabili . Master’s thesis, University of Siena, July 2011. (in Italian).Google Scholar
Montagna, F., Relative precomplete numerations and arithmetic. Journal of Philosophical Logic, vol. 11 (1982), pp. 419–430.Google Scholar
Myhill, J., Creative sets. Zeitschrift für mathematische Logik und Grundlagen der Mathematik, vol. 1 (1955), pp. 97–108.Google Scholar
Nies, A., Undecidable fragments of elementary theories. Algebra Universalis, vol. 35 (1996),pp. 8–33.Google Scholar
Odifreddi, P., Classical recursion theory , vol. II, Studies in Logic and the Foundations of Mathematics, vol. 143, North-Holland, Amsterdam, 1999.Google Scholar
Rogers, H. Jr, Theory of recursive functions and effective computability. McGraw-Hill, New York, 1967.Google Scholar
Shavrukov, V. Yu., Remarks on uniformly finitely positive equivalences. Mathematical Logic Quarterly, vol. 42 (1996), pp. 67–82.Google Scholar
Smullyan, R., Theory of formal systems . Princeton University Press, Princeton, New Jersey, 1961. Annals of Mathematical Studies, vol. 47.Google Scholar
Soare, R. I., Recursively enumerable sets and degrees. Perspectives in Mathematical Logic, Omega Series. Springer-Verlag, Heidelberg, 1987.CrossRefGoogle Scholar
Visser, A., Numerations, λ-calculus arithmetic, To H. B. Curry: Essays on combinatory logic, lambda calculus and formalism (Seldin, J. P. and Hindley, J. R., editors), pp. 259–284. Academic Press, London, 1980.Google Scholar
Young, P. R., Notes on the structure of recursively enumerable sets. Notices of the American Mathematical Society, vol. 10 (1963), p. 586.Google Scholar