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