\(\Sigma\)-predicates of finite types over an admissible set (Q1820777)

The theory of admissible sets is a successful synthesis of set theory, model theory (of infinite languages), and recursion theory. For any admissible set \({\mathbb{A}}=<A,\in,...>\) we define the concept of a \(\Sigma\)- set (a \(\Sigma\)-predicate) as a set (a predicate) defined by a \(\Sigma\)- formula \(\phi(x)\) \([\phi(\bar x)]\) (with parameters in A). This concept is a natural extension of the concept of a recursively enumerable set (predicate) to any admissible set; for a set \(B\subseteq A\) to belong to a set A \((B\in A)\) is an analog of a finite set; an analog of a recursive set is the concept of a \(\Delta\)-set (i.e., a \(\Sigma\)-set whose complement is also a \(\Sigma\)-set); \(\Sigma\)-recursive (partial) functions are defined as functions whose graph is a \(\Sigma\)-predicate. There exists a binary \(\Sigma\)-predicate, which is universal for the family of one-place \(\Sigma\)-predicates; moreover, among the universal predicates there exist some which induce a principal computable enumeration of one-place \(\Sigma\)-predicates (\(\Sigma\)-sets). It follows from this fact, in particular, that there exists a \(\Sigma\)-set which is not a \(\Delta\)-set. Unfortunately, in the general case (i.e., for arbitrary admissible sets) there does not exist a two-place \(\Sigma\)- function which is universal for the class of all one-place \(\Sigma\)- functions. Therefore, the concept of a \(\Sigma\)-predicate lies at the basis of the general recursion theory over admissible sets. The fundamental aim of this article is to construct a theory of \(\Sigma\)- predicates of higher types over any admissible set. The basis of the definition of such predicates is an idea which was successfully used earlier to construct a theory of partial computable functionals of finite types for classical recursion theory (over \(\omega)\). The essence of this idea is to define new objects, together with a ''correct'' enumeration of them: this enumeration enables us to make the following step ''upward''.