If you want to make money online : Register now

[Answers] An infinite language with no infinite RE or co-RE subsets?

, , No Comments
Problem Detail: 

Are there any languages that are infinite (that is, they contain infinitely many strings) but which do not have any infinite subsets that are RE or co-RE languages? This seems related to simple sets, but I can't seem to find any examples of languages with these properties.


Asked By : templatetypedef

Answered By : Yuval Filmus

Let's prove a more general result using diagonalization. Suppose $L_1, L_2, \ldots$ is a countably infinite list of infinite languages. Then there is an infinite language $L$ that doesn't contain any of them.

We construct $L$ in infinitely many steps. At each step $t$, we keep a list of words $A_t$ in the language, and a list of words $B_t$ outside the language; these will be monotone increasing, that is, $A_t \subseteq A_{t+1}$ and $B_t \subseteq B_{t+1}$. The lists $A_t,B_t$ will always be finite and disjoint, and furthermore $|A_t|$ will grow without bounds. We can take $L$ to be the union of all $A_t$.

Let $A_{-1}=B_{-1} =\emptyset$. At step $t$, let $B_t = B_{t-1} \cup \{x\}$ for some $x \in L_t \setminus A_{t-1}$, and $A_t = A_{t-1} \cup \{y\}$ for some $y \notin B_t$. Now $|A_t| = |B_t| = t$.

Step $t$ ensures that $L$ doesn't contain $L_t$, and at the same time that $|L| \geq t$. Taking $t\to\infty$, we deduce that $L$ is infinite and is not a superset of any $L_t$.

Best Answer from StackOverflow

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

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback