Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/dfc/2012/reports/Pakhomov15.pdf Дата изменения: Sun Dec 27 14:18:56 2015 Дата индексирования: Sun Apr 10 12:14:11 2016 Кодировка: Windows-1251 Поисковые слова: m 5

Отчет по гранту фонда Династия за 2015 год. Ф.Н. Пахомов.

В работе [1] изучались системы ординальных обозначений на основе иерархии Кукаля. Иерархия Кукаля это иерархия (быть может бесконечных) ориентированных графов с ребрами покрашенными в конечное число цветов. Каждый граф G такого вида соответствует структуре A с семейством бинарных отношений, проиндексированным цветами данного графа для каждого цвета c, отношение Rc такого, что xRc y в A, если и только если в G имеется ребро цвета c из x в y . Монадическая теория структуры A это множество всех предложений с кванторами по элементам A и кванторами по унарным предикатам для A, которые истины в A. Известно, что все графы из иерархии Кукаля соответствуют структурам с разрешимыми монадическими теориями. Для некоторых графов один из цветов соответствует бинарному отношению, являющемуся полным линейным порядком. В таком случае, в силу разрешимости монадической теории, это вполне упорядочивание является рекурсивным, т.е. фактически задается конструктивная система ординальных обозначений. Одним из важных приложений конструктивных систем ординальных обозначений являются классификации доказуемо рекурсивных функций различных теорий. Для этого из конструктивных ординальных обозначений строят иерархии быстро-растущих рекурсивных функций. Все построения такого рода иерархий требуют некоторой дополнительной структуры на ординалах. Как правило, в качестве такой дополнительной структуры используются системы кофинальных последовательностей; такая система S это набор последовательностей [n]S с limn [n]S = для всех предельных ординалов из некоторого собственного начального отрезка счетных ординалов. Известным методом определения иерархий быстрорастущих функций на основе систем кофинальных последовательностей является быстрорастущая иерархия. Быстрорастущая иерархия для системы кофинальных последовательностей S это сеS мейство функций F (x) для всех из начального отрезка счетных ординалов, на котором определена S . Важным техническим свойством систем кофинальных последовательностей является свойство Бахмана. Если система S обладает S свойством Бахмана, то для всех < , значения функции F (x) с некоторого S момента становятся больше значений функции F (x). Предметом нашего исследования являлось изучение естественных систем кофинальных последовательностей для конструктивных систем ординальных обозначений, извлекаемых из иерархии Кукаля указанным выше образом. Для этих целей мы отождествляем систему кофинальных последовательностей S с бинарным отношением
Результаты, полученные в этом году.

RS предельный и = [n]S для некоторого n.
Тем самым, систему ординальных обозначений с системой кофинальных последовательностей мы задаем парой бинарных отношений. Мы доказываем, что если некоторый граф G лежал в n-ом уровне иерархии Кукаля и некоторый цвет в нем задавал полный линейный порядок, то 1

def


мы можем найти граф G из n-ого уровня иерархии Кукаля, обогащающий G новым цветом и ребрами нового цвета, такой, что бинарное отношение соответствующее новому цвету задает систему кофинальных последовательностей со свойством Бахмана для исходного полного линейного порядка. Мы изучали быстрорастущие иерархии на основе такого рода систем ординальных обозначений с системами кофинальных последовательностей. Нами было установлено, что для уровней до эти иерархии всегда слабо отличаются от стандартной быстрорастущей иерархии Леба-Вайнера. Хотя нам не удалось, в общем случае, для больших ординалов установить связь этих иерархий c иерархии Леба-Вайнера (в иерархии Кукаля имеются системы ординальных обозначений для всех ординалов меньших 0 ), но нами было установлено, что если имеются две системы кофинальных обозначений на одном графе из иерархии Кукаля, то быстрорастущие иерархии на их основе слабо отличаются.
Опубликованные и поданные в печать работы.

1. F. Pakhomov. Ordinal notations in Caucal hierarcy. 115, December 2015. to appear.
Педагогическая деятельность.

ArXiv e-prints,

pages

для 7-ых классов.

Преподаю на Малом Мехмате в кружках

Сравнение заявки и достигнутых результатов Разрешимость элементарной теории свободной, -порожденной GLP-алгебры установлена не была. Но были установлены близкие результаты о разрешимости элементарных теорий свободных, -порожденных GLPn -алгебр для всех натуральных n. Отметим, что эти результаты родствены исходному вопросу и похоже, что дальнейшее развитие разработанной техники позволит получить положительный ответ на исходный вопрос. Как и предполагалось в заявке, удалось разработать метод эффективного достраивания монадически определимых вполне упорядочиваний в иерархии Кукаля до монадически определимых вполне упорядочиваний с монадически определимыми системами кофинальных последовательностей. В контексте изучения быстрорастущих иерархий на основе систем ординальных обозначений, извлекаемых из иерархии Кукаля, нам удалось установить примерное совпадение иерархий со стандартной до уровня . В заявке предполагалось установить совпадение вплоть до уровня 0 . До уровня 0 удалось установить примерное совпадение иерархий, в случае когда они извлекаются из одного графа из иерархии Кукаля. На настоящий момент не видно методов доказательства исходной гипотезы. Не удалось установить разрешимость монадической теории 0 , снабженного системами кофинальных последовательностей. Также не удалось установить ограничение на высоту фундированных отношений в иерархии Кукаля.

2


Список литературы
[1] F. Pakhomov. Ordinal notations in Caucal hierarcy. December 2015. to appear.
ArXiv e-prints

, pages 115,

3