12.5 Structure of Degrees

Turing degrees organize problems by computational power. After Post’s problem, it becomes clear that this structure is highly complex. It is not a simple linear hierarchy but a rich partially ordered system.

Partial Order

Turing degrees are ordered by reducibility:

means every set in degree $\mathbf{a}$ is computable using an oracle for any set in degree $\mathbf{b}$.

This order has three key properties:

• reflexive
• transitive
• antisymmetric (after identifying equivalent sets)

So degrees form a partial order, not a total order.

This means that for some degrees $\mathbf{a}$ and $\mathbf{b}$:

Such degrees are incomparable.

Incomparable Degrees

Incomparability is a central feature.

There exist degrees $\mathbf{a}$ and $\mathbf{b}$ such that neither can compute the other. These degrees represent problems with different kinds of computational content.

This shows that computational difficulty is multi-dimensional. Two problems may both be noncomputable, yet neither subsumes the other.

Upper and Lower Bounds

Given two degrees $\mathbf{a}$ and $\mathbf{b}$, we can ask whether there exists a degree above both or below both.

An upper bound $\mathbf{c}$ satisfies:

A natural upper bound is given by combining information from both sets.

A least upper bound (join) is written:

It represents the smallest degree that can compute both.

Similarly, a greatest lower bound (meet), when it exists, is written:

The structure of degrees is not a complete lattice. Some pairs do not have a well-defined meet.

The Jump Operator

The Turing jump produces strictly higher degrees.

For any degree $\mathbf{a}$, its jump is:

This satisfies:

Starting from the computable degree:

Each jump adds a new level of undecidability.

The jump operator plays a central role in organizing degrees into layers.

Density

One of the key structural results is density.

Between any two degrees:

there exists another degree $\mathbf{c}$ such that:

This means there are no immediate neighbors in the ordering. The structure has no gaps.

Density holds for the recursively enumerable degrees between $\mathbf{0}$ and $\mathbf{0'}$, and more generally in the full degree structure.

Minimal Degrees

A degree $\mathbf{a} > \mathbf{0}$ is minimal if there is no degree strictly between $\mathbf{0}$ and $\mathbf{a}$:

and there is no $\mathbf{b}$ such that:

Minimal degrees exist, but they are not recursively enumerable. This shows a difference between the full degree structure and the r.e. degrees.

Upper Semilattice

The Turing degrees form an upper semilattice.

This means:

• every pair of degrees has a least upper bound
• joins always exist

So for any $\mathbf{a}$ and $\mathbf{b}$:

is defined.

However, greatest lower bounds do not always exist, so the structure is not a full lattice.

Intuition

The structure of degrees reflects how information can be encoded and transformed.

• Some problems contain more information than others
• Some problems encode different kinds of information
• Combining problems increases computational power
• Iterating the jump leads to higher and higher levels

Instead of a single scale of difficulty, we get a landscape with branching paths, incomparable regions, and infinitely many intermediate levels.

This structure shows that undecidability is not a single phenomenon. It comes in many distinct forms, organized by reducibility into a deep and intricate hierarchy.