Теорема Гёделя и формальные системы

[ptQa]

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

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

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

[Xaositect]

ptQa в сообщении #756738 писал(а):

Мой вопрос вот в чем. Сводима ли математика к логике?

Это вопрос философский, потому что в нем есть три неопределенных термина :)

ptQa в сообщении #756738 писал(а):

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

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

ptQa в сообщении #756738 писал(а):

готов пойти читать умные книжки если укажут какие.

В.А.Успенский "Теорема Гёделя о неполноте" (http://publ.lib.ru/ARCHIVES/P/''Populya ... '.html#057) Книжка старая, там непривычная терминология и странные обозначения (русские буквы используются), но очень хорошая.
Есть популярные лекции по теме: http://www.mathnet.ru/php/presentation. ... sentid=122

[Sonic86]

ptQa в сообщении #756738 писал(а):

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

И теряем часть теорем? А зачем? Теорема Гудстейна Вам не нравится?

ptQa в сообщении #756738 писал(а):

готов пойти читать умные книжки если укажут какие.

Вообще, доказательство есть в Мендельсоне Введение в матлогику. Но если Вы биолог, то Вам будет сложно.

[nikvic]

ptQa в сообщении #756738 писал(а):

нельзя ли создать такую формальную систему в которой принципиально невозможно сформулировать утверждения Гёделя.

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

[Stan Slapenarski]

ptQa

Цитата:

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

Собственно, и мой ответ не особо авторитетный, поскольку я не логик, и, вероятно, Xaositect разбирается в этом лучше меня.

Цитата:

Сводима ли математика к логике? Гёдель вроде бы показал что нет.

Xaositect писал(а):

Это вопрос философский, потому что в нем есть три неопределенных термина :)

Я полагаю, что нет, но Теоремы Гёделя тут ни при чем, а потому, что математическая интуиция, являющаяся фундаментом математики (во всяком случае для меня, как для работающего математика), несводима к логической интуиции. Даже гораздо более скромная программа Бурбаки аксиоматизации архитектуры математики представляется мне хоть и благой, но довольно утопичной. Еще формалистскую философию математики критиковали, например, Анри Пуанкаре и Имре Лакатос (см. введение в его книгу «Доказательства и опровержения. Как доказываются теоремы»)

Цитата:

но готов пойти читать умные книжки если укажут какие.

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

Sonic86 писал(а):

Вообще, доказательство есть в Мендельсоне Введение в матлогику. Но если Вы биолог, то Вам будет сложно.

Лично я как-то не перевариваю этого Мендельсона, меня не устраивает его уровень строгости и ясности. Кстати, вот он.

Цитата:

но нельзя ли создать такую формальную систему в которой принципиально невозможно сформулировать утверждения Гёделя. Ведь Рассел успешно решил проблему парадокса множеств введением теории типов. Казалось бы вводим еще одну подобную аксиому, которая делает невозможным формулировать такие предложения, как сделал Гёдель.

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

Ну, определить натуральные числа, и даже с операцией их сложения, можно и в непротиворечивой, полной и разрешимой теории (т.н. арифметике Пресбургера), однако уже с введением умножения в формальную систему связаны проблемы. (см. с.67-70 книги Подниекса). Для каждого непротиворечивого рекурсивно аксиоматизируемого расширения формальной арифметики $S$ существует предложение, неразрешимое в нем (т.е. замкнутая формула, невыводимая и неопровержимая) (см. Следствие 3.34 из книги Мендельсона).

[b2L]

Цитата:

Сводима ли математика к логике?

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

[nikvic]

b2L в сообщении #757160 писал(а):

Логик много и все можно вывести одну из другой.

Ерунда.
Пятницо кончилось.

[b2L]

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

То, что логики должны быть эквивалентны-понимается кожей...разум подсказывает...так должно быть...так красиво...так гармонично...Та же идея великого объединения думаете откуда? Опять же из ощущения, что так должно быть...а вы говорите ерунда...Так считал Аристотель, так считал Платон, так считали Все, кто вам дорог из великих логиков и математиков и только ВЫ говорите что это ерунда...
Интуиция большинство действительно умных людей не обманывает...на то они и умные.
Тот же Марков выдвинул тезис о том, что его логика приводится к классической думаете почему? Он понимал что так красиво, так должно быть...но не смог этого доказать. А почему? Ума не хватило.

Кстати, у Геделя есть еще одна теорема "о полноте" формальной логики как системы. Из свойств полноты в частности вытекает, что любой закон формальной логики выводится из других ее законов.
По индукции, из этого следует, что все логики доказываются из других.

[Mopnex]

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

[Deggial]

b2L, предупреждение за попытку захвата темы

[ptQa]

Всем спасибо за ответы, буду думать и читать умные книжки :)

[arseniiv]

(Оффтоп)

ptQa в сообщении #756738 писал(а):

Ведь Рассел успешно решил проблему парадокса множеств введением теории типов.

Это можно сделать и без типов. В аксиоматике ZF(C) парадокс Рассела тоже не появляется.

[AndreUT]

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

Решил, что новую тему не стоит создавать для этого вопроса.

[Stan Slapenarski]

Цитата:

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

С удовольствием.

Цитата:

Но мне остается до сих пор непонятным, как такое утверждение формулируется в обычной геометрии. Был бы рад увидеть конкретные примеры :)

Аксиома параллельности Евклида.

[AndreUT]

Ну это понятно, что аксиомы - это как раз те вещи, которые мы принимаем без доказательств. Но хотелось бы услышать что-то более нестандартное.

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

Как связаны эти две формулировки? Недоказуемые и непротиворечивые и являются этими истинными недоказуемыми?