Turing Degrees and Automorphism Groups of Substructure Lattices

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

Research output: Contribution to journalArticlepeer-review


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 d, we investigate the groups of d-computable automorphisms of the lattice of d-computably enumerable vector spaces, of the interval Boolean algebra Bη of the ordered set of rationals, and of the lattice of d-computably enumerable subalgebras of Bη. 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 d′′ of d.

Original languageEnglish
Pages (from-to)18-32
Number of pages15
JournalAlgebra and Logic
Issue number1
Publication statusPublished - 1 Mar 2020


  • automorphism
  • groups of d-computable automorphisms
  • interval Boolean algebra of ordered set of rationals
  • lattice of d-enumerable vector subspaces
  • Turing degree
  • Turing jump
  • Turing reducibility

Fingerprint Dive into the research topics of 'Turing Degrees and Automorphism Groups of Substructure Lattices'. Together they form a unique fingerprint.

Cite this