On completely recursively enumerable classes and their key arrays
The author has already [Trans. Am. Math. Soc. 74, 358--366 (1953; Zbl 0053.00301)] introduced the notion of a completely recursively enumerable (c. r. e.) class of sets of positive integers viz: \(A\) is c. r. e. when the set \(\theta_A\) of all \(n\)'s such that the range of \(\Phi(n,x)\) is a member of \(A\), is r. e. (Here \(\Phi(n,x)\) recursively enumerates the partial recursive functions of \(x\).) He now defines the canonical index of the finite set \(\{a_1, a_2, \ldots, a_n\}\) (where \(a_1 < a_2 <\cdots < a_n)\) as the integer \(2^{a_1}+ 2^{a_2} + \cdots + 2^{a_n}\). Given a finite set and its cardinal number the canonical index can be effectively determined, and vice versa. He calls a class \(K\) of finite sets canonically r. e. when the set of canonical indices of the sets of \(K\) is r. e., and similarly for canonically recursive. McNaughton and others [see e. g. \textit{J. Myhill} and the reviewer, Z. Math. Logik Grundlagen Math. 1, 310--317 (1955; Zbl 0068.24706)] have shown that every c. r. e. class consists of all r. e. supersets of the sets in a ``key array or canonically r. e. class of finite sets. The author's first theorem is that the complement (with respect to the class of all r. e. sets) of a c. r. e. class \(A\) is r. e. (i. e. there exists a r. e. set containing for each member \(\alpha\) of \(A\) at least one integer \(n\) such that the range of \(\Phi(n, x)\) is \(\alpha\), and no other numbers) if and only if \(A\) has a canonically recursive key array. He then defines the core of a class \(A\) as the class of those elements of \(A\) which have no proper subsets in \(A\) and gives an example of a canonically r. e. class of finite sets whose core is not even r. e. Hence the core of a c. r. e. class cannot always be used as a key array. He uses this example to construct a simple deductive system (with a non-effective rule of inference) such that although it is possible to give effectively a set of axioms from which the theorems can be effectively generated yet it is impossible to give effectively an independent set of axioms.
- Certain properties of Post enumeration retracts
- Complexity classes of partial recursive functions
- A second step towards complexity-theoretic analogs of Rice's Theorem
- On learning of functions refutably.
- Some Theorems on Classes of Recursively Enumerable Sets
- Recursive equivalence types and combinatorial functions
- Recursively enumerable sets and degrees
- Generalization versus classification
- Vladimir Andreevich Uspensky (27/11/1930–27/6/2018)
- Array nonrecursiveness and relative recursive enumerability
- A simple example of blocking the Craig trick
- Lower bounds and the hardness of counting properties
This page was built for publication: On completely recursively enumerable classes and their key arrays
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3237143)