Función beta de Gödel

En lógica matemática, la función beta de Gödel es una función numérica que permite la definición de funciones recursivas dentro de una teoría formal aritmética.

Definición y propiedades

La definición de la función beta es la siguiente:

Dados tres números naturales $a$ , $b$ y $c$ , la función beta de Gödel viene dada por el resto de dividir $a$ entre $1 + (1 + c)\cdot b$ :

$\beta (a,b,c)={\text{resto}}(a,1+(1+c)b)$

o de manera equivalente, $β (a, b, c)$ es el menor natural $z$ que verifica:

$z\equiv a{\text{ mod}}(1+(1+c)b)$

La utilidad de esta función viene dada por el siguiente lema:

Dada una sucesión finita de números naturales $n 0$ , $n 1$ , $n 2$ , ..., $n k$ , existen $a$ y $b$ tales que, para cada $0 \leq i \leq k$ , se tiene

$\beta (a,b,i)=n_{i}$

Demostración
Sea $s$ un número mayor que todos los $n i$ y que $k$ . Los números $1 + s!$ , $1 + 2(s)!$ , ..., $1 + (k +1)\cdot(s)!$ son todos primos entre sí: si $p$ primo divide a $1 + i \cdot(s)!$ y $1 + j \cdot(s)!$ (con $1 \leq i < j \leq k + 1)$ entonces también divide a la diferencia $(j - i)\cdot(s)!$ , luego divide a uno de estos dos factores. Pero $j - i \leq k < s$ , luego $j - i$ divide a $s!$ y necesariamente $p$ divide a $s!$ , y por tanto a $i \cdot(s)!$ . Pero entonces $p$ divide a $(1 + i \cdot(s)!) - i \cdot(s)! = 1$ , y se obtiene una contradicción. Llamando $b = s!$ , los números $1 + (1 + i) b$ son primos entre sí $(0 \leq i \leq k)$ , luego por el teorema chino del resto, existe un $a$ tal que $n i \equiv a mod(1 + (1 + i) b)$ , para cada $0 \leq i \leq k$ . Como cada $n i < s$ , se tiene que $n i < (i + 1) b$ , y esto nos asegura que $n i = β (a, b, i)$ .

Aplicaciones

Mediante la función beta puede representarse cualquier función recursiva en una teoría aritmética formal. Como ejemplo, tómese el enunciado « $x$ es igual a $y$ elevado a $z$ », donde $x$ , $y$ y $z$ son variables de la teoría. En principio no es obvio como expresar esta frase utilizando solo el lenguaje de una teoría aritmética, que se compone de los símbolos lógicos más los símbolos aritméticos (los numerales « $n$ », el funtor siguiente « $S$ » , la suma «+» y el producto «·»).