Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4662333 | Annals of Pure and Applied Logic | 2012 | 7 Pages |
Abstract
We say that A≤LRB if every B-random real is A-random—in other words, if B has at least as much derandomization power as A. The LR reducibility is a natural weak reducibility in the context of randomness, and generalizes lowness for randomness. We study the existence and properties of upper bounds in the context of the LR degrees. In particular, we show that given two (or even finitely many) low sets, there is a low c.e. set which lies LR above both. This is very different from the situation in the Turing degrees, where Sacks’ splitting theorem shows that two low sets can join to 0′.
Related Topics
Physical Sciences and Engineering
Mathematics
Logic