Relations notation

Question

say, you have $R^* :== \bigcup_{k = 0}^{\infty}R^k$, where $R$ relation and $R^n =R^{n-1}R$.

Then $(R^*)^* = (\bigcup_{k = 0}^{\infty}R^k)^* = $ ??

I am not sure about how to open the second $*$

Answer 1

By definition, $$ (R^*)^* = \bigcup_{k = 0}^{\infty} (R^*)^k = \bigcup_{k = 0}^{\infty} ( \bigcup_{l=0}^{\infty} R^l ){}^k $$

Now (can you see and show this?), $$( \bigcup_{l=0}^{\infty} R^l )^k = \bigcup_{l=0}^{\infty} R^{lk}$$ so$$ (R^*)^* = \bigcup_{k = 0}^{\infty} (R^*)^k = \bigcup_{k = 0}^{\infty} \bigcup_{l=0}^{\infty} R^{lk} = \bigcup_{n = 0}^{\infty} R^{n} = R^* $$ where the reduction from two unions to one union is valid since $lk$ runs over all natural numbers.