# 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.

-
At the informal, or semi-formal level, the result is, to use an overused word, obvious. Take any algorithm that enumerates the code numbers of the words under one encoding. A tiny post-processor can turn these code numbers into code numbers under the other encoding. – André Nicolas Jul 2 '11 at 19:20

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.
Did I understood the following correctly: When you said "each of these classes [of sets, I assume] is closed under composition with a primitive recursive function", did you mean: If $M\subseteq \mathbb{N}$ is a, lets say, c.e. set - because being c.e. is the most general property of the three - and $f:\mathbb{N} \rightarrow \mathbb{N}$ a primitive recursive function, then $f(M)$ is a c.e. set as well? Sorry, if I'm so squeamish, but since I'm just at the beginning, I'm always a little bit uncomfortable with these "high-level" argumentations and need to see the "low-level" mathematical details. – temo Jul 3 '11 at 9:44
I got it now. Thank you very much. But in c.e. case, I proved it in slightly different way, because I couldn't figure out how to use the restriction of the characteristic function to the positive values. My idea was: $M$ is c.e. iff then there is a computable function $g$, such that $g(\mathbb{N})=M$. Thus $f(g(\mathbb{N}))=f(M)$. Since $f \circ g$ is computable, $f(M)$ is c.e.. But how should one use the restriction of the characteristic function of $M$ to the positive values to do the proof in the c.e. case? – temo Jul 3 '11 at 11:25