Với đóng góp này của von Neumann, hệ thống các tiên đề của lý thuyết tập hợp trở thành đủ hoàn chỉnh, và câu hỏi kế tiếp là liệu là nó đã xác định hay chưa, mà không cần phải cải tiến. Một câu trả lời phủ định khá mạnh đưa ra vào tháng 9 năm 1930 tại Hội nghị toán học lịch sử tại Konigsberg, mà trong đó Kurt Gödel công bố "định lý đầu tiên về sự không toàn vẹn" nổi tiếng của ông: các hệ thống tiên đề thông thường là không hoàn toàn, theo ý nghĩa là chúng không thể chứng minh được tất cả những sự thật có thể diễn tả được trong ngôn ngữ của hệ thống đó. Kết quả này đủ mới để làm bối rối các nhà toán học của thời gian đó. Nhưng von Neumann, tham dự trong hội nghị đó, đã khẳng định tiếng tăm của ông như một người suy nghĩ ra vấn đề ngay tức khắc, và dưới một tháng sau đã có khả năng liên lạc với chính Gödel một hệ quả thú vị của định lý của ông: những hệ thống tiên đề thông thường là không có khả năng diễn tả sự nhất quán của chính chúng. Chính xác là hệ quả này đã thu hút được nhiều sự chú ý nhất, ngay cả nếu như nguyên thủy Gödel chỉ xem nó như là một điều tò mò, và có thể suy ra nó một cách độc lập (chính vì lý do này mà kết quả được gọi là "định lý Gödel thứ hai", mà không nhắc đến tên của von Neumann).