Is this set recursively enumerable/recursive?

Question

I've recently started studying the ideas behind algorithms. That being said, I found myself browsing through different sorts of problems in order to get a better grasp on the subject.

Inspired by this question, I'm going to ask for a few more details, as I find myself unable to understand the answer. Precisely, what I would like to know is :

Given two sets, $L_1$ and $L_2$, such that $L_1$ is recursive and $L_2$ is recursively enumerable but not recursive, what can one say about $L_3 = L_1 -L_2$ and what's the formal reasoning behind it?

Answer 1

Note that $L_3^C$ is recursively enumerable as $L_3^C=L_2\cup L_1^C$ and both $L_2$ and $L_1^C$ are recursively enumerable.

Hence, as Crostul explained in comments, either $L_3$ is recursively enumerable (for example if $L_1$ is finite and so $L_3$ is recursive) or is not (for example if $L_1=\mathbb N$ and so $L_3$ is co-r.e.).

Answer 2

As the comments and Xoff's answer indicate, the set $L_3$ is not necessarily r.e., although it is co-r.e. (exercise). But it doesn't stop here! There's actually a rich hierarchy here: the $n$-r.e. sets. (See e.g. http://www.math.cornell.edu/~shore/papers/ps/nre32.ps.)

A set is:

• 1-r.e. if it is r.e. in the usual sense.

• $(n+1)$-r.e. if it is of the form $A-B$ for $A$ r.e. and $B$ $n$-r.e.

It is known that the $n$-r.e. hierarchy does not collapse: for any $n$, there is an $(n+1)$-r.e. set which is not $n$-r.e. (And more than this is true: there is an $(n+1)$-r.e. degree which is not an $n$-r.e. degree. I believe that for $n=1$ this was proved in Barry Cooper's Ph.D. thesis - I'll add a citation when I can find one.)

This hierarchy can actually be continued into the transfinite - the $\alpha$-r.e., or Ershov, hierarchy - but that's much more complicated; see http://ims.nju.edu.cn/~yuliang/ssyy.pdf.