Top

Published in:

2017 | OriginalPaper | Chapter

Enumeration Reducibility and Computable Structure Theory

Authors : Alexandra A. Soskova, Mariya I. Soskova

Published in: Computability and Complexity

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

The relationship between enumeration degrees and abstract models of computability inspires a new direction in the field of computable structure theory. Computable structure theory uses the notions and methods of computability theory in order to find the effective contents of some mathematical problems and constructions. The paper is a survey on the computable structure theory from the point of view of enumeration reducibility.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Revisiting Uniform Computable Categoricity: For the Sixtieth Birthday of Prof. Rod Downey

next chapter Strength and Weakness in Computable Structure Theory

Note, that this indexing does not quite match the usual definition of computable infinitary formulas, namely level zero in this definition corresponds to level one in the usual definition.

Theorem 17 was first announced by Soskov during his LC talk in Münster in 2002.

Arslanov, M.M., Cooper, S.B., Kalimullin, I.S.: Splitting properties of total enumeration degrees. Algebra Logic 42, 1–13 (2003)MathSciNetCrossRefMATH

Ash, C.J.: Generalizations of enumeration reducibility using recursive infinitary propositional senetences. Ann. Pure Appl. Logic 58, 173–184 (1992)MathSciNetCrossRefMATH

Ash, C.J., Knight, J.: Computable Structures and the Hyperarithmetical Hierarchy, Volume 144. Studies in Logic and the Foundations of Mathematics. North-Holland Publishing Co., Amsterdam (2000)MATH

Ash, C.J., Knight, J.F., Manasse, M., Slaman, T.: Generic copies of countable structures. Ann. Pure Appl. Logic 42, 195–205 (1989)MathSciNetCrossRefMATH

Baleva, V.: The jump operation for structure degrees. Arch. Math. Logic 45, 249–265 (2006)MathSciNetCrossRefMATH

Barwise, J.: Admissible Sets and Structures. Springer, Berlin (1975)CrossRefMATH

Boutchkova, V.: Genericity in abstract structure degrees. Ann. Sofia Univ. Fac. Math. Inf. 95, 35–44 (2001)MathSciNetMATH

Cai, M., Ganchev, H.A., Lempp, S., Miller, J.S., Soskova, M.I.: Defining totality in the enumeration degrees. J. Am. Math. Soc. http://dx.doi.org/10.1090/jams/848

Case, J.: Enumeration reducibility and partial degrees. Ann. Math. Logic 2, 419–439 (1971)MathSciNetCrossRefMATH

10.

Chisholm, J.: Effective model theory vs. recursive model theory. J. Symbol. Logic 55, 1168–1191 (1990)MathSciNetCrossRefMATH

11.

Coles, R., Downey, R., Slaman, T.: Every set has a least jump enumeration. Bull. Lond. Math. Soc. 62, 641–649 (2000)MathSciNetCrossRefMATH

12.

Cooper, S.B.: Partial degrees and the density problem. Part 2: the enumeration degrees of the \(\Sigma _2\) sets are dense. J. Symbol. Logic 49, 503–513 (1984)CrossRefMATH

13.

Downey, R.G.: On presentations of algebraic structures. In: Sorbi, A. (ed.) Complexity, Logic and Recursion Theory. Lecture Notes in Pure and Applied Mathematics, vol. 187, pp. 157–205 (1997)

14.

Downey, R.G., Knight, J.F.: Orderings with \(\alpha \)-th jump degree \({\bf {0}}^{(\alpha )}\). Proc. Am. Math. Soc. 114, 545–552 (1992)MathSciNetMATH

15.

Enderton, H.B., Putnam, H.: A note on the hyperarithmetical hierarchy. J. Symbol. Logic 35, 429–430 (1970)MathSciNetCrossRefMATH

16.

Ershov, Y.L.: \(\Sigma \)-denability in admissible sets. Sov. Math. Dokl. 3, 767–770 (1985)MATH

17.

Ershov, Y.L.: Definability and Computability. Consultants Bureau, New York-London-Moscow (1996)

18.

Ershov, Y., Puzarenko, V.G., Stukachev, A.I.: HF-computability. In: Cooper, B.S., Sorbi, A. (eds.) Computability in Context Computation and Logic in the Real World, pp. 169–242. Imperial College Press (2011)

19.

