ABSTRACT
A natural question is whether it is necessary to go up to the degree of B < in order to find the random set A. Martin-Lof random sets can be found below every set which is PA-complete, so there are Martin-Lof random sets in low and in hyperimmune-free Turing degrees. A set A is called PA-complete if one can compute relative to A a complete and consistent extension of the set of first-order formulas provable in Peano Arithmetic. An easier and equivalent definition of being PA-complete is to say that given any partial-recursive and
, one can compute relative to A a total extension is {0, l}-valued.
