Avoiding uniformity in the δ2 0 enumeration degrees

Liliana Badillo, C.M. Harris

Research output: Contribution to journalSpecial issue (Academic Journal)peer-review

2 Citations (Scopus)

Abstract

Defining a class of sets to be uniform  Δ20 if it is derived from a binary {0,1}{0,1}-valued function f≤TKf≤TK, we show that, for any C⊆DeC⊆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.
Original languageEnglish
Pages (from-to)1355-1379
Number of pages25
JournalAnnals of Pure and Applied Logic
Volume165
Issue number9
Early online date14 May 2014
DOIs
Publication statusPublished - Sep 2014

Bibliographical note

Conference Proceeding: Turing Centenary Conference: How the World Computes

Keywords

  • Enumeration reducibility; Degree; Ershov Hierarchy; Incomparable degree; Arithmetical uniformity; Low; High; Cappable

Fingerprint Dive into the research topics of 'Avoiding uniformity in the δ2 0 enumeration degrees'. Together they form a unique fingerprint.

Cite this