zbMATH — the first resource for mathematics

Computable classes of constructivizations for models of finite constructivizability type. (English. Russian original) Zbl 0860.03032
Sib. Math. J. 34, No. 5, 812-824 (1993); translation from Sib. Mat. Zh. 34, No. 5, 23-37 (1993).
Let \(\nu\) be an enumeration of a countable structure \(M\). Expanding \(M\) by the names of all elements \(\nu(n)\) gives a structure \(M^*\). The theory of \(M^*\) is denoted by Th\((M,\nu)\). The set of all formulas from Th\((M,\nu)\) with at most \(n\) blocks of quantifiers is denoted by Th\(_n(M,\nu)\). The structure \((M,\nu)\) is called \(n\)-constructivizable if Th\(_n (M, \nu)\) is decidable. It is called \(n\)-complete if for every \(\varphi ({\mathbf a})\in\text{Th}_n(M,\nu)\) there exists an \(\exists\)-formula \(\psi ({\mathbf x})\) realized by \({\mathbf a}\) in \(M\) such that \(\psi ({\mathbf x})\) implies \(\varphi ({\mathbf x})\) in \(M\).
The paper is devoted to proving the following theorem. Let \((M,\nu)\) be \((n+1)\)-constructivizable and let \(M\) be \(n\)-complete but not \((n+1)\)-complete in any finite expansion by constants. Then for every effective class \(S\) of constructivizations of \(M\) one can effectively find a constructivization \(\mu\) which is not an \((n+1)\)-constructivization and is not autoequivalent to any element of \(S\).

03C57 Computable structure theory, computable model theory
Full Text: DOI
[1] S. S. Goncharov, ?The problem, of the number of nonautoequivalent constructivizations,? Algebra i Logika,19, No. 6, 621-639 (1980).
[2] S. S. Goncharov, ?On the number of nonautoequivalent constructivizations,? Algebra i Logika,16, No. 3, 257-289 (1977).
[3] S. S. Goncharov, ?Autostability, and computable families of constructivizations,? Algebra i Logika,14, No. 6, 647-680 (1975).
[4] S. S. Goncharov, ?Autostability of models and Abelian groups,? Algebra i Logika,19, No. 1, 23-44 (1980).
[5] S. S. Goncharov and V. D. Dzgoev, ?Autostability of models,?. Algebra i Logika,19, No. 1, 45-58 (1980). · Zbl 0468.03023
[6] V. P. Dobritsa, ?Computability of certain classes of constructive algebras,? Sibirsk. Mat. Zh.,18, No. 3, 570-579 (1977).
[7] V. P. Dobritsa, ?Complexity of the index set of a constructive model,? Algebra i Logika,19, No. 1, 45-58 (1980).
[8] Yu. L. Ershov, Decidability Problems and Constructive Models [in Russian], Nauka, Moscow (1980).
[9] A. T. Nurtazin, ?Strong and weak constructivizations and computable families,? Algebra i Logika,13, No. 3, 311-323 (1974).
[10] C. J. Ash and A. Nerode, ?Intrinsically recursive relations,? in: Aspects of Effective Algebra: Proc. Conf. at Monash. Univ., Australia, Upside Down a Book Company, 1981, pp. 24-41. · Zbl 0467.03041
[11] S. S. Goncharov, ?Certain properties of constructivizations of Boolean algebras,? Sibirsk. Mat. Zh.,16, No. 2, 264-278 (1975).
[12] S. S. Goncharov, ?Bounded theories of constructive Boolean algebras,? Sibirsk. Mat. Zh.,17, No. 4, 797-812 (1976). · Zbl 0361.02066
[13] Yu. L. Ershov, The Theory, of Enumerations, [in Russian], Nauka, Moscow (1977).
[14] H. Rogers, Theory of Recursive Functions and Effective Computability [Russian translation], Mir, Moscow (1972).
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.