RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Ближайшие семинары
Календарь семинаров
Список семинаров
Архив по годам
Регистрация семинара

Поиск
RSS
Ближайшие семинары





Для просмотра файлов Вам могут потребоваться








Семинар отдела математической логики «Теория доказательств»
7 сентября 2015 г. 18:30, г. Москва, МИАН, ауд. 530
 


Некоторые новые результаты в монадической арифметике второго порядка

С. О. Сперанский

Количество просмотров:
Эта страница:102

Аннотация: Пусть $A$ – некоторая структура на множестве всех натуральных чисел. Рассмотрим следующие свойства:
  • для каждого положительного целого числа n множество всех $\Pi^1_n$-предложений, истинных в $A$, является $\Pi^1_n$-полным;
  • для каждого положительного целого числа n, если множество натуральных чисел $\Pi^1_n$-определимо в стандартной модели арифметики Пеано и замкнуто относительно автоморфизмов $A$, то оно $\Pi^1_n$-определимо в $A$.
Интуитивно, эти свойства соответствуют двум известным описаниям аналитической иерархии, в одном из которых используется m-сводимость, а в другом – второпорядковая определимость. В докладе речь пойдёт о том, как можно доказывать эти свойства для тех или иных структур (являющихся куда более бедными, чем стандартная модель арифметики Пеано, с точки зрения логики первого порядка). Например, любая $A$, в которой определимо формулой первого порядка отношение делимости, обладает обоими свойствами. То же верно и для ряда других интересных структур, включая стандартную модель арифметики Пресбургера, натуральные числа с отношением взаимной простоты и каждый треугольник Паскаля по модулю простого числа.

ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru
 
Обратная связь:
 Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020