Fraisse, R.: Une notion de recursivite relative. In: Proceedings of the Symposium of Mathematics 1959, Infinistic Methods, pp. 323–328. Pergamon Press, Warsaw (1961)

20.

Friedberg, R.M., Rogers Jr., H.: Reducibility and completeness for sets of integers. Z. Math. Logik Grundlag. Math. 5, 117–125 (1959)MathSciNetCrossRefMATH

21.

Friedman, H.: Algorithmic procedures, generalized turing algorithms and elementary recursion theory. In: Gandy, R.O., Yates, C.E.M. (eds.) Logic Colloquium-69, pp. 361–389. North-Holland, Amsterdam (1971)

22.

Ganchev, H.: A total degree splitting theorem and a jump inversion splitting theorem. In: Proceedings of the 5th Panhellenic Logic Symposium, Athens, Greece, pp. 79–81 (2005)

23.

Ganchev, H.: Exact pair theorem for the \(\omega \)-enumeration degrees. In: Cooper, S.B., Löwe, B., Sorbi, A. (eds.) CiE 2007. LNCS, vol. 4497, pp. 316–324. Springer, Heidelberg (2007). doi:10.1007/978-3-540-73001-9_33 CrossRef

24.

Ganchev, H.: A jump inversion theorem for the infinite enumeration jump. Ann. Univ. Sofia Univ. 98, 61–85 (2008)MathSciNet

25.

Ganchev, H.: Definability in the local theory of the \(\omega \)-enumeration degrees. In: Ambos-Spies, K., Löwe, B., Merkle, W. (eds.) CiE 2009. LNCS, vol. 5635, pp. 242–249. Springer, Heidelberg (2009). doi:10.1007/978-3-642-03073-4_25 CrossRef

26.

Ganchev, H., Soskov, I.N.: The groups Aut(\(\mathcal{D}^{\prime }_{\omega }\)) and Aut(\(\mathcal{D}_e\)) are isomorphic. In: Proceedings of the 6th Panhellenic Logic Symposium, Volos, Greece, pp. 53–57 (2007)

27.

Ganchev, H., Soskov, I.N.: The jump operator on the \(\omega \)-enumeration degrees. Ann. Pure Appl. Logic 160, 289–301 (2009)MathSciNetCrossRefMATH

28.

Ganchev, H., Soskova, M.: The high/low hierarchy in the local structure of the \(\omega \)-enumeration degrees. Ann. Pure Appl. Logic 163(5), 547–566 (2012)MathSciNetCrossRefMATH

29.

Ganchev, H.A., Soskova, M.I.: Interpreting true arithmetic in the local structure of the enumeration degrees. J. Symbol. Log. 77(4), 1184–1194 (2012)MathSciNetCrossRefMATH

30.

Ganchev, H.A., Soskova, M.I.: Definability via Kalimullin pairs in the structure of the enumeration degrees. Trans. AMS 367, 4873–4893 (2015)MathSciNetCrossRefMATH

31.

Goncharov, S., Khoussainov, B.: Complexity of categorical theories with computable models. Algebra Logic 43(6), 365–373 (2004)MathSciNetCrossRef

32.

Goncharov, S., Harizanov, V., Knight, J., McCoy, C., Miller, R., Solomon, R.: Enumerations in computable structure theory. Ann. Pure Appl. Logic 136(3), 219–246 (2005)MathSciNetCrossRefMATH

33.

Greenberg, N., Montalbán, A., Slaman, T.A.: Relative to any non-hyperarithmetic set. J. Math. Logic 13(01) (2013). doi:10.1142/S0219061312500079

34.

Gordon, C.: Comparisons between some generalizations of recursion theory. Compos. Math. 22, 333–346 (1970)MathSciNetMATH

35.

Harris, K., Montabán, A.: On the \(n\)-back-and-forth types of Boolean algebras. Trans. AMS 364, 827–866 (2012)MathSciNetCrossRefMATH

36.

Jojgov, G.: Minimal pairs of structure degrees. Master’s thesis, Sofia University (1997)

37.

Jockusch Jr., C.G.: Semirecursive sets and positive reducibility. Trans. Am. Math. Soc. 131, 420–436 (1968)MathSciNetCrossRefMATH

38.

Kalimullin, I.: Some notes on degree spectra of the structures. In: Cooper, S.B., Löwe, B., Sorbi, A. (eds.) CiE 2007. LNCS, vol. 4497, pp. 389–397. Springer, Heidelberg (2007). doi:10.1007/978-3-540-73001-9_40 CrossRef

