Принцесса или тигр   ::   Смаллиан Рэймонд

 Для любого числа n множество А9n должно совпадать с множеством n. В самом деле, множество А9n есть дополнение множества A3n, а множество А3n в свою очередь есть дополнение множества n; следовательно, множество А9n совпадает с Аn, Это означает, что множество A675 совпадает с множеством A75, и, стало быть, утверждение 675 Є А675 — это есть еще одно решение задачи. Аналогично утверждение 2175 Є A2175также является решением. Таким образом, мы получаем, что существует бесконечно много истинных утверждений, которые машина Фергюссона доказать не может: например, для любого n, которое равно произведению 75 на некоторое кратное числа 9 или произведению 73 на произвольное кратное числа 9, утверждение n Є А, является истинным, но недоказуемым посредством этой машины.



Доказуемость и истина



Крупной вехой в истории математической логики стал 1931 г. Именно в этом году Гёдель опубликовал знаменитую теорему о неполноте. Свою эпохальную работу[!«Uber formal unentscheidbare Satze der «Principia Mathematica» und verwandter Systeme'I» («О формально неразрешимых предложениях «Принципов математики» и других родственных систем»), Моnatshefte fur Mathematik und Physik, 38, 173–198.!] он начинает следующими словами:

«Развитие математики в направлении все большей точности привело к формализации целых ее областей, в связи с чем стало возможно проводить доказательства, пользуясь небольшим числом чисто механических правил.