On completely recursively enumerable classes and their key arrays (Q3237143)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3120044
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | On completely recursively enumerable classes and their key arrays |
scientific article; zbMATH DE number 3120044 |
Statements
On completely recursively enumerable classes and their key arrays (English)
0 references
1956
0 references
0.7975174784660339
0 references
0.7741124629974365
0 references
0.7660201191902161
0 references
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.
0 references