Turing Degrees and Automorphism Groups of Substructure Lattices

Turing Degrees and Automorphism Groups of Substructure Lattices Full article

Journal

Algebra and Logic
ISSN: 0002-5232 , E-ISSN: 1573-8302

Output data

Year: 2020, Volume: 59, Number: 1, Pages: 18-32 Pages count : 15 DOI: 10.1007/s10469-020-09576-x

Tags

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

Authors

Dimitrov R.D. ^1,4 , Harizanov V. ^2,4 , Morozov A.S. ^3,4

Affiliations

1	Department of Mathematics, Western Illinois University, Macomb, IL 61455, United States
2	Department of Mathematics, George Washington University, Washington, DC 20052, United States
3	Sobolev Institute of Mathematics, pr. Akad. Koptyuga 4, Novosibirsk, 630090, Russian Federation
4	Novosibirsk State University, ul. Pirogova 1, Novosibirsk, 630090, Russian Federation

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. © 2020, Springer Science+Business Media, LLC, part of Springer Nature.

Dimitrov R.D. , Harizanov V. , Morozov A.S.
Turing Degrees and Automorphism Groups of Substructure Lattices
Algebra and Logic. 2020. V.59. N1. P.18-32. DOI: 10.1007/s10469-020-09576-x WOS Scopus OpenAlex

Димитров Р. , Харизанова В. , Морозов А.С.
Тьюринговы степени и группы автоморфизмов решёток подструктур
Алгебра и логика. 2020. Т.59. №1. С.27-47. DOI: 10.33048/alglog.2020.59.102 РИНЦ MathNet OpenAlex

Web of science:	WOS:000534700100002
Scopus:	2-s2.0-85085048490
OpenAlex:	W3027676332

DB	Citing
Scopus	1
OpenAlex	2
Web of science	1