"Теорема Гёделя" никогда не была доказана

[Инт]

ПОСТ №1.

Утверждение Гёделя
«о неполноте формальной арифметики» никогда и никем не было доказано

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

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

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

Истинные мотивы «школы» находятся вне математики. Но аргументы против «школы» в конечном итоге можно выдвигать лишь математические.

(Дальше шли тезисы, примеры, которые я исключил из основного текста, чтобы сосредоточиться только на теореме Гёделя. Эти тезисы сохранились на посте ADа)

Подробнее разберём известное утверждение Гёделя.

§1

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

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

§2

Пусть в теории арифметики используются подстановки формул и функторов в формулы и функторы. Числовые значения функторов и истинностные значения формул, пусть зависят от таких же значений, используемых при подстановках. В частности, значения функторов могут зависеть от истинностных значений формул.

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

Гёделева «парадоксальная формула» выражается через рекурсивные функции. Определим функторы г и ф:

г(n) = гёделеву номеру той формулы, доказательство которой имеет гёделев номер n.
г(n) = 0, если n не является номером какого-либо доказательства.

ф(m, p) = гёделеву номеру той формулы, которая получена из формулы Ч с одной свободной переменной и с гёделевым номером m, путём подстановки значения p в Ч вместо свободной переменной.
ф(m, p) = 0, в противном случае.

Рассуждение Гёделя сводимо к следующему: Пусть формула: "не существует n (ф(x, x) = г(n))", обозначенная как Ч, имеет Гёделев номер M. Тогда формула Гёделя Ф, полученная подстановкой номера М в формулу Ч такова: "не существует n (ф(M, M) = г(n))". Ф имеет гёделев номер ф(M, M), в связи с указанной подстановкой. Предположим, Ф доказуема. Тогда, существует номер n некоторого доказательства формулы Ф. По определению функции г получаем, что "г(n) = гёделеву номеру формулы Ф = ф(M, M)". Т.е. истинно, что "ф(М, М) = г(n)", т.е. истинно отрицание формулы Ф. Т.к. из доказуемости следует истинность Ф, то предположение ведёт к противоречию. Предположим, что доказуема (следовательно истинна) формула не Ф. Отрицание Ф говорит в точности о том, что "существует номер n такой, что ф(М, М) = г(n)". Так как гёделевы номера формул не равны нулю, то n не может быть номером, не являющимся номером доказательства. Т.е. n – номер доказательства. Тогда, т.к. "ф(М, М) = г(n)", это доказательство формулы с гёделевым номером ф(М, М). Т.е. "Ф доказуема". Значит, Ф истинна одновременно с истинностью не Ф. Приводим к противоречию предположение о доказуемости формулы не Ф.

§3

В гёделевой арифметике можно говорить о доказательствах как о предметах и о взаимоотношениях между числами и доказательствами. Собственно, формула "существует n (m = г(n))" считается содержательно говорящей о том, что "формула, имеющая гёделев номер m, доказуема". Следовательно, по поводу этих взаимоотношений можно рассуждать внутри гёделевой арифметики, для чего и создан её язык. В частности поэтому, изложенное выше рассуждение должно быть рассуждением гёделевой арифметики. Можно так же утверждать, что функтор, перечисляющий доказательства, тем или иным способом определён в арифметике Гёделя, и значит, можно рассуждать о нём в этой арифметике.

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

Действительно, пусть предположение о доказуемости формулы Ф уже приведено к противоречию безусловно, т.е. из аксиом гёделевой арифметики (например, так, как это сделано выше). Выводим отсюда безусловно, т.е. как формулу гёделевой арифметики, что "Ф недоказуема". Тогда, каждый натуральный номер n не может быть номером доказательства для формулы Ф. Тогда, по определению г, "для каждого n верно, что ф(M, M) не равна г(n)". Т.е. верна формула "не существует n (ф(M, M) = г(n))", т.е. верна Ф. Это есть вывод формулы Ф из аксиом гёделевой теории арифметики. Вывод имеет конкретный гёделев номер. Выводим отсюда, что Ф доказуема.

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

§4

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

Значение г зависит не только от n, но и от того, доказуема или недоказуема формула Ф. Т.е. г зависит от Ф. Чтобы определить Ф необходимо полностью определить г, но, чтобы определить г необходимо определить Ф. Если мы хотим определить формулу Гёделя так, чтобы она была не доказуема, то мы должны для всех значений аргумента N определить "г(N) не равно ф(M, M)". Тем самым, мы тривиально устанавливаем, доказываем саму Ф. Если мы хотим доказуемости Ф, то должны приписать "г(N) равно ф(M, M)", и снова приходим к противоречию. Но мы должны приписать или "г(N) не равно ф(M, M)" или "г(N) равно ф(M, M)", что-то конкретное, иначе определение не будет определением. Отсюда находим только то, что данное определение не выполнимо (не имеет решения).

