$S$ is a subset of the class of all recursively enumerable languages over some finite symbols then $S$ is recursively enumerable iff

  1. If $L$ is in $S$ and $L'$ is a language such that $L ⊆ L'$ and $L'$ is recursively enumerable, then $L'$ is in $S$
  2. If $L$ is an infinite language in $S$, then there exists at least one finite subset of $L$ that is in $S$
  3. The set of all finite languages in $S$ is enumerable, i.e. a Turing machine can list all the finite languages in $S$

Source of the statement: https://cs.stackexchange.com/q/2322 and some online notes

Isn't the 3rd one contradictory to the 1st one?

  • $\begingroup$ No, because you are misreading the third condition. It doesn't say that $S$ contains all the finite r.e. languages. It says that those finite r.e. languages that happen to be in $S$ are r.e. $\endgroup$ Nov 5, 2018 at 13:36

1 Answer 1


No, it is not contradictory. Both conditions are positive in the sense that they "put things in $S$", so they cannot be at odds with each other.

There is an equivalent formulation of $S$: there is an r.e. set $B$ of finite languages such that $$S = \{L \mid \text{$L$ is r.e. and $\exists L_0 \in B \,.\, L_0 \subseteq L$}\}.$$ In words: $S$ is generated by an r.e. set of finite language $B$ in the following way: $S$ contains precisely all r.e. languages which contain an element of $B$.

  • $\begingroup$ So, whats the 3rd statement mean exactly? I still didn't get. $\endgroup$
    – Saravanan
    Nov 4, 2018 at 16:31
  • $\begingroup$ It says that there is a machine $M$ which enumerates $\{L \in S \mid \text{$L$ is finite}\}$. Is that clear? $\endgroup$ Nov 4, 2018 at 16:50
  • $\begingroup$ Then it means {$L\in S∣L$ is finite} is r.e, but by 1st statement r.e set should contains some infinite sets also, thats what I want to clarify $\endgroup$
    – Saravanan
    Nov 5, 2018 at 4:27
  • $\begingroup$ The first condition does not say that. For instance $S$ could be empty. The first condition says that if $L \in S$ and $L \subseteq L'$ then $L' \in S$. So yes, if $S$ contains a finite language, then it also contains a lot of infinite languages. $\endgroup$ Nov 5, 2018 at 7:41
  • $\begingroup$ Still, there is no contradiction. Are you using the word "contradiction" to mean "this looks strange to me"? Because that's not how it's used. $\endgroup$ Nov 5, 2018 at 7:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.