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

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

В. Е. Плиско

Аннотация

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

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

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

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