# How to prove by contradiction that every nonempty hereditary language contains the empty string?

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

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

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

Here's my attempt:

To prove by contradiction, we assume that for every nonempty string x in L, there is no character in x which can be deleted from x to give another string in L.

This means that if a character in x is deleted an empty string is left. Since an empty string is also a string, every nonempty hereditary language contains the empty string.

I'm not exactly sure how to proof by contradiction. Can someone help review this?

• The line after "here is my attempt" is wrong. Aug 31, 2019 at 19:56
• The second line is a non sequitur. What follows from the first (incorrect) line is that if a character in x is deleted, the result is not in L. Aug 31, 2019 at 20:09
• You say "This means that if a character in x is deleted an empty string is left". So the string has exactly one character??? Aug 31, 2019 at 20:10

Let L be a nonempty hereditary language. Let x be one of the shortest strings in L. x exists because L is not empty.

Removing any character from x would produce a string not in L, since x is one of the shortest strings. Because L is hereditary, we can remove a character from x giving another string in L, unless x is the empty string. Therefore x is the empty string. Therefore L contains the empty string.

If you insist on proof by contradiction: Let L be a nonempty hereditary language not containing the empty string, and let x be one of the shortest strings in L. x is not the empty string since L doesn't contain the empty string. Therefore there is a character in x which can be removed, giving a string y in L.

But y is shorter than x, therefore x is not the shortest string in L.