Интересно интерпретировать «парадокс лжеца», на содержании которого основана «теорема Гёделя», как непредикативное определение «утверждаемого лжецом». Утверждение «я лгу» можно интерпретировать так: «утверждаемое мною равносильно отрицаемому мною». Причём, так и не известно, что же в конце концов утверждает говорящий. Это утверждаемое есть X, определяемое непредикативно в форме: "X равносильно не X". Если эквивалентность "X равносильно не X" принять истинной лишь на том основании, что даётся определение X, то можно вывести, что истинной является как X, так и не X. По существу же, лжец лжёт.

Аналогично, можно непредикативно определить формулу Гёделя: как формулу эквивалентную утверждению о собственной недоказуемости. Т.е. Ф участвует в соотношении: "Ф равносильно не Prf(Ф)", где Prf(Ф) означает формулу: "Ф доказуема". В итоге, если мы определяем формулу Гёделя неконструктивно, через соотношение "Ф равносильно не Prf(Ф)", то просто выводим, что такой формулы нет. Если пытаться конструктивно определить Ф, надеясь выполнить указанное соотношение, то придём к противоречию в процессе определения, выводимому уже из самого соотношения, которому стремится удовлетворить определение.

Приводимы к противоречию все другие известные формулировки «теоремы Гёделя». Так в [4] даётся непредикативное определение гёделевой формулы, которое само по себе – тождественно ложная формула. Определяемые в [2] функции заданы противоречивыми алгоритмами, и не являются, поэтому, рекурсивными. И т.п.

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

В итоге, «теорема Гёделя» не является даже правдоподобной гипотезой, не говоря уже о том, чтобы быть теоремой.

Безусловно, существуют трудноразрешимые математические задачи. Однако, они трудно разрешимы чаще не по тем причинам, которые выставляет формалистская школа. Формулируемые «парадоксы» могут быть обойдены при другом содержательном подходе, т.е. не являются необходимыми.

ЛИТЕРАТУРА ПО «ТЕОРЕМЕ ГЁДЕЛЯ»

1. Gödel. K. Über formal unentscheidbare Sätze der Principina Mathematica und verwandter Systeme, Monatsh für Math. U. Phys., XXXVIII (1931), 173-198.

2. Коэн. Пол.Дж. Теория множеств и континуум-гипотеза. М. 1969.

3. Гильберт Д, Бернайс П. Основания математики. Теория доказательств, М. 1982.

4. Успенский В.А. теорема Гёделя о неполноте. М., 1982.

ВНИМАНИЕ! см. также мой пост, названный ПОСТ №2.

[ewert]

Вырываю из контекста:

Инт в сообщении #151736 писал(а):

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

Бесконечно малых или там больших в природе не встречается. Встречаются лишь процессы, которые на интуитивном уровне интерпретируются как бесконечно малые и большие. И эти процессы (при всей их малости или даже великости) ведут себя совершенно по-разному. Следовательно, попытки "нестандартного анализа" аксиоматизировать понятие "бесконечно малой" выглядят абсолютно неадекватно. С чисто практической точки зрения.

[Инт]

ewert-у

Хотел бы, чтобы обсуждение коснулось собственно "теоремы Гёделя"

[Xaositect]

Инт в сообщении #151736 писал(а):

Само слово «математика» можно перевести как «знание».

"Учение", "научение"

Инт в сообщении #151736 писал(а):

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

Эта функция может быть написана на рассматриваемом языке, и именно поэтому является эффективной.

Инт в сообщении #151736 писал(а):

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

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

Инт в сообщении #151736 писал(а):

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

Приведите.

Добавлено спустя 9 минут 3 секунды:

Если Вы хотите привести контрпример, то давайте рассмотрим конкретное доказательство, например, приведенное параграфе 1 главы III учебника Колмогорова и Драгалина "Математическая логика. Дополнительные главы": http://www.poiskknig.ru/cgi-bin/poisk.c ... &network=1
Приведите абзац, в котором содержится ошибка, и объясните. в чем она состоит.

[маткиб]

Инт в сообщении #151736 писал(а):

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

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

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

Инт в сообщении #151736 писал(а):

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

