# Proving $A^\ast = A$ on a given set

I am working on some set theory and am trying to prove how a set can have the property $$A^* = A$$.

For set $$A=\{0^n1^n \mid n \ge0\}$$, I still do not understand exactly what $$A^*$$ is. For example, I thought $$A^*$$ is the enumeration of the set $$A$$ so

$$A^* = \{\epsilon,01,0011,000111,00001111,....\}$$

Any helping in at least understanding what $$A^*$$ is for this problem would be much appreciated!

• $\{0^n1^n \mid n \ge0\}$ is exactly $\{\epsilon,01,0011,000111,00001111,\cdots\}$. – John L. Jan 29 '19 at 1:19
• Can you confirm $A^*$ is the Kleenen star of $A$ in the question? – John L. Jan 29 '19 at 1:21
• Your set doesn't satisfy $A^*=A$. – Yuval Filmus Jan 29 '19 at 4:57
• If you are searching from some set $A$ satisfying $A=A^*$, try choosing $A=B^*$ for any $B$. Further, not all sets $A$ satisfy $A=A^*$, e.g. $A=\{0\}$ is surely different from $A^* = \{\epsilon,0,00,\ldots\}$. – chi Jan 30 '19 at 11:46

What you have written (i.e., $$\{ \varepsilon, 01, 0011, 000111, \ldots \}$$) is simply $$A$$ itself.
(Assuming $$A^\ast$$ is the Kleene star operation) you cannot prove $$A = A^\ast$$ because it is not correct.
The Kleene star $$A^\ast$$ is defined as the union of the powers $$A^i$$, where $$A^0 = \{ \varepsilon \}$$ and $$A^{i+1} = A^i \cdot A = \{ w \cdot w' \mid w \in A^i, w' \in A \}$$. An inductive argument easily shows: $$A^i = \{ w_1 \cdots w_i \mid w_1, \ldots, w_i \in A \} = \{ 0^{n_1} 1^{n_1} \cdots 0^{n_i} 1^{n_i} \mid n_1, \ldots, n_i \ge 0 \}$$
Since $$A^\ast$$ is the union over all such $$A^i$$, we obtain $$A^\ast = \{ 0^{n_1} 1^{n_1} \cdots 0^{n_i} 1^{n_i} \mid i, n_1, \ldots, n_i \ge 0 \},$$ which is obviously not equal to $$A$$.