Занимательная задачка по мотивам теоремы Гёделя о неполноте
Альберт Эйнштейн награждает Гёделя (второй справа) наградой, названной в честь него самого
В 1931 году австрийский логик, математик и философ математики Курт Гёдель опубликовал свою теорему о неполноте. Эта работа считается одним из величайших интеллектуальных достижений современности.
В теореме утверждается, что в любой разумной математической системе всегда будут существовать истинные утверждения, которые невозможно доказать. Это утверждение шокировало математическую общественность, в которой до того преобладал неистребимый оптимизм, касающийся мощи и всеобъемлющей природы математики. Предполагалось, что математика «полна» — то есть, любое утверждение можно доказать или опровергнуть. 25-летний Гёдель показал, что это не так, составив корректное утверждение, доказать которое невозможно. Таким образом он продемонстрировал ограничения математики.
Теорема о неполноте преобразовала исследования основ математики и стала важным фактором развития информатики, поскольку из неё следует, что у возможностей всех формализованных систем, в том числе и языков программирования, есть свои ограничения.
Эта же теорема лежит и в основе сегодняшней загадки.
Гёдель доказал свою теорему через рекурсию – в формальной математической системе утверждение «Это предложение недоказуемо» будет истинным и формально недоказуемым.
Технические детали теоремы тяжело описать простыми словами. Но американский логик Рэймонд Смальян придумал отличный способ передать дух неполноты через логические загадки о людях, говорящих правду или лгущих. Сегодняшняя загадка вдохновлена его трудами.
Два племени острова Если
В океане Дедукции находится логический остров Если. Рождённые здесь люди принадлежат к одному из двух племён – алетейцам или псевдианцам. Единственный способ отличить их друг от друга – поговорить с ними. Алетейцы всегда говорят правду. Псевдианцы всегда лгут.
В центре острова глава алетейцев хранит Дневник идентичности; в этой книге перечислены имена всех рождённых на острове и их принадлежность к тому или иному племени. Ошибок в Дневнике нет, и его может посмотреть кто угодно.
Однажды на остров Если прибыл бесстрашный искатель приключений. Он встречался с обитателями острова и делил их на алетейцев и псевдианцев путём ловкой постановки вопросов.
После нескольких успешных встреч он познакомился с человеком по имени Курт. Исследователь ещё не знал его принадлежности, но прежде чем он успел задать вопрос, Курт опередил его утверждением: «У вас никогда не будет неопровержимых доказательств того, что я алетеец».
1. Принадлежит ли Курт к алетейцам, к псевдианцам, или ни к одному из племён?
2. Как эта задача связана с теоремой о неполноте?
В теореме утверждается, что в любой разумной математической системе всегда будут существовать истинные утверждения, которые невозможно доказать. Это утверждение шокировало математическую общественность, в которой до того преобладал неистребимый оптимизм, касающийся мощи и всеобъемлющей природы математики. Предполагалось, что математика «полна» — то есть, любое утверждение можно доказать или опровергнуть. 25-летний Гёдель показал, что это не так, составив корректное утверждение, доказать которое невозможно. Таким образом он продемонстрировал ограничения математики.
Теорема о неполноте преобразовала исследования основ математики и стала важным фактором развития информатики, поскольку из неё следует, что у возможностей всех формализованных систем, в том числе и языков программирования, есть свои ограничения.
Эта же теорема лежит и в основе сегодняшней загадки.
Гёдель доказал свою теорему через рекурсию – в формальной математической системе утверждение «Это предложение недоказуемо» будет истинным и формально недоказуемым.
Технические детали теоремы тяжело описать простыми словами. Но американский логик Рэймонд Смальян придумал отличный способ передать дух неполноты через логические загадки о людях, говорящих правду или лгущих. Сегодняшняя загадка вдохновлена его трудами.
Два племени острова Если
В океане Дедукции находится логический остров Если. Рождённые здесь люди принадлежат к одному из двух племён – алетейцам или псевдианцам. Единственный способ отличить их друг от друга – поговорить с ними. Алетейцы всегда говорят правду. Псевдианцы всегда лгут.
В центре острова глава алетейцев хранит Дневник идентичности; в этой книге перечислены имена всех рождённых на острове и их принадлежность к тому или иному племени. Ошибок в Дневнике нет, и его может посмотреть кто угодно.
Однажды на остров Если прибыл бесстрашный искатель приключений. Он встречался с обитателями острова и делил их на алетейцев и псевдианцев путём ловкой постановки вопросов.
После нескольких успешных встреч он познакомился с человеком по имени Курт. Исследователь ещё не знал его принадлежности, но прежде чем он успел задать вопрос, Курт опередил его утверждением: «У вас никогда не будет неопровержимых доказательств того, что я алетеец».
1. Принадлежит ли Курт к алетейцам, к псевдианцам, или ни к одному из племён?
2. Как эта задача связана с теоремой о неполноте?
1. Не принадлежит ни к одному из племён.
Если бы он был псевдианцем, утверждение «у вас никогда не будет неопровержимых доказательств того, что я алетейец» было бы истинным. Но псевдианцы никогда не говорят правды, поэтому Курт не может быть псевдианцем.
Если бы он был алетейцем, тогда всё, что он говорит, включая и утверждение «у вас никогда не будет неопровержимых доказательств того, что я алетеец», было бы истинным. Но мы знаем, что это утверждение неверно, поскольку искатель приключений может пойти к Дневнику идентичности, найти там имя человека и проверить его принадлежность. Поэтому Курт не алетеец.
Следовательно, Курт не был рождён на острове Если.
2. Теорема Гёделя о неполноте постулирует, что существуют истинные, но формально недоказуемые математические утверждения. Наша задачка даёт что-то похожее – пример истинного утверждения, не имеющего чётких доказательств его истинности.
Допустим, наш исследователь стал первым человеком, ступившим на остров, и не родившимся там. Тогда все остальные люди там будут либо алетейцами, либо псевдианцами. Также допустим, что когда Курт делает своё заявление, кто-либо сжёг Дневник (для того, чтобы избежать противоречий, упомянутых в пункте 1).
Мы уже показали, что псевдианец не может сделать такого заявления, которое сделал Курт – поэтому Курт не псевдианец. Тогда, если все люди, кроме исследователя, родились на острове, то Курт должен быть алетейцем, однако у исследователя никогда не будет неопровержимых доказательств этого.
Но у него никогда не будет неопровержимых доказательств того, что заявление Курта истинно – в ином случае у него тут же появятся неопровержимые доказательства того, что он алетеец (поскольку только они говорят правду). Но тогда можно будет заключить, что это утверждение неверно.
Поэтому реплика Курта истинна, но неопровержимых доказательств её истинности не существует. Подобное предложение – прекрасный пример утверждения, ссылающегося само на себя, то есть такого утверждения, которое и формирует основу доказательства теоремы Гёделя. В формальной математической системе утверждение «Это предложение недоказуемо» будет истинным и формально недоказуемым.
То есть остров Если – это волшебное место, где все утверждения по поводу принадлежности людей к племенам можно проверить при помощи Дневника. Но если устранить дневник, можно будет быстро прийти к истинному предложению, не имеющему неопровержимых доказательств.
Мир математики похож на остров Если без Дневника. У математики нет прямого доступа к истине, из-за чего и появляются правдивые утверждения, не имеющие доказательства.
Если бы он был псевдианцем, утверждение «у вас никогда не будет неопровержимых доказательств того, что я алетейец» было бы истинным. Но псевдианцы никогда не говорят правды, поэтому Курт не может быть псевдианцем.
Если бы он был алетейцем, тогда всё, что он говорит, включая и утверждение «у вас никогда не будет неопровержимых доказательств того, что я алетеец», было бы истинным. Но мы знаем, что это утверждение неверно, поскольку искатель приключений может пойти к Дневнику идентичности, найти там имя человека и проверить его принадлежность. Поэтому Курт не алетеец.
Следовательно, Курт не был рождён на острове Если.
2. Теорема Гёделя о неполноте постулирует, что существуют истинные, но формально недоказуемые математические утверждения. Наша задачка даёт что-то похожее – пример истинного утверждения, не имеющего чётких доказательств его истинности.
Допустим, наш исследователь стал первым человеком, ступившим на остров, и не родившимся там. Тогда все остальные люди там будут либо алетейцами, либо псевдианцами. Также допустим, что когда Курт делает своё заявление, кто-либо сжёг Дневник (для того, чтобы избежать противоречий, упомянутых в пункте 1).
Мы уже показали, что псевдианец не может сделать такого заявления, которое сделал Курт – поэтому Курт не псевдианец. Тогда, если все люди, кроме исследователя, родились на острове, то Курт должен быть алетейцем, однако у исследователя никогда не будет неопровержимых доказательств этого.
Но у него никогда не будет неопровержимых доказательств того, что заявление Курта истинно – в ином случае у него тут же появятся неопровержимые доказательства того, что он алетеец (поскольку только они говорят правду). Но тогда можно будет заключить, что это утверждение неверно.
Поэтому реплика Курта истинна, но неопровержимых доказательств её истинности не существует. Подобное предложение – прекрасный пример утверждения, ссылающегося само на себя, то есть такого утверждения, которое и формирует основу доказательства теоремы Гёделя. В формальной математической системе утверждение «Это предложение недоказуемо» будет истинным и формально недоказуемым.
То есть остров Если – это волшебное место, где все утверждения по поводу принадлежности людей к племенам можно проверить при помощи Дневника. Но если устранить дневник, можно будет быстро прийти к истинному предложению, не имеющему неопровержимых доказательств.
Мир математики похож на остров Если без Дневника. У математики нет прямого доступа к истине, из-за чего и появляются правдивые утверждения, не имеющие доказательства.