# 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. Commented 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. Commented 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??? Commented Aug 31, 2019 at 20:10