Every Set has a Least Jump Enumeration

Autor:	Theodore A. Slaman, Richard J. Coles, Rodney G. Downey
Rok vydání:	2000
Předmět:	Set (abstract data type) Combinatorics Discrete mathematics symbols.namesake Mathematics::Combinatorics Turing degree Degree (graph theory) General Mathematics Enumeration Jump symbols Mathematics
Zdroj:	Journal of the London Mathematical Society. 62:641-649
ISSN:	0024-6107
DOI:	10.1112/s0024610700001459
Popis:	Given a computably enumerable set B, there is a Turing degree which is the least jump of any set in which B is computably enumerable, namely 0 ′. Remarkably, this is not a phenomenon of computably enumerable sets. We show that for every subset A of N, there is a Turing degree, c′ μ(A), which is the least degree of the jumps of all sets X for which A is Σ1(X).
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::fed630c1930e9dfabd57f851ae70e977 https://doi.org/10.1112/s0024610700001459 Zobrazit plný text záznamu Plný text