Low upper bounds in the LR degrees |
| |
Authors: | David Diamondstone |
| |
Institution: | Department of Mathematics, Statistics, and Operations Research, Victoria University of Wellington, P.O. Box 600, Wellington, 6140, New Zealand |
| |
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′. |
| |
Keywords: | 03D25 03D30 03D32 68Q30 |
本文献已被 ScienceDirect 等数据库收录! |
|