TITLE: When is a countable language a non-recursive Language?
QUESTION [1 upvotes]: I'm studying Gödel's theorem this days. In my notes, as preliminarities I have the following definition:
Let $L$ a language. A recursive arithmetization of $L$ is a one-to-one mapping $\pi: L\longrightarrow\mathbb{N}$ such that the following are recursive:

$\{\pi(c)\ :\ c\in L\text{ is a constant }\}$
$\{\pi(f)\ :\ f\in L\text{ is a function symbol}\}$
$\{\pi(R)\ :\ R\in L\text{ is a relation symbol}\}$
$\{\langle\pi(s), n\rangle \ :\ s\in L\text{ is an $n$-ary function symbol or relation symbol}\}$

We say that $L$ is recursive if there is a recursive arithmetization of $L$.
Obviously, any uncountable language is not recursive, my question is when is a countable language not recursive. In particular:
If I have a language $L$ with infinite symbols satisfying the conditions of the sets above (infinite constant symbols and infinite $n$-ary function an relation symbols for any $n\in\mathbb{N}$) I can order this symbols (say $\{c_m \ :\  m\in\mathbb{N}\}$ is the set of all constant symbols and $\{f_m^n\ :\ m\in\mathbb{N}\},\ \{r_m^n \ :\ m\in\mathbb{N}\}$ are the sets of all $n$-ary function and relation symbols).
Then I can consider the function $\pi: L\longrightarrow \mathbb{N}$ given by $\pi({c_m})=2^2\cdot 3^m$, $\pi(f_m^n)=2^2\cdot 3^n\cdot 5^m+1$ and $\pi(r_m^n)=2^2\cdot 3^n\cdot 5^m+2$ which I think it is a recursive arithmetization.
If this is the case and I'm no wrong, then I can take any numerable language, $\hat{L}$, and extend it to an infinite language like the one above and, once I have a recursive arithmetization to the extended language, I have a recursive arithmetization for $\hat{L}$ which is just the restriction of the other one.
So, if my guessing is correct, What is the nuance added by this definition? What is the difference between a countable language and a recursive one?

REPLY [2 votes]: I believe the problem is condition 4. Let $S$ be a non-recursive set of natural numbers. Consider a language $L$ which has a single $n$-ary relation symbol $R_n$ for all $n\in S$, and no other symbols. If you have such a mapping $\pi$, then the set of pairs in condition 4 is $\{(\pi(R_n),n):n\in S\}$. But this set is not recursive since its projection to the second coordinate is $S$.
{"set_name": "stack_exchange", "score": 1, "question_id": 3822639}