I think the following exercise is to "warm up", but nevertheless it's quite difficult for me:
Let $k \in \mathbb{N}$ and let $L \in \Sigma_k$. Show that also $L^{*} \in \Sigma_k$.
The following details from my lecture notes seem to be useful:
Notation. Let $n \in \mathbb{N}$.
We write $\exists_n y. \varphi(y)$ for $\exists y \in \Sigma^{*}.|y| \le n \wedge \varphi(y)$.
We write $\forall_n y. \varphi(y)$ for $\forall y \in \Sigma^{*}.|y| \le n \Rightarrow \varphi(y)$.
Theorem.
$L \in \Sigma^P_i \Leftrightarrow$ there is a language $A \in P$ and a polynomial $p$ so that: $x \in L \Leftrightarrow \exists_{p(|x|)}y_1 \forall_{p(|x|)}y_2 \exists_{p(|x|)}y_3 .../\forall_{p(|x|)}y_i (x,y_1,y_2,...,y_i) \in A$
Unfortunately I don't see the solution of the "puzzle". Can somebody please help me a little bit (despite the fact that it's weekend)?