Effective choice of constructivizations and recursive consistency of problems on constructive models.

*(English. Russian original)*Zbl 0790.03038
Algebra Logic 31, No. 1, 1-12 (1992); translation from Algebra Logika 31, No. 1, 3-20 (1992).

The author considers a constructive (recursive) model \(\mathfrak M\) of some language \(L\) is a domain over which problems are defined. A problem on \(\mathfrak M\) is a relation on \(\mathfrak M\) that is invariant under automorphisms of \(\mathfrak M\). Suppose that \(\pi=\{\nu_ 0,\nu_ 1,\dots\}\) is a class of constructivizations of \({\mathfrak M}\), \(\Sigma=\{R_ 0,R_ 1,\dots\}\) is a computable family of problems, and for each \(R\in\Sigma\) there exists \(\nu\in\pi\) such that \(\nu^{-1}(R)\) is recursive. We say that the problem of the effective choice has a solution if there is a recursive function \(g\) for which \(\nu^{- 1}_{g(i)}(R_ i)\) is recursive for all \(i\in N\), \(R_ i\in\Sigma\), \(\nu_{g(i)}\in\pi\). A criterion for the problem of the effective choice to have a solution is given.

Reviewer: A.Ryaskin (Novosibirsk)

##### MSC:

03C57 | Computable structure theory, computable model theory |

03D45 | Theory of numerations, effectively presented structures |

##### References:

[1] | Yu. L. Ershov, Decidability Problems and Constructive Models [in Russian], Nauka, Moscow (1980). |

[2] | D. Scott, ”Logic with denumerable long formulas and finite strings of quantifiers”, in: The Theory of Models, North Holland, Amsterdam (1965). · Zbl 0166.26003 |

[3] | S. S. Goncharov and V. D. Dzgoev, ”Autostability of models,” Algebra Logika,19, No. 2, 45–58 (1980). · Zbl 0468.03023 |

[4] | C. J. Ash, ”Recursive labelling systems and stability of recursive structures in hyperarithmetical degrees”, Trans. Am. Math. Soc.,298, No. 2, 497–514 (1986). · Zbl 0631.03017 |

[5] | H. Rogers, Theory of Recursive Functions and Effective Computability, McGraw-Hill, New York (1967). · Zbl 0183.01401 |

[6] | V. A. Uspenskii and A. L. Semenov, Theory of Algorithms: Advances and Applications [in Russian], Moscow (1987). |

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.