ФУНДАМЕНТАЛЬНАЯ И ПРИКЛАДНАЯ МАТЕМАТИКА
1999, ТОМ 5, ВЫПУСК 1, СТР. 221-255

Об арифметической сложности предикатных логик полных конструктивных арифметических теорий

В. Е. Плиско

Аннотация

Посмотреть как HTML    Посмотреть как рисунок    Посмотреть в формате LaTeX

В статье доказывается, что предикатная логика всякой полной конструктивной арифметической теории $T$, обладающей свойством экзистенциальности, является $\Pi_1^T$-полной. Для этого используется техника равномерного частичного определения истинности для интуиционистских арифметических теорий. Основная теорема применяется для характеризации предикатной логики, соответствующей одному из вариантов понятия реализуемой предикатной формулы. А именно, показано, что множество всех неопровержимых предикатных формул рекурсивно изоморфно дополнению множества $\emptyset^{(\omega +1)}$.

Полнотекстовая версия статьи в формате PostScript (105 Kb)



Главная страница Редколлегия Информация для авторов
Поиск Содержание журнала Объявления

URL страницы: http://mech.math.msu.su/~fpm/rus/99/991/99113t.htm
Изменения вносились 27 апреля 1999