Language over a finite alphabet is "stable" with resprect to primitive recursiveness ( & etc.) under different enumerations 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.
 A: Your question is basically answered by the comment of user6312. The point is that the translation function---translating the encoding of a word in one enumeration to its encoding in another enumeration---is a primitive recursive permutation (and note also that the inverse function is also primitive recursive). Thus, by applying this function or its inverse as appropriate, we see that the original language is primitive recursive,  computable, or c.e., respectively, if and only if the variant lanaguage is in this class, since each of these classes is closed under composition with a primitive recursive function.
Meanwhile, allow me to point out that the result is not true when the alphabet is infinite. For example, imagine an alphabet with symbols $a_n$ for $n\in\mathbb{N}$, and a language $L$ consisting of the one-letter words $a_{2n}$, using the even letters only. This language is primitive recursive, and trivial in a variety of ways. By permuting the alphabet, however, we could realize any language consisting of an infinite co-infinite set of the one-letter words. Since there are continuum many of these, most of them are neither  primitive recursive, computable nor even c.e., violating the corresponding property for infinite alphabets.
But if you insist on primitive recursive re-enumerations of the alphabet, then the result becomes true again. Perhaps one way to think about it is that every permutation of a finite set is primitive recursive, and so the finite alphabet case is a special case of the more general fact.