Действительно, пусть предположение о доказуемости формулы Ф уже приведено к противоречию безусловно, т.е. из аксиом гёделевой арифметики (например, так, как это сделано выше). Выводим отсюда безусловно, т.е. как формулу гёделевой арифметики, что "Ф недоказуема". Тогда, каждый натуральный номер n не может быть номером доказательства для формулы Ф. Тогда, по определению г, "для каждого n верно, что ф(M, M) не равна г(n)". Т.е. верна формула "не существует n (ф(M, M) = г(n))", т.е. верна Ф. Это есть вывод формулы Ф из аксиом гёделевой теории арифметики. Вывод имеет конкретный гёделев номер. Выводим отсюда, что Ф доказуема.

Нет, отсюда мы только делаем вывод, что доказуемо "(Ф не доказуема)->Ф", потому что вывод мы построили именно для этого утверждения, а не для Ф.

[AD]

Инт в сообщении #151775 писал(а):

Хотел бы, чтобы обсуждение коснулось собственно "теоремы Гёделя"

А вот эти беспочвенные утверждения предпочтёте оставить без доказательства/обсуждения?:

Инт в сообщении #151736 писал(а):

1. Так «истиной» объявлены рассуждения Коэна и Гёделя, сводящиеся к выводу, что «континуум-гипотеза неразрешима в обычной теории множеств». Даже если это так, то те безалаберные рассуждения, которые предъявил Коэн, вообще не являются никаким доказательством выдвинутого им тезиса. Методом вынуждения можно доказать всё что угодно.

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

3. Из аксиомы выбора не следует – если доказательство поставить на строгую основу – возможность вполнеупорядочить каждое множество. Но обратное утверждает «школа».

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

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

[Инт]

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

[маткиб]

Инт в сообщении #151736 писал(а):

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

Замечу, что это предположение не приводится к противоречию из наших аксиом. В доказательстве теоремы Гёделя при приведении его к противоречию неявно испольуется факт "(Ф доказуема)->Ф", который из самих аксиом не выводится (а выводится из предположения о корректности теории, т.е. того, что доказать можно только истинные утверждения).

[Инт]

маткиб-у

Цитата:

Нет, отсюда мы только делаем вывод, что доказуемо "(Ф не доказуема)->Ф", потому что вывод мы построили именно для этого утверждения, а не для Ф

Цитата:

В доказательстве теоремы Гёделя при приведении его к противоречию неявно испольуется факт "(Ф доказуема)->Ф", который из самих аксиом не выводится (а выводится из предположения о корректности теории, т.е. того, что доказать можно только истинные утверждения).

Второе замечание, по делу. Утверждение "(Ф доказуема)->Ф" конечно же предполагается содержащимся в аксиомах теории. И использование его мною происходит не неявно, а явно. Это утверждение означает, что всегда, когда формула доказана она истина. Если это утверждение не является теоремой (в частности аксиомой) теории (арифметики), в которой рассматривается формула Гёделя, то мы имеем логически ограниченную теорию, т.е. такую, в которая содержит не классическую выводимость, где может отрицаться истинность формулы, не смотря на её доказуемость. Относительно такой не классической выводимости и доказуема тогда формула Гёделя. Следовательно, мы не можем делать обобщения на классическую арифметику. Гёделевская арифметика оказывается либо логически ограниченной, либо противоречивой. Могу дать ещё более тщательный вывод. Возможно я его дам для всех, так как поступили аналогичные вопросы.

Относительно вопроса первой цитаты, я его обдумаю. Однако, уже сейчас могу сказать, что мною приведён прямой вывод "Ф недоказуема", а не каких-то других утверждений. Утверждение, что мы должны сделать лишь вывод, что доказуемо "(Ф не доказуема)->Ф" пока мне не очень понятно. Обдумываю.

Добавлено спустя 33 минуты 21 секунду:

AD-у:

Цитата:

А вот эти беспочвенные утверждения предпочтёте оставить без доказательства/обсуждения?:

Утверждения эти не беспочвены. И мы обязательно их обсудим. Вижу по Вашим постам и постам других участников форума, что отвечать буду медленно. Возможно даже на обдумывание мне иногда потребуется один два дня (скажем, чтобы обратиться к книге, к которой меня высылают). Прошу задавать вопросы по тексту более технично и конкретно. Например, вопросы маткиб-а мне понравились техничностью. Начнём с 5 пункта.

маткиб-у:

Цитата:

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

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

Не совсем ясно, какую роль должны играть не завершаемые алгоритмы в отрицании моего утверждения. Можете ли уточнить примером?

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

[маткиб]

Инт в сообщении #151800 писал(а):

Утверждение "(Ф доказуема)->Ф" конечно же предполагается содержащимся в аксиомах теории.

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

Добавлено спустя 12 минут 22 секунды:

