×

\(\Sigma\)-predicates of finite types over an admissible set. (English. Russian original) Zbl 0615.03036

Algebra Logic 24, 327-351 (1985); translation from Algebra Logika 24, No. 5, 499-536 (1985).
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”.

MSC:

03D60 Computability and recursion theory on ordinals, admissible sets, etc.
03D65 Higher-type and set recursion theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Yu. L. Ershov, The Theory of Enumerations [in Russian], Nauka, Moscow (1977).
[2] Yu. L. Ershov, ”The principle of {\(\Sigma\)}-enumeration,” Dokl. Akad. Nauk SSSR,270, No. 4, 786–788 (1983).
[3] Yu. L. Ershov, ”Dynamic logic over admissible sets,” Dokl. Akad. Nauk SSSR,273, No. 5, 1045–1048 (1983). · Zbl 0576.68009
[4] M. Makkai, ”Admissible sets and infinite logic,” in: Textbook on Mathematical Logic [in Russian], Vol. 1, Nauka, Moscow (1982), pp. 235–288.
[5] J. Barwise, Admissible Sets and Structures, Springer-Verlag, Berlin (1975). · Zbl 0316.02047
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.