Avoiding uniformity in the δ2 0 enumeration degrees

Liliana Badillo; C.M. Harris

doi:10.1016/j.apal.2014.04.008

Avoiding uniformity in the δ2 0 enumeration degrees

Liliana Badillo, C.M. Harris

Research output: Contribution to journal › Special 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⊆D_eC⊆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 language	English
Pages (from-to)	1355-1379
Number of pages	25
Journal	Annals of Pure and Applied Logic
Volume	165
Issue number	9
Early online date	14 May 2014
DOIs	https://doi.org/10.1016/j.apal.2014.04.008
Publication status	Published - Sept 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

Access to Document

10.1016/j.apal.2014.04.008

Handle.net

Persistent link

Cite this

@article{aa3e174ecf7a4ddb953dd95368f221e1,

title = "Avoiding uniformity in the δ2 0 enumeration degrees",

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.",

keywords = "Enumeration reducibility; Degree; Ershov Hierarchy; Incomparable degree; Arithmetical uniformity; Low; High; Cappable",

author = "Liliana Badillo and C.M. Harris",

note = "Conference Proceeding: Turing Centenary Conference: How the World Computes",

year = "2014",

month = sep,

doi = "10.1016/j.apal.2014.04.008",

language = "English",

volume = "165",

pages = "1355--1379",

journal = "Annals of Pure and Applied Logic",

issn = "0168-0072",

publisher = "Elsevier B.V.",

number = "9",

}

TY - JOUR

T1 - Avoiding uniformity in the δ2 0 enumeration degrees

AU - Badillo, Liliana

AU - Harris, C.M.

N1 - Conference Proceeding: Turing Centenary Conference: How the World Computes

PY - 2014/9

Y1 - 2014/9

N2 - 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.

AB - 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.

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

U2 - 10.1016/j.apal.2014.04.008

DO - 10.1016/j.apal.2014.04.008

M3 - Special issue (Academic Journal)

SN - 0168-0072

VL - 165

SP - 1355

EP - 1379

JO - Annals of Pure and Applied Logic

JF - Annals of Pure and Applied Logic

IS - 9

ER -

Avoiding uniformity in the δ2 0 enumeration degrees

Abstract

Bibliographical note

Keywords

Access to Document

Handle.net

Fingerprint

Cite this