Covering the recursive sets

详细信息    查看全文

• 作者：Bjø ; rn Kjos-Hanssen^a ; ^{bjoern.kjos-hanssen@hawaii.edu} ; Frank Stephan^b ; ^{fstephan@comp.nus.edu.sg} ; Sebastiaan A. Terwijn^c ; ^{terwijn@math.ru.nl}
• 关键词：03D28 ; 03D32
• 刊名：Annals of Pure and Applied Logic
• 出版年：2017
• 出版时间：April 2017
• 年：2017
• 卷：168
• 期：4
• 页码：804-823
• 全文大小：493 K
• 卷排序：168

文摘

We give solutions to two of the questions in a paper by Brendle, Brooke-Taylor, Ng and Nies. Our examples derive from a 2014 construction by Khan and Miller as well as new direct constructions using martingales.At the same time, we introduce the concept of i.o. subuniformity and relate this concept to recursive measure theory. We prove that there are classes closed downwards under Turing reducibility that have recursive measure zero and that are not i.o. subuniform. This shows that there are examples of classes that cannot be covered with methods other than probabilistic ones. It is easily seen that every set of hyperimmune degree can cover the recursive sets. We prove that there are both examples of hyperimmune-free degree that can and that cannot compute such a cover.