0
$\begingroup$

Is an infinite set of RE languages create a language that is also RE?

I think it's true, and my first intuition is to try induction to prove this statement.

Am I on the right way?

Thanks!

$\endgroup$
4

1 Answer 1

4
$\begingroup$

The statement is not true; any language $L$ can be written as the (countably infinite) union of singleton languages which each just contain one word of $L$.

Also, even if the statement was true, one could not prove it using (regular) induction. This is because the finite union of RE languages is indeed RE. My go-to example here is that one can show using induction that every natural number is finite, but there exists no infinite natural number.

$\endgroup$
8
  • $\begingroup$ I don't see why it is a counter-example. Let me write it formally: If $L_1,L_2,...$ is an infinite set of languages such that each one of them is in RE, then $\bigcup_{j=1,2,...}L_j$ is in RE. $\endgroup$
    – Geo
    Nov 15, 2022 at 12:51
  • 1
    $\begingroup$ @Geo His answer is a counter-example. Consider $L$ a non-RE language. Since any language is countable, you can count its words, $u_1, u_2, …$ Now $L = \bigcup\limits_{j\geqslant 0}\{u_j\}$, and each $\{u_j\}$ is RE (because it is finite). $\endgroup$
    – Nathaniel
    Nov 15, 2022 at 12:57
  • $\begingroup$ @Nathaniel i do not understand, L is RE, why assuming its not? $\endgroup$
    – Geo
    Nov 15, 2022 at 13:59
  • $\begingroup$ We show that a non-RE language can be written as the countably infinite union of RE languages. That shows that in general, such infinite unions of RE languages are not necessarily RE themselves. $\endgroup$ Nov 15, 2022 at 14:30
  • $\begingroup$ I might be misunderstanding something, but say you have a non-RE language $L$, how are you going to take its singleton elements and then build $L$ back if there is no TM that can tell if $w$ is in $L$. How do we even know that $w$ is even in $L$? $\endgroup$
    – Russel
    Nov 15, 2022 at 15:12

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.