A universal recursive function on admissible sets (Q1095896)

For a structure \({\mathfrak M}\) of a finite language L let \(HF_{{\mathfrak M}}\) be the set of all hereditary finite sets with urelements in \({\mathfrak M}\). The set \(HF_{{\mathfrak M}}\) can be considered as a structure of the language \(L\cup \{U,\in \}\) where U is a predicate for the set of urelements. This structure is an admissible set over \({\mathfrak M}\), that is a model of the Kripke-Platek axiom system. The author calls a \(\Sigma\)- function F(x,y) on \(HF_{{\mathfrak M}}^ a \)universal recursive function on \(HF_{{\mathfrak M}}\) if for every \(\Sigma\)-function f(x) on \(HF_{{\mathfrak M}}\) there is \(a\in HF_{{\mathfrak M}}\) such that f(x) is F(x,a). Main results: (i) if the theory of \({\mathfrak M}\) is decidable, model complete, \(\omega\)-categorical and the set of complete formulas of this theory is recursive, then there exists a universal recursive function on \(HF_{{\mathfrak M}}\); (ii) there exists \({\mathfrak M}\) for which there is no universal recursive function on \(HF_{{\mathfrak M}}\).