Question

A language $L$ is called hereditary if it has the following property:

For every nonempty string $z$ in $L$, there is a character in $z$ which can be deleted from $z$ to give another string in $L$.

Prove by contradiction that every nonempty hereditary language contains the empty string.

---

Answer

Here is a proof by contradiction.

1. Proposition to Prove: Let $L$ be a language. If $L$ is nonempty and hereditary, then the empty string, $\epsilon$, is in $L$.

2. Assumption for Contradiction: Assume the proposition is false. This means there exists a language $L$ that is nonempty and hereditary, but does not contain the empty string ($\epsilon \notin L$).

3. Argument:

• Since we assume $L$ is nonempty, we can choose a string from it. Let's find a string in $L$ with the shortest possible length. Since the set of lengths of strings in $L$ is a nonempty set of non-negative integers, by the Well-Ordering Principle, a string with a minimum length must exist. Let's call this string $s$.
• By our assumption, we know that $\epsilon \notin L$. This means that $s$ cannot be the empty string, because if it were, $\epsilon$ would be in $L$. Therefore, $s$ must be a nonempty string.
• Now, we use the fact that $L$ is a hereditary language. The property of being hereditary states that for any nonempty string in $L$ (which $s$ is), we can delete a character to create a new string that is also in $L$.
• Let's create such a new string by deleting one character from $s$. Let's call this new string $s'$. By the hereditary property, $s' \in L$.
• The length of $s'$ is exactly one less than the length of $s$. So, length($s'$) < length($s$).
• This leads to a contradiction. We chose $s$ to be a string in $L$ with the minimum possible length. However, we have just constructed another string, $s'$, which is also in $L$ but is shorter than $s$. This contradicts the definition of $s$ as the shortest string in $L$.

4. Conclusion: Our initial assumption—that a nonempty, hereditary language $L$ can exist without containing the empty string—must be false.

Therefore, we conclude that every nonempty hereditary language must contain the empty string.

Changelog

8/8/25, 4:17 AM

View All Changelog

• 2aa48-web-deploy(Auto): Update base URL for web-pages branchon 8/8/25

Copyright

Copyright Ownership:WARREN Y.F. LONG

License under:Attribution-NonCommercial-NoDerivatives 4.0 International (CC-BY-NC-ND-4.0)