Classes bounded by incomplete sets

✍ Scribed by Kejia Ho; Frank Stephan

• Publisher: Elsevier Science
• Year: 2002
• Tongue: English
• Weight: 184 KB
• Volume: 116
• Category: Article
• ISSN: 0168-0072
• DOI: 10.1016/s0168-0072(01)00114-2

✦ Synopsis

We study connections between strong reducibilities and properties of computably enumerable sets such as simplicity. We say that a class S of computably enumerable sets bounded i there is an m-incomplete computably enumerable set A such that every set in S is m-reducible to A. For example, we show that the class of e ectively simple sets is bounded; but the class of maximal sets is not. Furthermore, the class of computably enumerable sets Turing reducible to a computably enumerable set B is bounded i B is low2. For r = bwtt; tt; wtt and T , there is a bounded class intersecting every computably enumerable r-degree; for r = c; d and p, no such class exists.