Инт в сообщении #151800 писал(а):

Итак, алгоритмов счётное множество. Они описаны в каком-то языке. Язык этот должен быть перечислим, например, в силу определения, что есть "эффективное". Алгоритмы, в этой связи, можно упорядочить и перечислить. Ясно, что сама функция перечисления, не описывается в том языке, не существует среди алгоритмов данного языка, т.е. не существует в теории, в которой описываются остальные алгоритмы.

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

[Инт]

маткиб-у:

Только хотел ответить другому, третьему участнику темы. Но отвечаю Вам оперативно.

Такую теорию строить не надо. Либо указанная Вами схема аксиом (ещё можно добавить: правило вывода) содержится в арифметике, выстриваемой Гёделём как аксиома, либо нет. Если первое, то такая арифметика противоречива. Если второе, то логически ограничена. Это на:

Цитата:

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

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

[маткиб]

Инт в сообщении #151819 писал(а):

Такую теорию строить не надо. Либо указанная Вами схема аксиом (ещё можно добавить: правило вывода) содержится в арифметике, выстриваемой Гёделём как аксиома, либо нет. Если первое, то такая арифметика противоречива. Если второе, то логически ограничена. Это на:

Цитата:А вы пробовали построить такую теорию, в которой такая аксиома (точнее, схема аксиом) содержится? Попробуйте и убедитесь, что у вас ничего не получится. Просто при добвлении аксиомы и понятие доказуемости изменится, поэтому аксиому придется модифицировать.

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

Добавлено спустя 20 минут 18 секунд:

Как я понял, вы говорите про какую-то "арифметику, выстраиваемую Гёделем". Что это за арифметика такая? Сила теоремы Гёделя как раз в том, что она доказывается для ЛЮБОЙ арифметики, а не для какой-то там, которую он сам выстраивает. Единственное накладываемое ограничение: должен существовать алгоритм (компьютерная программа), проверяющий доказательства.

Добавлено спустя 1 час 2 минуты 33 секунды:

Ах вот ещё где собака зарыта:

Инт в сообщении #151800 писал(а):

Утверждение "(Ф доказуема)->Ф" конечно же предполагается содержащимся в аксиомах теории. И использование его мною происходит не неявно, а явно. Это утверждение означает, что всегда, когда формула доказана она истина. Если это утверждение не является теоремой (в частности аксиомой) теории (арифметики), в которой рассматривается формула Гёделя, то мы имеем логически ограниченную теорию, т.е. такую, в которая содержит не классическую выводимость, где может отрицаться истинность формулы, не смотря на её доказуемость. Относительно такой не классической выводимости и доказуема тогда формула Гёделя. Следовательно, мы не можем делать обобщения на классическую арифметику.

Так вот, выделенное жирным вовсе не означает наличие аксиомы или правила вывода "(Ф доказуема)->Ф". Выделенный текст вообще не имеет отношения к каким-либо аксиомам или правилам вывода, это всего лишь разумное допущение, основанное на том, что аксиомы придумывались не от балды, а на основе представлений о реальном мире. Вообще, выражение "(Ф доказуема)->Ф" - это импликация, правая часть которого - формула Ф, а левая - достаточно сложная формула, выражающая наличие текста, являющегося доказательством для Ф.

Поэтому с вас пример корректной формальной теории, в которой для любой формулы Ф можно доказать "(Ф доказуемо)->Ф".

[Инт]

Xaositect-у:

Цитата:

Эта функция может быть написана на рассматриваемом языке, и именно поэтому является эффективной

В одном из постов я пояснил, что функция перечисляет все алгоритмы некоторой фиксированной теории. Следовательно, не принадлежит этой теории. Я могу использовать в создании этой функции другой язык.

Цитата:

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

Я нигде и не утверждал, что это любая теория. Ясно, что она должна содержать ту, о которой вы говорите.

Цитата:

Учение", "научение"

"Математика" с греческого переводится как "знание", см. энциклопедию.

Цитата:

Если Вы хотите привести контрпример, то давайте рассмотрим конкретное доказательство, например, приведенное параграфе 1 главы III учебника Колмогорова и Драгалина "Математическая логика. Дополнительные главы":

Информацию понял. Буду думать, что ответить. Может быть вы приведёте хотя бы канву рассуждения, которое я по Вашему мнению должен опроовергнуть. Вдруг я с таким рассуждением соглашусь.

Добавлено спустя 12 минут 28 секунд:

маткиб-у

Цитата:

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