39.

Kalimullin, I.S.: Enumeration degrees and enumerability of families. J. Logic Comput. 19(1), 151–158 (2009)MathSciNetCrossRefMATH

40.

Knight, J.F.: Degrees coded in jumps of orderings. J. Symbol. Logic 51, 1034–1042 (1986)MathSciNetCrossRefMATH

41.

Knight, J.F.: Degrees of models. In: Handbook of Recursive Mathematics, Volume 1, Studies Logic Foundations of Mathematics, vol. 138, pp. 289–309. North-Holland, Amsterdam (1998)

42.

Kreisel, G.: Some reasons for generalizing recursion theory. In: Gandy, R.O., Yates, C.E.M. (eds.) Logic Colloquium 69, pp. 139–198. North Holland (1971)

43.

Kreisel, G., Sacks, G.E.: Metarecursive sets. J. Symbol. Logic 30, 318–338 (1965)MathSciNetCrossRefMATH

44.

Kripke, S.: Transfinite recursion on admissible ordinals, I, II (abstracts). J. Symbol. Logic 29, 161–162 (1964)

45.

Lacombe, D.: Deux generalizations de la notion de recursivite relative. C. R. de l-Academie des Sciences de Paris 258, 3410–3413 (1964)MathSciNetMATH

46.

Lempp, S., Slaman, T.A., Sorbi, A.: On extensions of embeddings into the enumeration degrees of the \(\Sigma ^0_2\)-sets. J. Math. Log. 5(2), 247–298 (2005)MathSciNetCrossRefMATH

47.

Marker, D.: Non \(\Sigma _n\)-axiomatizable almost strongly minimal theories. J. Symbol. Logic 54(3), 921–927 (1989)MathSciNetCrossRefMATH

48.

McEvoy, K.: Jumps of quasi-minimal enumeration degrees. J. Symbol. Logic 50, 839–848 (1985)MathSciNetCrossRefMATH

49.

Medvedev, I.T.: Degrees of difficulty of the mass problem. Dokl. Nauk. SSSR 104, 501–504 (1955)MathSciNet

50.

Montalbán, A.: Notes on the jump of a structure. In: Ambos-Spies, K., Löwe, B., Merkle, W. (eds.) CiE 2009. LNCS, vol. 5635, pp. 372–378. Springer, Heidelberg (2009). doi:10.1007/978-3-642-03073-4_38 CrossRef

51.

Montalbán, A.: Rice sequences of relations. Philos. Trans. R. Soc. A 370, 3464–3487 (2012)MathSciNetCrossRefMATH

52.

Montalbán, A.: Computable Structure Theory, draft

53.

Montague, R.: Recursion theory as a branch of model theory. In: Proceedings of the Third International Congress for Logic Methodology and Philosophy of Science, pp. 63–86. North-Holland, Amsterdam-London (1967)

54.

Moschovakis, Y.N.: Abstract first order computability I. Trans. Am. Math. Soc. 138, 427–464 (1969)MathSciNetMATH

55.

Moschovakis, Y.N.: Elementary Induction of Abstract Structures. North-Holland, Amsterdam (1974)MATH

56.

Moschovakis, Y.N.: Abstract computability and invariant definability. J. Symbol. Logic 34, 605–633 (1969)MathSciNetCrossRefMATH

57.

Myhill, J.: A note on the degrees of partial functions. Proc. Am. Math. Soc. 12, 519–521 (1961)MathSciNetCrossRefMATH

58.

Platek, R.: Foundations of recursion theory. Ph.D. thesis, Stanford University (1966)

59.

Plotkin, G.D.: A set-theoretical definition of application Memorandum MIP-R-95. University of Edinburgh, School of Artificial Intelligence (1972)

60.

Richter, L.J.: Degrees of unsolvability of models. Ph.D. dissertation, University of Illinois, Urbana-Champaign (1977)

61.

Richter, L.J.: Degrees of structures. J. Symbol. Logic 46, 723–731 (1981)MathSciNetCrossRefMATH

62.

Rozinas, M.: The semi-lattice of e-degrees. In: Recursive functions (Ivanovo), pp. 71–84. Ivano. Gos. Univ. (1978). (Russian)

63.

