Función beta de Gödel

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)·b:

${\displaystyle \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:

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

Dada una sucesión finita de números naturales n₀, n₁, n₂, ..., n_k, existen a y b tales que, para cada 0 ≤ i ≤ k, se tiene

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

si p primo divide a 1 + i·(s)! y 1 + j·(s)! (con 1 ≤ i < j ≤ k + 1) entonces también divide a la diferencia (j − i)·(s)!, luego divide a uno de estos dos factores. Pero j − i ≤ k < s, luego j − i divide a s! y necesariamente p divide a s!, y por tanto a i·(s)!. Pero entonces p divide a (1 + i·(s)!) − i·(s)! = 1, y se obtiene una contradicción.

Llamando b = s!, los números 1 + (1 + i)b son primos entre sí (0 ≤ i ≤ k), luego por el teorema chino del resto, existe un a tal que n_i ≡ a mod(1 + (1 + i)b), para cada 0 ≤ i ≤ k. Como cada n_i < s, se tiene que n_i < (i + 1)b, y esto nos asegura que n_i = β(a,b,i).

${\displaystyle y^{z}\equiv w|\exists ab,\,\beta (a,b,0)=1\ \wedge \ \forall q<z\,\beta (a,b,q+1)=y\cdot \beta (a,b,q)\ \wedge \ w=\beta (a,b,z)}$