11.01.2017 14:28
vgivanov 122 30400 Источник


Теореме Гёделя о неполноте, одной из самых известных теорем математической логики, повезло и не повезло одновременно. В этом она похожа на специальную теорию относительности Эйнштейна. С одной стороны, почти все о них что-то слышали. С другой — в народной интерпретации теория Эйнштейна, как известно, «говорит, что всё в мире относительно». А теорема Гёделя о неполноте (далее просто ТГН), в примерно столь же вольной фолк-формулировке, «доказывает, что есть вещи, непостижимые для человеческого разума». И вот одни пытаются приспособить её в качестве аргумента против материализма, а другие, напротив, доказывают с её помощью, что бога нет. Забавно не только то, что обе стороны не могут оказаться правыми одновременно, но и то, что ни те, ни другие не удосуживаются разобраться, что же, собственно, эта теорема утверждает.

Итак, что же? Ниже я попытаюсь «на пальцах» рассказать об этом. Изложение моё будет, разумеется нестрогим и интуитивным, но я попрошу математиков не судить меня строго. Возможно, что для нематематиков (к которым, вообще-то, отношусь и я), в рассказанном ниже будет что-то новое и полезное.

Математическая логика — наука действительно довольно сложная, а главное — не очень привычная. Она требует аккуратных и строгих манёвров, при которых важно не перепутать реально доказанное с тем, что «и так понятно». Тем не менее, я надеюсь, что для понимания следующего ниже «наброска доказательства ТГН» читателю понадобится только знание школьной математики/информатики, навыки логического мышления и 15-20 минут времени.

Несколько упрощая, ТГН утверждает, что в достаточно сложных языках существуют недоказуемые высказывания. Но в этой фразе почти каждое слово нуждается в пояснении.

Начнём с того, что попытаемся разобраться, что такое доказательство. Возьмём какую-нибудь школьную задачку по арифметике. Например, пусть требуется доказать верность следующей незамысловатой формулы: «$\forall x \; (x-1)(x-2)-2=x(x-3)$» (напомню, что символ $\forall$ читается «для любого» и называется «квантор всеобщности»). Доказать её можно, тождественно преобразуя, скажем, так:

  1. $\forall x \; (x-1)(x-2)-2=x(x-3)$
  2. $\forall x \; x^2-3x+2-2=x^2-3x$
  3. $\forall x \; x^2-3x–x^2+3x=0$
  4. $\forall x \; 0 = 0$
  5. ИСТИНА

Переход от одной формулы к другой происходит по некоторым известным правилам. Переход от 4-й формулы к 5-й произошёл, скажем, потому, что всякое число равно самому себе — такова аксиома арифметики. А вся процедура доказывания, таким образом, переводит формулу в булево значение ИСТИНА. Результатом могла быть и ЛОЖЬ — если бы мы опровергали какую-то формулу. В таком случае мы бы доказали её отрицание. Можно себе представить программу (и такие программы действительно написаны), которые бы доказывали подобные (и более сложные) высказывания без участия человека.

Изложим то же самое чуть более формально. Пусть у нас есть множество, состоящее из строк символов какого-то алфавита, и существуют правила, по которым из этих строк можно выделить подмножество $S$ так называемых высказываний — то есть грамматически осмысленных фраз, каждая из которых истинна или ложна. Можно сказать, что существует функция $P$, сопоставляющая высказываниям из $S$ одно из двух значений: ИСТИНА или ЛОЖЬ (то есть отображающая их в булево множество $B$ из двух элементов).

Назовём такую пару — множество высказываний $S$ и функция $P$ из $>S$ в $B$ — «языком высказываний». Заметим, что в повседневном смысле понятие языка несколько шире. Например, фраза русского языка «А ну иди сюда!» не истинна и не ложна, то есть высказыванием, с точки зрения математической логики, не является.

Для дальнейшего нам понадобится понятие алгоритма. Приводить здесь формальное его определение я не буду — это завело бы нас довольно далеко в сторону. Ограничусь неформальным: «алгоритм» — эта последовательность однозначных инструкций («программа»), которая за конечное число шагов переводит исходные данные в результат. Выделенное курсивом принципиально важно — если на каких-то начальных данных программа зацикливается, то алгоритма она не описывает. Для простоты и в применении к нашему случаю читатель может считать, что алгоритм — это программа, написанная на любом известном ему языке программирования, которая для любых входных данных из заданного класса гарантированно завершает свою работу с выдачей булевого результата.

Спросим себя: для всякой ли функции $P$ существует «доказывающий алгоритм» (или, короче, «дедуктика»), эквивалентный этой функции, то есть переводящий каждое высказывание именно в то булево значение, что и она? Лаконичнее тот же вопрос можно сформулировать так: всякая ли функция над множеством высказываний вычислима? Как вы уже догадываетесь, из справедливости ТГН следует, что нет, не всякая — существуют невычислимые функции такого типа. Иными словами, не всякое верное высказывание можно доказать.

Очень может быть, что это утверждение вызовет у вас внутренний протест. Связано это с несколькими обстоятельствами. Во-первых, когда нас учат школьной математике, то иногда возникает ложное впечатление почти полной тождественности фраз «теорема $X$ верна» и «можно доказать или проверить теорему $X$». Но, если вдуматься, это совершенно не очевидно. Некоторые теоремы доказываются довольно просто (например, перебором небольшого числа вариантов), а некоторые — очень сложно. Вспомним, например, знаменитую Великую теорему Ферма:

  • Не существует таких натуральных $x, y, z$ и $n>2$, что $x^n+ y^n = z^n$.

доказательство которой нашли только через три с половиной века после первой формулировки (и оно далеко не элементарно). Следует различать истинность высказывания и его доказуемость. Ниоткуда не следует, что не существует истинных, но недоказуемых (и не проверяемых в полной мере) высказываний.

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

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