Sacks, G.E.: Forcing with perfect closed sets. Proc. Symp. Pure Math. 17, 331–355 (1971)MathSciNetCrossRefMATH

64.

Selman, A.L.: Arithmetical reducibilities I. Z. Math. Logik Grundlag. Math. 17, 335–350 (1971)MathSciNetCrossRefMATH

65.

Shepherdson, J.C.: Computation over abstract structures. In: Rose, H.E., Shepherdson, J.C. (eds.) Logic Colloquium-73, pp. 445–513. North-Holland, Amsterdam (1975)

66.

Skordev, D.G.: Computability in Combinatory Spaces. Kluwer Academic Publishers, Dordrecht-Boston-London (1992)CrossRefMATH

67.

Slaman, T.A.: Relative to any nonrecursive set. Proc. Am. Math. Soc. 126, 2117–2122 (1998)MathSciNetCrossRefMATH

68.

Slaman, T.A., Sorbi, A.: Quasi-minimal enumeration degrees and minimal Turing degrees. Annali di Matematica 174(4), 79–88 (1998)MathSciNetMATH

69.

Soskov, I.N.: Definability via enumerations. J. Symbol. Logic 54, 428–440 (1989)MathSciNetCrossRefMATH

70.

Soskov, I.N.: An external characterization of the Prime computability. Ann. Univ. Sofia Fac. Math. Inf. 83, 89–111 (1989)MathSciNetMATH

71.

Soskov, I.N.: Computability by means of effectively definable schemes and definability via enumerations. Arch. Math. Logic 29, 187–200 (1990)MathSciNetCrossRefMATH

72.

Soskov, I.N.: Constructing minimal pairs of degrees. Ann. Univ. Sofia 91, 101–112 (1997)MATH

73.

Soskov, I.N.: A jump inversion theorem for the enumeration jump. Arch. Math. Logic 39, 417–437 (2000)MathSciNetCrossRefMATH

74.

Soskov, I.N., Baleva, V.: Regular enumerations. J. Symbol. Logic 67, 1323–1343 (2002)MathSciNetCrossRefMATH

75.

Soskov, I.N.: Degree spectra and co-spectra of structures. Ann. Univ. Sofia 96, 45–68 (2004)MathSciNetMATH

76.

Soskov, I.N., Baleva, V.: Ash’s theorem for abstract structures. In: Chatzidakis, Z., Koepke, P., Pohlers, W. (eds.) Logic Colloquium 2002, Muenster, Germany, pp. 327–341. Association for Symbolic Logic (2006)

77.

Soskov, I.N., Kovachev, B.: Uniform regular enumerations. Math. Struct. Comput. Sci. 16(5), 901–924 (2006)MathSciNetCrossRefMATH

78.

Soskov, I.N.: The \(\omega \)-enumeration degrees. J. Logic Comput. 17, 1193–1217 (2007)MathSciNetCrossRefMATH

79.

Soskov, I., Soskova, M.: Kalimullin pairs of \(\Sigma ^0_2\) omega-enumeration degrees. Int. J. Softw. Inf. 5(4), 637–658 (2011)

80.

Soskov, I.N.: A note on \(\omega \)-jump inversion of degree spectra of structures. In: Bonizzoni, P., Brattka, V., Löwe, B. (eds.) CiE 2013. LNCS, vol. 7921, pp. 365–370. Springer, Heidelberg (2013). doi:10.1007/978-3-642-39053-1_43 CrossRef

81.

Soskov, I.N.: Effective properties of Marker’s extensions. J. Logic Comput. 23(6), 1335–1367 (2013). doi:10.1093/logcom/ext041 MathSciNetCrossRefMATH

82.

Soskova, A.A., Soskov, I.N.: Co-spectra of joint spectra of structures. Ann. Sofia Univ. Fac. Math. Inf. 96, 35–44 (2004)MathSciNetMATH

83.

Soskova, A.A.: Minimal pairs and quasi-minimal degrees for the joint spectra of structures. In: Cooper, S.B., Löwe, B., Torenvliet, L. (eds.) CiE 2005. LNCS, vol. 3526, pp. 451–460. Springer, Heidelberg (2005). doi:10.1007/11494645_56 CrossRef

84.

Soskova, A.A.: Properties of co-spectra of joint spectra of structures. Ann. Sofia Univ. Fac. Math. Inf. 97, 15–32 (2005)MathSciNet

