首页 | 本学科首页   官方微博 | 高级检索  
     


On Genericity and Ershov's Hierarchy
Authors:Amy Gale  Rod Downey
Abstract:It is natural to wish to study miniaturisations of Cohen forcing suitable to sets of low arithmetic complexity. We consider extensions of the work of Schaeffer [9] and Jockusch and Posner [6] by looking at genericity notions within the Δ2 sets. Different equivalent characterisations of 1‐genericity suggest different ways in which the definition might be generalised. There are two natural ways of casting the notion of 1‐genericity: in terms of sets of strings and in terms of density functions, as we will see here. While these definitions coincide at the first level of the difference hierarchy, they turn out to differ at other levels. Furthermore, these differences remain when the remainder of the Δ02 sets are considered. While the string characterization of 1‐genericity collapses at the second level of the difference hierarchy to 2‐genericity, the density function definition gives a very interesting hierarchy at level w and above. Both of these results point towards the deep similarities exhibited by the n‐c.e. degrees for n ≥ 2.
Keywords:1‐Generic sets  Ershov Hierarchy  Computably enumerable set
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号