کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4662333 1633489 2012 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Low upper bounds in the LR degrees
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات منطق ریاضی
پیش نمایش صفحه اول مقاله
Low upper bounds in the LR degrees
چکیده انگلیسی

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′.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Annals of Pure and Applied Logic - Volume 163, Issue 3, March 2012, Pages 314-320