| Article ID | Journal | Published Year | Pages | File Type | 
|---|---|---|---|---|
| 4661748 | Annals of Pure and Applied Logic | 2014 | 11 Pages | 
Abstract
												We study the complexity of generic reals for computable Mathias forcing in the context of computability theory. The n-generics and weak n-generics form a strict hierarchy under Turing reducibility, as in the case of Cohen forcing. We analyze the complexity of the Mathias forcing relation, and show that if G is any n-generic with nâ¥2 then it satisfies the jump property G(nâ1)â¡TGâ²ââ
(n). We prove that every such G has generalized high Turing degree, and so cannot have even Cohen 1-generic degree. On the other hand, we show that every Mathias n-generic real computes a Cohen n-generic real.
											Related Topics
												
													Physical Sciences and Engineering
													Mathematics
													Logic
												
											Authors
												Peter A. Cholak, Damir D. Dzhafarov, Jeffry L. Hirst, Theodore A. Slaman, 
											