High Minimal Pairs in the Enumeration Degrees

摘要

The natural embedding of the Turing degrees into the enumeration degrees preserves the jump operation, and maps isomorphically the computably enumerable Turing degrees onto the ∏_1~0 enumeration degrees. The embedding does not preserve minimal pairs, though, unless one of the two sides is low. In particular it is known that there exist high minimal pairs of c.e. Turing degrees that do not embed to minimal pairs of e-degrees. We show however that high minimal pairs of ∏_1~0 e-degrees do exist.