Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 2 down vote accepted

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.

share|cite|improve this answer
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
Yes, that is right. The class of primitive recursive functions is closed under composition (by definition), and so the composition of the translation function with the characteristic function of the language is primitive recursive, and the result is the characteristic function of the translated language. And the same for computable functions and sets, and with c.e., you use not the characteristic function, but the restriction of it to the positive values. – JDH Jul 3 '11 at 10:36
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
Your way is also fine. What I meant is that given a word in the new encoding, you first translate it into the old encoding, and then apply the characteristic function (restricted to affirmative values). This process will accept the word iff it is in the desired language. – JDH Jul 3 '11 at 11:34

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.