Именно так, как вы пишите. Гёдель формулирует некоторую теорию, которую неоправдано отождествляет с классической арифметикой. Именно такая арифметика Гёделя мною имеется ввиду. Именно она противоречива, так как противоречит фундаментальной логической аксиоме, если последняя введена в арифметику. Если такая аксиома не считается введённой в арифметику Гёделя, то мы получаем логически усечённую теорию арифметики, и не можем говорить о ней как о классической теории арифметики. Т.е. не можем переносить с усечённой теории выводы, которые сделал Гёдель и отстаивают его последователи, на классическую арифметику.

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

Добавлено спустя 15 минут 45 секунд:

ПОСТ №2

Xaositect-у, маткиб-у и другим.

маткиб-у: посмотрите ещё раз ПОСТ №1, там содержится доказательство (содержательное, в первом приближении) средствами теории арифметики, которую Гёдель отождествляет со своей теорией, того, что формула Ф недоказуема в такой арифметике. При доказательстве используется аксиома, что из доказуемости формул должна вытекать их истинность. Эта аксиома должна приниматься любой естественной теорией арифметики.

§5

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

T – теория, в которой даются все нижеследующие определения (метатеория).

S – теория, интерпретируемая средствами теории T. Это означает, что в T: определяются отношения и функторы для теории S; доказываются теоремы, которые суть – аксиомы теории S.

В результате, средствами T даётся определение, что означает «формула принадлежит S». Теория здесь отождествляется с множеством формул, функторов и т.п., которые в ней могут быть сформулированы или заданы, и тем самым, содержатся. Если Ж – формула, то «(Ж принадлежит S) влечёт (Ж принадлежит T)», обратная импликация, вообще говоря, неверна. Если M – теория, Ж – формула, то считаем, что выражение «Ж есть M-формула» означает то же, что и «Ж принадлежит M».

В качестве S формулируем арифметику, называемую здесь GA – «арифметикой Гёделя». В теории S так или иначе можно говорить: о доказуемости S-формул, о гёделевых номерах S-формул, о гёделевых номерах цепочек S-формул, о гёделевых номерах доказательств. Для этого, средствами T определён оператор Prf так, что если Ж есть S-формула, то Prf(Ж) – так же S-формула, означающая, что «Ж доказуема средствами S». При этом, «гед.ном.(Ж)» означает гёделев номер формулы Ж. Если W – цепочка S-формул, то «гёд.ном.(W)» означает гёделев номер цепочки W.

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

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

Арифметику Пеано обозначим PA. Эту теорию можно выбрать в качестве теории T, а можно отождествить с S = GA, как это делается в некоторых математических работах. Мы рассмотрим оба случая. В последнем случае, обозначение PA не справедливо, так как Пеано рассматривал свою арифметику совершенно в другом контексте. Естественнее считать, что PA = CA.

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

§6

S-вывод формулы Ж – это цепочка S-формул, являющаяся выводом формулы Ж (т.е. выводом в теории T) из посылок, которые суть S-формулы.

S-теорема – это такая формула, которая стоит в конце хотя бы одного S-вывода из аксиом теории S (S-аксиом). S-доказательство или безусловный S-вывод – это такой S-вывод, посылки которого суть S-теоремы. Если S-вывод не является безусловным, то он является условным S-выводом.

Аналогично определяется T-вывод, T-доказательство и т.п. Каждый S-вывод является одновременно T-выводом. Обратное не верно. Каждая S-теорема есть T-теорема, но не обратное.

В теории S гёделевы номера формул даются только S-формулам, гёделевы номера цепочек формул, выводов и доказательств даются только цепочкам S-формул, только S-выводам и только S-доказательствам соответственно. Функтор, ставящий в соответствие каждой S-формуле её гёделев номер, принадлежит S. Аналогично, принадлежат S функторы, перечисляющие цепочки формул, выводы и доказательства.

В теории S вводится логическое правило вывода: если вывод формулы Ж есть S-доказательство, то мы можем отсюда заключить, что верна формула Prf(Ж).

Средствами T в теории S определяется множество формул «верных в S». Каждая числовая формула из T считается либо «верной в T», либо «неверной в T», т.е. попросту верной ли или неверной, вне зависимости от её доказуемости в T. Предполагается, что так или иначе возможно верифицировать каждую формулу. Это интуитивное требование (аксиома) классической логики. Формула теории S считается «верной в S», если эта формула верна в T, т.е., если попросту она верна. В частности, каждая S-теорема считается «верной в S». Однако, в смысле данных определений, если формула верна в S, то это не означает, что она S-теорема, т.е., что она безусловно выводима из аксиом теории S.

