Affordable Access

Publisher Website

Avoiding uniformity in the [formula omitted] enumeration degrees

Authors
Journal
Annals of Pure and Applied Logic
0168-0072
Publisher
Elsevier
Volume
165
Issue
9
Identifiers
DOI: 10.1016/j.apal.2014.04.008
Keywords
  • Enumeration Reducibility
  • Degree
  • Ershov Hierarchy
  • Incomparable Degree
  • Arithmetical Uniformity
  • Low
  • High
  • Cappable

Abstract

Abstract Defining a class of sets to be uniformΔ20 if it is derived from a binary {0,1}-valued function f≤TK, we show that, for any C⊆De induced by such a class, there exists a high Δ20 degree c which is incomparable with every degree b∈C∖{0e,0e′}. We show how this result can be applied to quite general subclasses of the Ershov Hierarchy and we also prove, as a direct corollary, that every nonzero low degree caps with both a high and a nonzero low Δ20 degree.

There are no comments yet on this publication. Be the first to share your thoughts.