Geodesic
On functors enumerating structures
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 14 (2017), pp. 690-702.

Voir la notice de l'article provenant de la source Math-Net.Ru

We study a new notion of reduction between structures called enumerable functors related to the recently investigated notion of computable functors. Our main result shows that enumerable functors and effective interpretability with the equivalence relation computable are equivalent. We also obtain results on the relation between enumerable and computable functors.
Keywords: computable structure theory, enumerable functor, computable structures, enumeration reducibility. 
@article{SEMR_2017_14_a19,
     author = {Dino Rossegger},
     title = {On functors enumerating structures},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {690--702},
     publisher = {mathdoc},
     volume = {14},
     year = {2017},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2017_14_a19/}
}
TY  - JOUR
AU  - Dino Rossegger
TI  - On functors enumerating structures
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2017
SP  - 690
EP  - 702
VL  - 14
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2017_14_a19/
LA  - en
ID  - SEMR_2017_14_a19
ER  - 
%0 Journal Article
%A Dino Rossegger
%T On functors enumerating structures
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2017
%P 690-702
%V 14
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2017_14_a19/
%G en
%F SEMR_2017_14_a19
Dino Rossegger. On functors enumerating structures. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 14 (2017), pp. 690-702. http://geodesic.mathdoc.fr/item/SEMR_2017_14_a19/

[1] C. Ash, J. Knight, M. Manasse, T. Slaman, “Generic copies of countable structures”, Annals of Pure and Applied Logic, 42:3 (1989), 195–205 | DOI | MR | Zbl

[2] C. Ash, J. Knight, T. Slaman, “Relatively recursive expansions, II”, Fundamenta Mathematicae, 142:2 (1993), 147–161 | MR | Zbl

[3] W. Calvert, D. Cummins, J. Knight, S. Miller, “Comparing Classes of Finite Structures”, Algebra and Logic, 43:6 (2004), 374–392 | DOI | MR | Zbl

[4] J. Chisholm, “Effective model theory vs. recursive model theory”, Journal of Symbolic Logic, 55:3 (1990), 1168–1191 | DOI | MR | Zbl

[5] Yu. L. Ershov, Definability and Computability, Siberian School of Algebra and Logic, Springer-Verlag, 1996 | MR

[6] M. Harrison-Trainor, A.G. Melnikov, R. Miller, A. Montalbán, “Computable functors and effective interpretability”, Journal of Symbolic Logic, 82:1 (2017), 77–97 | DOI | MR | Zbl

[7] M. Harrison-Trainor, R. Miller, A. Montalbán, Borel Functors and Infinitary Interpretations, 2016, arXiv: 1606.07489

[8] D. R. Hirschfeldt, B. Khoussainov, R.A. Shore, A.M. Slinko, “Degree spectra and computable dimensions in algebraic structures”, Annals of Pure and Applied Logic, 115:1–3 (2002), 71–113 | DOI | MR | Zbl

[9] I. Sh. Kalimullin, “Relations between algorithmic reducibilities of algebraic systems”, Russian Mathematics, 53:6 (2009), 58–59 | DOI | MR | Zbl

[10] J. Knight, S. Miller, M. Vanden Boom, “Turing Computable Embeddings”, Journal of Symbolic Logic, 72:3 (2007), 901–918 | DOI | MR | Zbl

[11] R. Miller, B. Poonen, H. Schoutens, A. Shlapentokh, A computable functor from graphs to fields, 2015, arXiv: 1510.07322

[12] A. Montalbán, “Rice sequences of relations”, Philosophical Transactions of the Royal Society of London A: Mathematical, Physical and Engineering Sciences, 370:1971 (2012), 3464–3487 | DOI | MR | Zbl

[13] A. Montalbán, “Computability theoretic classifications for classes of structures”, Proccedings of the ICM 2014, v. 2, 2014, 79–101

[14] A. S. Morozov, M. V. Korovina, “${\Sigma}$-definability of countable structures over real numbers, complex numbers, and quaternions”, Algebra and Logic, 47:3 (2008), 193–209 | DOI | MR | Zbl

[15] V. G. Puzarenko, “A certain reducibility on admissible sets”, Siberian Mathematical Journal, 50:2 (2009), 330–340 | DOI | MR | Zbl

[16] D. Rossegger, Computable Transformations of Classes of Structures, Master's thesis, Technische Universität Wien, 2015

[17] R. I. Soare, Turing Computability, Theory and Applications of Computability, Springer, Berlin–Heidelberg, 2016 | DOI | MR | Zbl

[18] A. Soskova, M. Soskova, “Enumeration Reducibility and Computable Structure Theory”, Computability and Complexity, Springer, 2017, 271–301 | DOI | Zbl

[19] A. I. Stukachev, “Degrees of presentability of structures, I”, Algebra and Logic, 46:6 (2007), 419–432 | DOI | MR | Zbl

[20] A. I. Stukachev, “Degrees of presentability of structures, II”, Algebra and Logic, 47:1 (2008), 65–74 | DOI | MR | Zbl

[21] A. I. Stukachev, “Effective model theory: An approach via $\Sigma$-definability”, Effective Mathematics of the Uncountable, Lecture Notes in Logic, 41, 2013, 164–197 | MR | Zbl