# 12.5 Structure of Degrees

## 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:

$$
\mathbf{a} \leq_T \mathbf{b}
$$

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}$:

$$
\mathbf{a} \nleq_T \mathbf{b}
\quad \text{and} \quad
\mathbf{b} \nleq_T \mathbf{a}
$$

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:

$$
\mathbf{a} \leq_T \mathbf{c}
\quad \text{and} \quad
\mathbf{b} \leq_T \mathbf{c}
$$

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

A **least upper bound** (join) is written:

$$
\mathbf{a} \lor \mathbf{b}
$$

It represents the smallest degree that can compute both.

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

$$
\mathbf{a} \land \mathbf{b}
$$

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:

$$
\mathbf{a'}
$$

This satisfies:

$$
\mathbf{a} <_T \mathbf{a'}
$$

Starting from the computable degree:

$$
\mathbf{0} <_T \mathbf{0'} <_T \mathbf{0''} <_T \cdots
$$

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:

$$
\mathbf{a} <_T \mathbf{b}
$$

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

$$
\mathbf{a} <_T \mathbf{c} <_T \mathbf{b}
$$

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}$:

$$
\mathbf{0} <_T \mathbf{a}
$$

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

$$
\mathbf{0} <_T \mathbf{b} <_T \mathbf{a}
$$

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}$:

$$
\mathbf{a} \lor \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.