# Prove that A* is the smallest reflexive and transitive set containing A

I'm trying to learn automata theory on my own and I am running into an issue with the second part of the question:

We say B is transitive if $BB\subseteq B$ and reflexive if $\epsilon \in B$

Show that A* is a reflexive and transitive set containing A and if B is any other reflexive and transitive set containing A, then $A^*\subseteq B$.

I've shown that Kleene star satisfies these two conditions. I've tried partitioning B into two sets with $A = B \cup C$ and trying a constructive proof but this hasn't led any where. I also am considering a proof by contradition but don't know where to start.

Can you help me with a hint on how to approach this problem?

• Do you see how $BB \subseteq B$ implies that $b_1b_2b_3 \in B$ for any $b_1, b_2, b_3 \in B$? – Karolis Juodelė Jan 19 '14 at 8:29

Hint: Try the usual approach to show set inclusion! That is, pick $w \in A^*$ and show that $w \in B$.
Apply transitivity of $B$ repeatedly.
If $w \in A^*$ then either $w = \varepsilon \in B$ or there are $w_1, \dots, w_k \in A \subseteq B$ with $w = w_1 \cdot \dots \cdot w_k$. Now, because $BB \subseteq B$ we have $w_2' = w_1 w_2 \in B$. For the same reason, $w_2' w_3 \in B$. And so on. Perform induction for the general proof.