Godel numbering the iterated Kleene closure of an alphabet

49 Views Asked by At

Suppose we have a finite alphabet $\{a_1,...,a_n\}$. We can Godel number the Kleene closure of the alphabet. However, I am interested in Godel numbering the iterated Kleene closure of the alphabet. The iterated Kleene closure is just taking the Kleene closure $\omega$ times. For example, if our alphabet is $\{a,b\}$, some elements of the Kleene closure are $a$, $b$, $(a,b,a)$, $((a,b),(a,a))$, $((),a,(b,a))$, etc. I want to assign a Godel number to each element of the iterated Kleene closure, such that different elements get different numbers. Basically, the Godel numbering has to be injective. What is the formal definition of it?