Premium
Every Set has a Least Jump Enumeration
Author(s) -
Coles Richard J.,
Downey Rod G.,
Slaman Theodore A.
Publication year - 2000
Publication title -
journal of the london mathematical society
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.441
H-Index - 62
eISSN - 1469-7750
pISSN - 0024-6107
DOI - 10.1112/s0024610700001459
Subject(s) - mathematics , degree (music) , turing , enumeration , maximal set , discrete mathematics , abelian group , invariant (physics) , jump , set (abstract data type) , recursively enumerable language , combinatorics , computer science , physics , quantum mechanics , acoustics , mathematical physics , programming language
Given a computably enumerable set W , there is a Turing degree which is the least jump of any set in which W is computably enumerable, namely 0 ′. Remarkably, this is not a phenomenon of computably enumerable sets. It is shown 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 0( X ). In addition this result provides an isomorphism invariant method for assigning Turing degrees to certain torsion‐free abelian groups.