Почему теорему Гёделя о неполноте сложно доказать: дело в формулировках, а не только в сути

в 4:56, , рубрики: Занимательные задачки, математика, осторожность, парадокс Берри, парадокс Рассела, самореференция, теорема Гёделя

Грубо говоря, теорема Гёделя о неполноте утверждает, что существуют истинные математические утверждения, которые невозможно доказать. Когда я был в 11-м классе, мы втроём с учителем геометрии г-н Олсеном и моим другом Умой Рой провели пять недель, читая оригинальное доказательство Гёделя. Почему так долго? Отчасти потому, что мы были ещё школьниками. Отчасти потому, что 24-летний Гёдель был не самым талантливым писателем. Но главным образом потому, что доказательство на самом деле довольно трудное.

Это может показаться удивительным, ведь всё доказательство по сути можно уместить в один абзац. Гёдель начинает с построения математического утверждения, по существу эквивалентного предложению,

Это утверждение невозможно доказать.

Затем Гёдель рассматривает, что будет в случае, если это утверждение ложно. То есть если это утверждение можно доказать. Но любое утверждение, которое может быть доказано, должно быть истинным — здесь противоречие. Из этого Гёдель делает вывод, что утверждение должно быть истинным. Но, поскольку утверждение истинно, из этого следует, что утверждение не может быть доказано. Обратите внимание, что это заключительное утверждение не является противоречием. Наоборот, это и есть доказательство теоремы Гёделя.

Так почему же реальное доказательство настолько сложное? Хитрость в том, что то, что может звучать как действительное математическое утверждение на английском языке, часто таковым не является (особенно когда предложение ссылается само на себя). Рассмотрим, например, такое предложение:

Это предложение ложно.

Предложение бессмысленно: оно не может быть ложным (поскольку это сделало бы его истинным) и оно не может быть истинным (поскольку это сделало бы его ложным). И его, конечно, нельзя записать в виде формального математического утверждения.

Вот ещё один пример (известный как парадокс Берри):

Определите {x} как наименьшее натуральное число, которое нельзя описать менее чем 100 словами.

Это может выглядеть как допустимое математическое определение. Но опять же, оно не имеет смысла. И, что важно для здравомыслия математики, никакое аналогичное утверждение невозможно записать формально, то есть математически.

Даже утверждения на языке математики могут быть бессмысленными:

$S={A mid A notin A}$

(то есть $S$ — это множество множеств $A$, которые не являются элементами самих себя).

Это снова бессмысленное определение (известное как парадокс Рассела). В частности, как только мы определили $S$, мы можем задать вопрос, содержит ли $S$ себя? Если это так, то $S$ не может быть членом $S$ — противоречие; а если нет, то $S$ будет членом $S$ — опять противоречие.

Смысл этих трёх примеров в том, что если вы хотите доказать теоремы о математических утверждениях, то следует быть очень осторожным насчёт того, что вы реально оперируете математическими утверждениями. И действительно, от 46 определений в начале до удивительно плотных доказательств в конце оригинальная статья Гёделя — ни что иное, как массивное упражнение в осторожности.

Автор: m1rko

Источник

* - обязательные к заполнению поля