# An infinite language with no infinite RE or co-RE subsets?

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.

Thanks!

• You mean infinite languages that don't have infinite subsets that are RE or co-RE. – Yuval Filmus Nov 24 '14 at 18:42
• @YuvalFilmus Yes, sorry about that. Question updated! – templatetypedef Nov 24 '14 at 18:49
• @Raphael I attempted to use some sort of diagonal construction (list all RE and co-RE languages interwoven with one another) but ran into trouble because trying to convince myself that the diagonal language formed couldn't itself be an RE or co-RE languages. I considered using a cardinality argument (looking at the number of RE and co-RE languages and how many sets of strings contain each as a subset), but that didn't seem to resolve it either. For what it's worth, this isn't a problem set question - I'm actually teaching a computability class right now and this was purely out of curiosity. – templatetypedef Nov 24 '14 at 19:21

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