zbMATH — the first resource for mathematics

On the Ershov upper semilattice \({\mathfrak L}_E\). (Russian, English) Zbl 1063.03019
Sib. Mat. Zh. 45, No. 1, 211-228 (2004); translation in Sib. Math. J. 45, No. 1, 173-187 (2004).
Some basic relations between the \(\Sigma\)-reducibility in algebraic systems and \(T\)-reducibility are established. Then the author proves a series of results on \(\Sigma\)-definability in algebraic systems in which these systems appear to be isomorphic to computable systems. In particular, he proves that 1) if a quasi-rigid model is strongly \(\Sigma\)-definable over a hereditarily finite admissible set over a locally constructivizable model then it is isomorphic to a computable model; 2) each Abelian group and Ershov algebra are locally constructivizable; 3) if an antisymmetric and connected model is \(\Sigma\)-definable over a hereditarily finite admissible set over a countable Ershov algebra, then it has a constructivization.

03C57 Computable structure theory, computable model theory
03D45 Theory of numerations, effectively presented structures
03D60 Computability and recursion theory on ordinals, admissible sets, etc.
Full Text: EuDML EMIS