Введение

Понятие в математической логике и теории множеств

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

Аналитическая иерархия множеств натуральных чисел

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

Аналитическая иерархия на подмножествах пространства Кантора и Байра

Аналитическая иерархия может быть определена на любом эффективном польском пространстве; определение особенно просто для пространства Кантора и пространства Байра, поскольку они согласуются с языком обычной арифметики второго порядка. Пространство Кантора – это множество всех бесконечных последовательностей из 0 и 1; пространство Байра – это множество всех бесконечных последовательностей натуральных чисел. Оба эти пространства являются польскими. Обычная аксиоматизация арифметики второго порядка использует язык, основанный на множествах, в котором кванторы по множествам могут естественным образом интерпретироваться как квантификация по пространству Кантора. Подмножеству пространства Кантора присваивается классификация , если оно определимо формулой (с одной свободной переменной, представляющей множество, и без свободных числовых переменных). Множеству присваивается классификация , если оно определимо формулой. Если множество одновременно и , то ему присваивается дополнительная классификация . Подмножество пространства Байра имеет соответствующее подмножество пространства Кантора посредством отображения, которое переводит каждую функцию из в в характеристическую функцию её графа. Подмножеству пространства Байра присваивается классификация , , или тогда и только тогда, когда соответствующее подмножество пространства Кантора имеет ту же классификацию. Эквивалентное определение аналитической иерархии на пространстве Байра дается путем определения аналитической иерархии формул с использованием функциональной версии арифметики второго порядка; затем аналитическая иерархия на подмножествах пространства Кантора может быть определена на основе иерархии на пространстве Байра. Это альтернативное определение дает ровно те же классификации, что и первое определение. Поскольку пространство Кантора гомеоморфно любой конечной декартовой степени самого себя, а пространство Байра гомеоморфно любой конечной декартовой степени самого себя, аналитическая иерархия в равной степени применима к конечным декартовым степеням одного из этих пространств. Аналогичное расширение возможно для счетных степеней и произведений степеней пространства Кантора и степеней пространства Байра.

Расширения

Как и в случае с арифметической иерархией, можно определить релятивизированную версию аналитической иерархии. Язык расширяется добавлением постоянного символа множества A. Формула в расширенном языке определяется индуктивно как , либо , используя то же индуктивное определение, что и выше. Для заданного множества Y, множество X определяется как , если оно определимо формулой, в которой символ A интерпретируется как Y; аналогичные определения применимы для и . Множества, которые являются или , для любого параметра Y, классифицируются в проективной иерархии и часто обозначаются полужирными греческими буквами, чтобы указать на использование параметров.

Примеры

Для отношения на , утверждение "является хорошим порядком на " (не путать с общим случаем для хорошо обоснованных отношений на множествах, см. иерархию Леви). Множество всех натуральных чисел, являющихся индексами вычислимых ординалов, является множеством, которое не является . Эти множества являются точно рекурсивно перечислимыми подмножествами [Bar75, с. 168]. Функция определяется формализмом систем уравнений Гербранда 1931 года тогда и только тогда, когда она гиперарифметическая. Множество непрерывных функций, обладающих свойством средней точки, не ниже чем в иерархии. Множество элементов пространства Кантора, являющихся характеристическими функциями хороших порядков на , является множеством, которое не является . Фактически, это множество не является для любого элемента пространства Байра. Если аксиома конструктивности верна, то существует подмножество произведения пространства Байра с самим собой, которое является и является графом хорошего порядка на пространстве Байра. Если аксиома верна, то существует также хороший порядок на пространстве Кантора.