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

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

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

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

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

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


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

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

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

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


  1. Sirion
    23.10.2018 08:39
    #19268793
    +2

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

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

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


    1. ni-co
      23.10.2018 09:48
      #19269137

      del


    1. knstqq
      23.10.2018 09:59
      #19269195

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


    1. UnknownUser
      23.10.2018 11:53
      #19269931

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


  1. andyudol
    23.10.2018 09:43
    #19269103

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


    1. Sirion
      23.10.2018 12:51
      #19270305

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


      1. Deosis
        23.10.2018 12:59
        #19270383

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


        1. Sirion
          23.10.2018 13:09
          #19270449

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


      1. andyudol
        23.10.2018 13:50
        #19270747

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


        1. Sirion
          23.10.2018 14:00
          #19270821

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

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

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


          1. andyudol
            23.10.2018 15:20
            #19271257

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

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

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

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


            1. Sirion
              23.10.2018 17:13
              #19271763
              +1

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


              1. andyudol
                24.10.2018 07:33
                #19273839

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

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


                1. Sirion
                  24.10.2018 07:50
                  #19273857

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


                  1. andyudol
                    24.10.2018 09:33
                    #19274133

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


                    1. Sirion
                      24.10.2018 10:00
                      #19274277

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


                      1. andyudol
                        24.10.2018 11:30
                        #19274699

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


                        1. Sirion
                          24.10.2018 11:41
                          #19274747

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


                          1. andyudol
                            24.10.2018 13:52
                            #19275447

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


                      1. Azoh
                        24.10.2018 12:22
                        #19274957

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

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


                        1. Sirion
                          24.10.2018 12:51
                          #19275099

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


                          1. ni-co
                            24.10.2018 12:59
                            #19275159

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


                          1. Azoh
                            24.10.2018 13:00
                            #19275171

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


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


                            1. Sirion
                              24.10.2018 13:20
                              #19275257

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


                              1. Azoh
                                24.10.2018 13:59
                                #19275487

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


                              1. phenik
                                25.10.2018 05:42
                                #19278343

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


            1. opetrenko
              23.10.2018 23:39
              #19273227

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

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


          1. ni-co
            23.10.2018 22:19
            #19272999

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


            1. Sirion
              24.10.2018 00:34
              #19273387

              На русском. А вы?


            1. andyudol
              24.10.2018 07:41
              #19273849

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


              1. ni-co
                24.10.2018 08:53
                #19274009

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


                1. Sirion
                  24.10.2018 09:01
                  #19274035

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


            1. Gutt
              26.10.2018 12:44
              #19285663

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


  1. panvartan
    23.10.2018 13:04
    #19270409

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