$K^X \ge_T X$

Written by Turetsky. Proved by Miller and Turetsky, and then vastly simplified by Bienvenu.

Proposition. For any real $X$, $K^X \ge_T X$.

Proof. $X$ is $X$-trivial. That is, $K^X(X\!\!\upharpoonright_n) \le K^X(n) + c$. Note that $K^X$ can compute the tree $\{\sigma \in 2^{<\omega} : K^X(\sigma) \le K^X(|\sigma|) + c\}$. This tree has finitely many infinite paths, and $X$ is one of them. As an isolated path, $K^X$ can compute $X$. [Source: The 2013 Logic Blog, page 31]

Leave a Reply