Замечу также, что если бы речь шла о привычных функциях, отображающих множество вещественных чисел в него же, то «невычислимость» функции никого бы не удивила (только не надо путать «вычислимые функции» и «вычислимые числа» — это разные вещи). Любому школьнику известно, что, скажем, в случае функции $\sin x$ вам должно сильно повезти с аргументом, чтобы процесс вычисления точного десятичного представления значения этой функции окончился за конечное число шагов. А скорее всего вы будете вычислять её с помощью бесконечного ряда, и это вычисление никогда не приведёт к точному результату, хотя может подойти к нему как угодно близко — просто потому, что значение синуса большинства аргументов иррационально. ТГН просто говорит нам о том, что даже среди функций, аргументами которой являются строки, а значениями — ноль или единица, невычислимые функции, хотя и совсем по другому устроенные, тоже бывают.

Для дальнейшего опишем «язык формальной арифметики». Рассмотрим класс строк текста конечной длины, состоящих из арабских цифр, переменных (букв латинского алфавита), принимающих натуральные значения, пробелов, знаков арифметических действий, равенства и неравенства, кванторов $\exists$ («существует») и $\forall$ («для любого») и, быть может, каких-то ещё символов (точное их количество и состав для нас неважны). Понятно, что не все такие строки осмысленны (например, «$12 = + \forall x>$» — это бессмыслица). Подмножество осмысленных выражений из этого класса (то есть строк, которые истинны или ложны с точки зрения обычной арифметики) и будет нашим множеством высказываний.

Примеры высказываний формальной арифметики:

  • $1=1$
  • $2\times2=5$
  • $\exists x \; x>3$
  • $\forall y \; \forall z \; y\times z>y+z$

и т.д. Теперь назовём «формулой со свободным параметром» (ФСП) строку, которая становится высказыванием, если в качестве этого параметра подставить в неё натуральное число. Примеры ФСП (с параметром $x$):

  • $x=0$
  • $2\times2=x$
  • $\exists y \; x+y>x$

и т.д. Иными словами, ФСП эквивалентны функциям натурального аргумента с булевыми значением.

Обозначим множество всех ФСП буквой $F$. Понятно, что его можно упорядочить (например, сначала выпишем упорядоченные по алфавиту однобуквенные формулы, за ними — двухбуквенные и т.д.; по какому именно алфавиту будет происходить упорядочивание, нам непринципиально). Таким образом, любой ФСП соответствует её номер $k$ в упорядоченном списке, и мы будем обозначать её $F_k$.

Перейдём теперь к наброску доказательства ТГН в такой формулировке:

  • Для языка высказываний формальной арифметики не существует полной непротиворечивой дедуктики.

Доказывать будем от противного.

Итак, допустим, что такая дедуктика существует. Опишем следующий вспомогательный алгоритм $A$, ставящий в соответствие натуральному числу $k$ булево значение следующим образом:

  1. Находим $k$-ю формулу в списке $F$.
  2. Подставляем в неё число $k$ в качестве аргумента.
  3. Применяем к полученному высказыванию наш доказывающий алгоритм (по нашему предположению, он существует), который переводит его в ИСТИНУ или ЛОЖЬ.
  4. Применяем логическое отрицание к полученному результату.

Проще говоря, алгоритм приводит к значению ИСТИНА тогда и только тогда, когда результат подстановки в ФСП её собственного номера в нашем списке даёт ложное высказывание.

Тут мы подходим к единственному месту, в котором я попрошу читателя поверить мне на слово.

Очевидно, что, при сделанном выше предположении, любой ФСП из $F$ можно сопоставить алгоритм, содержащий на входе натуральное число, а на выходе – булево значение. Менее очевидно обратное утверждение:

  • Лемма: Любому алгоритму, переводящему натуральное число в булево значение, соответствует какая-то ФСП из множества $F$.

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

Пройдя это скользкое место, мы быстро добираемся до конца.

Итак, выше мы описали алгоритм $A$. Согласно лемме, в которую я попросил вас поверить, существует эквивалентная ему ФСП. Она имеет какой-то номер в списке $F$ — скажем, $n$. Спросим себя, чему равно $F_n(n)$? Пусть это ИСТИНА. Тогда, по построению алгоритма $A$ (а значит, и эквивалентной ему функции $F_n$), это означает, что результат подстановки числа $n$ в функцию $F_n$ — ЛОЖЬ. Аналогично проверяется и обратное: из $F_n(n)=$ЛОЖЬ следует $F_n(n)=$ИСТИНА. Мы пришли к противоречию, а значит, исходное предположение неверно. Таким образом, для формальной арифметики не существует полной непротиворечивой дедуктики. Что и требовалось доказать.

Здесь уместно вспомнить Эпименида (см. портрет в заголовке), который, как известно, заявил, что все критяне — лжецы, сам являясь критянином. В более лаконичной формулировке его высказывание (известное как «парадокс лжеца») можно сформулировать так: «Я лгу». Именно такое высказывание, само превозглашающее свою ложность, мы и использовали для доказательства.

В заключение я хочу заметить, что ничего особенного удивительного ТГН не утверждает. В конце концов, все давно привыкли, что не все числа представимы в виде отношения двух целых (помните, у этого утверждения есть очень изящное доказательство, которому больше двух тысяч лет?). И корнями полиномов с рациональными коэффициентами являются тоже не все числа. А теперь вот выяснилось, что не все функции натурального аргумента вычислимы.

Приведённый набросок доказательства относился к формальной арифметике, но нетрудно понять, что ТГН применима и к многим другим языкам высказываний. Разумеется, не всякие языки таковы. Например, определим язык следующим образом:

  • «Любая фраза китайского языка является верным высказыванием, если она содержится в цитатнике товарища Мао Дзе Дуна, и неверна, если не содержится».

Тогда соответствующий полный и непротиворечивый доказывающий алгоритм (его можно назвать «догматической дедуктикой») выглядит примерно так:

  • «Листай цитатник товарища Мао Дзе Дуна, пока не найдёшь искомое высказывание. Если оно найдено, то оно верно, а если цитатник закончился, а высказывание не найдено, то оно неверно».

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

