×

zbMATH — the first resource for mathematics

Some theorems on classes of recursively enumerable sets. (English) Zbl 0083.00302
Verff. beweisen eine Reihe von Sätzen über (rekursiv-) aufzählbare (a.), vollständig-aufzählbare (v. a.) und entscheidbare (e.) (- vollständig-rekursive) Klassen von a. Mengen im Sinne von Rice (vgl. auch wegen der Bezeichnungen H. G. Rice [Trans. Am. Math. Soc. 74, 358–366 (1953; Zbl 0053.00301)]. Sie geben u. a. mehrere Beweise des Satzes von Rice (loc. cit.), daß es keine nichttriviale e. Klasse gibt, (darunter einen sehr einfachen), sowie verschiedene Verschärfungen dieses Satzes, u. a.: Für jede nichttriviale Klasse \(A\) ist der Unlösbarkeitsgrad im Sinne von Kleene-Post [S. C. Kleene and E. L. Post, Ann. Math. (2) 59, 379–407 (1954; Zbl 0057.24703)] von \(\theta A\geq 0'\). Weiter bestimmen sie u. a. für die Klasse \(Q\) aller endlichen Mengen den Unlösbarkeitsgrad von \(\theta Q\) zu \(0''\). Ferner wird die Ricesche key-array-conjecture über v. a. Klassen bewiesen.
Weitere Beweise und Verschärfungen des genannten Satzes von Rice ergeben sich durch Betrachtung von Klassen \(A, B\), für welche \(\theta A\) und \(\theta B\) nicht durch a. Mengen getrennt werden können, sowie durch eine Topologisierung der Klasse \(F\).
Ferner werden die Begriffe der Produktivität (vgl. J. C. E. Dekker, Trans. Am. Math. Soc. 78, 129–149 (1955; Zbl 0064.01001)]), Kreativität usw. in naheliegender Weise von Mengen auf Klassen übertragen und eine Reihe von Existenzfragen über solche Klassen beantwortet. Hierbei werden u. a. noch folgende interessanten Sätze bewiesen: Der Durchschnitt zweier a. Klassen ist nicht notwendig a. Es gibt abzählbar viele v. a. Klassen \(A\) mit a. Komplement \(F - A\).
Die Arbeit enthält auch einige Sätze über Mengen, z. B.: Jede produktive Menge besitzt eine rekursive produktive Funktion (vgl. hierzu Dekker, loc. cit.). Es gibt genau abzählbar viele a., nicht rekursive Mengen, die weder einfach noch semikreativ sind (vgl. Dekker (loc. cit.) und [Proc. Am. Math. Soc. 4, 495–501 (1953; Zbl 0052.25001)]).
Reviewer: E. Burger

MSC:
03-XX Mathematical logic and foundations
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Martin Davis, Computability and unsolvability, McGraw-Hill Series in Information Processing and Computers, McGraw-Hill Book Co., Inc., New York-Toronto-London, 1958. · Zbl 0080.00902
[2] J. C. E. Dekker, The constructivity of maximal dual ideals in certain Boolean algebras, Pacific J. Math. 3 (1953), 73 – 101. · Zbl 0050.00802
[3] J. C. E. Dekker, Two notes on recursively enumerable sets, Proc. Amer. Math. Soc. 4 (1953), 495 – 501. · Zbl 0052.25001
[4] J. C. E. Dekker, Productive sets, Trans. Amer. Math. Soc. 78 (1955), 129 – 149. · Zbl 0064.01001
[5] J. C. E. Dekker and J. Myhill, Recursion theory, to be published by the North Holland Pub. Co., Amsterdam. · Zbl 0094.00803
[6] R. M. Friedberg, The solution of Post’s problem by the construction of two recursively enumerable sets of incomparable degree of unsolvability, Bull. Amer. Math. Soc. Abstract 62-3-362.
[7] Stephen Cole Kleene, Introduction to metamathematics, D. Van Nostrand Co., Inc., New York, N. Y., 1952. · Zbl 0047.00703
[8] S. C. Kleene and Emil L. Post, The upper semi-lattice of degrees of recursive unsolvability, Ann. of Math. (2) 59 (1954), 379 – 407. · Zbl 0057.24703 · doi:10.2307/1969708 · doi.org
[9] R. McNaughton, On the effective distinguishability of classes of theories, abstract, J. Symbolic Logic vol. 19 (1954) p. 157.
[10] Andrzej Mostowski, On definable sets of positive integers, Fund. Math. 34 (1947), 81 – 112. · Zbl 0031.19401
[11] Andrzej Mostowski, On a set of integers not definable by means of one-quantifier predicates, Ann. Soc. Polon. Math. 21 (1948), 114 – 119. · Zbl 0031.33904
[12] A. A. Muchnik, Negative answer to the problem of reducibility of the theory of algorithms, C. R. (Doklady) Acad. Sci. URSS vol. 108 (1956) pp. 194-197. · Zbl 0070.24701
[13] John Myhill, Creative sets, Z. Math. Logik Grundlagen Math. 1 (1955), 97 – 108. · Zbl 0065.00105
[14] J. Myhill and J. C. Shepherdson, Effective operations on partial recursive functions, Z. Math. Logik Grundlagen Math. 1 (1955), 310 – 317. · Zbl 0068.24706
[15] Emil L. Post, Recursively enumerable sets of positive integers and their decision problems, Bull. Amer. Math. Soc. 50 (1944), 284 – 316. · Zbl 0063.06328
[16] H. G. Rice, Classes of recursively enumerable sets and their decision problems, Trans. Amer. Math. Soc. 74 (1953), 358 – 366. · Zbl 0053.00301
[17] H. G. Rice, On completely recursively enumerable classes and their key arrays, J. Symb. Logic 21 (1956), 304 – 308. · Zbl 0072.00504
[18] Norman Shapiro, Degrees of computability, Trans. Amer. Math. Soc. 82 (1956), 281 – 299. · Zbl 0070.24602
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.