Алиса в стране смекалки - Смаллиан Р.М.
Скачать (прямая ссылка):
Чтобы решить задачу, прежде всего необходимо доказать аналог условия G.
Условие G. Для любого учтенного множества А найдется высказывание, истинное в том и только в том случае, если его номер принадлежит А.
Ше:Шу4 _Ьиблиотека_КОЛХОЗ/ко1хо3^5с05/М_МАТНЕМ/МРОР_РОР/16.511Ст1Мт (13о? 19)19.01.2004 16:56:35
"Как же называется эта книга?" - 16
Чтобы доказать условие G, выберем любое учтенное множество А. Пусть В - множество, заданное условием Н, п -номер страницы, на котором записано В в "Книге множеств". По условию Н если число п принадлежит В, то у него имеется сопряженное число ^ принадлежащее множеству А, а если п не принадлежит В то у него есть сопряженное число ^ не принадлежащее А. Мы утверждаем, что высказывание X на h-й странице и есть то самое высказывание, которое требуется найти.
Высказывание X утверждает, что п - экстраординарное число, то есть что п принадлежит множеству В (так как множество В занесено на п-ю страницу "Книги множеств"). Если X истинно, то число п действительно принадлежит множеству В. Следовательно, h принадлежит А. Итак, если X истинно, то его номер (число ^ принадлежит множеству А.
Предположим теперь, что X ложно. Тогда число п не принадлежит В. Следовательно, сопряженное число h не принадлежит А. Итак, X истинно в том и только в том случае, если его номер принадлежит множеству А.
После того как условие G доказано, ответить на вопросы логика уже не трудно. Дано, что множество номеров А всех доказуемых высказываний - учтенное множество. Следовательно, по условию С множество А всех чисел, не совпадающих с номерами доказуемых высказываний, также учтенное множество. Значит (по условию G), существует высказывание X, которое истинно в том и только в том случае, если его номер принадлежит множеству А. Но если номер высказывания X принадлежит множеству А, то он не принадлежит множеству А, то есть высказывание X недоказуемо (так как множество А состоит из номеров доказуемых высказываний). Итак, X истинно в том и только в том случае, если X недоказуемо. Это означает, что либо X истинно и недоказуемо, либо X ложно и доказуемо. По условиям задачи ни одно ложное высказывание недоказуемо в системе. Следовательно, X должно быть истинным и недоказуемым в системе.
Построим теперь ложное высказывание, которое неопровержимо в системе. Пусть А - множество всех
Ше:Шу4 _Ьиблиотека_КОЛХОЗШхо3^5с05/М_МАТНЕМ/МРОР_РОР/16.511Ш1Мт (14оБ 19)19.01.2004 16:56:35
"Какже называется эта книга?" -16
опровержимых высказываний. Воспользовавшись условием G, мы получим высказывание Y, истинное в том и только в том случае, если его номер совпадает с номером какого-нибудь опровержимого высказывания, то есть Y истинно в том и только в том случае, если Y опровержимо. Это означает, что Y либо истинно и опровержимо, либо ложно и неопровержимо. Первая альтернатива отпадает, так как опровержимое высказывание не может быть истинным. Следовательно, У должно быть ложным, но неопровержимым в системе.
Перейдем теперь к остальным вопросам логики. Если бы множество номеров всех ложных высказываний было учтенным множеством, то существовало бы высказывание Z, которое было бы истинным в том и только в том случае, если бы его номер совпадал с номером какого-нибудь ложного высказывания. Иначе говоря, Z было бы истинным в том и только в том случае, если Z ложно, что невозможно. (Е напоминало бы высказывание "это высказывание ложно".) Следовательно, множество номеров всех ложных высказываний - неучтенное множество. Из условия С следует, что множество номеров истинных высказываний также не является учтенным множеством.
270. Теорема Гёделя.
Предыдущая задача представляет собой не что иное, как упрощенный вариант знаменитой теоремы Гёделя о полноте.
В 1931 г. Курт Гёдель совершил поразительное открытие. Он установил, что математическую истину в некотором смысле нельзя формализовать полностью. Гёдель доказал, что в математической системе, принадлежащей широкому классу систем, всегда найдется утверждение, недоказуемое (то есть невыводимое из аксиом системы), несмотря на свою истинность! Следовательно, ни одной аксиоматической системы, сколь бы остроумно она ни была устроена, не достаточно для доказательства всех математических истин. Гёдель впервые доказал свою теорему для системы "Рг1пс1р1а Ма^ета^са" Уайтхеда и Расселла, но предложенное им доказательство, как я уже говорил, допускает перенос и на многие другие системы. Во всех этих системах существует вполне определенное множество выражений, называемых
Ше:Шу4 _Ьиблиотека_КОЛХОЗ/ко1хо3^5с05/М_МАТНЕМ/МРОР_РОР/16.511Ш1Мт (15оБ 19)19.01.2004 16:56:35
"Какже называется эта книга?" -16
предложениями, которые подразделяются на истинные и ложные. Некоторые истинные предложения приняты за аксиомы системы. Точный перечень правил вывода позволяет доказывать (выводить из аксиом) одни предложения и опровергать другие. Помимо предложений система содержит имена различных множеств (целых и положительных) чисел. Любое множества чисел, наделенное в рассматриваемой системе именем, можно назвать именуемым, или определимым, множеством системы (в предыдущей задаче такие множества скрывались под псевдонимом "учтенные множества"). Весьма существенно, что все предложения можно перенумеровать, а все определимые множества перечислить по порядку. Это означает, что математическая система удовлетворяет условиям Е1, Е2, С и Н нашей задачи. (Номер, присваиваемый каждому предложению, - в задаче мы называли его просто номером - в математической логике известен подназванием гёделевого номера предложения.) Доказать, что система удовлетворяет условиям С и Н, очень просто.
