2
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ You mean infinite languages that don't have infinite subsets that are RE or co-RE. $\endgroup$ – Yuval Filmus Nov 24 '14 at 18:42
  • $\begingroup$ @YuvalFilmus Yes, sorry about that. Question updated! $\endgroup$ – templatetypedef Nov 24 '14 at 18:49
  • $\begingroup$ @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. $\endgroup$ – templatetypedef Nov 24 '14 at 19:21
5
$\begingroup$

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

$\endgroup$

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.