Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/dfc/2012/Program1/Pakhomov_summary.pdf Дата изменения: Tue Oct 16 11:40:14 2012 Дата индексирования: Mon Feb 4 18:23:40 2013 Кодировка: Windows-1251 Поисковые слова: кассиопеиды

Краткое изложение заявки. Ф.Н. Пахомов.

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

<

, такие, что интерпретация

<

является вполне упорядочиванием, все элементы этой моде-

лей являются значениями некоторых термов и разрешима проблема

<

-сравнения значений

замкнутых термов. Основной мотивацией моих исследований является, давно обнаруженая, проблема связанная с формализацией, возникающего на практике понятия естественной системы ординальных обозначений; данный план не предполагает разрешения этой проблемы, известной, как проблема каноничности систем ординальных обозначений, но некоторые результаты, которые планируется получить в рамках этого исследования, могут быть полезны в дальнейшем для е? решения. В работе [1] и моей дипломной работе О разрешимости элементарных теорий алгебр доказуемости и их фрагментов. рассматривались системы ординальных обозначений, основанные, на полимодальной логике доказуемости доказательственный ординал нальных обозначений доходят до и включают

GLP. 0

Порядковые типы таких систем ордибольшой сч?тный ординал, теоретико-

PA

. Эта логика и такого рода системы обозначений активно

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





, либо ординал







.

Вед?тся работа над теоремой, контрастирующей с предыдущими результатами планируется доказать разрешимость элементарной теории свободнопорожд?нной из констант алгебры; все структуры из предыдущих результатов вкладываются в эту алгебру. Недавно (2009 г.) Л. Бро для всех

GLP-

<

0 была установлена разрешимость монадической

теории (множества всех формул с кванторами по множествам элементов и индивидуальным элементам, истинных в данной модели) системы ординальных обозначений, построенной естественным образом из стандартной системы кофинальных последовательностей до тем же автором и А. Кара?лем была получена верхняя грань



. Позднее



0 (точная в силу предыдущего

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

0

на



2 -ординального анализа и



1 -ординального

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



0 , аналогичную рассмотреным Л. Бро. Для положительного

решения этого вопроса, предположительно, потребуется новый мощный метод доказательства разрешимости монадических теорий и при этом, в силу лежания у границы применимости известного метода, возможно конструкция нового(гипотетического) метода будет значительно яснее, чем это могло быть до привед?нных выше результатов Бро и Кара?ля. Скорее всего, опять же при положительном решение проблемы, разработанную технику можно будет применять для аналогичных задач со значительно большими ординалами.

Список литературы
[1] Ф. Н. Пахомов. Неразрешимость элементарной теории полурешетки
сб., 203:141160, 2012.

GLP

-слов. Матем.