Friedberg–Muchnik theorem below C

Statement

This shows that the order-structure of Turing degrees is quite complicated, even among enumerable sets.

WLOG, we assume that $C$ is enumerated as $C_0 \subsetneq C_1 \subsetneq C_2 \subsetneq \cdots$, each $C_n$ being a finite set.

To prove the theorem, we define the concept of permission. Technically, this is the Yates permitting. There are other kids of permissions.

Given two sequences of finite sets $A_n \uparrow A, C_n \uparrow C$, we say that $\{C_n\}_{n \in \mathbb{N}}$ permits $\{A_n\}_{n \in \mathbb{N}}$ iff

$$\forall n, i \quad C_n \cap [0:i] = C \cap [0:i] \implies i \not\in A_{n+1} \setminus A_n$$

A bit more generally, if $f : \mathbb{N} \to \mathbb{N}$, then we say that $\{C_n\}_{n \in \mathbb{N}}$ f-permits $\{A_n\}_{n \in \mathbb{N}}$ iff

$$\forall n, i \quad C_n \cap [0:f(i)] = C \cap [0:f(i)] \implies i \not\in A_{n+1} \setminus A_n$$