Замечание. Если Ж есть S-формула, полученная в результате вывода, среди посылок которого содержится формула не принадлежащая S, то мы не можем отсюда заключить средствами теории S, что Prf(Ж) верна, даже если в T формула доказуема. Таким образом, мы не сможем средствами S установить Prf(Ж) как теорему теории S. Этим, в частности, множество T-выводов отличается от множества S-выводов. Мало того, если Ж получена в результате S-вывода из теорем теории T, но хотя бы одна из посылок не является теоремой теории S (такая посылка может быть недоказуемой, но верной в S формулой), то мы не можем применить к формуле Ж определённое выше правило вывода и заключить средствами теории S, что Prf(Ж) верна, т.е. не можем установить Prf(Ж) как теорему теории S.

§7

Для вывода противоречия в теории S нам потребуются два утверждения.

1. Какова бы ни была S-формула Ж, средствами теории S из доказуемости Ж можно извлечь, что Ж верна. Т.е., в S верна аксиома: «Prf(Ж) влечёт Ж» (схема аксиом). Эта аксиома может быть заменена на некоторое эквивалентное правило вывода.

2. Существует формула Ф из S такая, что средствами теории S доказуемо, что «Ф равносильна формуле неPrf(Ф)».

Утверждение 2 доказывают, предполагая, что завершено определение предиката Prf. Пусть sb(n, m) – гёделев номер формулы, полученной подстановкой номера m вместо свободной переменной в такую формулу с одной свободной переменной, гёделев номер которой есть n. Функтор sb всегда определим в S, посредством аксиом S. Пусть U – S-формула, z – единственная свободная переменная этой формулы. Рассмотрим формулу U(sb(x, x)), где x – свободная переменная. Пусть, гёд.ном.(U(sb(x, x))) = L. Определим в качестве V формулу U(sb(L, L)). По определению sb: гёд.ном.(V) = гёд.ном.(U(sb(L, L))) = sb(L, L). Следовательно, V равносильна U(sb(L, L)) равносильна U(гёд.ном.(V)). В теории S определён предикат Pr(z) означающий: «доказуема формула с гёделевым номером z». Тогда, если X – S-формула, то Prf(X) введём как S-формулу Pr(гёд.ном.(X)). В качестве Ф возьмём формулу V, для которой U есть неPr, ч т.д.

Выведем противоречие, предполагая, что аксиома, указанная в 1, есть S-теорема. Действительно. Предположим, рассуждая в S, что Ф доказуема средствами S, т.е. в S предположим, что верно Prf(Ф). По указанной аксиоме получаем, что в S верна Ф. Тогда, из утверждения 2, (таким образом, средствами S) извлекаем, что верно неPrf(Ф). Это противоречие. Следовательно, предположение о доказуемости Ф неверно. Следовательно, (это вывод из аксиом S) верно неPrf(Ф). Но тогда, по утверждению, указанному в 2, верна Ф. Это S-доказательство формулы Ф. Применяя правило вывода из §6, получаем, что верна Prf(Ф). Снова противоречие.

Если аксиома, указанная в 1, не является теоремой S, то она должна быть хотя бы теоремой теории T (иначе, по крайней мере, простым путём, в T недоказуема недоказумость Ф, т.е. не установима собственно «теорема Гёделя», см. далее), причём эта теорема одновременно есть S-формула. Возможно так же, что в S не допустимы «рассуждения от противного». Тогда, уже средствами T, можно снова повторить приведённый выше вывод и придти к утверждению «о безусловной недоказуемости формулы Ф средствами S» – в качестве теоремы теории T, но не как S-теоремы. Из недоказуемости Ф в S извлечём истинность Ф (в силу 2). Этим установим истинность Ф S-выводом, но в силу замечания §6, не можем перейти к утверждению о верности Prf(Ф). Т.е. устанавливаем истинность Ф и одновременно не приходим к противоречию. Интересно, что при полной расшифровке, формула Ф даже графически совпадает с формулой неPrf(Ф) и выражает средствами T «недоказуемость» Ф в S.

Из такого рода «недоказуемости» формул Ф и неФ в S делают вывод (если T непротиворечива), что теория S непротиворечива (иначе все формулы выводимы) и неполна (обе формулы Ф и неФ не выводимы в S). Мало того, делают вывод, что «достаточно богатая непротиворечивая теория» должна содержать S, а потому, такая теория должна быть неполна. Поэтому, думают, что «все достаточно богатые теории или неполны, или непротиворечивы».

§8

