# Isn't the given characterisation of recursively enumerable subsets of the class of all recursively enumerable languages?

$$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?

• 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. – Andrej Bauer Nov 5 '18 at 13:36

## 1 Answer

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

• So, whats the 3rd statement mean exactly? I still didn't get. – Saravanan Nov 4 '18 at 16:31
• It says that there is a machine $M$ which enumerates $\{L \in S \mid \text{$L$is finite}\}$. Is that clear? – Andrej Bauer Nov 4 '18 at 16:50
• 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 – Saravanan Nov 5 '18 at 4:27
• 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. – Andrej Bauer Nov 5 '18 at 7:41
• 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. – Andrej Bauer Nov 5 '18 at 7:42