Proving closure of S is the smallest closed set containing S.

Question

How does one approach the problem of showing that cl($S$) is the smallest set containing $S$?

I would assume that the smallest set containing $S$ is $S$ itself maybe with one more element.

I am not asking for the proof, just the approach.

EDIT: By closure, $S$* = $S$⁰ ∪ $S$¹ ∪ $S$² ∪ ... This was the definition of "closure" given to us during lecture.

Answer 1

You suggested in the comments that your actual question is to show that $S^*$, the Kleene closure of $S$, is the smallest set that contains $S$, contains $\{\varepsilon\}$, and is closed under concatenation.

There are two parts to this. The first is to show that $S^*$ actually has those three properties. The second is to show that any language $L$ that has those three properties must contain $S^*$. This shows that $S^*$ is the smallest such set, because any other set with those properties must be at least as big, since it actually contains $S^*$ itself.

1. The first part is straightforward. Recall that $S^* = S^0\cup S^1\cup S^2\cup\cdots$.

   1. Therefore $S^*$ contains $S^0$, which is $\{\varepsilon\}$.
   2. And it contains $S^1$, which is $S$.
   3. We also need to show that $S^*$ is closed under concatenation. Let $a$ and $b$ be elements of $S^*$. We want to show that $ab\in S^*$ as well. There must be $m$ such that $a\in S^m$, and similarly $n$ such that $b\in S^n$. That means that $a$ is the concatenation of some sequence of $m$ elements of $S$, and $b$ similarly, so $ab$ is the concatenation of some finite sequence of $m+n$ elements of $S$ and is therefore an element of $S^{m+n}$, which is contained in $S^*$. So $S^*$ is closed under concatenation.

2. For the second part, say $L$ is some language that contains $S$, contains $\{\varepsilon\}$, and is closed under concatenation. We want to show that $L$ contains $S^*$. It is enough to show that if $s$ is any string of $ S^*$, $s$ is also in $L$.

   If $s$ is $\varepsilon$ or is an element of $S$, we are done.

   Otherwise $s$, being an element of $S^*$, is a concatenation of some finite sequence of elements $s_1, s_2,\ldots s_n$ of $S$. Since these are elements of $S$, they are elements of $L$ also, by hypothesis. Since $L$ is closed under concatenation, the concatenation $s_1s_2\ldots s_n=s$ is an element of $L$.

   Every element of $S^*$ is therefore an element of $L$, so $L$ contains $S^*$, and we are done.

Answer 2

"Closure" is a fuzzy term, used in many branches of mathematics, for functions that map sets to sets where it can be proved that

$f(A)$ is the smallest set that contain $A$ and satisfies such-and-such additional conditions

where the "additional conditions" vary between various kinds of closure. The usual way to this claim for a particular function $f$ is to prove each direction separately:

• $f(A)$ contains $A$ and satisfies the such-and-such conditions.
• Assume some set $C$ satisfies the such-and-such conditions. Then $f(B)\subseteq C$ for every $B\subseteq C$.

These two properties combine into the alternative characterization of $f$:

$f(A)$ is the intersection of all supersets of $A$ that satisfies such-and-such conditions.

This can be used as an alternative definition of $f$, but requires proof that (a) the such-and-such conditions are preserved by infinite intersection, and (b) there is at least one set (usually a "universal set" in some sense) that satisfies the conditions.

For any given closure concept, it is not uncommon that some texts will define it by one of the above characterization and others by a concrete construction that happens to provide the abstract closure property.