A Survey on Universal Computably Enumerable Equivalence Relations

详细信息    查看全文

• 关键词：Computably enumerable equivalence relation ; Computable reducibility on equivalence relations
• 刊名：Lecture Notes in Computer Science
• 出版年：2017
• 出版时间：2017
• 年：2017
• 卷：10010
• 期：1
• 页码：418-451
• 参考文献：1.Andrews, U., Lempp, S., Miller, J.S., Ng, K.M., San Mauro, L., Sorbi, A.: Universal computably enumerable equivalence relations. J. Symbolic Logic 79(1), 60–88 (2014)MathSciNet CrossRef MATH
  2.Andrews, U., Sorbi, A.: The complexity of index sets of classes of computably enumerable equivalence relations. J. Symbolic Logic (to appear)
  3.Andrews, U., Sorbi, A.: Jumps of computably enumerable equivalence relations (2016, in preparation)
  4.Badaev, S.: On weakly precomplete positive equivalences. Siberian Math. J. 32, 321–323 (1991)MathSciNet CrossRef MATH
  5.Badaev, S., Sorbi, A.: Weakly precomplete computably enumerable equivalence relations. Mat. Log. Quart. 62(1–2), 111–127 (2016)MathSciNet CrossRef MATH
  6.Bernardi, C.: On the relation provable equivalence and on partitions in effectively inseparable sets. Studia Logica 40, 29–37 (1981)MathSciNet CrossRef MATH
  7.Bernardi, C., Montagna, F.: Equivalence relations induced by extensional formulae: classifications by means of a new fixed point property. Fund. Math. 124, 221–232 (1984)MathSciNet MATH
  8.Bernardi, C., Sorbi, A.: Classifying positive equivalence relations. J. Symbolic Logic 48(3), 529–538 (1983)MathSciNet CrossRef MATH
  9.Cleave, J.P.: Creative functions. Z. Math. Logik Grundlag. Math. 7, 205–212 (1961)MathSciNet CrossRef MATH
  10.Cooper, S.B.: Computability Theory. Chapman & Hall/CRC Mathematics, Boca Raton, London, New York, Washington, DC (2003)MATH
  11.Coskey, S., Hamkins, J.D., Miller, R.: The hierarchy of equivalence relations on the natural numbers. Computability 1, 15–38 (2012)MathSciNet MATH
  12.Ershov, Y.L.: Positive equivalences. Algebra Logic 10(6), 378–394 (1973)CrossRef MATH
  13.Ershov, Y.L.: Theorie der Numerierungen I. Z. Math. Logik Grundlag. Math. 19, 289–388 (1973)MathSciNet CrossRef MATH
  14.Ershov, Y.L.: Theorie der Numerierungen II. Z. Math. Logik Grundlag. Math. 19, 473–584 (1975)MathSciNet CrossRef
  15.Fokina, E., Khoussainov, B., Semukhin, P., Turetsky, D.: Linear orders realized by c.e. equivalence relations. J. Symbolic Logic (to appear)
  16.Fokina, E., Friedman, S., Nies, A.: Equivalence relations that are \(\Sigma ^0_3\) complete for computable reducibility. In: Ong, L., Queiroz, R. (eds.) WoLLIC 2012. LNCS, vol. 7456, pp. 26–33. Springer Berlin Heidelberg, Berlin, Heidelberg (2012). doi:10.​1007/​978-3-642-32621-9_​2 CrossRef
  17.Fokina, E.B., Friedman, S.D., Harizanov, V., Knight, J.F., McCoy, C., Montalbán, A.: Isomorphism relations on computable structures. J. Symbolic Logic 77(1), 122–132 (2012)MathSciNet CrossRef MATH
  18.Friedman, H.: Proof-theoretic degrees (Unpublished)
  19.Gao, S., Gerdes, P.: Computably enumerable equivalence realations. Studia Logica 67, 27–59 (2001)MathSciNet CrossRef MATH
  20.Gravuskin, A., Jain, S., Khoussainov, A., Stephan, F.: Graphs realized by r.e. equivalence relations. Ann. Pure Appl. Logic 165(7–8), 1263–1290 (2014)MathSciNet MATH
  21.Gravuskin, A., Khoussainov, A., Stephan, F.: Reducibilities among equivalence relations induced by recursively enumerable structures. Theoret. Comput. Sci. 612(25), 137–152 (2016)MathSciNet MATH
  22.Lachlan, A.H.: A note on positive equivalence relations. Z. Math. Logik Grundlag. Math. 33, 43–46 (1987)MathSciNet CrossRef MATH
  23.Mal’tsev, A.I.: Sets with complete numberings. Algebra i Logika 2(2), 4–29 (1963)MathSciNet
  24.Miller III, C.F.: On Group-Theoretic Decision Problems and Their Classification. Annals of Mathematics Studies. Princeton University Press, Princeton (1971)MATH
  25.Montagna, F.: Relative precomplete numerations and arithmetic. J. Philos. Logic 11, 419–430 (1982)MathSciNet CrossRef MATH
  26.Myhill, J.: Creative sets. Z. Math. Logik Grundlag. Math. 1, 97–108 (1955)MathSciNet CrossRef MATH
  27.Nies, A., Sorbi, A.: Calibrating word problems of groups via the complexity of equivalence relations. Math. Structures Comput. Sci. (2016, to apper)
  28.Rogers Jr., H.: Theory of Recursive Functions and Effective Computability. McGraw-Hill, New York (1967)MATH
  29.Shavrukov, V.Y.: Remarks on uniformly finitely positive equivalences. Math. Log. Quart. 42, 67–82 (1996)MathSciNet CrossRef MATH
  30.Smullyan, R.: Theory of Formal Systems. Annals of Mathematical Studies, vol. 47. Princeton University Press, Princeton (1961)CrossRef MATH
  31.Soare, R.I.: Recursively Enumerable Sets and Degrees. Perspectives in Mathematical Logic, Omega Series. Springer, Heidelberg (1987)CrossRef MATH
  32.Visser, A.: Numerations, \(\lambda \) -calculus & arithmetic. In: Seldin, J.P., Hindley, J.R. (eds.) To H. B. Curry: Essays on Combinatory Logic, Lambda Calculus and Formalism, pp. 259–284. Academic Press, London (1980)
  
• 作者单位：Uri Andrews (19)
  Serikzhan Badaev (20)
  Andrea Sorbi (21)
  
  19. Department of Mathematics, University of Wisconsin, Madison, WI, 53706-1388, USA
  20. Department of Fundamental Mathematics, Al-Farabi Kazakh National University, Almaty, 050040, Kazakhstan
  21. Dipartimento di Ingegneria Informatica e Scienze Matematiche, Università Degli Studi di Siena, 53100, Siena, Italy
  
• 丛书名：Computability and Complexity
• ISBN：978-3-319-50062-1
• 卷排序：10010

文摘

We review the literature on universal computably enumerable equivalence relations, i.e. the computably enumerable equivalence relations (ceers) which are \(\Sigma ^0_1\)-complete with respect to computable reducibility on equivalence relations. Special attention will be given to the so-called uniformly effectively inseparable (u.e.i.) ceers, i.e. the nontrivial ceers yielding partitions of the natural numbers in which each pair of distinct equivalence classes is effectively inseparable (uniformly in their representatives). The u.e.i. ceers comprise infinitely many isomorphism types. The relation of provable equivalence in Peano Arithmetic plays an important role in the study and classification of the u.e.i. ceers.