Show that for every language there exists a harder language

Question

I came across this problem that I could not figure out... For every language $A$, there is supposed to be a language $B$ such that:

$$ A \leq_T B $$

but:

$$ B \not \leq_T A $$

If it is $A \leq_TB$ and $B \leq_T A$, this is easy since we can just let $B := \bar{A}$, but for the above I could not think of anything. Any help ?

Answer 1

There are a few ways to approach this.

You can use a counting argument to show that for every $A$ there exists $B$ such that $B\nleq_T A$. Let $L_A=\{B| B\le_T A\}$ denote the set of all languages reducible to $A$. Show that $f:L_A\rightarrow \mathbb{N}$ that maps languages $B\in L_A$ to $n$ such that $M_n$ is a reduction from $B$ to $A$ is an injection, and conclude that there exists a language outside of $L_A$. Next, you want to make it comparable to $A$. We can get such a language with the join operator:

$A\sqcup B=\{0w|w\in A\}\cup\{1w|w\in B\}$.

I leave it to you to show that $A\sqcup B$ is the least upper bound for $A,B$, i.e. $A,B\le_T A\sqcup B$ and additionally for every $L$ such that $A,B\le_T L$ we have $A\sqcup B\le L$ (you only care about the former). Show that if $B\nleq_T A$ then $A\sqcup B\nleq_T A$.

Another way to prove this is to use the jump operator. We need to introduce the notion of oracle machines, and then show that $B=\left\{\left(M^A,w\right)| \text{$M^A$ halts on $w$}\right\}$ is a strictly harder language. The proof is identical to the undecidability of the standard halting problem, only that now we show the stronger property that no machine with oracle access to $A$ can decide $B$.

You can also directly construct such a language via diagonalization. define $B=\left\{n | M_n(n)\notin A\right\}$. We constructed $B$ such that any computable function $M_n$ fails to be a reduction from $B$ to $A$ on at least one input (specifically, the encoding of the reduction). You can now use the join operator to make them comparable.