2

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?

Community
  • 1
johndoe
  • 21
  • It depends. If $L_1$ is empty then $L_1-L_2$ is recursive. If $L_1=\mathbb N$ then $L_1-L_2$ is not recursively enumerable. – bof Oct 29 '15 at 10:05
  • The problem of recursive enumerable sets which are not recursive is that the complement is not recursive enumerable. If you take $L_1= \Bbb{N}$, you immediatly get an example of a non recursive enumerable $L_3$. – Crostul Oct 29 '15 at 10:30

2 Answers2

0

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.).

Xoff
  • 10,310
0

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.

Noah Schweber
  • 245,398