# What kind of subset any class of languages may or may not have?

There are different class of languages, regular,CFL, recursive and r.e. and non-r.e. Clearly a language is set of strings. if an infinite set belongs to any of these classes then what can we say about any infinite subset of that set?

As an example the language $\{a^n | n\in N\}$ is a regular language and it is infinite, so is it possible to take a non-recursive or non-r.e subset of this set?

So I would like to know what kind of subsets any of these class of sets may or may not have.

• Of course -- $\Sigma^*$. – Raphael Feb 17 '15 at 8:25
• @Raphael what exactly do you mean? – M a m a D Feb 19 '15 at 4:43
• $\Sigma^*$ is regular but contains all kinds of languages. All kinds, from all levels in the hierarchy since it is a superset of all languages (over alphabet $\Sigma$). Therefore, your question (as I understand it) turns out to be boring: the complexity of a language does not tell you anything about its subsets. – Raphael Feb 19 '15 at 8:15
• So how do we find out if a language, say regular, contains non-recursive subset or not? – M a m a D Feb 19 '15 at 9:11

I do not have a general answer as I am not sure this can be actually answered in a single proof. So your question is really too broad, involving many special cases. And I am afraid there are several readings that increase that breadth, because of the expression "may or may not".

Regarding your example, $\{a^n | n\in\mathbb N\}$, it is trivially computably isomorphic to $\mathbb N$, as it is $\mathbb N$ in unary notation. So I guess it does have have non-recursive or non-r.e. subsets, just like $\mathbb N$.

But let us consider one simple case to understand what you may be after.

I intend to prove that there exists a recursive set such that no infinite regular set can be a subset of that recursive set.

Consider the language $L=\{a^{2^i}\mid i\in\mathbb N\}$. It is clearly a recursive set.

Assume that $R$ is an infinite regular set which is a subset of $L$. Then, the language $R$ has a pumping constant $p$. The language $R$ being infinite, it does have a word longer than $p$. Hence you can prove that it contains a sequence of words that differ in length by some constant value $q$. But the definition of $L$ is such that it contains no such sequence.

Hence $L$ contains no infinite subset that is regular.

So there are recursive set that contain no regular subset.

The proof can be transposed to CFL too.

Is that the kind of answer you are looking for?

• Actually I thought there might any rule and from what I find out of your answer, it totally depends on the characteristic function of the language. about the $a^n$ language, is it true to say that it has at least one non-recursive subset? – M a m a D Feb 19 '15 at 4:50
• Yes it is true. It is in obvious computable bijection with the integers. Actually, it is one common notation for the integer, up to the symbol used. And I seem to recall that there are non-recursive subsets of the integers. – babou May 20 '15 at 16:31
• Yes it is true. It is in obvious computable bijection with the integers. Actually, it is one common notation for the integers, up to the symbol used. And I seem to recall that there are non-recursive subsets of the integers. Actually, I think you might say that up to computable mapping, it contains all the non-recursive sets as subsets. (but I would prefer to have confirmation from a calculability/complexity specialist, which I am not: I am wary of cute statements). – babou May 20 '15 at 16:52