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


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

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

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

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

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

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

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


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

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

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

Вы можете помочь и перевести немного средств на развитие сайта



Комментарии (34):

  1. Sirion
    /#19268793 / +2

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

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

    В общем, низачот.

    • knstqq
      /#19269195

      Первое — это не парадок, а формулировка теоремы Гёделя «неформально».

    • UnknownUser
      /#19269931

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

  2. andyudol
    /#19269103

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

    • Sirion
      /#19270305

      К конечному множеству аксиом же.

      • Deosis
        /#19270383

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

        • Sirion
          /#19270449

          Да неужто? И как же я, математик по образованию, в комментариях к статье про эту теорему, приведя ссылку на другую статью про эту теорему, этот факт упустил? Стыд мне и позор.

      • andyudol
        /#19270747

        Аксиомы — тоже высказывания. Если можно было бы доказать любые, то и аксиомы можно было бы тоже.

        • Sirion
          /#19270821

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

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

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

          • andyudol
            /#19271257

            Впрочем, если бы вам действительно было интересно, вы бы давно всё это нагуглили.

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

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

            На самом деле в реальной жизни аксиомы являются не начальным множеством утверждений, а конечным.

            • Sirion
              /#19271763 / +1

              Мне не очень понятно, что такое «аксиомы в реальной жизни»)

              • andyudol
                /#19273839

                Я же сказал, я не математик. Для меня реальная жизнь — это жизнь, в которой нет вот этого:

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

                • Sirion
                  /#19273857

                  Ну а что такое тогда для вас аксиомы? Где вы их встречаете в реальной жизни? В магазине? В троллейбусе? Под кроватью? Вы напираете на то, что не математик, однако зачем-то пользуетесь сугубо математическим понятием. Откажитесь от него вообще, всем станет легче.

                  • andyudol
                    /#19274133

                    Аксиома не является сугубо математическим понятием.

                    • Sirion
                      /#19274277

                      О, вот это интересно. Приведите мне пример не математической аксиомы.

                      • andyudol
                        /#19274699

                        Ну что же вы, батенька!:
                        1. Душа бессмертна.
                        2. Нет власти аще не от Бога.

                        n. Ну и «далее везде».

                        • Sirion
                          /#19274747

                          Тогда два вопроса.
                          1. Почему те, кто считает, что душа бессмертна, так считают?
                          2. Почему те, кто считает, что верен закон исключённого третьего, так считают?

                          • andyudol
                            /#19275447

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

                      • Azoh
                        /#19274957

                        Приведите мне пример не математической аксиомы.

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

                        • Sirion
                          /#19275099

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

                          • ni-co
                            /#19275159

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

                          • Azoh
                            /#19275171

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


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

                            • Sirion
                              /#19275257

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

                              • Azoh
                                /#19275487

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

                              • phenik
                                /#19278343

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

            • opetrenko
              /#19273227

              И причина идет после следствия в реальной жизни:
              — Вовочка, почему опоздал?
              — проспал…
              — А почему проспал?
              — Поздно лег…
              и т.д.

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

          • ni-co
            /#19272999

            «Любую аксиому(!) можно доказать(!), сопоставив(!) её с этой же самой аксиомой)...»
            Это вы на каком языке сейчас говорите? :)

            • andyudol
              /#19273849

              — Что это, Бэримор?
              — Математика, сэр!

              • ni-co
                /#19274009

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

                • Sirion
                  /#19274035

                  А кто здесь пытается говорить на языке математики? Покажите пальцем, будьте любезны.

            • Gutt
              /#19285663

              Я бы сказал так: любое высказывание в рамках теории, повторяющее одну из аксиом этой теории, можно доказать, сопоставив его с этой же аксиомой. В этом смысле аксиома, которую мы рассматриваем как утверждение в рамках теории, ничем не хуже и не лучше других утверждений. Просто случай вырожденный.

  3. panvartan
    /#19270409

    Наша вселенная непротиворечива, а наше мышление противоречиво. Результат события «это утверждение невозможно доказать» оказывает влияние на причину этого же события, делая его истинным. Во вселенной такой номер не проходит, время не позволяет провернуть такой фокус. Событие можно сделать истинным, но это будет уже другое событие. Но человек создал свою вселенную, где это возможно. ТГН показывает какую цену за это приходится платить.