Show that for every language there exists a harder language

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 ?

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.

• I'm having trouble formalizing the argument that $B \not \leq A$ for the oracle machine? Would you mind giving some more clarity on how to complete the proof you described?
– ENV
Commented Feb 10, 2022 at 14:35