Теоремы Гёделя.

[Eric Avagyan]

Возник вопрос касательно теорем Гёделя.А именно о тереме о неполноте и теореме непротиворечивости.
В общем,вопрос примерно такой:
1) "Теоремы Гёделя распространяются на любую формальную систему,либо на определённый класс формальных систем,либо на одну и вполне конкретную формальную систему-арифметику Пеано?".
Отсюда,соответственно,вытекает следующий вопрос:
2) "Если вариант ответа второй,то что такого общего у этих формальных систем?Если вариант третий,то что такого необычного именно в арифметике Пеано?".
Вопрос возник в связи с тем,что в различных источниках теоремы сформулированы по-разному.Где-то они начинаются примерно так:"В любой формальной системе...".Где-то написано так:"В любой достаточно богатой формальной системе...".Ну и наткнулся на один источник,где было написано что эти теоремы касаются лишь одной конкретной системы-арифметики Пеано (правда источник такой себе,это просто по сути ответ одного человека на каком-то форуме).
И да,чтобы не писать новое сообщение.Если ответ второй,а именно если теоремы распространяются на БОГАТЫЕ формальные системы,то почему?Во-первых,что подразумевается под "богатством"?Количество аксиом/количество возможных выводимых истин/что-то ещё?И как именно этот аспект влияет на неполноту такой системы и невозможности доказать в её рамках её же непротиворечивость?
Заранее замечу,что я не изучаю математическую логику.Я пытаюсь понять теоремы Гёделя на достаточно поверхностном уровне,рассматривая их лишь в рамках истории логики.

[Anton_Peplov]

Eric Avagyan в сообщении #1297666 писал(а):

Если вариант ответа второй,то что такого общего у этих формальных систем?

В максимальной (видимо) общности теорема Гёделя о неполноте сформулирована Клини в 1943 г.

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

Eric Avagyan в сообщении #1297666 писал(а):

заранее замечу,что я не изучаю математическую логику.Я пытаюсь понять теоремы Гёделя на достаточно поверхностном уровне,рассматривая их лишь в рамках истории логики.

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

[Xaositect]

Вариант второй. Теоремы о неполноте применимы к формальным системам логики первого порядка, которые удовлетворяют некоторым свойствам. Эти свойства часто формулируют как требование того, что в теории интерпретируется арифметика (не обязательно Пеано, достаточно Робинсона), но их суть в том, что теория может выступать в качестве метатеории, то есть некоторые ее объекты можно сопоставить формулам формального языка, определить некоторый предикат, который соответствует доказуемости формул, и доказать некоторые свойства этого предиката доказуемости (https://en.wikipedia.org/wiki/Hilbert%E ... conditions).

[epros]

Eric Avagyan в сообщении #1297666 писал(а):

Я пытаюсь понять теоремы Гёделя на достаточно поверхностном уровне,рассматривая их лишь в рамках истории логики.

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

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

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

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

[Pphantom]

Тема перемещена из форума «Дискуссионные темы (М)» в форум «Помогите решить / разобраться (М)»
Причина переноса: отсутствие дискуссионности.

[iifat]

epros в сообщении #1297717 писал(а):

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

Странно мне это как-то. Имея натуральные числа со сложением, что за проблема добавить туда умножение?

epros в сообщении #1297717 писал(а):

Современные доказательства теоремы Гёделя о неполноте строятся несколько иначе, они опираются на понятие алгоритмической вычислимости

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

[epros]

iifat в сообщении #1297754 писал(а):

Странно мне это как-то. Имея натуральные числа со сложением, что за проблема добавить туда умножение?

Язык не позволяет. В языке арифметики Пресбургера тупо нет значка для умножения. А если его добавить (вместе с двумя соответствующими акиомами, которые рекурсивно определяют умножение через сложение), то получится уже арифметика Пеано.

iifat в сообщении #1297754 писал(а):

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

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

[Anton_Peplov]

(Оффтоп)

epros в сообщении #1297717 писал(а):

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

Ну уж. В физике слово "теория" имеет несколько иное значение, чем в основаниях математики:))) В частности, там не фиксированы правила вывода. Рассуждай как хочешь, но предскажи результат эксперимента, и тебе всё простят. Даже если на ноль что-нибудь разделишь.

[mihaild]

(Оффтоп)

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

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

[arseniiv]

Anton_Peplov
mihaild
Я тоже не понимаю далеко идущих выводов о запрете теории всего, подписываюсь.

[george66]

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

[epros]

Anton_Peplov в сообщении #1297808 писал(а):

Ну уж. В физике слово "теория" имеет несколько иное значение, чем в основаниях математики:))) В частности, там не фиксированы правила вывода. Рассуждай как хочешь, но предскажи результат эксперимента, и тебе всё простят. Даже если на ноль что-нибудь разделишь

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

[warlock66613]

epros в сообщении #1297927 писал(а):

а физикам на математическую корректность да и на логику в целом плевать

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

[epros]

warlock66613 в сообщении #1297932 писал(а):

адекватность теорий первого порядка для формализации математики, мягко говоря, сомнительна

Это Вы про множественность моделей? А что делать, какова альтернатива?

[Anton_Peplov]

epros в сообщении #1297927 писал(а):

Признать раздвоение научного сознания за норму никак не могу.

Осталось уговорить Рокфеллера убедить физиков, что Вы лучше них знаете, какими должны быть физические теории.