I'm trying to prove the following proposition: The fact that a language $L$ over a finite alphabet $A$ is primitive recursive, recursive or recursively enumerable does not depend upon the enumeration of the alphabet.
My first questions are:
1) Did I understand this right: If my language is recursively enumerable under the bijection $\alpha: A \rightarrow \left\{1,2,\ldots, |A| \right\}$ (meaning the set $\alpha^\star (L)$ is recursively enumerable, where $\alpha^\star$ is the extension of $\alpha$ to the set $A^\star = \cup_{k \in \mathbb{N}} A^k$, assigning every tupel of elements from $A$ the corresponding numbers by the function $\alpha$ and the using a coding function to code the tupel into a single natural number ) then for every other bijection every $\beta: A \rightarrow \left\{1,2,\ldots, |A| \right\}$, $\beta^\star (L)$ has to be recursively enumerable as well ? I wonder, couldn't it happen, because $A$ is finite, that if $\alpha^\star (L)$ is recursively enumerable, that it is also , for example, primitive recursive ? (If not, is there a counterexample ?)
2) How can I prove this ? Because any coding isn't by definition recursive because its domain is $\mathbb{N}^\star = \cup_{k \in \mathbb{N}} \mathbb{N}^k$, but I think I have to use that somehow.