Гильберт был убежден, что всю математику можно построить из набора постулатов, или аксиом. С его точки зрения, тщательно и систематически применяя правила логики, любой математический факт во Вселенной можно вывести из не более чем полудюжины аксиом. Исключений быть не должно. Проверка любого математического факта от 2 + 2 = 4 до последней теоремы Ферма должна была иметь логическое доказательство. Именно программа Гильберта являлась движущей силой математики, когда на нее обратил внимание Гёдель.
Погруженный в жизнь Вены, спокойно посещающий собрания «Венского кружка» и наблюдающий за бесконечными обсуждениями способов распространить программу Гильберта на всю природу, которые вели логики и математики, Гёдель медленно и неуклонно подбирался к собственной фундаментальной гипотезе. И в какой-то момент одним махом полностью разрушил планы Гильберта, сформулировав теорему о неполноте.
Эта теорема утверждала крайне простые вещи. Любое Математическое описание системы начинается с набора аксиом и правил. Гёдель показал, что при любом наборе первоначальных постулатов всегда останутся аспекты, которые невозможно вывести: недоказуемые неопровержимые формулы. Обнаруженную формулу можно добавить в существующий набор аксиом. Но теорема Гёделя показала наличие бесконечного количества таких недоказуемых неопровержимых формул. По мере того как вы находите все новые истины, которые невозможно доказать, и добавляете их к своим аксиомам, ваша простая и элегантная дедуктивная система раздувается до гигантских размеров, оставаясь тем не менее неполной.
Теорема Гёделя парализовала программу Гильберта и выбила из седла многих его коллег. Сам Гильберт сначала с раздражением отказался признавать результат Гёделя, но в конечном итоге он его принял и безуспешно попытался встроить в свою программу. Другие философы опубликовали ничем не обоснованную критику, от которой Гёдель дистанцировался. Английский философ Бертран Рассел так никогда и не смог нормально воспринять результаты Гёделя. Доминировавший в философских течениях первой половины XX века Людвиг Витгенштейн просто отверг теорему о неполноте как неуместную. Но Гёдель верил, что она таковой не была.
Хотя Гёдель любил Вену, в конечном счете его начало привлекать место, которое Эйнштейн называл «замечательным местечком и… церемонным поселком маленьких полубогов на ходулях». После ряда визитов в 1930-х он стал комфортно чувствовать себя в Институте перспективных исследований, водя дружбу с Эйнштейном, вступая в дискуссии с фон Нейманом и постепенно осознавая, насколько высок интеллектуальный уровень эмигрантов, нашедших приют в Принстоне. Неприятный инцидент в Вене, когда Гёделя избили, приняв за еврея, вынудил его к переезду.