Recursively enumerable sets of positive integers and their decision problems.

*(English)*Zbl 0063.06328From the introduction: Recent developments of symbolic logic have considerable importance for mathematics both with respect to its philosophy and practice. That mathematicians generally are oblivious to the importance of this work of Gödel, Church, Turing, Kleene, Rosser and others as it affects the subject of their own interest is in part due to the forbidding, diverse and alien formalisms in which this work is embodied. Yet, without such formalism, this pioneering work would lose most of its cogency. But apart from the question of importance,
these formalisms bring to mathematics a new and precise mathematical concept, that of the general recursive function of Herbrand-Gödel-Kleene, or its proved equivalents in the developments of Church and Turing.

It is the purpose of this lecture to demonstrate by example that this concept admits of development into a mathematical theory much as the group concept has been developed into a theory of groups.

Contents: 1. Recursive versus recursively enumerable sets. 2. A form of Gödel’s theorem. 3. The complete set \(K\); creative sets. 4. One-one reducibility, to \(K\); many-one reducibility. 5. Simple sets. 6. Reducibility by truth-tables. 7. Non-reducibility of creative sets to simple sets by bounded truth-tables. 8. Counter-example for unbounded truth-tables. 9. Hyper-simple sets. 10. Non-reducibility of creative sets to hyper-simple sets by truth-tables unrestricted.

It is the purpose of this lecture to demonstrate by example that this concept admits of development into a mathematical theory much as the group concept has been developed into a theory of groups.

Contents: 1. Recursive versus recursively enumerable sets. 2. A form of Gödel’s theorem. 3. The complete set \(K\); creative sets. 4. One-one reducibility, to \(K\); many-one reducibility. 5. Simple sets. 6. Reducibility by truth-tables. 7. Non-reducibility of creative sets to simple sets by bounded truth-tables. 8. Counter-example for unbounded truth-tables. 9. Hyper-simple sets. 10. Non-reducibility of creative sets to hyper-simple sets by truth-tables unrestricted.

##### MSC:

03D25 | Recursively (computably) enumerable sets and degrees |

03D50 | Recursive equivalence types of sets and structures, isols |