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)·b: o de manera equivalente, β(a,b,c) es el menor natural z que verifica: La utilidad de esta función viene dada por el siguiente lema: Dada una sucesión finita de números naturales n0, n1, n2, ..., nk, existen a y b tales que, para cada 0 ≤ i ≤ k, se tiene si p primo divide a 1 + i·(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.
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 ni ≡ a mod(1 + (1 + i)b), para cada 0 ≤ i ≤ k. Como cada ni < s, se tiene que ni < (i + 1)b, y esto nos asegura que ni = β(a,b,i).
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 «·»).
Sin embargo, usando la función beta, este predicado puede expresarse de forma sencilla como: