Computable embeddability for algebraic structures

Nikolay A. Bazhenov, Manat Mustafa

2021

Closed access Metadata (CSL-JSON)
DOI 10.1142/s1793557122501261
Data confidence 70 medium
How this score is calculated

It is built from checkable properties of the record itself: whether the article has a DOI, how many independent sources confirmed its data, whether the required fields are filled in, and how recent the latest confirmation is. Disagreement between sources and a missing identifier lower it. A value of 80 or above means the record was published without further checking; 60 to 79 means it is published at reduced confidence, with a manual check advisable. A record verified by an editor by hand is never pushed below 90 by a recalculation. This scores our data about the article, not the article itself.

Abstract

In computability theory, the standard tool to classify preorders is provided by the computable reducibility. If [Formula: see text] and [Formula: see text] are preorders with domain [Formula: see text], then [Formula: see text] is computably reducible to [Formula: see text] if and only if there is a computable function [Formula: see text] such that for all [Formula: see text] and [Formula: see text], [Formula: see text] [Formula: see text][Formula: see text]. We study the complexity of preorders which arise in a natural way in computable structure theory. We prove that the relation of computable isomorphic embeddability among computable torsion abelian groups is a [Formula: see text] complete preorder. A similar result is obtained for computable distributive lattices. We show that the relation of primitive recursive embeddability among punctual structures (in the setting of Kalimullin et al.) is a [Formula: see text] complete preorder.