×

zbMATH — the first resource for mathematics

Effectively infinite classes of weak constructivizations of models. (English. Russian original) Zbl 0824.03013
Algebra Logic 32, No. 6, 342-360 (1993); translation from Algebra Logika 32, No. 6, 631-664 (1993).
Weak constructivizations of strongly constructive models are studied. An enumerated model \((M, \nu)\), where \(\nu\) is an enumeration of \(M\), is called strongly constructive (constructive) if there exists an algorithm to recognize all (quantifier-free) formulas \(\varphi(\overline x)\) and tuples \(\overline m\) of natural numbers for which \(M\models \varphi(\nu\overline m)\) holds. A model \(M\) is called \(n\)-complete if, for each formula \(\varphi(x_ 1, \dots, x_ m)\) which has at most \(n\) alternations of quantifiers and for each tuple \(a_ 1,\dots, a_ m\in M\), there exists an \(\exists\)-formula \(\psi(x_ 1,\dots, x_ m)\) such that \(M\models \psi(x_ 1,\dots, x_ m)\) and \(M\models \forall\overline x(\varphi\to \psi)\). A model \(M\) is called limit-\(\omega\)-complete if, for any \(n\), it possesses a finite \(n\)-complete enrichment by constants, but it has no finite complete enrichments by constants. Theorem 1. If a model \(M\) is limit-\(\omega\)-complete and possesses a strong constructivization, then, given any computable class \(S\) of constructivizations of \(M\) we can effectively build a non-strong constructivization that is not equivalent to any constructivization from \(S\). Theorem 2. If \(M\) is strongly and weakly constructivizable, then, for a given computable class of its constructivizations, we can effectively build a weak constructivization of \(M\) that is not autoequivalent to any constructivization in this class. It follows that the class of weak constructivizations of a strongly constructivizable model is either empty or effectively infinite, and in this case, it is not computable.

MSC:
03C57 Computable structure theory, computable model theory
03D45 Theory of numerations, effectively presented structures
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] C. J. Ash and A. Nerode, ”Intrinsically recursive relations. Aspects of effective algebra,” in:Proc. Conf. Monash Univ., Australia (1981), pp. 24–41. · Zbl 0467.03041
[2] C. J. Ash and J. F. Knight, ”Pairs of recursive structure,”Logic Paper,64, 1–45 (1988).
[3] C. J. Ash and S. S. Goncharov, ”Strong {\(\Delta\)} 2 0 -categoricity,”Algebra Logika,24, No. 6, 718–727 (1985).
[4] S. S. Goncharov, ”The problem of the number of nonequivalent constructivizations,”Algebra Logika,19, No. 6, 621–639 (1980).
[5] S. S. Goncharov, ”The number of nonequivalent constructivizations,”Algebra Logika,16, No. 3, 257–289 (1977).
[6] S. S. Goncharov, ”autostability and computable families of constructivizations,”Algebra Logika,14, No. 6, 647–680 (1975).
[7] S. S. Goncharov, ”Autostability of models and Abelian groups,”Algebra Logika,19, No. 1, 23–44 (1980). · Zbl 0468.03022
[8] S. S. Goncharov and V. D. Dzgoev, ”Autostability of models,”Algebra Logika,19, No. 1, 45–58. (1980). · Zbl 0468.03023
[9] S. S. Goncharov, ”Computable classes of constructivizations for models of finite type,”Sib. Mat. Zh.,34, No. 5, 23–37 (1993). · Zbl 0860.03032
[10] V. P. Dobritsa, ”Computability of some classes of algebras,”Sib. Mat. Zh.,18, No. 3, 570–579 (1977). · Zbl 0361.02065
[11] V. P. Dobritsa, ”Structural properties of computable classes of constructive models,”Algebra Logika,26, No. 1, 36–62 (1987). · Zbl 0636.03030
[12] A. T. Nurtazin, ”Strong and weak constructivizations and computable families,”Algebra Logika,13, No. 3, 311–323 (1974).
[13] S. S. Goncharov, ”Bounded theories of constructive Boolean algebras,”Sib. Mat. Zh.,17, No. 4, 797–812 (1976). · Zbl 0361.02066
[14] S. S. Goncharov, ”Some properties of constructivizations for Boolean algebras,”Sib. Mat. Zh.,16, No. 2, 264–278 (1975).
[15] Yu. L. Ershov,Decidability Problems and Constructive Models [in Russian], Nauka, Moscow (1980).
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.