Hostname: page-component-586b7cd67f-dlnhk Total loading time: 0 Render date: 2024-11-28T07:42:07.947Z Has data issue: false hasContentIssue false
  • English
  • Français

EVERY SET HAS A LEAST JUMP ENUMERATION

Published online by Cambridge University Press:  13 February 2001

RICHARD J. COLES ,
ROD G. DOWNEY  and
THEODORE A. SLAMAN
RICHARD J. COLES
Affiliation:
Department of Computer Science, University of Auckland, Private Bag 92019, Auckland, New Zealand; [email protected]
ROD G. DOWNEY
Affiliation:
School of Mathematical and Computing Sciences, Victoria University of Wellington, PO Box 600, Wellington, New Zealand; [email protected]
THEODORE A. SLAMAN
Affiliation:
Department of Mathematics, University of California, Berkeley, CA 94720-3840, USA; [email protected]
Get access

Abstract

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 ℕ, there is a Turing degree, c′μ(A), which is the least degree of the jumps of all sets X for which A is [sum ]01(X). In addition this result provides an isomorphism invariant method for assigning Turing degrees to certain torsion-free abelian groups.

Type
Research Article
Information
Journal of the London Mathematical Society , Volume 62 , Issue 3 , December 2000 , pp. 641 - 649
Copyright
The London Mathematical Society 2000

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)