Constructing decidable graphs from decidable structures

N. A. Bazhenov ; M. Harrison-Trainor

Algebra i logika, Tome 58 (2019) no. 5, pp. 553-573.

Résumé

It is shown that every structure (including one in an infinite language) can be transformed into a graph that is bi-interpretable with the original structure, for which the full elementary diagrams can be computed one from the other.

Détail

Keywords: decidable structure, decidable graph, bi-interpretable structures, full diagram.

Bibliographie

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

[2] A. Montalbán, “Computability theoretic classifications for classes of structures”, Proc. of the Int. Congress of Math., ICM 2014 (Seoul, Korea, August 13–21, 2014), v. II, Invited lectures, eds. Sun Young Jang et al., KM Kyung Moon Sa, Seoul, 2014, 79–101 | MR | Zbl

[3] W. Hodges, Model theory, Encycl. Math. Appl., 42, Cambridge Univ. Press, Cambridge, 1993 | MR | Zbl

[4] R. Miller, B. Poonen, H. Schoutens, A. Shlapentokh, “A computable functor from graphs to fields”, J. Symb. Log., 83:1 (2018), 326–348 | DOI | MR | Zbl

[5] S. S. Goncharov, “Problema chisla neavtoekvivalentnykh konstruktivizatsii”, Algebra i logika, 19:6 (1980), 621–639 | MR

[6] S. S. Goncharov, M. I. Marchuk, “Indeksnye mnozhestva avtoustoichivykh otnositelno silnykh konstruktivizatsii konstruktivnykh modelei konechnoi signatury i signatury grafov”, Algebra i logika, 54:6 (2015), 663–679

[7] N. Bazhenov, “Autostability spectra for decidable structures”, Math. Structures Comput. Sci., 28:3 (2018), 392–411 | DOI | MR

[8] M. Harrison-Trainor, “There is no classification of the decidably presentable structures”, J. Math. Log., 18:2 (2018), 1850010, 41 pp. | DOI | MR | Zbl

[9] T. A. Slaman, “Relative to any nonrecursive set”, Proc. Am. Math. Soc., 126:7 (1998), 2117–2122 | DOI | MR | Zbl

[10] S. Wehner, “Enumerations, countable structures and Turing degrees”, Proc. Am. Math. Soc., 126:7 (1998), 2131–2139 | DOI | MR | Zbl

[11] D. R. Hirschfeldt, “Computable trees, prime models, and relative decidability”, Proc. Am. Math. Soc., 134:5 (2006), 1495–1498 | DOI | MR | Zbl

[12] S. S. Goncharov, “O chisle neavtoekvivalentnykh konstruktivizatsii”, Algebra i logika, 16:3 (1977), 257–282 | MR | Zbl

[13] S. S. Goncharov, “Avtoustoichivost i vychislimye semeistva konstruktivizatsii”, Algebra i logika, 14:6 (1975), 647–680 | MR | Zbl

[14] O. V. Kudinov, “Avtoustoichivaya 1-razreshimaya model bez vychislimogo semeistva Skotta $\exists$-formul”, Algebra i logika, 35:4 (1996), 458–467 | MR | Zbl

[15] U. Andrews, J. S. Miller, “Spectra of theories and structures”, Proc. Am. Math. Soc., 143:3 (2015), 1283–1298 | DOI | MR | Zbl

[16] U. Andrews, M. Cai, D. Diamondstone, S. Lempp, J. S. Miller, “Theory spectra and classes of theories”, Trans. Am. Math. Soc., 369:9 (2017), 6493–6510 | DOI | MR | Zbl

[17] P. M. Semukhin, D. Turetski, E. B. Fokina, “Spektry stepenei struktur otnositelno ekvivalentnostei”, Algebra i logika, 58:2 (2019), 229–251 | Zbl

[18] A. Montalbán, “A fixed point for the jump operator on structures”, J. Symb. Log., 78:2 (2013), 425–438 | DOI | MR | Zbl

[19] Yu. L. Ershov, Opredelimost i vychislimost, Sibirskaya shkola algebry i logiki, Nauchnaya kniga (NII MIOO NGU), Novosibirsk, 1996 | MR

[20] H. Gaifman, “On local and non-local properties”, Proc. Herbrand Symp., Logic colloquium '81 (Marseille, 1981), Stud. Logic Found. Math., 107, 1982, 105–135 | DOI | MR | Zbl

[21] A. Montalbán, Computable structure theory: Within the arithmetic, https://math.berkeley.edu/ãntonio/CSTpart1.pdf