×

zbMATH — the first resource for mathematics

Examples of nonautostable systems. (English. Russian original) Zbl 0595.03031
Sib. Math. J. 25, 538-545 (1984); translation from Sib. Mat. Zh. 25, No. 4(146), 37-45 (1984).
An enumeration \(\nu\) : \(N\to {\mathfrak A}\) is called a constructivization of a countable model \({\mathfrak A}\) if (roughly speaking) the relations and functions of the presentation of \({\mathfrak A}\) on N given by \(\nu\) are recursive. Constructivizations \(\nu\) and \(\mu\) are autoequivalent if there is an automorphism \(\phi\) of \({\mathfrak A}\) and a recursive function f such that \(\phi \nu =\mu f\). Model \({\mathfrak A}\) is called autostable if any two constructivizations of \({\mathfrak A}\) are autoequivalent. The algorithmic dimension of a model \({\mathfrak A}\), \(\dim_ A{\mathfrak A}\), is the maximal number of nonautoequivalent constructivizations of \({\mathfrak A}\). Among the results on algorithmic dimensions and possible numbers of autoequivalent constructivizations, which are not recursively equivalent, we have the following: there are models \({\mathfrak A}\) and \({\mathfrak B}\) such that \(\dim_ A{\mathfrak A}=1\) and \(\dim_ A{\mathfrak A}^ 2\geq 2\), \(\dim_ A{\mathfrak B}=\aleph_ 0\) and \(\dim_ A{\mathfrak B}^ 2=1\). Examples are given to show that the class of autostable models is not closed under finitely generated extensions. The paper is concluded with remarks concerning autostability of periodic groups.
Reviewer: R.Kossak

MSC:
03C57 Computable structure theory, computable model theory
03D45 Theory of numerations, effectively presented structures
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] S. S. Goncharov, ?Autostability of models and Abelian groups,? Algebra Logika,19, No. 1, 23-44 (1980).
[2] S. S. Goncharov and V. D. Dzgoev, ?Autostability of models,? Algebra Logika,19, No. 2, 45-58 (1980). · Zbl 0468.03023
[3] S. S. Goncharov, ?Autostability and computable families of constructivizations,? Algebra Logika,14, No. 6, 647-680 (1975).
[4] S. S. Goncharov and A. A. Novikov, ?Two examples of nonautostable systems,? in: Sixteenth All-Union Algebraic Conference, Leningrad (1981).
[5] V. D. Dzgoev, ?Recursive automorphisms of constructive models,? in: Fifteenth All-Union Algebraic Conference. Abstracts of Reports, Krasnoyarsk (1979).
[6] Yu. L. Ershov, Theory of Enumerations [in Russian], Nauka, Moscow (1977).
[7] Yu. L. Ershov, Problems of Solvability and Constructive Models [in Russian], Nauka, Moscow (1980).
[8] A. I. Mal’tsev, ?Recursive Abelian groups,? Dokl. Akad. Nauk SSSR,156, No. 5, 1009-1012 (1962).
[9] A. T. Nurtazin, ?Computable enumerations of classes and algebraic tests for autostability,? Author’s Abstract of Candidate’s Dissertation (1975).
[10] A. I. Mal’tsev, Algebraic Systems [in Russian], Nauka, Moscow (1970).
[11] H. Rogers, Jr., Theory of Recursive Functions and Effective Computability, McGraw-Hill (1967). · Zbl 0183.01401
[12] L. Fuchs, Infinite Abelian Groups, Academic Press (1970, 1973). · Zbl 0209.05503
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.