Infinite regular sets

Question

Would it be true that for all infinite regular subsets, each one contains subsets that are not c.e/r.e (countably enumerable/recursively enumerable)?

Intuitively this seems true because of sets that are uncountable.

Answer 1

Uncountability has nothing to do with it: none of the sets that you’re talking about in this context is uncountable. However, the statement is true; it follows from the pumping lemma for regular languages. If $L$ is regular and infinite, let $p$ be its pumping length, and let $w\in L$ be such that $|w|\ge p$. Then $w$ can be decomposed as $w=xyz$ in such a way that $|xy|\le p$, $|y|\ge 1$, and $xy^kz\in L$ for all $k\ge 0$. Let $A\subseteq\Bbb N$ be a non-r.e. set, and consider $\{xy^kz:k\in A\}\subseteq L$.