Поделиться с друзьями
-->

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


  1. Olorin111
    11.01.2017 17:57
    #9807452
    +2

    Все это уже было в симпсонах у Пенроуза. Но статья неплохая, спасибо.


    1. vgivanov
      11.01.2017 17:59
      #9807474
      +3

      Спасибо на добром слове. К сожалению, Пенроуза не читал, но осуждаю одобряю.


      1. 1eqinfinity
        18.01.2017 16:18
        #9822874

        «Новый Ум Короля».
        (Если будете в мск, могу безвозмездно отдать бумажную версию. Перевод неплохой, но редактура и само издание ужасны.)


  1. vgivanov
    11.01.2017 18:32
    #9807566
    +1

    Спасибо всем за замечание. Перепутанные кванторы переставил.


    1. mrhru
      13.01.2017 17:08
      #9813102

      Тогда хочется добавить замечание, что утверждение критянина «Все критяне — лжецы» — не является парадоксом.

      Отрицанием этого утверждения является «Не все критяне — лжецы», а вовсе не «Все критяне — не лжецы», как обычно подразумевается. В этом случае Эпименид — лжец, но не все критяне лжецы. Никакого парадокса.

      Даже сокращение охватываемого каким-либо утверждением множества субъектов, что-либо когда-либо заявлявших, т.е. со всех критян до одного Эпименида, — «Я лгу», тоже не становится парадоксом. Максимум на парадокс тянет утверждение «Это утверждение ложно».

      Здесь уже вспоминали Смаллиана, который, в своей книге «Алиса в стране смекалки», довольно подробно разбирает этот и другие «парадоксы»


      1. vgivanov
        13.01.2017 17:16
        #9813128
        +1

        Если парадокс Эпименида сформулирован словесно — то да, у вас обычно есть свобода понять его так, чтобы парадокса не возникало. Если сформулировать его строго — то он есть, и он глубок. Погуглите «антиномия Рассела», например.


  1. Vanger13
    11.01.2017 19:28
    #9807708
    +4

    Еще более разжевано это же можно прочесть в книге https://ru.wikipedia.org/wiki/Гёдель,_Эшер,_Бах
    которую я никогда не устану рекламировать — уж слишком она хороша :)


    1. pestilent
      13.01.2017 01:22
      #9811400

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


  1. petropavel
    11.01.2017 20:41
    #9807914
    +2

    Обозначим множество всех ФСП буквой F. Понятно, что его можно упорядочить по алфавиту (по какому именно, нам непринципиально). Таким образом, любой ФСП соответствует её номер k в упорядоченном списке, и мы будем обозначать её Fk.

    Это почему? Каким таким образом из того, что множество упорядочено, следует, что оно счётно?
    Множество действительных чисел упорядочено. И Кантор именно таким диагональным способом доказывал, что оно несчётно.


    1. vgivanov
      11.01.2017 21:27
      #9807994
      +2

      Вы сомневаетесь в том, что множество слов над конечным алфавитом счётно?


      1. petropavel
        11.01.2017 23:27
        #9808238

        Слов ограниченной длины? Не сомневаюсь. Даже конечно.

        А если неограниченной? Ваше же доказательство блестяще показывает, что множество функций натурального аргумента несчётно. Хотя можно и проще — конечный алфавит 0,1,2,3,4,5,6,7,8,9. Множество слов — все действительные числа между 0 и 1. Континуум.


        1. khoramus
          12.01.2017 01:01
          #9808372
          +2

          Нет не все действительные. 0,(3) нет например. Зато если 0 на A заменить, то получится, что можно каждому числу сопоставить натуральное, переведя из одиннадцатеричной системы счисления.


        1. vgivanov
          12.01.2017 01:20
          #9808402
          +2

          А если неограниченной?


          И неограниченной — тоже. Вам ниже уже ответили.


          1. Welran
            12.01.2017 08:09
            #9808750
            -1

            И ответили неправильно. Множество слов неограниченной длины не счетно.


            1. GlukKazan
              12.01.2017 09:46
              #9808898
              -2

              Докажите?


              1. vgivanov
                12.01.2017 12:17
                #9809316

                Выстроим все слова в алфавитном порядке. Сопоставим слову его номер в этом списке. Множество пронумеровано. Q.e.d.


                1. GlukKazan
                  12.01.2017 12:26
                  #9809366
                  -2

                  Именно


                1. Awoody
                  18.01.2017 16:02
                  #9822804

                  Вы правы в том, что это множество счётное, но так занумеровать слова не получится. Если длина слов не ограничена, то Вы не сможете выстроить их все в алфавитном порядке. Пусть у Вас всего две буквы: А и Б. Тогда алфавитный список слов будет иметь вид:
                  А
                  АА
                  ААА
                  АААА…

                  Вы даже не доберётесь до слов, в которых есть буква Б. То есть занумеровать-то, конечно, можно, но по-другому, как-нибудь так: сперва все однобуквенные (их конечное число), затем двухбуквенные и т. д.


                  1. vgivanov
                    18.01.2017 16:13
                    #9822854
                    +2

                    сперва все однобуквенные (их конечное число), затем двухбуквенные и т. д.


                    Именно это и имелось в виду. Я неправ в том, что забыл это уточнить.


              1. xi-tauw
                13.01.2017 17:16
                #9813132

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


                1. GlukKazan
                  13.01.2017 18:08
                  #9813244
                  -1

                  Уже было


                1. Welran
                  15.01.2017 18:34
                  #9816192

                  Для этого вам сначала придется доказать что мощность множества слов алфавита из одной буквы эквивалентная мощности множества слов из 2 и более букв (что очевидно не так).


                  1. AFH
                    20.01.2017 18:02
                    #9830452
                    -1

                    А почему не так? Мне кажется это совсем не очевидно, более того мощность таких множеств эквивалентна.


            1. GlukKazan
              12.01.2017 12:28
              #9809376

              Так вы собираетесь доказывать своё утверждение?
              Я могу доказать, что множество слов (не важно какой длины) на конечном алфавите счётно, а вы в состоянии доказать обратное?


              1. GlukKazan
                12.01.2017 12:43
                #9809434

                Я немного разочарован. Математические доказательства не определяются результатом голосования.


                1. mayorovp
                  12.01.2017 12:57
                  #9809490
                  +1

                  Действительные числа в диапазоне [0; 1) можно рассматривать как слова бесконечной длины над алфавитом 0-9.


                  Вы готовы доказать что множество действительных чисел счетно?


                  PS да, я понимаю, что исходно звучало слово "неограниченной", а не "бесконечной". Но всем кроме вас очевидно что Welran и petropavel попросту перепутали эти два понятия. Или читали другие книги, где термины определяются немного иначе (к сожалению, такое частенько бывает).


                  Можно было бы просто написать об этом. Более того, ниже уже так и сделали. Зачем вы так упорно пытаетесь выбить ответ от пользователя, который не может вам ответить в силу отрицательной кармы?


                  1. GlukKazan
                    12.01.2017 13:04
                    #9809514

                    Вы готовы доказать что множество действительных чисел счетно?

                    Нет, не готов. А Вы готовы доказать, что множество слов построенных на конечном алфавите взаимно однозначно отображается на множество действительных чисел?


                    1. mayorovp
                      12.01.2017 13:10
                      #9809530

                      Достаточно того факта, что любое действительное число из указанного интервала — это уже "слово" над алфавитом 0-9


                      1. GlukKazan
                        12.01.2017 13:16
                        #9809554
                        +1

                        Любое конечное представление действительного числа неограниченной длины (иными словами рациональное число), да. Но не иррациональное число (не имеющее конечного представления). Разница тонкая, да. Бесконечность — вообще коварная штука. Нельзя просто так взять число не имеющее конечного представления и запросто оперировать с ним как с элементом множества. Это прямой путь к парадоксам.


                        1. mayorovp
                          12.01.2017 13:34
                          #9809628

                          То есть вы из тех кто отрицает доказательство Кантора? Ясно, до свидания.


                          1. GlukKazan
                            12.01.2017 13:39
                            #9809642

                            Нет, не из тех, до свидания.


                            1. vintage
                              12.01.2017 14:31
                              #9809830
                              -3

                              То есть вы прихожанин Церкви Святого Апостола Кантора? Здравствуйте :-)


        1. Coob
          12.01.2017 01:25
          #9808404
          +2

          Обычно уточняют, что слово — последовательность конечной, но неограниченной длины (т.е. не берем расчет бесконечные строки, ведь множество бесконечных последовательностей, составленных конечным алфавитом, и правда не счетно). Тогда все просто: Сперва сортируем по алфавиту все слова длины 1, затем все слова длины 2 и т.д. Счетное объединение конечных множеств вполне себе счетно.


          1. petropavel
            12.01.2017 02:40
            #9808494
            +1

            А, тогда да. Если конечной — то согласен. Но в тексте просто

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

            Будем считать, там было написано «Рассмотрим класс строк конечной длины, состоящих из арабских цифр...»


            1. vgivanov
              12.01.2017 03:43
              #9808538
              +1

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


              1. mayorovp
                12.01.2017 09:17
                #9808832

                Вы просто не писали на Хаскеле.


                string = 'a' : string

                Строка выше задает строку, состоящую из бесконечного числа символов 'a'.


                1. GlukKazan
                  12.01.2017 09:56
                  #9808914
                  -1

                  И кто сказал, что она не элемент счётного множества?


                  1. mayorovp
                    12.01.2017 12:29
                    #9809380

                    При чем тут вообще множество? Я про строки и программирование говорил.


                    1. GlukKazan
                      12.01.2017 12:44
                      #9809440
                      -2

                      Разве строка не может быть элементом математического множества?


                      1. mayorovp
                        12.01.2017 13:02
                        #9809502
                        +1

                        Может. Что дальше?


                        1. GlukKazan
                          12.01.2017 13:11
                          #9809536
                          -2

                          Докажите, что множество строк {'a', 'aa', 'aaa', 'aaaa' и т.д. до бесконечности} не счётно.
                          Мне хватит даже этого доказательства. Сразу посыплю голову пеплом.


                          1. GlukKazan
                            12.01.2017 13:19
                            #9809568
                            -2

                            Опять кто-то решает математические задачи путём прямого (и тайного) голосования?


                          1. mayorovp
                            12.01.2017 13:25
                            #9809588
                            +1

                            Зачем мне это доказывать, если я это не утверждал?


                            1. GlukKazan
                              12.01.2017 13:32
                              #9809622
                              -2

                              То есть вы не возражаете, что оно счётно? Ответ принят.


        1. Awoody
          18.01.2017 16:00
          #9822794
          +1

          Вы правы в том, что из упорядоченности вовсе не следует счётность, но пример с континуумом некорректен: речь же в тексте идёт о словах КОНЕЧНОЙ (пусть и неограниченной) длины, а числа между 0 и 1 имеют в своей записи бесконечное число цифр после запятой (кроме счётного подмножества).


    1. GlukKazan
      11.01.2017 22:37
      #9808144
      +1

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


      1. GlukKazan
        11.01.2017 22:44
        #9808168

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


        1. petropavel
          11.01.2017 23:21
          #9808226
          -1

          А вот это как раз не «поскольку». Между двумя взятыми наугад различными рациональными числами тоже найдётся хотя бы ещё одно рациональное число. Однако же…


          1. GlukKazan
            12.01.2017 09:25
            #9808848

            Главное здесь не то, что на рациональных числах задано отношение порядка. Оно никак не помогает пронумеровать рациональные числа! Именно потому, что между двумя рациональными числами тоже всегда найдётся хотя бы одно рациональное. Суть в том, что используя трюк с нумерацией рациональных чисел «змейкой» можно задать другое отношение порядка, уже позволяющее пронумеровать рациональные числа, поскольку в этом порядке между двумя соседними рациональными числами ещё одно число уже не втиснуть.


            1. valambar
              13.01.2017 22:24
              #9813682

              Кстати, меня смущает в змейковой нумерации рациональных чисел то, что некоторые числа там встречаются даже в начале подсчета по несколько раз (1/1, 2/2 и т.д.) — а во всем подсчете так и вообще бесконечное количество. Надо бы модифицировать эту нумерацию, пропуская сократимые дроби.


              1. Sayonji
                14.01.2017 01:59
                #9813896
                +1

                Зачем? Оттого, что есть повторы в нумерации, рациональных не может стать больше (а наоборот «меньше», раз некоторые выкидываются). Т. е. нумерация змейкой утверждает, что рациональных не больше чем натуральных. То что их не меньше, чем натуральных, очевидно.


              1. pestilent
                14.01.2017 11:56
                #9814296
                +2

                Для эстетов есть последовательность Калкина — Уилфа.


        1. valambar
          13.01.2017 22:30
          #9813686

          Между двумя действительными числами всегда есть континуум действительных чисел. То есть не хотя бы одно. И между двумя рациональными числами бесконечное множество рациональных чисел — но по Кантору оно более «редкое». Там их опять можно пронумеровать. В обоих случаях любой отрезок числовой прямой, какой бы он ни был длины, и на множестве рациональных, и на множестве действительных чисел является однозначным отображением другого отрезка любой длины (в том числе бесконечно большой). Удивительное свойство, которое напрочь убивает воображение. Понять это можно, вообразить — нельзя. Как и можно понять разницу между действительными и рациональными числами — но она невообразима.


      1. petropavel
        11.01.2017 23:19
        #9808222

        Наоборот, я имел в виду доказательство (тоже не очевидного) факта, что множество действительных чисел несчётно. Там было точно так же, как в посте — пусть оно счётно, выпишем все действительные числа от 0 до 1 по порядку, посмотрим на первую цифру первого числа, вторую цифру второго, и так далее. Построим новое число, где на n-й позиции будет 1, если у n-го действительного числа на n-й позиции 0, иначе там будет 0. Получается новое действительное число которое отличается от уже всех пронумерованных.


        1. vintage
          12.01.2017 08:59
          #9808804
          -2

          И всё, что мы таким образом можем выяснить — это то, что выражение содержащее самоотрицание не является высказыванием (то есть чем-то осмысленным). «Этот тезис ложен» — противоречивое выражение. Он не может быть ни истинным ни ложным, так как отрицает сам себя. Это бессмыслица. Аналогично и с «доказательством» Канотора — он определил число через самоотрицание, но из того, что такое число невозможно, сделал неправильные выводы: вместо того, чтобы понять, несостоятельность завуалированного высказывания «возьмём такое число из D, такое, что оно не равно любому числу из D», он решил, что «одно **бесконечное** множество может быть минимум на один элемент больше другого **бесконечного** множества». И понеслось…


          1. mayorovp
            12.01.2017 09:20
            #9808838
            +1

            Он не говорил "возьмём такое число из D, такое, что оно не равно любому числу из D", а конструктивно построил такое число.


            Или вы из тех, кто считает закон исключенного третьего ересью?


            1. vintage
              12.01.2017 09:53
              #9808912
              -2

              **Завуалированно** сказал ровно это. Присмотритесь внимательнее:
              1. Предположим, что мы пересчитали все числа из D.
              2. Построим такое число d из D, что оно не равно каждому числу из (1). Например, «диагональным методом». Но метод тут может быть совершенно любой.
              3. Если число d не равно ни одному числу из D, значит оно не входит в D, что противоречит исходному посылу (1).
              4. Противоречие (3) говорит нам, что ошибка либо в исходном посыле (1), либо в определении числа d (2).
              5. Кантор решил, что ошибка в (1) и пришёл к довольно глупому выводу: **бесконечное** множество D минимум на 1 элемент больше **бесконечного** множества N.
              6. Почему-то никого не смущает, что число d определяется через самоотрицание. Так же как и «брадобрей d — это тот, кто бреет всех жителей деревни D, которые не бреют себя сами».


              1. mayorovp
                12.01.2017 09:58
                #9808916

                Ну и где вы видите ошибку в определении числа d?


                1. vintage
                  12.01.2017 10:08
                  #9808934
                  -2

                  Там же, где и ошибка в определении брадобрея d — в самоотрицании.Рекурсивные определения можно использовать лишь после доказательства их непротиворечивости.


      1. Awoody
        18.01.2017 16:14
        #9822856
        +1

        > континуально, то есть не счётно

        Строго говоря, «континуум» и «несчётно» — не синонимы. Континуум — это ведь не любое несчётное множество, а множество, равномощное множеству вещественных чисел. Но есть и более мощные несчётные множества.


    1. mrxak
      12.01.2017 22:35
      #9811154

      Я просто оставлю две ссылки.


  1. sdi74
    11.01.2017 21:18
    #9807980

    Спасибо, хорошо читается.


  1. worldmind
    11.01.2017 21:18
    #9807982
    +1

    Как понимаю арифметика непротиворичива, но неполна.
    Так вот есть ли примеры истинных арифметических утверждений недоказуемых в рамках арифметики?
    И доказуема ли их недоказуемость?


    1. vgivanov
      11.01.2017 21:34
      #9808022

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


    1. Sychuan
      11.01.2017 21:49
      #9808056

      Как понимаю арифметика непротиворичива, но неполна.

      Возможно что-то полезное будет в этом тексте Непротиворечивость арифметики


    1. DmitriyN
      11.01.2017 22:21
      #9808106
      +1

      Конечно, такие теоремы довольно просто строить. Для примера — теорема Гудстейна.


    1. Olorin111
      11.01.2017 22:38
      #9808152
      +2

      Советую покурить вот это. Буквально прямой ответ на ваш вопрос.


    1. Olorin111
      11.01.2017 22:40
      #9808158

      Немного не успел)


  1. Sayonji
    12.01.2017 00:57
    #9808368
    -1

    Очевидно, что любой ФСП из F можно сопоставить алгоритм, содержащий на входе натуральное число, а на выходе – булево значение.

    Вообще-то только если в формуле нет неограниченных кванторов. Если формула имеет вид «exists x: f(x)», то максимум вы можете написать алгоритм, который будет говорить true если формула истинна и зависать иначе. А если в начале больше одного разнотипного квантора (например, «exists x: forall y: f(x, y)»), то и этого не можете. Это основа теориии алгоритмов.

    Также, вы в начале алгоритмом называете что-то, что обязано завершаться. Предположим, что вы вправе в своем материале вводить свою терминологию, но всё-таки не стоит так делать. Алгоритм — это всё что можно накодить, в том числе бесконечные циклы и т. д. Обязаны завершаться, например, примитивно-рекурсивные функции, но они намного слабее алгоритмов.

    Напоследок:
    всякая ли функция над множеством высказываний вычислима? Как вы уже догадываетесь, ТГН утверждает, что нет, не всякая — существуют невычислимые функции такого типа. Иными словами, не всякое верное высказывание можно доказать.

    У вас после «иными словами» идёт сравнительно правильная формулировка. А вот перед этим намного более простое утверждение, которое не имеет отношения к ТНГ и которое, кстати, относится к первой части моего комментария, иными словами, противоречит вашему утверждению, о том что каждой формуле можно сопоставить завершающийся алгоритм.

    Прошу прощения, но данная статья это какая-то каша с кучей ошибок, про теорему Геделя можно прочитать на википедии, там же есть набросок доказательства. На английской поподробнее, а совсем подробно в книге Верещагина-Шеня.


    1. vgivanov
      12.01.2017 01:18
      #9808398
      +1

      Очевидно, что любой ФСП из F можно сопоставить алгоритм, содержащий на входе натуральное число, а на выходе – булево значение.


      Вообще-то только если в формуле нет неограниченных кванторов.


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

      У вас после «иными словами» идёт сравнительно правильная формулировка. А вот перед этим намного более простое утверждение, которое не имеет отношения к ТНГ


      Какое? Вот это?

      ТГН утверждает, что нет, не всякая — существуют невычислимые функции такого типа


      А в чём ваши претензии?

      Прошу прощения, но данная статья это какая-то каша с кучей ошибок, про теорему Геделя можно прочитать на википедии, там же есть набросок доказательства. На английской поподробнее, а совсем подробно в книге Верещагина-Шеня.


      Не сомневаюсь, что ошибки и неточности есть, но надеюсь, что не «куча». Что касается Википедии и проч., то наличие N (хороших) текстов по предмету не является запретом для написания одного (допустим, не очень хорошего). Моей задачей было не привести строгое и исчерпывающее доказательство теоремы, а дать представление о таковом. Возможно, я с ней не справился.


      1. Sayonji
        12.01.2017 03:17
        #9808526

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

        У вас не написано «предположим», у вас написано «очевидно». А дальше ложное утверждение.

        ТГН утверждает, что нет, не всякая — существуют невычислимые функции такого типа
        А в чём ваши претензии?

        В том, что ТНГ должно формулироваться как существование недоказуемой формулы в непротиворечивой арифметике. Утверждение выше это не ТНГ.


        1. vgivanov
          12.01.2017 03:56
          #9808552

          Некоторая вольность формулировок — цена за то, чтобы текст не был слишком тяжёл для чтения.Там ведь много где нужно делать оговорки. Впрочем, я сейчас попытался чуть подправить текст в соответствии с вашими замечаниями.


          1. Sayonji
            12.01.2017 04:21
            #9808572

            Это не вольность формулировок, а другая теорема. Если знаете английский, вот. Утверждение «существуют невычислимые функции такого типа (арифметические формулы с параметрами)», это частный, почти тривиальный, случай теоремы Поста (по ссылке как раз говорится, что вычислимыми такие функции будет только в том случае, если они не начинаются с кванторов).
            ТГН о другом.


            1. vgivanov
              12.01.2017 04:41
              #9808592

              Я полагаю, что если ТГН для формальной арифметики верна, то существуют невычислимые функции со строковым аргументом и булевым значением. С такой формулировкой вы будете спорить?


              1. Sayonji
                12.01.2017 05:03
                #9808600

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


        1. Olorin111
          12.01.2017 04:00
          #9808556
          -1

          ТНГ должно формулироваться как существование недоказуемой формулы в непротиворечивой арифметике.

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


          1. Sayonji
            12.01.2017 04:04
            #9808560
            +1

            То что вы говорите не похоже скорее на философию, а не на математику. Теорема Геделя это сложный математически стогий результат, с чёткими условиями выполнения, а не какой-то принцип или еще что-то. Может я не прав, но тогда формализуйте понятия «утверждение», «описание», «свойства», а то я не до конца понимаю, что они значат.


            1. Olorin111
              12.01.2017 15:50
              #9810126

              Действительно, это больше философский подход.
              Наверняка меня заминусуют, но я все-же попробую.
              Та-же теорема Гудстейна.(утверждение)
              В рамках арифметики Пеано применим принцип матиндукции. пусть это будет *описание*
              Свойства, которые по средствам матиндукции по началу применимы для описания данного утверждения в целом не полны.
              Однако под описание отрицания принципа матиндукции свойства утверждения теоремы Гудстейна вполне себе подходят.
              И да, оно не приведет к доказательству, однако исключит попытку пойти по ложному пути.

              Как пример из реального мира — хотелось бы попробовать взять сознание. Но мне не нужна отрицательная карма. Это скользкая тема.


            1. Olorin111
              12.01.2017 16:04
              #9810196

              Прошу меня извинить. немного неточно выразился.
              Свойства, которые по средствам матиндукции по началу применимы для описания данного утверждения в целом не полны. Скорее противоречивы
              Однако под описание отрицания принципа матиндукции свойства утверждения теоремы Гудстейна вполне себе подходят. Однако вот здесь как раз они неполны.


  1. valambar
    12.01.2017 03:57
    #9808554

    Пара вопросов.

    1. Я иногда встречал такие суждения, что «такая-то теория одновременно непротиворечива и полна». Как я понимаю из подобных суждений, какие-то системы высказываний могут не попадать под теорему Геделя. Сам с этим не сталкивался, но можно привести примеры таких систем? И каков критерий того, что к данной системе высказываний будет применима теорема Геделя?

    2. Читал, что метод геделевской нумерации применяется не только к доказательству данной теоремы, но и для решения многих задач по теории автоматов. Поэтому вопрос — где найти подробное (уровень — для чайников) описание, как применять геделевскую нумерацию к конкретным задачам?


    1. vgivanov
      12.01.2017 04:02
      #9808558

      Вырожденный случай полной непротиворечивой дедуктики описан в конце текста.

      Что касается остальной части вопроса — то тут, увы, я не специалист. Быть может, комментаторы подтянутся?


    1. Sayonji
      12.01.2017 19:02
      #9810716

      1. Теория должна описывать натуральные числа, сложение и умножение (естественным образом). Тогда применима теорема Геделя. Причина в том, что на натуральных числах со сложением и умножением можно эмулировать работу машин Тьюринга, т. е. записывать алгоритмы. Если выбросить из арифметики Пеано умножение, например, то она может быть станет полной и непротиворечивой (а может и нет, но похожую полную непротиворечивую точно можно придумать).

      2. Верещагин, Шень «Лекции по математической логике и теории алгоритмов». Третья часть. Но это большая сложная книга. И строится на фундаменте первых двух частей, которые тоже большие сложные книги. Однако начинать читать можно без каких-либо знаний, все три части можно за полгода осилить разбираясь или в режиме «факты без доказательств» за пару недель.


  1. ivansmith
    12.01.2017 12:17
    #9809318

    «Иными словами, не всякое верное высказывание можно доказать.»
    — Дилетантский вопрос, как мы знаем, что высказывание верное, если мы это не можем проверить?


    1. mayorovp
      12.01.2017 12:20
      #9809340

      Никак. Но истинность высказывания не зависит от того, знаем ли мы об этом.


    1. vgivanov
      12.01.2017 12:30
      #9809384

      Никак.

      Скажем, высказывание вида «для любых x и y f(x,y)=0» может быть верным — f(x,y) ни для одной пары натуральных аргументов не отличается от нуля. Но доказать это — то есть свести высказывание к известным аксиомам, мы не можем.


    1. Sayonji
      12.01.2017 19:14
      #9810762

      Существует такая замкнутая формула арифметики, что мы не можем доказать ни её ни её отрицание (средствами арифметики). А ведь хотя бы одна из них должна быть истинной. Вот и получается недоказуемая верная формула. Ну или же всё-таки арифметика противоречива и доказать можно всё что угодно.


      1. vintage
        12.01.2017 20:57
        #9811010
        -1

        > А ведь хотя бы одна из них должна быть истинной.

        Докажите этот тезис. ;-)


        1. Sayonji
          12.01.2017 21:03
          #9811018

          Да легко. Мое последнее предложение говорит об том, что я предполагаю непротиворечивость арифметики, то есть считаю, что наши привычные натуральные числа это её модель. А в модели любая замкнутая формула однозначным образом разбирается и оценивается. Каково бы ни было значение формулы, значение её отрицания противоположно (потому что при разборе (по определению модели) внешнее отрицание всегда будет применено последним).


          1. vintage
            12.01.2017 22:04
            #9811124

            Тут вы делаете предположение, что формула возвращает значение булевого типа. Довольно необоснованное предположение.


            1. Sayonji
              12.01.2017 22:08
              #9811126

              Это определение формулы. Термы возвращают элементы множества-носителя модели (числа), а термы связанные предикатами, логическими операторами и кванторами называются формулами. К термам понятие выводимости/доказуемости вообще неприменимо.


              1. vintage
                12.01.2017 22:54
                #9811190
                -1

                1/0 тоже число возвращает?


                1. mayorovp
                  12.01.2017 23:04
                  #9811218
                  -1

                  Опять вы к словам придираетесь. 1/0 = ?


                  1. 0xd34df00d
                    12.01.2017 23:32
                    #9811280
                    -1

                    Нет, /0 (обратный элемент нуля) не существует.


                    1. mayorovp
                      12.01.2017 23:41
                      #9811292
                      -1

                      ? (bottom) — это не обратный элемент ноля. Это символ ошибки в вычислениях или вечного выполнения.


                      1. 0xd34df00d
                        12.01.2017 23:55
                        #9811304

                        Я знаю. Я говорил о том, что эта запись не имеет смысла сама по себе, потому что a/b = a*(b^{-1)), а 0^{-1} не существует.

                        Да, функция взятия обратного элемента по умножению, если рассматривать её как функцию из всего поля, не является тотальной, и там вылезет bottom, но это, ИМХО, другой вопрос.


                1. Sayonji
                  12.01.2017 23:57
                  #9811308

                  Какую цель вы преследуете? В арифметике Пеано нет символа деления, мы вроде о ней говорим. В какой-нибудь тругой теории, в которой есть деление, 1/0 это терм.


                  1. vintage
                    13.01.2017 04:06
                    #9811532

                    Только вот терм 1/0 не возвращает число. А 1/1 — возвращает.


                    1. Sayonji
                      13.01.2017 06:06
                      #9811590

                      Какая неприятность.


    1. valambar
      13.01.2017 21:57
      #9813638

      «Проверить» — не значит «доказать», Аксиомы арифметики и геометрии мы проверяем тем, что каждый раз применяя их, получаем верный результат. И верим (!), что и в следующий раз результат получится верный. А вот доказать не можем. Нет более простых понятий, из которых они складываются. А потому и не можем построить доказывающие их суждения.


  1. erwins22
    12.01.2017 12:17
    #9809320

    Интересно, а в нашей вселенной возможно создание сверхтьюрингового компьютера и опровержение данной теоремы?


    1. vgivanov
      12.01.2017 12:19
      #9809332

      Математику не обманешь.


    1. mayorovp
      12.01.2017 12:25
      #9809362

      В строгом доказательстве Теоремы Гёделя не используется понятия машины тьюринга. Поэтому никакая "сверхтьюринговость" не поможет, чтобы это слово не означало.


      1. erwins22
        12.01.2017 12:34
        #9809400

        в строгом доказательстве отсутствует оракул и получение результатов из будущего.
        согласно ОТО есть получение результатов из будущего.
        согласно квантовой механики есть оракул.

        Если мир соответствовал бы классической механики, то вопросов бы не было.


        1. mayorovp
          12.01.2017 12:42
          #9809432

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


          Во-вторых, доказательство не привязано ни к одной модели вычислений.


          1. erwins22
            12.01.2017 12:45
            #9809444
            -2

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


          1. erwins22
            12.01.2017 13:20
            #9809574
            -1

            Доказательство основано как минимум на теории множеств непротиворечивость которой не доказана.


      1. alex_blank
        16.01.2017 21:49
        #9818952

        Разве нет однозначного соответствия между decidability и computability?


        1. erwins22
          17.01.2017 14:00
          #9820160
          +1

          есть.


  1. Zulkijind
    12.01.2017 17:34
    #9810482

    Может я глупая картофелина, но подскажите пожалуйста, что нужно изучить, и чтобы понять эту статью? Я её прочёл, но ничего не понял, хотя автор заверил, что он сам не математик. За саму статью спасибо, хочу прочесть еще раз, когда начну понимать.


    1. vgivanov
      12.01.2017 17:43
      #9810508

      Я надеялся, что школьного курса достаточно, чтобы понять процентов 75 как минимум. Хотя, может быть, я слишком хорошо думаю о современной школе?

      хочу прочесть еще раз, когда начну понимать


      Если не прочтёте ещё раз, то понимание вряд ли придёт само.


      1. Zulkijind
        16.01.2017 01:01
        #9816622

        У меня знания математики до 9 класса. Никакой математической логики или дискретной математики мы не проходили, но у меня в планах их изучать, но даже курсы «для чайников» как-то слишком сложно даются, будто все вводящие книги или учебники сделаны так, что тебе необходимы объяснения специалистов, будто самому не осилить.


    1. vanxant
      13.01.2017 06:53
      #9811610

      Погуглите что-нибудь типа [математическая логика для чайников].


    1. bars_arseniy
      13.01.2017 16:38
      #9813032

      Позвольте узнать, как вы читали статью? Как какую-нибудь новость, где читаешь и всё понятно? — для этого надо неплохо разбираться в математике и логике, чтобы так сходу прочесть и понять.
      Вы перечитывали по 5-10 раз фразы, смысл которых не ясен? Медленно, слово за словом пытаясь понять что значит каждое слово, зачем оно в этом предложении и какой несёт смысл? Если нет, то попробуйте. Я именно так и читаю всякие определения и описания, если сходу не ясно, что там написано. Часть про «поверить на слово», вывод её и из неё я перечитал раз 5-7 и чувствую, что не до конца понял.
      Ещё можно не читать какие-нибудь дополняющие и уточняющие обороты из предложений, чтобы понять общий смысл. Как будет понятен общий смысл можно читать предложения с уточняющими оборотами.
      Так же можно читать информацию по ссылкам. Она тоже может помогать. Хотя математические статьи в вики могут гораздо сложнее. Но если по ходу чтения в них что-нибудь поймёте, вернувшись сюда вам будет проще. Пока будете читать что-то в вики и не понимать, открывайте ссылки на новые термины. Вот так прочитаете с десяток другой подобных статьей или сложнее. Вернётесь сюда и будет легче читать. Это такое неструктурированное изучение области))
      С точки зрения терминов автор вроде прав, школьных знаний хватит. Хотя если вы не очень были в математике, не особо вникали в доказательства теорем, то может этого будет недостаточно.
      Если не знаете, что значит термин — погуглите. Погуглите термины, которые автор объяснил кратко, может более полное определение поможет.


    1. valambar
      13.01.2017 22:03
      #9813648

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


  1. Rembo123
    13.01.2017 17:05
    #9813096
    -1

    С формальной точки зрения теорема Гёделя не очень интересна, но из неё есть интересные следствия. Я бы даже сказал вольные философские умозаключения. Ну например, такое, не знаю, на сколько точно оно соответствует тому что стремился показать сам Гёдель, но тем не менее:

    Теорема: Существует такая теорема которую нельзя ни доказать, ни опровергнуть.

    Доказательство собственно в самой формулировке теоремы.


  1. Radionuclide
    13.01.2017 20:50
    #9813536
    +1

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


  1. gromozeka1980
    18.01.2017 12:12
    #9822020

    Вопрос к тем, кто в отличие от меня знает математику…

    Есть аксиоматика А (включающая аксиоматику Пеано, замкнутая для логики первого порядка, короче все условия для ТГН), согласно ТГН, в этой аксиоматике существует утверждение Р, которое в этой аксиоматике истинно, но недоказумо.
    я беру обратное утверждение и строю аксиоматику А+~P
    если аксиоматика А непротиворечива, то и новая аксиоматика непротиворечива, т.к. если бы она была противоречивой, это опровергало бы Р в А и приводило бы к противоречию с условиями. имеем две непротиворечивых аксиоматики, в одной Р — истинно, в другой — ложно.
    вопрос такой. если Р истинно в аксиоматике А, может ли оно в принципе быть ложным в аксиоматике, включающей А в качестве подмножества? ну или где у меня ошибка в рассуждениях?


    1. mayorovp
      18.01.2017 13:14
      #9822256

      Если брать тот вариант теоремы, который говорит про существование истинного, но недоказуемого P — то там отрицание P противоречит самому себе.


    1. Sayonji
      18.01.2017 16:00
      #9822796
      -1

      в этой аксиоматике существует утверждение Р, которое в этой аксиоматике истинно, но недоказумо

      Не совсем, оно истинно «в реальности», а не в А. Если добавить отрицание P к A, то полученная аксиоматика снова будет непротиворечива, но она просто уже не будет описывать привычную нам арифметику, а какую-то другую.


  1. Hillion
    18.01.2017 23:11
    #9826334
    -1

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

    Хотя, конечно, я не изучал вопрос глубоко.


    1. Sayonji
      19.01.2017 12:29
      #9827302

      Не обязано. В той же арифметике Пеано бесконечно аксиом.


  1. vgivanov
    18.01.2017 23:16
    #9826346
    +1

    А нельзя ли узнать, почему, собственно, количество аксиом обязано быть конечным?


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