Logic Colloquium 2008
Antonin Kucera Properties of PA sets and random sets
We discuss methods of coding information into PA-sets and ML-random sets (e.g. how to make a given set T-reducible to some PA-set or ML-random set). Slaman and Kucera used these techniques for PA-sets to provide a characterization of ideals in the T-degrees for which there is a low T-upper bound. As a corollary, there is a PA-set which is a low T-upper bound for the class of K-trivial sets. In the case of ML-random sets, the situation is naturally more complicated and the techniques are less powerful. We survey some results in this area including new developments, e.g. a result of Barmpalias and Montalban that any K-trivial set is T-reducible to an incomplete (even low) ML-random set.
back