Does there exist a set of strings $L \subseteq 1^*$ such that $L$ is an irregular language?

Question

I am currently trying to prove/disprove the following statement from my textbook:

Let $1^*$ be the regular language of all strings consisting of only ones. Does there exist a set of strings $L \subseteq 1^*$ such that $L$ is an irregular language?

My initial assumption is that the statement is false (unless I am wrong), so that is what I am trying to prove.

My proof: Given $L \subseteq 1^*$, let us define some strings in $L$ such that $L \subseteq 1^*$. Let $L = \{1,11,111\}$. Now $L \subseteq 1^*$. Let us check if each string in $L$ is regular. $1$ is a string that contains only one $1$ and is a regular language since it is accepted by $1^*$. $11$ is a string that contains only two $1$s and is a regular language since it is accepted by $1^*$. Likewise, $111$ is a string that contains three $1$s and is a regular language since it is accepted by $1^*$. So, $L$ is a regular language. From this, we can claim that there doesn't exist a set of strings $L \subseteq 1^*$ such that $L$ is an irregular language. The basic condition that needs to be met is that $L \subseteq 1^*$ which means that $L$ should only contain strings that are accepted by $1^*$. Thus, $L \subseteq 1^*$ is never an irregular language.

Is my proof correct? I am somewhat unsure due to how little thought it took for me to come up with sufficient reasoning to prove my assumption. If not, can someone please provide sufficient proof for me to understand what I did wrong? Any help or suggestion would be greatly appreciated.

Answer 1

Is my proof correct?

Unfortunately not. If this is a beginning foray into formal proofs, I encourage you to think carefully about the logical structure of your initial attempt and how it compares to the statement you want to prove. I would rephrase the question as: Prove or give a counterexample to the statement, 'Every $L\subseteq 1^*$ is a regular language.'

You must either provide an L which is irregular, i.e. a counterexample to the claim "every $L\subseteq 1^*$ is regular", or you must prove that every such $L$ is regular. Your argument exhibits a single regular $L$, but isn't enough to prove that there is not some different $L$ out there which is not regular.

If not, can someone please provide sufficient proof for me to understand what I did wrong?

Let me suggest you refine this question down into two sub-questions:

1. Is every nonempty finite $L\subseteq 1^*$ a regular language? Give a proof or counterexample.
2. Is every infinite $L\subseteq 1^*$ a regular language? Give a proof or counterexample.

Some modest hints: You should get different answers to the above sub-questions. Your attention should be focused on understanding the pumping lemma https://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages. Your textbook almost certainly contains an example of how this Theorem is used which you should read over carefully.

Answer 2

I am afraid that your solution does not make any sense, as shown in the comments. Here are a few facts related to your question:

1. The language $\{1^{n^2} \mid n \geqslant 0 \}$ is not regular.
2. A language of $1^*$ is regular if and only if it is of the form $F \cup G(1^k)^*$ where $F$ and $G$ are finite languages and $k \geqslant 0$.
3. There are only countably many regular languages, and since the set of languages of $1^*$ is uncountable, there are uncountably many irregular languages in $1^*$.
4. A language of $1^*$ is regular if and only if it is context-free.