0
$\begingroup$

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

Improve this question
$\endgroup$
  • $\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$ – Andrej Bauer Nov 5 '18 at 13:36
1
$\begingroup$

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

Improve this answer
$\endgroup$
  • $\begingroup$ So, whats the 3rd statement mean exactly? I still didn't get. $\endgroup$ – Saravanan Nov 4 '18 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$ – Andrej Bauer Nov 4 '18 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 '18 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$ – Andrej Bauer Nov 5 '18 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$ – Andrej Bauer Nov 5 '18 at 7:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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