RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
General information
Latest issue
Archive
Impact factor
Subscription

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Algebra Logika:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Algebra Logika, 2020, Volume 59, Number 1, Pages 27–47 (Mi al933)  

Turing degrees and automorphism groups of substructure lattices

R. D. Dimitrova, V. S. Harizanovb, A. S. Morozovcd

a Dep. Math., Western Illinois Univ., Macomb, IL 61455, USA
b Dep. Math., George Washington Univ., Washington, DC 20052, USA
c Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Novosibirsk
d Novosibirsk State University

Abstract: 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}$.

Keywords: automorphism, 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.

Funding Agency Grant Number
National Science Foundation DMS-1101123
Simons Foundation


DOI: https://doi.org/10.33048/alglog.2020.59.102

Full text: PDF file (299 kB)
First page: PDF file
References: PDF file   HTML file

UDC: 510.65
Received: 06.03.2019
Revised: 30.04.2020

Citation: R. D. Dimitrov, V. S. Harizanov, A. S. Morozov, “Turing degrees and automorphism groups of substructure lattices”, Algebra Logika, 59:1 (2020), 27–47

Citation in format AMSBIB
\Bibitem{DimHarMor20}
\by R.~D.~Dimitrov, V.~S.~Harizanov, A.~S.~Morozov
\paper Turing degrees and automorphism groups of substructure lattices
\jour Algebra Logika
\yr 2020
\vol 59
\issue 1
\pages 27--47
\mathnet{http://mi.mathnet.ru/al933}
\crossref{https://doi.org/10.33048/alglog.2020.59.102}


Linking options:
  • http://mi.mathnet.ru/eng/al933
  • http://mi.mathnet.ru/eng/al/v59/i1/p27

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Алгебра и логика Algebra and Logic
    Number of views:
    This page:83
    References:2
    First page:4

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020