85.

Soskova, A.A.: Relativized degree spectra. In: Beckmann, A., Berger, U., Löwe, B., Tucker, J.V. (eds.) CiE 2006. LNCS, vol. 3988, pp. 546–555. Springer, Heidelberg (2006). doi:10.1007/11780342_56 CrossRef

86.

Soskova, A.A.: Relativized degree spectra. J. Logic Comput. 17, 1215–1234 (2007)MathSciNetCrossRefMATH

87.

Soskova, A.A.: A jump inversion theorem for the degree spectra. In: Cooper, S.B., Löwe, B., Sorbi, A. (eds.) CiE 2007. LNCS, vol. 4497, pp. 716–726. Springer, Heidelberg (2007). doi:10.1007/978-3-540-73001-9_76 CrossRef

88.

Soskova, A.A., Soskov, I.N.: Jump spectra of abstract structures. In: Proceeding of the 6th Panhellenic Logic Symposium, Volos, Greece, pp. 114–117 (2007)

89.

Soskova, A.A.: \(\omega \)-degree spectra. In: Beckmann, A., Dimitracopoulos, C., Löwe, B. (eds.) CiE 2008. LNCS, vol. 5028, pp. 544–553. Springer, Heidelberg (2008). doi:10.1007/978-3-540-69407-6_58 CrossRef

90.

Soskova, A.A., Soskov, I.N.: A jump inversion theorem for the degree spectra. J. Logic Comput. 19, 199–215 (2009)MathSciNetCrossRefMATH

91.

Soskova, A., Soskov, I.N.: Quasi-minimal degrees for degree spectra. J. Logic Comput. 23(2), 1319–1334 (2013). doi:10.1093/logcom/ext045 MathSciNetCrossRefMATH

92.

Soskova, M., Soskov, I.: Embedding countable partial orderings in the enumeration degrees and the omega enumeration degrees. J. Logic Comput. 22(4), 927–952 (2012). doi:10.1093/logcom/exq051. First published online October 23, 2010MathSciNetCrossRefMATH

93.

Stukachev, A.I.: A jump inversion theorem for semilattices of \(\Sigma \)-degrees. Sib. \(\grave{E}\)lektron. Mat. Izv. 6, 182–190 (2009)

94.

Stukachev, A.I.: A jump inversion theorem for the semilattices of Sigma-degrees. Siberian Adv. Math. 20(1), 68–74 (2010)MathSciNetCrossRef

95.

Stukachev, A.I.: Effective model theory: an approach via \(\Sigma \)-definability. In: Greenberg, N., Hamkins, J.D., Hirschfeldt, D., Miller, R. (eds.) Effective Mathematics of the Uncountable. Lecture Notes in Logic, vol. 41, pp. 164–197 (2013)

96.

Vatev, S.: Omega spectra and co-spectra of structures. Master thesis, Sofia University (2008)

97.

Vatev, S.: Conservative extensions of abstract structures. In: Löwe, B., Normann, D., Soskov, I., Soskova, A. (eds.) CiE 2011. LNCS, vol. 6735, pp. 300–309. Springer, Heidelberg (2011). doi:10.1007/978-3-642-21875-0_32 CrossRef

98.

Vatev, S.: Another jump inversion theorem for structures. In: Bonizzoni, P., Brattka, V., Löwe, B. (eds.) CiE 2013. LNCS, vol. 7921, pp. 414–423. Springer, Heidelberg (2013). doi:10.1007/978-3-642-39053-1_49 CrossRef

99.

Vatev, S.: Effective properties of structures in the hyperarithmetical hierarchy. Ph.D. thesis, Sofia University (2014)

100.

Vatev, S.: On the notion of jump structure. Ann. Sofia Univ. Fac. Math. Inf. 102, 171–206 (2015)MathSciNet

101.

Wehner, St.: Enumerations, countable structures and turing degrees. Proc. Am. Math. Soc. 126, 2131–2139 (1998)

Title: Enumeration Reducibility and Computable Structure Theory
Authors: Alexandra A. Soskova
Mariya I. Soskova
Publisher: Springer International Publishing
Book: Computability and Complexity
Print ISBN: 978-3-319-50061-4

Electronic ISBN: 978-3-319-50062-1

Copyright Year: 2017
DOI: https://doi.org/10.1007/978-3-319-50062-1_19

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner