Turing degree - Definition and Overview

In computability theory, the Turing degree of a subset <math>X<math> of the natural numbers, <math>\omega<math>, is the equivalence class of all subsets of <math>\omega<math> equivalent to <math>X<math> under Turing reducibility. Turing reducibility induces a partial order on the Turing degrees. The degree of a set <math>X<math> is denoted <math>\textbf{deg}(X)<math>. The minimal element in the partial order is <math>\textbf{deg}(\emptyset)<math> and contains all recursive sets (computable sets).

A recursively enumerable Turing degree (computably enumerable Turing degree) is one containing a recursively enumerable set (computably enumerable set). The recursively enumerable Turing degrees under the partial order induced by Turing reducibility form an upper semi-lattice and are an object that has been much studied by the logic community.