Para un cálculo de predicado de primer orden, que no posee ningún axioma apropiado el Teorema de la completitud de Gödel indica que los teoremas son exactamente las fórmulas bien formadas lógicamente válidas, así que la identificación de teoremas es recurrentemente enumerable, es decir que con recursos ilimitados eventualmente todo teorema válido pueden ser demostrado.