Under which operations is the class of non-recursive languages a closure?

Question

I am currently studying turing computability and related problems such as the halting problem with a background in formal languages.

I know that the class of recursive (decidable) languages is a closure under union, intersection and complement, and that recursively enumerable languages (semi-decidable) are a closure under union and intersection, but what about non-recursive (undecidable) languages?

To be more specific, I am trying to prove that a specific language of the form $$L = \{ w \in \Sigma^* : w \in A \lor w \in B \}$$ is non-recursive. I managed to prove that neither $A$ nor $B$ are recursive by reducing them to the universal halting problem, but I am not sure what that implies for $L$.

The exact language is $$L = \left\{ w\#u \in \left\{ 0, 1, \# \right\}^* | \\ M_w \text{ will halt with input } u \text{ or } M_u \text{ will halt with input } w \right\}$$ where $M_b$ is the turing machine whose transition function $\delta$ is represented using Gödel numbering as a binary string $b$.

Is the class of non-recursive languages a closure under union? If it is, how could I prove it myself or where could I find an existing proof?

Answer 1

Non-recursive languages are closed under complement, but not under union or intersection.

Indeed, a decider for $A$ exists iff there is a decider for $A^c$. Hence the closure under complement.

However, let $B$ be any non-recursive language. $B^c$ is also non-recursive. But $B \cap B^c = \emptyset$ and $B \cup B^c = \Sigma^*$ are both recursive. Hence, non-recursive languages are not closed under union or intersection.

In the example you mention, you can not conclude anything about $L$ from $A,B$ being non recursive.

I will provide a hint for $L$, only. When you have a language of the form $L=\{f(x,y) | x,y\mbox{ s.t. } p(x,y)\}$, it is sometimes convenient to choose a particular value $a$ and study the related language $L_a = \{ y | y\mbox{ s.t. } p(a,y) \}$ first. Maybe one can choose $a$ to make $p(a,y)$ simple enough so that other proof techniques apply.