Il est l'auteur de deux théorèmes en logique, pour lesquels il définit deux notions fondamentales de la logique moderne, « l'incomplétude » et « l'indécidabilité ». Ses travaux ont modifié durablement les conceptions des mathématiciens (Sur les propositions indécidables des « Principia Mathematica »..., 1931).
