Geodesic
The Friedberg-Muchnik Theorem Re-Examined
Canadian journal of mathematics, Tome 24 (1972) no. 6, pp. 1070-1078

Voir la notice de l'article provenant de la source Cambridge University Press

In the well-known solution to Post's problem, Friedberg [1] and Muchnik [13] each constructed a pair of incomparable recursively enumerable (r.e.) degrees a and b. Subsequently, Sacks [15, p. 81] constructed r.e. degrees c and d such that c ∪ d = 0’ and C’ = d’ = 0'. Lachlan showed [7, p. 69] that such degrees c, d could have no greatest lower bound in the upper semilattice of r.e. degrees. We show that the original Friedberg-Muchnik degrees a, b automatically satisfy Sack's conditions and hence witness that the upper semi-lattice of r.e. degrees is not a lattice. 
Soare, Robert I. The Friedberg-Muchnik Theorem Re-Examined. Canadian journal of mathematics, Tome 24 (1972) no. 6, pp. 1070-1078. doi: 10.4153/CJM-1972-110-4
@article{10_4153_CJM_1972_110_4,
     author = {Soare, Robert I.},
     title = {The {Friedberg-Muchnik} {Theorem} {Re-Examined}},
     journal = {Canadian journal of mathematics},
     pages = {1070--1078},
     year = {1972},
     volume = {24},
     number = {6},
     doi = {10.4153/CJM-1972-110-4},
     url = {http://geodesic.mathdoc.fr/articles/10.4153/CJM-1972-110-4/}
}
TY  - JOUR
AU  - Soare, Robert I.
TI  - The Friedberg-Muchnik Theorem Re-Examined
JO  - Canadian journal of mathematics
PY  - 1972
SP  - 1070
EP  - 1078
VL  - 24
IS  - 6
UR  - http://geodesic.mathdoc.fr/articles/10.4153/CJM-1972-110-4/
DO  - 10.4153/CJM-1972-110-4
ID  - 10_4153_CJM_1972_110_4
ER  - 
%0 Journal Article
%A Soare, Robert I.
%T The Friedberg-Muchnik Theorem Re-Examined
%J Canadian journal of mathematics
%D 1972
%P 1070-1078
%V 24
%N 6
%U http://geodesic.mathdoc.fr/articles/10.4153/CJM-1972-110-4/
%R 10.4153/CJM-1972-110-4
%F 10_4153_CJM_1972_110_4

[1] 1. Friedberg, R. M., Two recursively enumerable sets of incomparable degrees of unsolvability, Proc. Nat. Acad. Sci. U.S.A. 43 (1957), 236–238. Google Scholar

[2] 2. Friedberg, R. M., The fine structure of degrees of unsolvability of recursively enumerable sets, Summaries of Cornell University Summer Institute for Symbolic Logic (1957), 404–406. Google Scholar

[3] 3. Jockusch, C. G. Jr. and Soare, R. I., Degrees of members of 7Ti° classes, Pacific J. Math. 40 (1972), 605–616. Google Scholar

[4] 4. Lachlan, A. H., Lower bounds for pairs of recursively enumerable degrees, Proc. London Math. Soc. 16 (1966), 537–569. Google Scholar

[5] 5. Lachlan, A. H., The priority method. I, Zeitschr. f. math. Logik und Grundlagen Math. 13 (1967), 1–10. Google Scholar

[6] 6. Lachlan, A. H., Complete recursively enumerable sets, Proc. Amer. Math. Soc. 19 (1968), 99–102. Google Scholar

[7] 7. Lachlan, A. H., The priority method for the construction of recursively enumerable sets (to appear). Google Scholar

[8] 8. Ladner, R. E., Mitotic recursively enumerable sets (to appear). Google Scholar

[9] 9. Ladner, R. E., A completely mitotic nonrecursive recursively enumerable degree (to appear). Google Scholar

[10] 10. Martin, D. A., Classes of r.e. sets and degrees of unsolvability, Zeitschr. f. math. Logik und Grundlagen Math. 12 (1966), 295–310. Google Scholar

[11] 11. Martin, D. A., Completeness, the recursion theorem, and effectively simple sets, Proc. Amer. Math. Soc. 17 (1966), 838–842. Google Scholar

[12] 12. McLaughlin, T. G., Retraceable sets and recursive permutations, Proc. Amer. Math. Soc. 17 (1966), 427–429. Google Scholar

[13] 13. Muchnik, A. A., Negative answer to the problem of reducibility of the theory of algorithms (Russian), Dokl. Akad. Nauk SSSR 108 (1956), 194–197. Google Scholar

[14] 14. Rogers, H. Jr., Theory of recursive functions and effective computability (McGraw-Hill, New York, 1967). Google Scholar

[15] 15. Sacks, G. E., Degrees of unsolvability, Ann. of Math. Studies No. 55 (Princeton University Press, Princeton, New Jersey, 1963). Google Scholar

[16] 16. Shoenfield, J. R., Degrees of unsolvability (North-Holland Publishing Company, Amsterdam, 1971). Google Scholar

[17] 17. Soare, R. I., The Friedberg-Muchnik theorem re-examined (abstracts), Notices Amer. Math. Soc. 18 (1971), 381–382, and 1086. Google Scholar

[18] 18. Yates, C. E. M., Three theorems on the degrees of recursively enumerable sets, Duke Math. J. 32 (1965), 461–468. Google Scholar

Cité par Sources :