[Solved]: Is there a name for complement of recursively enumerable set?

Problem Detail: 

If there is a recursive function $$ f(x) = \begin{cases} 1 & \text{if $x \notin A$}\\ \text{undefined} & \text{if $x \in A$}\\ \end{cases} $$

Is there a special name for the class of sets like $A$?

Asked By : Juris

Answered By : Huck Bennett

The complement of a recursively enumerable (RE) language is called co-recursively enumerable (co-RE).

As RE and co-RE form the first level of the arithmetic hierarchy, they are also known by aliases $\Sigma_1^0$ and $\Pi_1^0$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/11564

3.2K people like this

 Download Related Notes/Documents