Proof of A = {0, 1} and B ⊆ {0, 1}*

Question

//Note that the "*" is the kleene star.

Prove: If A = {0, 1} and B ⊆ {0, 1}* , then A* = B* ⇒ A ⊆ B.

I will prove these two statements separately.

First I'm proving A*=B* by showing that A*⊆B* and B*⊆A*.

A={0,1}, so A*={0,1}*

B⊆{0,1}* is where I have trouble, because {0,1}* = {e,0,1,00,01,10,11,...} and I thought this meant that B could be equal to {0}. If this were true, then B*={0}* , which would make A*⊆B* false.

I must be misinterpreting what B⊆{0,1}* is. Any help is appreciated.

Answer 1

$B\subseteq\{0,1\}^{*}$ means that $B$ isn’t empty, then B has at least some elements of $\{0,1\}^{*}$.

I believe that you may be misinterpreting the statement you’re asked to prove. The statement is: “If A = $\{0, 1\}$ and $B \subseteq \{0, 1\}^{*}$ , then $A^*= B^* ⇒ A \subseteq B$”.

One needs to show that $A^*= B^* ⇒ A \subseteq B$, with $A,B$ characterized as above. It constrains $B$ to be in the Klene closure in such a way that it’s Klene closure is the same as $A$. Of course there are examples where this implication doesn’t hold, but that’s not what we are asked to prove.

Answer 2

$A$ is fixed. So we know that $A^* = \{0,1\}^*$. So we know among other things that $0\in A^*$ and also $1\in A^*$. Both of these are not concatenations of any other nonempty strings. So if they are in the Kleene closure of a set, then they are in the original set.

So if $A^* = B^* = \{0,1\}^*$ we know that both $1$ and $0$ must be in $B$. This shows that the right-hand side of the implication always holds when $A^* = B^*$ is true. When $A^* = B^*$ is false, the implications holds in all cases.