НГУ

Интервью филдсовского лауреата Владимира Воеводского в газете "Поиск".
Бальзам на душу всяческим разгильдяям , но весьма любопытно, особенно про основания математики. Интересно было бы почитать, если б кто-нибудь разбирающийся прокомментировал.
http://www.poisknews.ru/theme/science/1348/

А Вы какой комментарий хотите? ZFC исполнилось что-то около 100 лет, и попытки её "улучшить" широкую известность не приобрели. С одной стороны, её постулаты достаточно очевидны, и признаются математиками. С другой, всё, что признаётся доказанным, в итоге удаётся вывести из ZFC. Такое положение дел не располагает к новациям.

Что она алгоритмически плохо устроена, вполне вероятно, но тут надо смотреть, что именно В.Воеводский предлагает. С общих слов толку мало.

А вот весьма спорное (или провокационное-?) выступление лауреата на 80-летии института for advanced study в Принстоне.

_________________
Ненужность матана — не повод его не осилить

Да, Вы правы: интересно, что он предлагает. Можно ли это как-то неспециалистам объяснить?

На сколько я понимаю, он пока ничего не предлагает, он только собирается заняться основаниями математики. Где-то в конце 1997-го года Фридман писал на http://www.cs.nyu.edu/pipermail/fom/ , что основаниям математике надо специально учить, что учёным работающим в мэйнстриме математики не под силу получать достаточно глубокие результаты по основаниям---нужны специалисты именно в этой области. Там с Фридманом многие спорили на эту тему, в частности, Пилэй, Маркер, Барвайс, Балдвин и др. Случай с Воеводским мне кажется очень показательным: если ему удастся получить что-то действительно стоящее по основаниям, это немного покачнёт позиции Фридмана. На ФОМе, кстати, тоже обсуждают доклад Воеводского, многие относятся скептически.

_________________
Ненужность матана — не повод его не осилить

Лекцию, на которую сослался Alexandr, я не послушал; в частности, я плохо понимаю английский на слух. Но из Fom'овского обсуждения, где как раз собрались типа специалисты, так понял, что идеи Воеводского кажутся пока сырыми и немного дилетантскими.

В замечательном месте, Institute for Advanced Study, где он работает, можно заниматься чем угодно по своему усмотрению: возможно, что через некоторое время он погрузится в тему оснований математики глубже, и тогда...

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

Да, да, как я понял, цель у Воеводского именно такая---проверять доказательства на компе. И эта цель служит для него мотивом разобраться в основаниях математики, не обязательно ZFC. В докладе он объявляет совместность аксиом арифметики открытым вопросом (и даже намекает на то, что более вероятное его решение---отрицательное). Это явно проблема из оснований математики. И люди, считающиеся на сегодняшний день специалистами в этих самых основаниях, с ним не согласны. А `учить' основаниям предлагает Фридман, не Воеводский, Воеводский, кажется, совсем против того, чтобы кого-то учить математике (может, и не только математике).

_________________
Ненужность матана — не повод его не осилить

Кто ещё не видел, Воеводский ответил на FOM-е: `I think that in-consistency of Peano arithmetic as well as in-consistency of ZFC are open and very interesting problems in mathematics. Consistency on the other hand is not an interesting problem since it has been shown by Goedel to be impossible to proof.'

Сути дела это, конечно, не проясняет. Что подразумевается под `impossible to prove', равно как и под `it has been shown', непонятно.

_________________
Ненужность матана — не повод его не осилить

За эти высказывания его, в частности, и ругают: одна из теорем Гёделя говорит, что в PA (арифметике Пеано) невозможно доказать утверждение, говорящее о непротиворечивости PA. В ZFC непротиворечивость PA доказывается элементарно: легко выводится, что у PA есть модель, а имеющая модель теория не может быть противоречивой. Желание В.Воеводского свалить всё это в одну кучу у специалистов энтузиазма не вызывает.

Рассуждать о противоречивости PA - по крайней мере осмысленное занятие, но весьма неперспективное, по мнению опять же большинства специалистов. Это как дожидаться краха капитализма - можно, но через какое-то время надоедает.

Задача проверки теорем на компьютере - и осмысленная, и перспективная, но проблем противоречивости математики, как мне кажется, касается только косвенно. Например, скорее всего (хотя не буду настаивать) большинство теорем теории конечных графов можно доказать в PA, так как любой конечный граф можно с точностью до изоморфизма построить на натуральных числах, и свести всё к работе с числами. То есть вся ZFC, например, тут не нужна, и вопрос о её непротиворечивости не очень важен.

А можно в этом контексте пояснить для неспециалиста суть результата Лаврова И.А. (Эффективная неотделимость множества тождественно истинных и множества конечно опровержимых формул некоторых элементарных теорий // Алгебра и логика, 2 (1963), - № 1, - С. 5-18)? Вроде он дает как раз отрицательный ответ на предположение о "неинтересности" теории конечных графов.

Вот здесь есть примеры теорем теории (конечных) графов (Propositions A, B, C, D), недоказуемых в ZFC, но доказуемых в некоторых её расширениях, касающихся существования больших кардиналов.

_________________
Ненужность матана — не повод его не осилить

Если Вам интересно подробно обсудить этот результат, это можно сделать отдельно; но если говорить только про мой пост выше, то я совсем не хотел сказать, что теория конечных графов в каком-то смысле неинтересна, проста или малосодержательна. Это безусловно не так, и статья И.А. Лаврова это подтверждает.

Смысл был в том, что если мы хотим, например, проверять на компьютере доказательства в теории конечных графов, то в большинстве случаев можем ограничиться поиском доказательств в PA. А поскольку PA наверняка непротиворечива, то вопрос о противоречивости оснований математики оказывается тут вообще ни при чём. Точно так же во многих других областях математики используется лишь ограниченные фрагменты ZFC. Впрочем, он и в случае работы со всей ZFC не играет особой роли. Автоматический поиск доказательств на компьютерах - интересная область, в которой ключевыми являются другие проблемы.

Завтра по ссылке схожу, сегодня лень.

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

И, навереяка, всё зависит от того, какова сложность кванторной приставки у упомянутых утверждений. Если они , то их наверняка можно доказать (если они верны), если сложность --- наверняка можно опровергнуть в случае их ложности. Если же есть перемены кванторов, то с ходу ничего сказать нельзя. (У ВТФ, кстати, сложность , но её, к счастью, доказали. А какова, кстати, сложность утверждения , или меньше?)

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

P. P. S. Подскажите какие-нибудь "естественные" примеры элементарных подмоделей (на примере известных структур, а не те, которые получаются через теорему Левенгейма-Сколема или ультрапроизведение). Недавно семинар был по матлогике на эту тему. Я с ходу сообразил лишь насчёт и . Кто-нибудь знает ещё?

_________________
Don't let the sun blast your shadow
Don't let the milk float ride your mind

Это `естественный' пример?:

Пусть f и g---частичные функции k переменных из натуральных чисел в натуральные числа, такие, что для каждой из них существуют большие единицы константы c и d, такие, что почти для всех х, на которых f определена. Тогда существуют бесконечные подмножества множества натуральных чисел А, В, С, такие, что 1) 2) Здесь а операция определена и равна объединению, если множества не пересекаются, и неопределена иначе.






среди эренфойхтовых теорий много примеров;
среди -категоричных тоже, например, теория счётного числа констант.

P.s. bolbot, slb, похоже, пора отделить тему.

_________________
Ненужность матана — не повод его не осилить