L'importance de la récursivité dans la preuve du théorème d'« improuvabilité » de Gödel réside (Proposition V) dans le fait que chaque relation récursive affirmée entre des nombres x₁, x₂, … x_n peut s'exprimer par une formule f du système formel P qui peut être « prouvée » à l'intérieur de P si l'affirmation est vraie et peut être infirmée (« dé-prouvée ») à l'intérieur de P (autrement dit, la négation de f, écrite comme Neg f, est « prouvable » à l'intérieur de P) si l'affirmation est fausse »
(Braithwaite 1992 [1962] : 13). « L'exigence que f soit « récursif » implique que, si f n'est pas un « théorème » de P, Neg f l'est » (ibid. 30).