Однако, если мы не признаём утверждение «Prf(Ж) влечёт Ж» в качестве аксиомы (схемы аксиом) теории S, или не допускаем «рассуждения от противного», то и не можем говорить о том, что доказали классическую не выводимость Ф. В самом деле, доказана не выводимость Ф в теории S, которая почему-то отождествляется с PA, но в которой, например, запрещено извлекать из доказуемости формул их истинность. Это означает, что, отрицая аксиому «Prf(Ж) влечёт Ж», мы рассматриваем усечённую, неклассическую «доказуемость». Относительно такой «доказуемости» и устанавливаем «недоказуемость формулы Ф». Получаем, что в S потеряны логические операции, ради которых создавалась S, и которыми располагает любая естественная теория. Таким образом, в содержательной интерпретации гёделева арифметика либо логически ограничена, либо противоречива.

Если считать, что T совпадает с PA, то выводы не изменятся. Чем бы ни были T и S, выводим или противоречие в S, или логическую ограниченность S.

Утверждая аксиому «Prf(Ж) влечёт Ж», приходим к отрицанию «Ф равносильна неPrf(Ф)». Т.е. ставим под сомнение гёделево определение «доказуемости» Prf, которое непредикативно и противоречиво.

В итоге, «первая теорема о неполноте», при содержательной интерпретации теории S, не может претендовать на доказанность. Так же и «при арифметической интерпретации теоремы», т.е. тогда, когда считается, что Ф чисто арифметическая формула, и отрицанию аксиомы «Prf(Ж) влечёт Ж» придаётся арифметический, а не логический смысл. В самом деле, Ф не входит в множество формул теории S, которые интерпретируются как высказывания обычной арифметики, поскольку, эти последние не используют предикат Prf, и не образуют всей S. Таким образом, в данной интерпретации Ф находится вне множества формул классической арифметики. Следовательно, гёделев вывод не касается классических формул арифметики, не влечёт того, что в достаточно развитой классической арифметике есть неразрешимая формула.

С другой стороны, «в арифметическом смысле», который приписывает формуле Ф теория T, Ф может быть формулой классической арифметики тогда, когда классическая арифметика отождествляется с T. Но Ф классически доказуема в метатеории T (при условии отрицания аксиомы «Prf(Ж) влечёт Ж» в S; если эта аксиома определена в S, то T противоречива).

§9

Нет необходимости использовать логику, искусственно ограничивающую способы доказательств, всегда можно перейти к определениям, так или иначе тривиально разрешающим Ф. Мы так же можем настаивать на аксиоме «Prf(Ж) влечёт Ж», которая порождает множество формул, не содержащее «гёделеву формулу». Почему нельзя использовать подобные переопределения всякий раз, когда предъявлена «неразрешимая гёделева формула»? Почему теория с аксиомой «Prf(Ж) влечёт Ж» не может быть полной? Новые определения, кроме «разрешения Ф», не уменьшат «богатства» S. С другой стороны, некоторые из таких определений вернут всё в рамки классической логики. Иными словами, вообще нет проблемы «разрешения формулы Ф» в плане практического знания, т.е. «узнавания, что же на самом деле». Если не выдумывать причины, по которым достаточно тривиальная формула неразрешима. Но почему именно эта формула? С таким же успехом, можно придумать причину, по которой не доказуемо, например, что 5 простое число.

Добавлено спустя 11 минут 42 секунды:

AD-у:

Так как поле Ваших вопросов обширно. Прошу конкретизировать.

[маткиб]

Инт в сообщении #151936 писал(а):

В одном из постов я пояснил, что функция перечисляет все алгоритмы некоторой фиксированной теории. Следовательно, не принадлежит этой теории. Я могу использовать в создании этой функции другой язык.

А вас не смущает существование интерпретаторов программ, например, на бейсике? Которые тоже являются программами.

Добавлено спустя 1 час 18 минут 59 секунд:

Инт в сообщении #151936 писал(а):

Однако, если мы не признаём утверждение «Prf(Ж) влечёт Ж» в качестве аксиомы (схемы аксиом) теории S, или не допускаем «рассуждения от противного», то и не можем говорить о том, что доказали классическую не выводимость Ф.

Вы так и не предъявили хотя бы одну теорию, в которой эта аксиома выполняется.

Это хорошо сказать, что типа пусть у нас есть такая аксиома и всё тут. Но нельзя же забывать, что $\mathrm{Prf}$ у нас не просто значок, а отображение, которое каждой формуле ставит в соответствие формулу, и это отображение, вообще говоря, зависит от самой теории (потому что доказуемость мы рассматриваем именно в этой теории). Лучше во избежание недоразумений вместо $\mathrm{Prf}$ использовать значок $\mathrm{Prf}_T$. Тогда вам нужно предъявить теорию $T$, в которой для любой формулы $\Phi$ выводится $\mathrm{Prf}_T(\Phi)\rightarrow\Phi$. Это уже уравнение, неизвестным в котором является $T$. Которое, как я утверждаю, не имеет решений.

