Allora, abbiamo un insieme numerabile di simboli A.
Consideriamo l'insieme di tutte le stringhe finite su A e chiamiamolo A* (lo facciamo per comodita', poiche'
l'operazione '*' e' definita su linguaggi, e A non e' un linguaggio... Perche'?)
Se indichiamo con
A0 l'insieme composto dalla stringa vuota,
A1 l'insieme A stesso
A2 l'insieme fatto dalle stringhe di elementi di A lunghe 2
ecc.ecc.
abbiamo che A* e' l'unione di tutti gli An per ogni n
(non abbiamo usato l'operazione di potenza, poiche' noi l'abbiamo definita su linguaggi...)
Ogni An e' un insieme numerabile e quindi
puo' essere enumerato, con una lista del tipo
An,0,An,1,An,2....
(dove An,k e' il k+1-esimo elemento della lista con cui enumeriamo gli elementi di An
[dato n, l'enumerazione per An si puo' ottenere con lo stesso metodo indicato
nel seguito, a partire da An-1 e A]
Quindi quel che dobbiamo fare ora e' trovare una enumerazione per A*
(descrivere cioe' una lista che contenga tutti gli elementi di tutti gli An)
Consideriamo quindi la seguente tabella infinita
0 1 2 3 4 ....
A0
A1
A2
A3
.
.
e riempiamola nel seguente modo
0 1 2 3 4 ....
A0 A0,0 A0,1 A0,2 A0,3...
A1 A1,0 A1,1 A1,2 ...
A2 A2,0 A2,1 A2,2 ....
A3 A3,0 A3,1 A3,2 ....
. ............
. .....
Si faccia ora una lista di tutti gli elementi della matrice considerando tutte le diagonali
che vanno dal basso a sinistra in alto a destra, dalla piu' piccola in avanti, cioe'
A0,0, A1,0, A0,1, A2,0, A1,1,A0,2, A3,0, A2,1, A1,2, A0,3, A4,0, A3,1, ecc.ecc.
Per come l'abbiamo costruita, questa lista conterra' tutti e soli gli elementi di A*.