о противоречивости арифметики пеано (математическое)

[avva]

Эдвард Нельсон, профессор Принстонского университета, объявил, что он доказал противоречивость арифметики Пеано (PA) (Update: если страница не открывается, то вот кэш-версия). Он выложил эскиз своего доказательства; полное и строгое доказательство он все еще пишет, и собирается выкладывать его по частям вместе с формальной проверкой с помощью программы, которую он сам написал.

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

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

P.S. Можно помечтать о том, что будет, если ошибки нет. Конечно, это тогда автоматически самый знаменитый и важный результат в логике за последние сто лет, и немедленный кризис в основаниях математики. Если PA противоречива, то и теория множеств, на которую опирается вся современная математика, тоже противоречива. Будет кризис в основаниях математики, похожий на тот, что случился с открытием парадокса Расселла. Нужно будет заменить теорию множеств на такую, которая все еще достаточно мощна, чтобы поддерживать современную математику, но не доказывает полную неограниченную индукцию в арифметике. Не факт, что это будет просто сделать. "Обычные" математики, не связанные с логикой, конечно, особенно волноваться не будут, как не волновались они и 100 лет назад. Но все равно, если это верно, то гигантской важности результат.

P.P.S. Обсуждение в блоге Джона Баэза.

Comments

[bespechnoepero.livejournal.com]

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

[kirenenko.livejournal.com]

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

[bespechnoepero.livejournal.com]

спасибо. хотя с натуральными числами тут не все ясно. ряд натуральных чисел - бесконечен, то есть включает в себя бесконечно большое число. если для конечных чисел справедливо m+1=n, то для бесконечно большого числа M+1=M. впрочем, я не совсем уверен, что в случае бесконечно большого числа можно использовать знак равенства, да и вообще производить с ним арифметические операции.

[kirenenko.livejournal.com]

с натуральными числами тут не все ясно - именно. И дело не только в том, что их бесконечно много. Они упорядочены очень загадочным способом. С одной стороны этот способ очень естественный: для любого числа мы немедленно можем указать следующее. С другой стороны, если мы можем до ЛЮБОГО числа добраться за конечное число шагов (просто переходя к следующему), то почему, черт возьми, мы не можем исчерпать их ВСЕ?
Простые арифметические действия сложения и умножения тоже скрывают загадочные свойства. Несмотря на то, что мы очень естественно определяем умножение как многократное сложение, свойства чисел по отношению к умножению оказываются неожиданно очень сложными и богатыми (делимость, простые числа). Мощь этих свойств и позволяет формальной арифметике описать саму себя и попасть в ловушку теорем Геделя. А заодно и поставить перед людьми невероятно сложные задачи в обычной математике (вроде гипотезы Римана).
Но я что-то расписался.