Turing degrees and automorphism groups of substructure lattices

R. D. Dimitrov ; V. S. Harizanov ; A. S. Morozov

Algebra i logika, Tome 59 (2020) no. 1, pp. 27-47.

Résumé

The study of automorphisms of computable and other structures connects computability theory with classical group theory. Among the noncomputable countable structures, computably enumerable structures are one of the most important objects of investigation in computable model theory. Here we focus on the lattice structure of computably enumerable substructures of a given canonical computable structure. In particular, for a Turing degree $\mathbf{d}$, we investigate the groups of $\mathbf{d}$-computable automorphisms of the lattice of $\mathbf{d}$-computably enumerable vector spaces, of the interval Boolean algebra $\mathcal{B}_{\eta}$ of the ordered set of rationals, and of the lattice of $\mathbf{d}$-computably enumerable subalgebras of $\mathcal{B}_{\eta}$. For these groups, we show that Turing reducibility can be used to substitute the group-theoretic embedding. We also prove that the Turing degree of the isomorphism types for these groups is the second Turing jump $\mathbf{d^{\prime \prime }}$ of $\mathbf{d}$.

Détail

Mots-clés : automorphism
Keywords: lattice of $\mathbf{d}$-enumerable vector subspaces, groups of $\mathbf{d}$-computable automorphisms, interval Boolean algebra of ordered set of rationals, Turing reducibility, Turing degree, Turing jump.

Bibliographie

[1] B. L. Van der Waerden, Algebra, v. I, II, Springer, New York, NY, 2003 ; B. L. Van der Varden, Algebra, Nauka, M., 1976 | MR | MR

[2] R. I. Soare, Recursively enumerable sets and degrees. A study of computable functions and computably generated sets, Perspect. Math. Log., Omega Series, Springer-Verlag, Berlin etc., 1987 ; R. I. Soar, Vychislimo perechislimye mnozhestva i stepeni. Izuchenie vychislimykh funktsii i vychislimo perechislimykh mnozhestv, Kazanskoe matem. ob-vo, Kazan, 2000 | DOI | MR

[3] H. Rogers, Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967 ; Kh. Rodzhers, Teoriya rekursivnykh funktsii i effektivnaya vychislimost, Mir, M., 1972 | MR | Zbl

[4] S. S. Goncharov, Yu. L. Ershov, Konstruktivnye modeli, Sibirskaya shkola algebry i logiki, Nauchnaya kniga, Novosibirsk, 1999

[5] E. B. Fokina, V. Harizanov, A. Melnikov, “Computable model theory”, Turing's Legacy: Developments from Turing's ideas in logic, Lect. Notes Log., 42, ed. R. Downey, Cambridge Univ. Press, Assoc. Symbol. Logic, Cambridge, 2014, 124–194 | MR

[6] A. S. Morozov, “Groups of computable automorphisms”, Handbook of recursive mathematics, v. 1, Stud. Log. Found. Math., 138, Recursive model theory, eds. Yu. L. Ershov et al., Elsevier, Amsterdam, 1998, 311–345 | DOI | MR | Zbl

[7] A. S. Morozov, “Perestanovki i neyavnaya opredelimost”, Algebra i logika, 27:1 (1988), 19–36

[8] A. S. Morozov, “Tyuringova svodimost kak algebraicheskaya vlozhimost”, Sib. matem. zh., 38:2 (1997), 362–364 | Zbl

[9] A. S. Morozov, “O teoriyakh klassov grupp rekursivnykh perestanovok”, Matematicheskaya logika i algoritmicheskie problemy, Tr. in-ta matem. SO AN SSSR, 12, 1989, 91–104 | Zbl

[10] A. S. Morozov, “O vychislimykh gruppakh avtomorfizmov modelei”, Algebra i logika, 25:4 (1986), 415–424 | Zbl

[11] S. S. Goncharov, V. S. Kharizanov, Yu. F. Nait, A. S. Morozov, A. V. Romina, “Ob avtomorfnykh kortezhakh elementov v vychislimykh modelyakh”, Sib. matem. zh., 46:3 (2005), 523–532 | Zbl

[12] J. F. Knight, “Degrees coded in jumps of orderings”, J. Symb. Log., 51:4 (1986), 1034–1042 | DOI | MR | Zbl

[13] V. Harizanov, R. Miller, “Spectra of structures and relations”, J. Symb. Log., 72:1 (2007), 324–348 | DOI | MR | Zbl

[14] L. J. Richter, Degrees of unsolvability of models, Ph. D. thesis, Univ. Illinois at Urbana-Champaign, 1977 | MR | Zbl

[15] L. J. Richter, “Degrees of structures”, J. Symb. Log., 46:4 (1981), 723–731 | DOI | MR | Zbl

[16] R. Dimitrov, V. Harizanov, A. Morozov, “Automorphism groups of substructure lattices of vector spaces in computable algebra”, Pursuit of the universal, 12th conf. comput. Europe, CiE 2016 (Paris, France, June 27–July 1, 2016), Lect. Notes Comput. Sci., 9709, eds. A. Beckmann et al., Springer, Cham, 2016, 251–260 | DOI | MR | Zbl

[17] G. Metakides, A. Nerode, “Recursively enumerable vector spaces”, Ann. Math. Logic, 11 (1977), 147–171 | DOI | MR | Zbl

[18] R. G. Downey, J. B. Remmel, “Computable algebras and closure systems: coding properties”, Handbook of recursive mathematics, v. 2, Stud. Logic Found. Math., 139, Recursive algebra, analysis and combinatorics, eds. Yu. L. Ershov et al., Elsevier, Amsterdam, 1998, 997–1039 | MR

[19] R. D. Dimitrov, V. S. Harizanov, A. S. Morozov, “Dependence relations in computably rigid computable vector spaces”, Ann. Pure Appl. Logic, 132:1 (2005), 97–108 | DOI | MR | Zbl

[20] R. G. Downey, D. R. Hirschfeldt, A. M. Kach, S. Lempp, J. R. Mileti, A. Montalbán, “Subspaces of computable vector spaces”, J. Algebra, 314:2 (2007), 888–894 | DOI | MR | Zbl

[21] D. R. Guichard, “Automorphisms of substructure lattices in recursive algebra”, Ann. Pure Appl. Logic, 25 (1983), 47–58 | DOI | MR | Zbl