Принцесса или тигр - Смаллиан Р.М.
Скачать (прямая ссылка):
Заключение
Фергюссон вовсе не хотел отказываться от идеи создания такой машины, которая могла бы доказывать арифметические истины, не будучи в состоянии доказывать ложные заключения, поэтому он напридумывал целую кучу таких логических машин*. Однако для каждой новой машины либо он сам, либо Крейг с Мак-Каллохом все-таки находили такое истинное утверждение, которое машина доказать не могла. Поэтому в конце концов Фергюссон отказался от мысли сконструировать чисто механическое устройство, которое было бы одновременно и точным (в указанном выше смысле.— Перев.), и могло бы доказать любое истинное арифметическое утверждение.
Итак, все героические попытки Фергюссона не увенчались успехом, однако причина этого заключалась отнюдь не в недостатке авторской изобретательности. Мы не должны забывать о том, что он жил за несколько десятилетий до знаменитых открытий таких известных логиков, как Гёдель, Тарский, Клини, Тьюринг, Пост, Черч и другие ученые, о работах которых у нас вот-вот пойдет речь. Если бы Фергюссон дожил до этих открытий, то он понял бы, что неудачи его обусловлены исключительно тем, что он пытался создать нечто по сути своей совершенно невозможное! Поэтому, отдав должное Фергюссону и его коллегам
* Некоторые из них оказались весьма интересными, и о иих я надеюсь рассказать в своей следующей книге.
Крейгу и Мак-Каллоху, распрощаемся с ними и перенесемся на три-четыре десятилетия вперед, в переломный 1931 год.
Решения
1. Одно из решений состоит в следующем: утверждение 15Е.А-15 является истинным, но не может быть доказано машиной. И вот почему.
Допустим, что утверждение 75ЕА75 ложно. Тогда число 75 не принадлежит множеству Ац. Следовательно, это число должно принадлежать множеству А 25 (согласно свойству 2, множество А75 является дополнением множества А 25)- Это означает (согласно свойству 3), что число 75*75 принадлежит множеству Аз, поскольку 25=3x8+1, и, следовательно, машина может напечатать число 75 * 75. Иначе говоря, это означает, что утверждение 75?А75 может быть доказано машиной. Таким образом, если бы утверждение 75еА75 было ложным, то оно вполне могло бы быть доказано машиной. Однако нам известно по условию, что машина точна и никогда не доказывает ложные утверждения. Поэтому утверждение 75?А75 не может оказаться ложным, и, стало быть, оно должно быть истинным.
Далее, поскольку утверждение 75еА75 истинно, то число 75 действительно принадлежит множеству А 75. Поэтому оно не может принадлежать множеству А 25 (согласно свойству 2), и, следовательно, число 75 * 75 в свою очередь не может принадлежать множеству А в, поскольку если бы это было так, то тогда, согласно свойству 3, число 75 принадлежало бы множеству А25. Поскольку ясно, что число 75 * 75 не принадлежит множеству Аз, то утверждение 75 ? А 75 не может быть доказано машиной. Итак, утверждение 75ЕА75 является истинным, но оно недоказуемо с помощью машины.
2. Прежде чем рассматривать другие решения, установим следующий факт весьма общего свойства. Пусть для всего дальнейшего ключевым является множество К—это множество всех чисел х, для которых утверждение хЕА* недоказуемо машиной, или, что то же самое, множество таких чисел х, для которых число
173
х*х не может быть напечатано машиной. Далее, множество А 75 как раз и есть такое множество К, потому что утверждение, что х принадлежит множеству А75, равносильно утверждению, что х не принадлежит множеству А25, что в свою очередь равносильно утверждению, что число х*х не принадлежит множеству Ая, где А% — это множество тех чисел, которые машина может напечатать. Итак, А75=/С, Но при этом и А-п=К, потому что утверждение, что некое число х принадлежит множеству А73, равносильно утверждению, что число х*х принадлежит множеству А24 (согласно свойству 3, поскольку 73=3x24+1), что в свою очередь равносильно утверждению, что число х*х не принадлежит множеству Ав (согласно свойству 2). Таким образом, А 73— это множество всех тех чисел х, для которых число х*х не принадлежит множеству А8 или, что то же самое, множество всех чисел х, для которых утверждение хЕА* не может быть доказано машиной. Следовательно, А 73 — это то же самое множество чисел, что и А75, поскольку оба они тождественны множеству К. Более того, для любого заданного числа п, для которого А„=К, утверждение пЕАп должно быть истинным, но недоказуемым с помощью машины. Это можно показать буквально с помощью тех же самых рассуждений, что и в рассмотренном нами частном случае и =75 (в еще более общей форме эти рассуждения приведены в следующей главе). Тем самым мы получаем, что утверждение 7ЗЕА73 — это еще один пример истинного утверждения, кодовый номер которого машина напечатать не может.
3. Для любого числа п множество А».п должно совпадать с множеством Ап- В самом деле, множество Ад.„ есть дополнение множества А3.„, а множество Аз.п в свою очередь есть дополнение множества А„; следовательно, множество Ад.п совпадает с Ал. Это означает, что множество А675 совпадает с множеством А75, и, стало быть, утверждение 675Е Ав75—это есть еще одно решение задачи. Аналогично утверждение 2175ЕАг175 также является решением. Таким образом, мы получаем, что существует бесконечно много истинных утверждений, которые машина Фергюссона доказать не
