Principal numerations of functionals on admissible sets
The main goal of this paper is to find necessary conditions for an admissible set to possess principal numerations of the computable functionals of finite types over it. It is well-known that there exist principal numerations of the \(\Sigma\)-predicates of finite types over any admissible set [\textit{Yu. L. Ershov}, Algebra Logika, 24, No.5, 499-536 (1985; Zbl 0615.03036)]. The same question concerning functionals appeared to be more complicated. The notion of a resolvent admissible set, which was introduced by Yu. L. Ershov [loc. cit.] plays an important role in the proofs. The author proves in particular that if \({\mathbb{A}}\) is a resolvent admissible set then there exist principal numerations of the computable functionals of finite types over \({\mathbb{A}}\). If \({\mathfrak M}\) is an atomic model of a decidable theory with recursive set of atomic formulae, and for some \(m_ 1,...,m_ k\in {\mathfrak M}\) every atomic formula is equivalent to a \(\exists\)-formula with parameters \(m_ 1,...,m_ k\), then there exist principal numerations of the computable functionals of finite types over HF(\({\mathfrak M})\). For an arbitrary model \({\mathfrak M}\) there exist principal numerations of the computable functionals of finite types over HYP(\({\mathfrak M})\).
- \(\Sigma\)-predicates of finite types over an admissible set
- scientific article; zbMATH DE number 1534577
- scientific article; zbMATH DE number 1531363
- scientific article; zbMATH DE number 1534487
- scientific article; zbMATH DE number 1302870
- A computable structure with non-standard computability
- Computability in special models
- On the collection of all computable subsets on admissible sets
- Using resolution for deciding solvable classes and building finite models
- Computability-Theoretic Complexity of Countable Structures
- Computable functionals and arithmetic of ordinal types
- On the collection of all computable subsets on admissible sets
- Characterization of the effective computability in \({\mathfrak f}\)-enumerations
- Admissible functionals in abstract structures with arbitrary power
- Admissible functionals and infinite-valent functions
- scientific article; zbMATH DE number 1534570 (Why is no real title available?)
- Acceptable Numerations of Function Spaces
This page was built for publication: Principal numerations of functionals on admissible sets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q810015)
