Computable bi-embeddable categoricity
Nikolay A. Bazhenov, E. B. Fokina, D. Rossegger, L. San Mauro · Algebra i logika · 2018
We study the algorithmic complexity of isomorphic embeddings between computable structures.Suppose that L is a language.We say that L-structures A and B are bi-embeddable (denoted A ≈ B) if there are isomorphic embeddings f : A → B and g : B → A. The systematic investigation of the bi-embeddability relation in computable structure theory was initiated by Montalbán [1, 2]: he proved that any hyperarithmetical linear order is bi-embeddable with a computable one.In [3], similar results were obtained for Abelian p-groups, Boolean algebras, and compact metric spaces.The paper [4] studies degree spectra with respect to bi-embeddability.Definition 1.Let d be a Turing degree.We say that a computable structure S is d-computably bi-embeddably categorical if, for any computable structure A ≈ S, there are d-computable isomorphic embeddings f : A → S and g : S → A. The bi-embeddable categoricity spectrum of S is the set CatSpec ≈ (S) = {d : S is d-computably bi-embeddably categorical}.