Aunque "Principia" no cayó presa de las paradojas de Frege, más tarde Kurt Gödel demostró que ni "Principia Mathematica", ni otro sistema consistente de aritmética recursiva primitiva podrían, dentro de ese sistema, determinar que cada proposición que pudiera ser formulada dentro de ese sistema era decidible, esto es, podría decidir si esa proposición o su negación era demostrable dentro del sistema (Teorema de la incompletitud de Gödel).