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

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

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

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

Вот ещё один пример (известный как парадокс Берри):
Определите {x} как наименьшее натуральное число, которое нельзя описать менее чем 100 словами.
Это может выглядеть как допустимое математическое определение. Но опять же, оно не имеет смысла. И, что важно для здравомыслия математики, никакое аналогичное утверждение невозможно записать формально, то есть математически.

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

$S = \{A \mid A \not\in A\}$


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

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

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

Подробнее
Реклама

Комментарии 35

    +12
    Что я только что прочитал? Содержание статьи не соответствует заголовку. В ней содержится три достаточно банальных математических парадокса, которые имеют весьма косвенное отношение к заявленной теме. Я бы сказал, что она содержит отрицательное количество информации по теме, потому что после её прочтения у читателя может сложиться ложное ощущение, что теперь он что-то знает о сабже, хотя на самом деле он не узнал о нём ничего.

    При этом поиск без труда находит гораздо более годную статью на ту же тему.
    https://habr.com/post/400513/

    В общем, низачот.
      0
      del
        +1
        Первое — это не парадок, а формулировка теоремы Гёделя «неформально».
          0
          Да, увидел статью с утра, даже отложил чтение на попозже, чтобы в спокойствии, так сказать, после обеда приобщиться.
          В итоге, не совсем понял, что это было?
            0
            фарм кармы.
            Знаете, как в онлайн-играх фармят голду, вот на хабре такими «переводами» ниачом фармят карму.

            Ведь «нельзя же минусануть человека», он старался (на самом деле нет), переводил (на самом деле нет).
          0
          С тех пор, как я узнал о теореме Гёделя, меня терзают смутные сомнения.
          Для того, чтобы что-то доказать, надо иметь правила доказательства. Тогда возможность доказать любое высказывание означает возможность подобрать такие правила, которые позволят свести множество всех высказываний к пустому множеству.
          Что я понял не так?
            +1
            К конечному множеству аксиом же.
              0

              Гёдель доказал, что к конечному множеству свести не получится.

                +1
                Да неужто? И как же я, математик по образованию, в комментариях к статье про эту теорему, приведя ссылку на другую статью про эту теорему, этот факт упустил? Стыд мне и позор.
                0
                Аксиомы — тоже высказывания. Если можно было бы доказать любые, то и аксиомы можно было бы тоже.
                  +3
                  Любую аксиому можно доказать, сопоставив её с этой же самой аксиомой)
                  Возможно, я неверно понял ваше исходное сообщение. Согласитесь, что «свести множество всех высказываний к пустому множеству» — не очень строгая формулировка. Давайте я вам сформулирую, а вы уже разбирайтесь, так вы поняли или нет.

                  У нас есть некоторое начальное множество утверждений, которые мы называем аксиомами. У нас есть правила вывода, по которым мы из утверждений получаем другие утверждения. Утверждение называется выводимым, если его можно получить последовательным применением правил вывода к аксиомам. Аксиомы по определению выводимы, поскольку любую аксиому можно получить из неё же самой, применив к ней правила вывода нуль раз =)

                  Первая теорема Гёделя о неполноте утверждает, что в любой достаточно сложной (с) теории существует такое утверждение, что ни оно само, ни его отрицание не является выводимым. Впрочем, если бы вам действительно было интересно, вы бы давно всё это нагуглили.
                    –1
                    Впрочем, если бы вам действительно было интересно, вы бы давно всё это нагуглили.

                    Что я нагуглил, а что нет — это не имеет никакого значения.
                    Дело в том, что я не математик и вот это
                    Аксиомы по определению выводимы, поскольку любую аксиому можно получить из неё же самой, применив к ней правила вывода нуль раз

                    я не способен (видимо генетически) понять ни при каких обстоятельствах. Это типа я положил рубль в карман, а потом раз в секунду вынимаю его и говорю: «О! Ещё рубль заработал!».

                    На самом деле в реальной жизни аксиомы являются не начальным множеством утверждений, а конечным.
                      +1
                      Мне не очень понятно, что такое «аксиомы в реальной жизни»)
                        0
                        Я же сказал, я не математик. Для меня реальная жизнь — это жизнь, в которой нет вот этого:
                        Аксиомы по определению выводимы, поскольку любую аксиому можно получить из неё же самой, применив к ней правила вывода нуль раз
                          0
                          Ну а что такое тогда для вас аксиомы? Где вы их встречаете в реальной жизни? В магазине? В троллейбусе? Под кроватью? Вы напираете на то, что не математик, однако зачем-то пользуетесь сугубо математическим понятием. Откажитесь от него вообще, всем станет легче.
                            0
                            Аксиома не является сугубо математическим понятием.
                              0
                              О, вот это интересно. Приведите мне пример не математической аксиомы.
                                0
                                Ну что же вы, батенька!:
                                1. Душа бессмертна.
                                2. Нет власти аще не от Бога.

                                n. Ну и «далее везде».
                                  0
                                  Тогда два вопроса.
                                  1. Почему те, кто считает, что душа бессмертна, так считают?
                                  2. Почему те, кто считает, что верен закон исключённого третьего, так считают?
                                    0
                                    Откуда я знаю?
                                    Что вообще означает это «считают»? Оно одинаковое в обоих случаях? Кто те, которые «считают»? Например, студент, сформулировавший на экзамене закон исключённого третьего, он точно что-то считает? Или просто тупо повторил из учебника?
                                    Наверное, в общем случае, чисто формально, на оба вопроса можно ответить — исторически так сложилось.
                                  0
                                  Приведите мне пример не математической аксиомы.

                                  Вот это как раз легко. Пример: максимальная скорость постоянна, не зависит от выбора ИСО и равняется скорости света в вакууме.

                                    0
                                    Теоретическая физика — это прикладная математика же. Но формально подловили)
                                      0
                                      «Теоретическая физика — это прикладная математика же.» Очень спорное утверждение. В моем понимании — ложное.
                                        0

                                        Хорошо, вот вам "типа материализм" в аксиоматической форме:


                                        1. Реальна только материя.
                                        2. Сознание является физиологическим процессом, протекающим в материальном носителе.
                                        3. Идеи являются субъективными формами восприятия, создаваемыми сознанием.
                                          0
                                          Ну окей, ладно. Погорячился, был неправ. Аксиоматическую теорию можно построить в любой области знания.
                                            0

                                            Но, к сожалению, при понижении "точности" предмета исследований, польза от подобного формализма тоже быстро падает. Если в случае физики аксиоматический метод позволяет делать конструктивные выводы, имеющие важную предсказательную функцию, в случае философии польза уже сильно сомнительна.

                                              0
                                              Можно так выкрутится) Любое описание, включая любые аксиомы, только модель реальности. А модели по определению не полны, не тождественны реальности. В этом смысле абсолютного знания нет вообще. Ну может кроме «Я существую»)
                              0
                              И причина идет после следствия в реальной жизни:
                              — Вовочка, почему опоздал?
                              — проспал…
                              — А почему проспал?
                              — Поздно лег…
                              и т.д.

                              может ли в реальной жизни фундамент здания быть «конечным множеством»? Конечно, если рассуждать в стиле:
                              — Где чердак?
                              — Над 9м этажом.
                              — А 9й этаж где?
                              — над 8м.

                              0
                              «Любую аксиому(!) можно доказать(!), сопоставив(!) её с этой же самой аксиомой)...»
                              Это вы на каком языке сейчас говорите? :)
                                0
                                На русском. А вы?
                                  0
                                  — Что это, Бэримор?
                                  — Математика, сэр!
                                    0
                                    Не бросайте в меня камни, но я сейчас наблюдаю диалог в котором математик с не математиком разговаривает на русском, а не математик пытается говорить с ним на языке математики. Статья, кстати много об этом. Еще раз извиняюсь если не поняли.
                                      0
                                      А кто здесь пытается говорить на языке математики? Покажите пальцем, будьте любезны.
                                    0
                                    Я бы сказал так: любое высказывание в рамках теории, повторяющее одну из аксиом этой теории, можно доказать, сопоставив его с этой же аксиомой. В этом смысле аксиома, которую мы рассматриваем как утверждение в рамках теории, ничем не хуже и не лучше других утверждений. Просто случай вырожденный.
                            0
                            Наша вселенная непротиворечива, а наше мышление противоречиво. Результат события «это утверждение невозможно доказать» оказывает влияние на причину этого же события, делая его истинным. Во вселенной такой номер не проходит, время не позволяет провернуть такой фокус. Событие можно сделать истинным, но это будет уже другое событие. Но человек создал свою вселенную, где это возможно. ТГН показывает какую цену за это приходится платить.

                            Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                            Самое читаемое