Принцесса или тигр - Смаллиан Р.М.
Скачать (прямая ссылка):
— Сначала я хотел бы выяснить вот что,— сказал Мак-Каллох.—Допустим на некоторое время, что любое утверждение, доказуемое с помощью вашей машины, на самом деле является истинным. Значит ли это, что любое истинное утверждение вида х?А у доказуемо с ее помощью? Иначе говоря, способна ли ваша машина доказывать все истинные утверждения типа X ? А у или только некоторые из них?
— Это очень важный вопрос,— ответил Фергюссон,—но, увы, ответа на него я не знаю. В этом-то как раз и состоит главная проблема, которую я никак не могу разрешить! Уже не один месяц я пытаюсь найти ответ на этот вопрос, но пока безуспешно. Так, я совершенно точно знаю, что моя машина может доказать любое утверждение вида которое является
логическим следствием заложенных в нее аксиом, однако я не знаю, достаточное ли количество аксиом введено мною в машину. Аксиомы, о которых идет речь, представляют собой нечто вроде общей суммы сведений, известных математикам относительно систе-
мы положительных целых чисел; и все же, может быть, их недостаточно, чтобы строго установить, какие же числа х и к каким поддающимся описанию множествам А у принадлежат. ДЬ сих пор любое утверждение вида хЕ.Ау, которое я считал истинным, исходя из чисто математических соображений, оказывалось логическим следствием заложенных в машину аксиом; при этом машина способна доказать любое взятое мною утверждение такого вида. Однако то, что я не сумел найти истинного утверждения, которое машина не могла бы доказать, вовсе не означает, что такого утверждения не существует— может быть, я его просто еще не обнаружил. В то же время вполне может оказаться, что машина действительно способна доказать все истинные утверждения—но этого я тоже еще не сумел доказать. Пока я просто не знаю, как это сделать!
Короче говоря, после этого Фергюссон подробно объяснил Крейгу и Мак-Каллоху, какие аксиомы заложены в машину и какие чисто логические правила позволяют доказывать новые утверждения на основании уже имеющихся. Все эти подробности вполне убедили Крейга и Мак-Каллоха в том, что машина на самом деле точна—что она действительно доказывает лишь истинные утверждения. Однако вопрос о том, может ли машина доказать все истинные утверждения или только некоторые из них, так и остался нерешенным. На протяжении нескольких последующих месяцев они часто собирались вместе для детального обсуждения возникших вопросов—пока, наконец, задача не была полностью решена.
Я не стану утомлять читателя и приводить все подробности полученного ими решения; упомяну лишь о том, что действительна представляется для нас важным. Переломный момент в их исследованиях наступил тогда, когда друзья в конце концов сумели сформулировать три ключевые особенности машины; этого оказалось достаточно для полного решения задачи. Кажется, первыми обратили внимание на эти особенности Крейг и Мак-Каллох, однако их окончательная формулировка принадлежит Фергюссону. Но
прежде чем переити к описанию особенностей машины, я позволю себе сделать небольшое отступление.
Для любого множества А положительных целых чисел, под его дополнением А понимается множество положительных целых чисел, не входящих в А. Например, если А—множество четных чисел, то его дополнением А будет множество нечетных чисел; если А— множество чисел, делящихся на 5, то А — это множество чисел, которые на 5 не делятся.
Для любого множества А положительных целых чисел под А* мы будем подразумевать множество всех положительных целых чисел х, для которых является элементом множества А. Поэтому для любого числа х выражение «число х принадлежит множеству А*» эквивалентно выражению «число х*х принадлежит множеству А».
А теперь перечислим три главные особенности данной машины, которые были обнаружены Крейгом и Мак-Каллохом.
Свойство 1. Множество А8—это множество всех чисел, которые машина может напечатать.
Свойство 2. Для любого положительного целого числа п множество Аз-и является дополнением множества А„. (При этом под символом Ъ'П мы понимаем 3, умноженное на п.)
Свойство 3. Для любого положительного целого числа п множество А3.„ + 1 представляет собой множество А? (то есть множество всех чисел х, для которых число лг*х принадлежит множеству А„).
1. С помощью свойств 1—3 можно, оказывается, строго показать, что машина Фергюссона не способна доказать все истинные утверждения. Читателю предлагается найти такое утверждение, которое является истинным, но при этом не может быть доказано с помощью этой машины. Иначе говоря, мы должны найти такие числа пит (они могут быть как одинаковыми, так и разными), для которых кодовый номер утверждения пЕАт—то есть число п*т—не мог бы быть напечатан машиной, но чтобы при этом число п являлось бы элементом множества А т.
171
2. В решении задачи 1, которое приведено ниже, числа пит оба меньше 100. Имеется и другое решение этой задачи, для которого числа пит также оказываются меньше 100 (при этом они опять могут быть как одинаковыми, так и разными). Сумеет ли читатель найти это решение?
3. Если не ограничивать сверху величину чисел пит, то сколько всего решений может быть у такой задачи? Иначе, сколько существует истинных утверждений, которые недоказуемы с помощью машины Фергюссона?
