Mathematical logic and foundations Definition

Turing degree

Builds on Turing reduction Computable set

Definition

Let $\le_T$ be Turing reducibility on subsets of $\N$ , and let $A \equiv_T B$ mean $A \le_T B$ and $B \le_T A$ . The relation $\equiv_T$ is an equivalence relation on the power set of $\N$ . The Turing degree of a set $A \subseteq \N$ is its equivalence class $\deg(A) = \set{B \subseteq \N : B \equiv_T A}.$ The degrees are partially ordered by $\deg(A) \le \deg(B)$ if and only if $A \le_T B$ ; this does not depend on the choice of representatives.

Remarks

Example: the set $E$ of even numbers and the set $\set{0}$ have the same degree. Both are computable sets, and every computable set is computable from every set, so $E \le_T \set{0}$ and $\set{0} \le_T E$ . This common degree is written $\mathbf{0}$ ; it is the least degree.

Non-example: the halting problem $K$ does not belong to $\mathbf{0}$ , because $K \not\le_T \emptyset$ . Its degree is written $\mathbf{0}'$ .

Every degree is a countable set, since there are only countably many oracle machines. Hence there are uncountably many degrees. Any two degrees $\deg(A)$ and $\deg(B)$ have a least upper bound, the degree of $A \oplus B = \set{2n : n \in A} \cup \set{2n + 1 : n \in B}$ .

Reading path

To understand this page from the ground up, read these 3 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Computable set concept
Turing reduction concept
Turing degree definition

Tag	`CNRVT7009S`
URI	`m2://CNRVT7009S`
Kind	definition
Writing	W0 stub
MSC	03D28, 03D30
Defines	Turing degree
Uses	Turing reduction, Computable set
Changed	2 November 2026

Turing degree

Definition

Remarks

Reading path

Further reading

What this page needs for W1

What links here