Limits to joining with generics and randoms
| Autor: | Day, Adam R., Dzhafarov, Damir D. |
|---|---|
| Rok vydání: | 2012 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | Posner and Robinson (1981) proved that if $S \subseteq \omega$ is non-computable, then there exists a $G \subseteq \omega$ such that $S \oplus G \geq_T G'$. Shore and Slaman (1999) extended this result to all $n \in \omega$, by showing that if $S \nleq_T \emptyset^{(n-1)}$ then there exists a $G$ such that $S \oplus G \geq_T G^{(n)}$. Their argument employs Kumabe-Slaman forcing, and so the set they obtain, unlike that of the Posner-Robinson theorem, is not generic for Cohen forcing in any way. We answer the question of whether this is a necessary complication by showing that for all $n \geq 1$, the set $G$ of the Shore-Slaman theorem cannot be chosen to be even weakly 2-generic. Our result applies to several other effective forcing notions commonly used in computability theory, and we also prove that the set $G$ cannot be chosen to be 2-random. Comment: Submitted to "Proceedings of the 2011 Asian Logic Conference" |
| Databáze: | arXiv |
| Externí odkaz: |
|