Альберт Эйнштейн награждает Гёделя (второй справа) наградой, названной в честь него самого
В 1931 году австрийский логик, математик и философ математики Курт Гёдель опубликовал свою теорему о неполноте. Эта работа считается одним из величайших интеллектуальных достижений современности.
В теореме утверждается, что в любой разумной математической системе всегда будут существовать истинные утверждения, которые невозможно доказать. Это утверждение шокировало математическую общественность, в которой до того преобладал неистребимый оптимизм, касающийся мощи и всеобъемлющей природы математики. Предполагалось, что математика «полна» — то есть, любое утверждение можно доказать или опровергнуть. 25-летний Гёдель показал, что это не так, составив корректное утверждение, доказать которое невозможно. Таким образом он продемонстрировал ограничения математики.
Теорема о неполноте преобразовала исследования основ математики и стала важным фактором развития информатики, поскольку из неё следует, что у возможностей всех формализованных систем, в том числе и языков программирования, есть свои ограничения.
Эта же теорема лежит и в основе сегодняшней загадки.
Гёдель доказал свою теорему через рекурсию – в формальной математической системе утверждение «Это предложение недоказуемо» будет истинным и формально недоказуемым.
Технические детали теоремы тяжело описать простыми словами. Но американский логик Рэймонд Смальян придумал отличный способ передать дух неполноты через логические загадки о людях, говорящих правду или лгущих. Сегодняшняя загадка вдохновлена его трудами.
Два племени острова Если
В океане Дедукции находится логический остров Если. Рождённые здесь люди принадлежат к одному из двух племён – алетейцам или псевдианцам. Единственный способ отличить их друг от друга – поговорить с ними. Алетейцы всегда говорят правду. Псевдианцы всегда лгут.
В центре острова глава алетейцев хранит Дневник идентичности; в этой книге перечислены имена всех рождённых на острове и их принадлежность к тому или иному племени. Ошибок в Дневнике нет, и его может посмотреть кто угодно.
Однажды на остров Если прибыл бесстрашный искатель приключений. Он встречался с обитателями острова и делил их на алетейцев и псевдианцев путём ловкой постановки вопросов.
После нескольких успешных встреч он познакомился с человеком по имени Курт. Исследователь ещё не знал его принадлежности, но прежде чем он успел задать вопрос, Курт опередил его утверждением: «У вас никогда не будет неопровержимых доказательств того, что я алетеец».
1. Принадлежит ли Курт к алетейцам, к псевдианцам, или ни к одному из племён?
2. Как эта задача связана с теоремой о неполноте?
Если бы он был псевдианцем, утверждение «у вас никогда не будет неопровержимых доказательств того, что я алетейец» было бы истинным. Но псевдианцы никогда не говорят правды, поэтому Курт не может быть псевдианцем.
Если бы он был алетейцем, тогда всё, что он говорит, включая и утверждение «у вас никогда не будет неопровержимых доказательств того, что я алетеец», было бы истинным. Но мы знаем, что это утверждение неверно, поскольку искатель приключений может пойти к Дневнику идентичности, найти там имя человека и проверить его принадлежность. Поэтому Курт не алетеец.
Следовательно, Курт не был рождён на острове Если.
2. Теорема Гёделя о неполноте постулирует, что существуют истинные, но формально недоказуемые математические утверждения. Наша задачка даёт что-то похожее – пример истинного утверждения, не имеющего чётких доказательств его истинности.
Допустим, наш исследователь стал первым человеком, ступившим на остров, и не родившимся там. Тогда все остальные люди там будут либо алетейцами, либо псевдианцами. Также допустим, что когда Курт делает своё заявление, кто-либо сжёг Дневник (для того, чтобы избежать противоречий, упомянутых в пункте 1).
Мы уже показали, что псевдианец не может сделать такого заявления, которое сделал Курт – поэтому Курт не псевдианец. Тогда, если все люди, кроме исследователя, родились на острове, то Курт должен быть алетейцем, однако у исследователя никогда не будет неопровержимых доказательств этого.
Но у него никогда не будет неопровержимых доказательств того, что заявление Курта истинно – в ином случае у него тут же появятся неопровержимые доказательства того, что он алетеец (поскольку только они говорят правду). Но тогда можно будет заключить, что это утверждение неверно.
Поэтому реплика Курта истинна, но неопровержимых доказательств её истинности не существует. Подобное предложение – прекрасный пример утверждения, ссылающегося само на себя, то есть такого утверждения, которое и формирует основу доказательства теоремы Гёделя. В формальной математической системе утверждение «Это предложение недоказуемо» будет истинным и формально недоказуемым.
То есть остров Если – это волшебное место, где все утверждения по поводу принадлежности людей к племенам можно проверить при помощи Дневника. Но если устранить дневник, можно будет быстро прийти к истинному предложению, не имеющему неопровержимых доказательств.
Мир математики похож на остров Если без Дневника. У математики нет прямого доступа к истине, из-за чего и появляются правдивые утверждения, не имеющие доказательства.
Комментарии (34)
salas
26.11.2022 04:25+5Очень заманчивая грамматическая неоднозначность в подписи к картинке. Но, к сожалению, нет, премию Гёделя учредили гораздо позже.
andyudol
26.11.2022 07:21+11…правдивые утверждения, не имеющие доказательства.
Какие у нас основания считать утверждение правдивым, если оно не имеет доказательства?
nin-jin
26.11.2022 08:55-1Потому что это элементарно доказывается используя более мощные логические системы, чем те, что рассматривал Гёдель. Фактически его теорема доказывает, что любая бинарная логика не полна. Подробнее тут:
inkelyad
26.11.2022 11:25+1Если я не ошибаюсь, любое утверждение про натуральные числа, для которого нет доказательства (т.е нет процедуры вывода его истинности) -- является истинным. Потому что для ложного существует контрпример числа, на котором оно становится ложным. А предъявление контрпримера - есть доказательство, которого, по предположению, не должно существовать.
AxelLx
28.11.2022 01:18С другой стороны, любое утверждение про натуральные числа, для которого имеется доказательство (т.е есть процедура вывода его истинности) — является истинным.
Следовательно, любое утверждение про натуральные числа является истинным.
vics001
27.11.2022 01:52К сожалению, с этими парадоксами все только становится запутанным. Классический пример, предположим мы не смогли найти доказательство теоремы Ферма, но в то же время, мы проверили очень много чисел. Теорема Ферма будет правдивой, если таких чисел никогда не найдется, но в то же время у нее может не быть доказательства.
В Аксиоматике есть инструмент - это аксиомы из которых выводятся утверждения, например о целых числах, в то же время числа можно использовать как модель и на них проверять "правдивость". Тут конечно, же влазит правило исключенного 3-го и разные штуки, что если мы доказали существование, но не можем найти такие числа, то по сути мы не доказали еще и т.д.Но суть такова, что не важно сколько аксиом мы будем добавлять, всегда будут теоремы Правдивые, но не Доказуемые.
Uris
26.11.2022 09:02Все это тогда можно распространить и на программирование. Каков бы не был программист профи, всё одно он накосячит... Или так. В любом коде есть ошибки.
garwall
26.11.2022 11:43+1Для программирования из подобного больше подходит теорема Райса. Так что каким-бы крутым и ai не становился copilot, будет нужен человек.
Kealon
26.11.2022 15:30+2Мне одному кажется, что теорема Гёделя несколько проще, чем эти два острова?
dxq3
26.11.2022 17:48+1Задача-то глубже. Человек из задачи может быть псевдианцем, хотя бы потому, что не является Куртом - он начал обман с этапа знакомства)
Vsevo10d
26.11.2022 23:11Ну вы еще на рассказчика все свалите ;)
andyudol
27.11.2022 09:06Всё ещё интереснее, потому что эта задача на самом деле не математическая.
Кто делает записи в Книге? Кто такой Курт и что он делает на острове? Не он ли делает эти записи? И действительно ли там два племени, а не одно? А записи Курт делает по каким-то своим правилам, например, за взятку? Но без ошибок. И не в сговоре ли автор задачи с этим Куртом?
victor_1212
26.11.2022 18:33+6Ув. Вячеслав, Вам как автору переводов вероятно не все равно, что именно переводить, в данном случае Вы сделали перевод автора детских книжек - Alex Bellos, его самая популярная книга "Futebol: The Brazilian Way of Life", про жизнь Pelé, Ronaldo и пр.
Конечно от Alex Bellos не стоило ожидать понимания теоремы Геделя, но Вы насколько знаю окончили физтех, и должны знать что теорем Геделя о полноте две, и относятся они к аксиоматическому определению арифметики, или формальной системе включающей арифметику, первая теорема говорит что в такой системе всегда можно написать утверждение никак не вытекающее из аксиом, а вторая теорема о неполноте говорит что для такой системы само утверждение о непротиворечивости ее аксиоматики также невыводимо из аксиом.
Результат важный и интересный, но остальное типа "утверждение шокировало математическую общественность, в которой до того преобладал неистребимый оптимизм, касающийся мощи и всеобъемлющей природы математики" - больше подходит для детских книжек, на которых собственно Alex Bellos зарабатывает себе на жизнь, как он сам выражается: "I write and I talk. Usually about mathematics, puzzles, football or Brazil".
phenik
27.11.2022 06:29Обосновать математику чисто логически невозможно, что и показал Гедель, но и любые другие подходы без привлечения логики не обходятся, и поэтому всегда будут сомнительными. Что автор и выразил фразой
Мир математики похож на остров Если без Дневника. У математики нет прямого доступа к истине, из-за чего и появляются правдивые утверждения, не имеющие доказательства.
Любые формы познания страдают этим в той или иной степени, включая эмпирический. Впрочем, если не согласны с этим найдите решение задачи без привлечения книги)
Pi-man
26.11.2022 19:22+1Не очень понял часть 2. статьи.
Если убрать из задачи вариант что Курт может не быть ни алетейцем, ни псевдианцем, то разве доказанный факт того, что он не псевдианец не дает неопровержимого доказательства, что он алетеец?
me21
26.11.2022 19:34+1Да. Мы, видимо, получаем противоречие, и описанной ситуации произойти не могло.
leshabirukov
27.11.2022 16:27Ну, "бесстрашный искатель приключений" не обязательно прочтёт Дневник. Молния там ударит, или бесстрашность вдруг улетучится. Так что, Курт может быть алетейцем.
karabas_b
27.11.2022 05:14Он не может быть алетейцем, потому что алетейцы не врут.
mSnus
27.11.2022 10:18Всей правды мы не узнаем.
victor_1212
27.11.2022 15:59+2это точно + к теоремам Геделя о полноте данная логическая головоломка отношения не имеет, хотя бы потому что теоремы Геделя применимы к аксиоматике арифметики (или ее расширений), а здесь просто хитрости или двусмысленности в описании детской задачи, арифметика с ее аксиомами осталась за бортом, Гёдель здесь ни при чём
Yukr
28.11.2022 01:18На мой дилетантский взгляд, в таких задачах часто встречается подвох, в виде изменения "граничных условий":
на острове кто-то сжигает Дневник.... а где сказано, что его можно сжечь? а если он высечен на скале??
известная задача о проведении непрерывной ломаной через 9 точек (3 ряда, 3 столбика) - имеет решение только при выходе звеньев ломаной за "пределы границ" точек, т.е. как бы создаётся новая точка
-
да даже случай фрекен Бок: " Вы перестали пить коньяк по утрам?" ))) подразумевает, что пила...
Выдержит ли теория Гёделя проверку с жёстко задаными граничными (начальными) условиями ?
iig
28.11.2022 10:19даже случай фрекен Бок: " Вы перестали пить коньяк по утрам?" ))) подразумевает, что пила
Нет. Ответ "да" - значит что пила, но перестала. Ответ "нет" не значит ничего (не пила и не пьёт, пила и продолжает, не пила но начала пить - этот ответ может значить что угодно). Это неоднозначность живого человеческого языка.
Допустим мы спросили у Буратино: "У тебя в кармане 5 сольдо?". Ответ "да" - значит у него в кармане ровно 5 сольдо, не 0, не 4, и не 666.
Допустим мы спросили у Буратино: "У тебя в кармане есть 5 сольдо?". Ответ "да" может значить что угодно - и 5, и 55, и 555.
Yukr
28.11.2022 20:58Но мы же обсуждаем метематическую логику. Есть высказывание А=" ф.Бок перестала пить ". Тогда отрицание, НЕ (А)= " ф.Бок НЕ ПЕРЕСТАЛА пить". А неоднозначность = расширение первоначально не оговореных / не корректно оговоренных условий.
У Буратино тогда нужно спрашивать "есть ли у тебя в кармане сумма ровно в 5 сольдо"
iig
29.11.2022 00:15Фрекен Бок может быть в 4 состояниях: пила но перестала, пила и продолжает пить, не пила и не пьёт, не пила но начала пить. Инверсия сюда не натягивается. Так же как и на Буратино с его 5 сольдо. Если А == "у Буратино есть 5 сольдо", то НЕ (А) может означать что угодно.
Неправильное использование математики не делает математику неправильной.
Tsvetik
Здорово.
Уже забыл курс философии, но что там было про то, что, Бэкон, что ли работал над методами познания и сформулировал понятия о фальсифицируемости гипотез и правила вывода одних истинных утверждений из других. Могу путать, давно было.
Так вот получается, что некоторые истины недостижимы с помощью таких методов.
Кто-то может тут увидеть идею веры и недоказуемость существования Бога.
DirectoriX
Теорема Гёделя говорит, грубо говоря, что существуют недоказуемые (здесь и далее «доказеумый» = «можно доказать что истина или ложь») утверждения в рамках заданной системы аксиом. Если вы расширите список аксиом — ранее недоказуемое утверждение может стать доказуемым (но появятся новые).
Archius11
Либо, если нет недоказуемых утверждений, значит есть противоречие. Т.е. доказательство, что утверждение и истинно, и ложно.