¿Cuándo un lenguaje contable es un lenguaje no recursivo?

Question

Estos días estoy estudiando el teorema de Gödel. En mis apuntes, como preliminares tengo la siguiente definición:

Dejemos que $L$ una lengua. A aritmética recursiva de $L$ es un mapeo uno a uno $\pi: L\longrightarrow\mathbb{N}$ de tal manera que las siguientes son recursivas:

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

Decimos que $L$ es recursivo si existe una aritmética recursiva de $L$ .

Obviamente, cualquier lenguaje incontable no es recursivo, mi pregunta es cuándo un lenguaje contable no es recursivo. En particular:

Si tengo un idioma $L$ con infinitos símbolos que satisfacen las condiciones de los conjuntos anteriores (infinitos símbolos constantes e infinitos $n$ -función primaria y símbolos de relación para cualquier $n\in\mathbb{N}$ ) Puedo pedir estos símbolos (digamos $\{c_m \ :\ m\in\mathbb{N}\}$ es el conjunto de todos los símbolos constantes y $\{f_m^n\ :\ m\in\mathbb{N}\},\ \{r_m^n \ :\ m\in\mathbb{N}\}$ son los conjuntos de todos los $n$ -arios de funciones y relaciones).

Entonces puedo considerar la función $\pi: L\longrightarrow \mathbb{N}$ dado por $\pi({c_m})=2^2\cdot 3^m$ , $\pi(f_m^n)=2^2\cdot 3^n\cdot 5^m+1$ y $\pi(r_m^n)=2^2\cdot 3^n\cdot 5^m+2$ que creo que es una aritmética recursiva.

Si este es el caso y no me equivoco, entonces puedo tomar cualquier idioma numerable, $\hat{L}$ y lo extiendo a un lenguaje infinito como el anterior y, una vez que tengo una aritmética recursiva para el lenguaje extendido, tengo una aritmética recursiva para $\hat{L}$ que no es más que la restricción de la otra.

Entonces, si mi suposición es correcta, ¿cuál es el matiz que añade esta definición? ¿Cuál es la diferencia entre un lenguaje contable y uno recursivo?

Answer 1

Creo que el problema es la condición 4. Dejemos que $S$ sea un conjunto no recursivo de números naturales. Consideremos un lenguaje $L$ que tiene un único $n$ Símbolo de la relación -aria $R_n$ para todos $n\in S$ y ningún otro símbolo. Si tiene una asignación de este tipo $\pi$ entonces el conjunto de pares en la condición 4 es $\{(\pi(R_n),n):n\in S\}$ . Pero este conjunto no es recursivo ya que su proyección a la segunda coordenada es $S$ .