Добавлено спустя 23 минуты 55 секунд:

Инт в сообщении #151936 писал(а):

Почему нельзя использовать подобные переопределения всякий раз, когда предъявлена «неразрешимая гёделева формула»?

В принципе, это делать можно. Например, можно взять базовую теорию $T_0$, например, арифметику Пеано. Потом построить последовательность теорий $\{T_n\}$:
$T_{n+1}=T_n+(\forall\Phi)(\mathrm{Prf}_{T_n}(\Phi)\rightarrow\Phi)$
(имеется в виду добавление той самой злосчастной схемы аксиом), затем взять объединение, получится новая теория $T_{\omega}$:
$T_{\omega}=\bigcup_{n}T_n$,
потом продолжить этот процесс: $T_{\omega+1}=T_{\omega}+(\forall\Phi)(\mathrm{Prf}_{T_{\omega}}(\Phi)\rightarrow\Phi)$, $T_{\omega+2}=T_{\omega+1}+(\forall\Phi)(\mathrm{Prf}_{T_{\omega+1}}(\Phi)\rightarrow\Phi)$, .... Таким образом можно ординалам ставить в соответствие теории. Но если пытаться формализовать сразу весь этот процесс, вы потерпите неудачу. Аналогично тому, что не существует множества всех ординалов. Короче, это процесс творческий. Кстати, это всё уже давно исследовано, этим чуть ли не Тьюринг занимался.

Инт в сообщении #151936 писал(а):

Иными словами, вообще нет проблемы «разрешения формулы Ф» в плане практического знания, т.е. «узнавания, что же на самом деле».

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

[Инт]

маткиб-у

Цитата:

Вы так и не предъявили хотя бы одну теорию, в которой эта аксиома выполняется. Это хорошо сказать, что типа пусть у нас есть такая аксиома и всё тут...

Мною приведено доказательство. Доказательства абсолютны или это не доказательства.

В доказательстве, я задаю Вам вопросы пошагово, и на каждом шаге требую ответ:

Вы фиксировали теорию арифметики, в которой считаете существует формула Гёделя, и которая претендует быть "настоящей арифметикой"? Да, Нет?

Употребляется ли в этой теории предикат Prf (пусть даже он обозначается как у Вас, в моих рассуждениях теория не меняется)? Да, Нет?

Является ли оспариваемая Вами аксиома (из доказуемости вытекает истинность) аксиомой фиксированной ранее теории? Да, Нет?

Если в последнем вопросе Вы отвечаете Да, то противоречие. Если Нет, то Вы не можете говорить, что у Вас фиксирована адекватная теория арифметики. Т.е. в обоих случаях теория арифметики Гёделя неадекватна.

Что же касается предъявления теории, о которой вы говорите, то непредъявление такой теории никак не отменяет моих рассуждений. Моих рассуждений не отменяет и зачем-то выстраиваемая Вами иерархия теорий (это не по делу). Я задаю вопрос о полноте некоторой возможной теории именно потому, что уже мною в доказательстве установлена неадекватность гёделевских построений. Ваши рассуждения относительно возможной иерархии вероятны, и есть только лишь предположения, а мой вывод в ПОСТАХ 1 и 2 точен абсолютно.

Такое ощущение, что Вы читаете мои пояснительные посты или только пояснительную часть текста в ПОСТАХ 1 и 2, и, видимо, не прочли внимательно полные доказательства в ПОСТАХ 1 и 2, где все аргументы.

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

По Вашей просьбе укажу как построить требуемую Вами теорию. Повторяю, это никак не влияет ни на отрицание, ни на подтверждение моих выводов, т.е. вопрос Ваш не по существу дела: Считаем, что формула Гёделя присоеденена к арифметике в качестве аксиомы изначально. Поэтому, существует (возможно не один) номер N доказательства для Ф. Для функтора г, о котором говорится в ПОСТЕ №1, переопределяем г(N) = 0, не смотря на то, что N - номер доказательства, для остальных номеров доказательств значения г оставляем прежними. Тогда: 1) формула Гёделя тривиально разрешима; 2) богатство теории от этого очевидно не пострадает; 3) будет снято противоречие, о котором я говорю.

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

Добавлено спустя 8 минут 34 секунды:

Цитата:

А вас не смущает существование интерпретаторов программ, например, на бейсике? Которые тоже являются программами.

Не смущает. Это не отменяет моих рассуждений.