# How hard can identifying non-membership in a semi-decidable language be?

A language is called semi-decidable if there is an algorithm for identifying members. There are well-known examples of semi-decidable languages where identifying non-members is equivalent to $$\emptyset'$$, such as the Halting Problem.

My question is: how hard can identifying non-membership be?

• Non-membership is always in $\emptyset'$, since given $x$, you can decide whether $\exists y \, f(x,y)$ using an oracle for the halting problem. – Yuval Filmus Nov 2 '18 at 6:43

A language $$L$$ is semidecidable if there exists a computable predicate $$f$$ such that $$x \in L \Leftrightarrow \exists y \, f(x,y).$$ We can construct a machine $$M$$ which halts on $$x$$ iff $$\exists y \, f(x,y)$$: the machine just goes over all possible $$y$$, for each one checks whether $$f(x,y)$$, and if so, halts. This shows that we can decide $$L$$ using an oracle to the halting problem, i.e., using an $$\emptyset'$$-machine.