The Friedberg-Muchnik Theorem Re-Examined
- 1 December 1972
- journal article
- Published by Canadian Mathematical Society in Canadian Journal of Mathematics
- Vol. 24 (6) , 1070-1078
- https://doi.org/10.4153/cjm-1972-110-4
Abstract
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.Keywords
This publication has 0 references indexed in Scilit: