Definamos ahora la función g(n) del siguiente modo: \( g(n) = c\'od(\overline{n}) \). es decir, la función g le asigna a cada número n el código de su numeral (el código de su "nombre"). (Recordemos que \( \overline{n} \) se define como \( SS\ldots S0 \) donde la S aparece n + 1 veces.)
Queremos probar que g es expresable. Es decir, que la relación binaria "y = g(x)" es expresable.
Para hacerlo usaremos una variante del Principio Generador. La diferencia es que antes trabajamos con sucesiones de expresiones aritméticas y ahora trabajaremos con sucesiones de pares ordenados de expresiones aritméticas.
En el lenguaje formal al par ordenado de expresiones aritméticas \( (E_i,F_i) \) lo indicaremos como \( E_i\otimes{}\otimes{}F_i \). La sucesión de pares:
\( (E_1,F_1),(E_2,F_2),\ldots ,(E_k,F_k) \)
la escribiremos como:
\( \otimes{}E_1\otimes{}\otimes{}F_1\otimes{}E_2\otimes{}\otimes{}F_2\otimes{}\ldots \otimes{}E_k\otimes{}\otimes{}F_k\otimes{} \)
De manera similar a como lo hicimos para las sucesiones de expresiones aritméticas, se puede probar que:
1. "Ser un par ordenado de expresiones aritméticas" es expresable.
2. "Ser una sucesión de pares ordenados de expresiones aritméticas" es expresable.
3. La relación "El par ordenado de expresiones aritméticas (E,F) aparece en la sucesión H" es expresable.
4. La relación "Los pares ordenados de expresiones aritméticas (E,F) y (E',F') aparecen consecutivamente, en ese orden, en la sucesión H" es expresable.
Diremos que una sucesión de pares ordenados de expresiones aritméticas corresponde a la función g si se cumple que:
1. El primer par de la sucesión es (0,8). (Traducido, claro está, al lenguaje formal, es decir, la sucesión comienza con \( \otimes{}0\otimes{}\otimes{}SSSSSSSS0\otimes{} \). La elección del 8 se debe a que 8 = g(0).)
2. Si (x,y) aparece en la sucesión entonces (x,y) y (Sx,z) son consecutivos en la sucesión, donde z se obtiene de concatenar el código de S con y.
Es fácil ver que "Ser una sucesión de pares ordenados de expresiones aritméticas que corresponde a la función g" es expresable.
Por otra parte, una sucesión que corresponde a g es siempre de este tipo: (0,g(0)), (1,g(1)), (2,g(2)),..., (k,g(k)). Por lo tanto:
"y = g(x)" si y sólo si existe una sucesión que corresponde a g en la que aparece el par (x,y). Como todas estas condiciones son expresables, entonces g es expresable.
Nota: Podemos generalizar el razonamiento que hicimos para g y probar que si f es una función tal que el valor de f(0) es conocido y el procedimiento para calcular f(n + 1) a partir de f(n) es expresable, entonces f es expresable.