On pairs of recursively enumerable degrees

Abstract

Lachlan and Yates proved that some, but not all, pairs of incomparable recursively enumerable (r.e.) degrees have an infimum. We answer some questions which arose from this situation. We show that not every nonzero incomplete r.e. degree is half of a pair of incomparable r.e. degrees which have an infimum, whereas every such degree is half of a pair without infimum. Further, we prove that every nonzero r.e. degree can be split into a pair of r.e. degrees which have no infimum, and every interval of r.e. degrees contains such a pair of degrees.