×

Some properties of algebraic reducibility of constructivizations. (English. Russian original) Zbl 0734.03020

Algebra Logic 29, No. 5, 395-405 (1990); translation from Algebra Logika 29, No. 5, 597-612 (1990).
In the paper under review the author studies the notion of algebraic reducibility of constructivizations. The author introduces for any \(n\in \omega\), \(n>0\), the notion of n-algebraic reducibility of constructivizations (which is the usual algebraic reducibility of constructivizations reduced to relations with n free variables) and studies the relationship between these reducibilities. Further, it is shown that any finite Boolean algebra is the structure of algebraic reducibility for some suitable partially ordered set. Moreover, in some natural sense the class of partially ordered sets is complete.
Reviewer: M.M.Arslanov

MSC:

03C57 Computable structure theory, computable model theory
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] V. A. Uspenskii and A. L. Semenov, ”The theory of algorithms: its basic developments and applications,” in: Algorithms in Contemporary Mathematics and Its Applications [in Russian], Part 1, Novosibirsk (1982).
[2] Yu. L. Ershov, Decidability Problems and Constructive Models [in Russian], Nauka, Moscow (1980).
[3] S. T. Fedoryaev, ”Constructivizable models with a linear algebraic reducibility structure,” Mat. Zametki,48, No. 6, 106–111 (1990). · Zbl 0722.03035
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.