Принцесса или тигр - Смаллиан Р.М.
Скачать (прямая ссылка):
4. Найдите утверждение, которое было бы ложным, но неопровержимым.
5. Имеются такие два утверждения X и У, что одно из них (правда, нам не известно, какое именно) должно быть либо истинным, но недоказуемым, либо ложным, но неопровержимым (мы не знаем, каким именно). Такие пары можно строить двумя способами, и соответственно я предлагаю вашему вниманию две задачи:
а. Найдите такие высказывания X и У, чтобы X утверждало доказуемость У, а У утверждало опровер-жимость X. Далее, покажите, что одно из них (мы не можем сказать, какое именно) либо истинно, но недоказуемо, либо ложно, но неопровержимо.
б. Найдите такие высказывания X и У, чтобы X утверждало недоказуемость У, а У утверждало неопровержимость X. Далее покажите, что одно из этих высказываний, X или У (мы не можем сказать, какое именно), либо истинно, но недоказуемо, либо ложно, но неопровержимо.
6. А теперь рассмотрим задачу с четырьмя неизвестными! Пусть нам требуется найти такие высказывания X, У, Z и W, чтобы X утверждало доказуемость У, У утверждало опровержимость Z, Z утверждало опровер-жимость W, a W утверждало бы неопровержимость X. Покажите, что одно из этих четырех высказываний должно быть либо истинным, но недоказуемым, либо ложным, но неопровержимым (хотя, какое из этих четырех будет именно таким высказыванием, сказать невозможно).
192
Машина Мак-Каллоха и теорема Гёделя
Возможно, читатель уже отметил определенное сходство приведенных выше задач с некоторыми свойствами первой машины Мак-Каллоха. В самом деле, работа этой машины оказывается связанной с теоремой Гёделя, и вот каким образом.
7. Пусть у нас имеется некоторая математическая система, приводящая к набору утверждений, одни из которых называются истинными, а другие — доказуемыми. Мы предполагаем также, что эта система правильная, то есть каждое доказуемое в ней утверждение является истинным. Далее, пусть каждому числу N ставится в соответствие некоторое утверждение, которое мы будем называть утверждением N. Предположим наконец, что наша система удовлетворяет следующим двум условиям.
Условие Мсь Для любых чисел X и У, если число X порождает число У в первой машине МакКаллоха, утверждение 8Х истинно тогда и только тогда, если утверждение У доказуемо. (Напомним, что число 8Х это не 8, умноженное на X, а цифра 8, за которой стоит число X.)
Условие Мс2- Для любого числа X утверждение 9Х истинно тогда и только тогда, если утверждение X не является истинным.
Найдите такое число М, при котором утверждение N истинно, но недоказуемо в данной системе.
8. Предположим, ЧТО В УСЛОВИИ Мс 1 говорится не о «первой машине Мак-Каллоха», а о «третьей машине Мак-Каллоха». Попробуем теперь найти такое утверждение, которое было бы истинным, но недоказуемым.
9. Парадокс ли это? Вернемся вновь к задаче 1, однако внесем в нее некоторые изменения. Вместо символа Р мы будем использовать символ В (в силу определенных психологических причин — каких именно, станет ясно из дальнейшего). Определение «утверждения» остается тем же, что и раньше, только на этот раз символ Р везде заменяется на символ В. Таким образом, наши
193
утверждения принимают теперь вид: В—X, NB—X, В А—X, NBA—X. Все утверждения, как и прежде, делятся на две группы — истинные и ложные, причем нам не известно, какие именно из утверждений истинны, а какие — ложны. Далее, вместо машины, печатающей различные утверждения, у нас теперь имеется ученый-логик, который верит одним утверждениям и не верит другим. Когда мы говорим, что наш логик не верит какому-то утверждению, мы вовсе не имеем в виду, что он обязательно сомневается в нем или отвергает его; просто неверно, что он верит в это утверждение. Другими словами, он либо считает его ложным, либо вообще не имеет о нем никакого мнения. Таким образом, символ В (от англ. believe — верить) означает «то, во что верит логик». Тогда для любого выражения X у нас есть четыре интерпретации выражений, содержащих X:
В].* утверждение В—X истинно тогда и только тогда, когда логик верит в X;
В2: утверждение NB—X истинно тогда и только тогда, когда логик не верит в X;
Вз: утверждение В А — X истинно тогда и только тогда, когда логик верит в X—X;
В 4: утверждение BA—X истинно тогда и только тогда, когда логик не верит в X—X.
Предполагая, что наш логик точен, то есть что он не верит в ложные утверждения, мы можем, разумеется, найти некое утверждение, которое является истинным, но о котором логик не знает, что оно истинно. Таким утверждением будет высказывание NBA—NBA (которое говорит нам о том, что логик не верит в ассоциат выражения NBA, имеющий вид NBA—NBA).
А дальше начинается нечто интересное. Предположим, нам известно об этом ученом-логике следующее. Обстоятельство 1. Наш ученый-логик знает логику не хуже нас с вами. Предположим, что он обладает абсолютными логическими способностями; это означает, что если ему заданы какие-нибудь логические посылки, то он может вывести из них все возможные суждения.
Обстоятельство 2. Логику известно, что выполняются условия Bj, В2, Вз и В4.
194
Обстоят ельство 3. Логик всегда точен, то есть он не верит в ложные утверждения.
