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

[avva]

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

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

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

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

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

Comments

обозримое и необозримое

[falcao.livejournal.com]

Вот это важный момент. Поверить в то, что автор может предъявить вывод "обозримой" длины из аксиом PA, я никак не могу. Потому что тогда анализ этого доказательства тоже занял бы "обозримое" время, и можно было бы "отловить" какой-то переход от чего-то условно "верного" к чему-то "неверному". Следует это примерно вот из какого соображения: если у нас есть "куча", то просто путём выбрасывания песчинок по одной мы можем не обнаружить ситуации, где n штук не образует "кучи", а n+1 уже образует. Но если мы начнём делить песок "пополам", то мы быстро к такому обнаружению придём.

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

Мне кажется, в самое ближайшее время всё должно так или иначе проясниться.

Re: обозримое и необозримое

[kirenenko.livejournal.com]

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