[Fondamenti di Informatica] Cardinalità di un linguaggio

[IlRosso1]

Salve a tutti! Sto studiando per l'esame di Fondamenti di Informatica e sto cercando di fare tutti gli esercizi della dispensa del prof! Premetto che sono all'inizio ma c'è un esercizio sulla cardinalità di un linguaggio a cui credo di aver trovato la risposta ma che vorrei sottoporre a voi! Il testo è questo:
Definendo

$ { ( Sigma^0 = {epsilon} ),( Sigma^(n+1)={ax:ain Sigma,x in Sigma^n} ):} $

si osservi che $ Sigma^**=uu _(i>=0)Sigma^i $
Qual è la cardinalità di $ Sigma^i $ ?

La mia risposta intuitivamente sarebbe $ i $ ma visto che questo è un esame un pò bastardo sono dubbioso vista la semplicità della risposta! Attendo con ansia le vostre risposte!!!

[killing_buddha]

La risposta dipende dalla cardinalità di $\Sigma$, ovviamente. Prova a dimostrare che se $\Sigma$ è un insieme finito, diciamo con $k$ elementi, allora \(\Sigma^n = \Sigma \times \dots \times\Sigma\) ha esattamente $k^n$ elementi. Questo dovrebbe essere facile.

Ora comincia la parte leggermente più difficile, perché se $\Sigma$ è infinito, $\Sigma^n$ è infinito anche lui, e ha la stessa cardinalità di $\Sigma$; allo stesso modo una unione finita o numerabile di insiemi di cardinalità $|\Sigma|$ ha ancora la cardinalità di $\Sigma$. Per mostrare questo è sufficiente trovare la giusta biiezione, il che richiede un pizzico di follia e la giusta dose di ubriachezza.

[IlRosso1]

"killing_buddha":La risposta dipende dalla cardinalità di $\Sigma$, ovviamente. Prova a dimostrare che se $\Sigma$ è un insieme finito, diciamo con $k$ elementi, allora \(\Sigma^n = \Sigma \times \dots \times\Sigma\) ha esattamente $k^n$ elementi. Questo dovrebbe essere facile.

Allora, la prima parte l'ho risolta così: sono partito da presupposto che $ |Sigma^n|=k^n $ elementi (Ipotesi induttiva).
Poi per induzione:
Passo base (n=1)
$ |Sigma^1|=k^1=k $
Passo induttivo (n=n+1)
$ |Sigma^(n+1)|=|Sigma^n|*|Sigma^1| $
$ |Sigma^n| $ e $ |Sigma^1| $ li conosco già, cioè $ |Sigma^n|=k^n $ (Ipotesi induttiva) e $ |Sigma^1|=k $ (Passo base) . Quindi:
$ |Sigma^(n+1)|=k^n*k=k^(n+1) $

Ora penso alla seconda parte!
EDIT: mi sto scervellando ma niente! qualche suggerimento?