11 января в 17:28

Теорема Гёделя о неполноте за 20 минут из песочницы



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

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

Математическая логика — наука действительно довольно сложная, а главное — не очень привычная. Она требует аккуратных и строгих манёвров, при которых важно не перепутать реально доказанное с тем, что «и так понятно». Тем не менее, я надеюсь, что для понимания следующего ниже «наброска доказательства ТГН» читателю понадобится только знание школьной математики/информатики, навыки логического мышления и 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)=$ИСТИНА. Мы пришли к противоречию, а значит, исходное предположение неверно. Таким образом, для формальной арифметики не существует полной непротиворечивой дедуктики. Что и требовалось доказать.

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

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

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

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

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

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

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

@vgivanov
карма
6,0
рейтинг 0,0
Пользователь
Похожие публикации
Самое читаемое

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

  • +2
    Все это уже было в симпсонах у Пенроуза. Но статья неплохая, спасибо.
    • +3
      Спасибо на добром слове. К сожалению, Пенроуза не читал, но осуждаю одобряю.
      • 0
        «Новый Ум Короля».
        (Если будете в мск, могу безвозмездно отдать бумажную версию. Перевод неплохой, но редактура и само издание ужасны.)
  • +1
    Спасибо всем за замечание. Перепутанные кванторы переставил.
    • 0
      Тогда хочется добавить замечание, что утверждение критянина «Все критяне — лжецы» — не является парадоксом.

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

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

      Здесь уже вспоминали Смаллиана, который, в своей книге «Алиса в стране смекалки», довольно подробно разбирает этот и другие «парадоксы»
      • +1
        Если парадокс Эпименида сформулирован словесно — то да, у вас обычно есть свобода понять его так, чтобы парадокса не возникало. Если сформулировать его строго — то он есть, и он глубок. Погуглите «антиномия Рассела», например.
  • +4
    Еще более разжевано это же можно прочесть в книге https://ru.wikipedia.org/wiki/Гёдель,_Эшер,_Бах
    которую я никогда не устану рекламировать — уж слишком она хороша :)
  • +2
    Обозначим множество всех ФСП буквой F. Понятно, что его можно упорядочить по алфавиту (по какому именно, нам непринципиально). Таким образом, любой ФСП соответствует её номер k в упорядоченном списке, и мы будем обозначать её Fk.

    Это почему? Каким таким образом из того, что множество упорядочено, следует, что оно счётно?
    Множество действительных чисел упорядочено. И Кантор именно таким диагональным способом доказывал, что оно несчётно.
    • +2
      Вы сомневаетесь в том, что множество слов над конечным алфавитом счётно?
      • 0
        Слов ограниченной длины? Не сомневаюсь. Даже конечно.

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


          И неограниченной — тоже. Вам ниже уже ответили.
          • –1
            И ответили неправильно. Множество слов неограниченной длины не счетно.
            • –2
              Докажите?
              • 0
                Выстроим все слова в алфавитном порядке. Сопоставим слову его номер в этом списке. Множество пронумеровано. Q.e.d.
                • –2
                  Именно
                • 0
                  Вы правы в том, что это множество счётное, но так занумеровать слова не получится. Если длина слов не ограничена, то Вы не сможете выстроить их все в алфавитном порядке. Пусть у Вас всего две буквы: А и Б. Тогда алфавитный список слов будет иметь вид:
                  А
                  АА
                  ААА
                  АААА…

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


                    Именно это и имелось в виду. Я неправ в том, что забыл это уточнить.
              • 0
                Достаточно попросить доказать более слабое утверждение. Есть алфавит из одной буквы и нет ограничения на длину слова. Пусть уважаемый Welran попробует доказать несчетность множества слов, не смотря на очевидный способ нумерации.
                • –1
                  Уже было
                • 0
                  Для этого вам сначала придется доказать что мощность множества слов алфавита из одной буквы эквивалентная мощности множества слов из 2 и более букв (что очевидно не так).
                  • –1
                    А почему не так? Мне кажется это совсем не очевидно, более того мощность таких множеств эквивалентна.
            • 0
              Так вы собираетесь доказывать своё утверждение?
              Я могу доказать, что множество слов (не важно какой длины) на конечном алфавите счётно, а вы в состоянии доказать обратное?
              • 0
                Я немного разочарован. Математические доказательства не определяются результатом голосования.
                • +1

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


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


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


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

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

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

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

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

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

                          • 0
                            Нет, не из тех, до свидания.
                            • –3
                              То есть вы прихожанин Церкви Святого Апостола Кантора? Здравствуйте :-)
        • +2
          Обычно уточняют, что слово — последовательность конечной, но неограниченной длины (т.е. не берем расчет бесконечные строки, ведь множество бесконечных последовательностей, составленных конечным алфавитом, и правда не счетно). Тогда все просто: Сперва сортируем по алфавиту все слова длины 1, затем все слова длины 2 и т.д. Счетное объединение конечных множеств вполне себе счетно.
          • +1
            А, тогда да. Если конечной — то согласен. Но в тексте просто
            Рассмотрим класс строк текста, состоящих из арабских цифр, переменных (букв латинского алфавита), принимающих натуральные значения, пробелов, знаков арифметических действий, равенства и неравенства, кванторов ∃ и ∀ и, быть может, каких-то ещё символов
            так что было неоднозначно. Мне как-то не пришло в голову, что имеются в виду только строки конечной длины.

            Будем считать, там было написано «Рассмотрим класс строк конечной длины, состоящих из арабских цифр...»
            • +1
              С точки зрения математика вы, конечно, правы. Хотя программист во мне не смог представить строку бесконечной длины:)
              • 0

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


                string = 'a' : string

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

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

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

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

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

                        • –2
                          Докажите, что множество строк {'a', 'aa', 'aaa', 'aaaa' и т.д. до бесконечности} не счётно.
                          Мне хватит даже этого доказательства. Сразу посыплю голову пеплом.
                          • –2
                            Опять кто-то решает математические задачи путём прямого (и тайного) голосования?
                          • +1

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

                            • –2
                              То есть вы не возражаете, что оно счётно? Ответ принят.
        • +1
          Вы правы в том, что из упорядоченности вовсе не следует счётность, но пример с континуумом некорректен: речь же в тексте идёт о словах КОНЕЧНОЙ (пусть и неограниченной) длины, а числа между 0 и 1 имеют в своей записи бесконечное число цифр после запятой (кроме счётного подмножества).
    • +1
      Насколько я понимаю, под «диагональным методом» вы понимаете доказательство того (не очевидного) факта, что множество рациональных чисел — счётно (при этом, вещественные числа, помимо рациональных, включает иррациональные, множество которых, как раз, континуально, таким образом и множество действительных чисел континуально, то есть не счётно). Доказательство счётности множества рациональных чисел было построено как раз на том, что их удалось упорядочить, раздав каждому из чисел порядковые номера. Множество слов, построенных на конечном алфавите также легко «пересчитать» подобным образом. Если считать буквы алфавита цифрами, произвольное слово будет представляться числом, записанным в системе счисления с основанием равным количеству букв в алфавите. Множество бесконечно, но при этом счётно. Прошу простить за капитанство.
      • 0
        Дополню. Множество действительных чисел упорядочено, но номер каждому действительному числу раздать не получится. Поскольку между двумя взятыми наугад различными действительными числами всегда найдётся хотя бы ещё одно действительное число.
        • –1
          А вот это как раз не «поскольку». Между двумя взятыми наугад различными рациональными числами тоже найдётся хотя бы ещё одно рациональное число. Однако же…
          • 0
            Главное здесь не то, что на рациональных числах задано отношение порядка. Оно никак не помогает пронумеровать рациональные числа! Именно потому, что между двумя рациональными числами тоже всегда найдётся хотя бы одно рациональное. Суть в том, что используя трюк с нумерацией рациональных чисел «змейкой» можно задать другое отношение порядка, уже позволяющее пронумеровать рациональные числа, поскольку в этом порядке между двумя соседними рациональными числами ещё одно число уже не втиснуть.
            • 0
              Кстати, меня смущает в змейковой нумерации рациональных чисел то, что некоторые числа там встречаются даже в начале подсчета по несколько раз (1/1, 2/2 и т.д.) — а во всем подсчете так и вообще бесконечное количество. Надо бы модифицировать эту нумерацию, пропуская сократимые дроби.
              • +1
                Зачем? Оттого, что есть повторы в нумерации, рациональных не может стать больше (а наоборот «меньше», раз некоторые выкидываются). Т. е. нумерация змейкой утверждает, что рациональных не больше чем натуральных. То что их не меньше, чем натуральных, очевидно.
              • +2
        • 0
          Между двумя действительными числами всегда есть континуум действительных чисел. То есть не хотя бы одно. И между двумя рациональными числами бесконечное множество рациональных чисел — но по Кантору оно более «редкое». Там их опять можно пронумеровать. В обоих случаях любой отрезок числовой прямой, какой бы он ни был длины, и на множестве рациональных, и на множестве действительных чисел является однозначным отображением другого отрезка любой длины (в том числе бесконечно большой). Удивительное свойство, которое напрочь убивает воображение. Понять это можно, вообразить — нельзя. Как и можно понять разницу между действительными и рациональными числами — но она невообразима.
      • 0
        Наоборот, я имел в виду доказательство (тоже не очевидного) факта, что множество действительных чисел несчётно. Там было точно так же, как в посте — пусть оно счётно, выпишем все действительные числа от 0 до 1 по порядку, посмотрим на первую цифру первого числа, вторую цифру второго, и так далее. Построим новое число, где на n-й позиции будет 1, если у n-го действительного числа на n-й позиции 0, иначе там будет 0. Получается новое действительное число которое отличается от уже всех пронумерованных.
        • –2
          И всё, что мы таким образом можем выяснить — это то, что выражение содержащее самоотрицание не является высказыванием (то есть чем-то осмысленным). «Этот тезис ложен» — противоречивое выражение. Он не может быть ни истинным ни ложным, так как отрицает сам себя. Это бессмыслица. Аналогично и с «доказательством» Канотора — он определил число через самоотрицание, но из того, что такое число невозможно, сделал неправильные выводы: вместо того, чтобы понять, несостоятельность завуалированного высказывания «возьмём такое число из D, такое, что оно не равно любому числу из D», он решил, что «одно **бесконечное** множество может быть минимум на один элемент больше другого **бесконечного** множества». И понеслось…
          • +1

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


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

            • –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, которые не бреют себя сами».
              • 0

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

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

        Строго говоря, «континуум» и «несчётно» — не синонимы. Континуум — это ведь не любое несчётное множество, а множество, равномощное множеству вещественных чисел. Но есть и более мощные несчётные множества.
    • 0
      Я просто оставлю две ссылки.
  • 0
    Спасибо, хорошо читается.
  • +1
    Как понимаю арифметика непротиворичива, но неполна.
    Так вот есть ли примеры истинных арифметических утверждений недоказуемых в рамках арифметики?
    И доказуема ли их недоказуемость?
    • 0
      Вопросы хороши, но хороших ответов у меня нет. Возможно, копать нужно в сторону второй теоремы Гёделя.
    • 0
      Как понимаю арифметика непротиворичива, но неполна.

      Возможно что-то полезное будет в этом тексте Непротиворечивость арифметики
    • +1
      Конечно, такие теоремы довольно просто строить. Для примера — теорема Гудстейна.
    • +2
      Советую покурить вот это. Буквально прямой ответ на ваш вопрос.
    • 0
      Немного не успел)
  • –1
    Очевидно, что любой ФСП из F можно сопоставить алгоритм, содержащий на входе натуральное число, а на выходе – булево значение.

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

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

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

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

    Прошу прощения, но данная статья это какая-то каша с кучей ошибок, про теорему Геделя можно прочитать на википедии, там же есть набросок доказательства. На английской поподробнее, а совсем подробно в книге Верещагина-Шеня.
    • +1
      Очевидно, что любой ФСП из F можно сопоставить алгоритм, содержащий на входе натуральное число, а на выходе – булево значение.


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


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

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


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

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


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

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


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

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

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

        В том, что ТНГ должно формулироваться как существование недоказуемой формулы в непротиворечивой арифметике. Утверждение выше это не ТНГ.
        • 0
          Некоторая вольность формулировок — цена за то, чтобы текст не был слишком тяжёл для чтения.Там ведь много где нужно делать оговорки. Впрочем, я сейчас попытался чуть подправить текст в соответствии с вашими замечаниями.
          • 0
            Это не вольность формулировок, а другая теорема. Если знаете английский, вот. Утверждение «существуют невычислимые функции такого типа (арифметические формулы с параметрами)», это частный, почти тривиальный, случай теоремы Поста (по ссылке как раз говорится, что вычислимыми такие функции будет только в том случае, если они не начинаются с кванторов).
            ТГН о другом.
            • 0
              Я полагаю, что если ТГН для формальной арифметики верна, то существуют невычислимые функции со строковым аргументом и булевым значением. С такой формулировкой вы будете спорить?
              • 0
                Это утверждение верно постольку поскольку верно утверждение «существуют невычислимые функции со строковым аргументом и булевым значением». Теорема Гедёля о неполноте не об этом. Я вам уже приводил формулировку, сбрасывал ссылку на теорему Поста, больше мне нечего сказать.
        • –1
          ТНГ должно формулироваться как существование недоказуемой формулы в непротиворечивой арифметике.

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

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

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

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

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

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

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

    • 0
      Никак.

      Скажем, высказывание вида «для любых x и y f(x,y)=0» может быть верным — f(x,y) ни для одной пары натуральных аргументов не отличается от нуля. Но доказать это — то есть свести высказывание к известным аксиомам, мы не можем.
    • 0
      Существует такая замкнутая формула арифметики, что мы не можем доказать ни её ни её отрицание (средствами арифметики). А ведь хотя бы одна из них должна быть истинной. Вот и получается недоказуемая верная формула. Ну или же всё-таки арифметика противоречива и доказать можно всё что угодно.
      • –1
        > А ведь хотя бы одна из них должна быть истинной.

        Докажите этот тезис. ;-)
        • 0
          Да легко. Мое последнее предложение говорит об том, что я предполагаю непротиворечивость арифметики, то есть считаю, что наши привычные натуральные числа это её модель. А в модели любая замкнутая формула однозначным образом разбирается и оценивается. Каково бы ни было значение формулы, значение её отрицания противоположно (потому что при разборе (по определению модели) внешнее отрицание всегда будет применено последним).
          • 0
            Тут вы делаете предположение, что формула возвращает значение булевого типа. Довольно необоснованное предположение.
            • 0
              Это определение формулы. Термы возвращают элементы множества-носителя модели (числа), а термы связанные предикатами, логическими операторами и кванторами называются формулами. К термам понятие выводимости/доказуемости вообще неприменимо.
              • –1
                1/0 тоже число возвращает?
                • –1

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

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

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

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

                        Да, функция взятия обратного элемента по умножению, если рассматривать её как функцию из всего поля, не является тотальной, и там вылезет bottom, но это, ИМХО, другой вопрос.
                • 0
                  Какую цель вы преследуете? В арифметике Пеано нет символа деления, мы вроде о ней говорим. В какой-нибудь тругой теории, в которой есть деление, 1/0 это терм.
                  • 0
                    Только вот терм 1/0 не возвращает число. А 1/1 — возвращает.
                    • 0

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

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

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

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

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

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


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

          • –2
            нет. с помощью получения информации из будущего можно пройти до бесконечности любую рекурсивную функцию.
            Т.е. решить проблему останова со всеми вытекающими,
            А доказательство неполноты основано на том, что мы не можем пройти рекурсивную функцию до бесконечности и получить однозначный ответ.
          • –1
            Доказательство основано как минимум на теории множеств непротиворечивость которой не доказана.
      • 0
        Разве нет однозначного соответствия между decidability и computability?
        • +1
          есть.
  • 0

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

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

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


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

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

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

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

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

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

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

    Хотя, конечно, я не изучал вопрос глубоко.
    • 0
      Не обязано. В той же арифметике Пеано бесконечно аксиом.
  • +1
    А нельзя ли узнать, почему, собственно, количество аксиом обязано быть конечным?


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

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