Hostname: page-component-7b7567c8c-z4zkx Total loading time: 0 Render date: 2026-11-17T08:36:58.113Z Has data issue: false hasContentIssue false

A HIERARCHY OF COMPUTABLY ENUMERABLE DEGREES

Published online by Cambridge University Press:  26 April 2018

ROD DOWNEY
Affiliation:
SCHOOL OF MATHEMATICS AND STATISTICS VICTORIA UNIVERSITY P.O. BOX 600 WELLINGTON, NEW ZEALAND E-mail: Rod.Downey@vuw.ac.nz
NOAM GREENBERG
Affiliation:
SCHOOL OF MATHEMATICS AND STATISTICS VICTORIA UNIVERSITY P.O. BOX 600 WELLINGTON, NEW ZEALAND E-mail: greenberg@msor.vuw.ac.nz
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We introduce a new hierarchy of computably enumerable degrees. This hierarchy is based on computable ordinal notations measuring complexity of approximation of ${\rm{\Delta }}_2^0$ functions. The hierarchy unifies and classifies the combinatorics of a number of diverse constructions in computability theory. It does so along the lines of the high degrees (Martin) and the array noncomputable degrees (Downey, Jockusch, and Stob). The hierarchy also gives a number of natural definability results in the c.e. degrees, including a definable antichain.

Information

Type
Articles
Copyright
Copyright © The Association for Symbolic Logic 2018