Effective choice of constructivizations and recursive consistency of problems on constructive models (Q2366356): Difference between revisions

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.