Арифметическая иерархия
-
Арифметическая иерархия
- Классифицирует множества на основе сложности формул, их определяющих
- Изобретена Клини и Мостовски независимо
- Важна в теории вычислимости и формальных теориях
-
Арифметическая иерархия формул
- Присваивает формулам классификации на языке арифметики первого порядка
- Классификации обозначаются Σn0 и Πn0 для натуральных чисел n
- Σn0 формулы начинаются с экзистенциальных кванторов, Πn0 формулы начинаются с универсальных кванторов
- Каждая формула имеет предварительную нормальную форму и получает по крайней мере одну классификацию
-
Арифметическая иерархия множеств натуральных чисел
- Множество определяется формулой на языке арифметики Пеано
- Каждому множеству присваивается классификация Σn0, Πn0 или Δn0
- Δn0 множества определяются формулами, которые являются одновременно Σn0 и Πn0
-
Значение обозначения
- Нижний индекс n указывает количество чередований кванторов
- Верхний индекс 0 указывает тип объектов, по которым проводится количественная оценка
-
Примеры
- Σ10 множества определяются формулами с ограниченными кванторами
- Π20 множества включают индексы машин Тьюринга
- Σ10 множества являются открытыми в топологии пространства Бэра или Кантора
- Π10 множества являются закрытыми в топологии пространства Бэра или Кантора
-
Иерархия Бореля
- Расширяет арифметическую иерархию, включая дополнительные наборы Бореля
- Π20 множества являются Gδ множествами
- Σ00 множества являются Π00 множествами
-
Арифметические иерархии и их ограничения
- Формулы можно проверить, просмотрев все случаи, что возможно благодаря ограниченным кванторам.
- Время проверки полиномиально в аргументах, что делает задачи решения экспоненциальными по количеству бит.
- Альтернативные определения Σ00 = Π00 = Δ00 позволяют использовать примитивно-рекурсивные функции.
-
Релятивизированные арифметические иерархии
- Можно определить, что означает быть Σn0, Δn0 или Πn0 через Y, обозначаемые как Σn0,Y, Δn0,Y и Πn0,Y соответственно.
- X находится в Σn0,Y, если определено с помощью Σn0 формулы на расширенном языке.
-
Арифметическая сводимость и степени
- Множество X является арифметическим, если определено формулой на языке арифметики Пеано.
- X арифметически сводится к Y, если определено формулой на расширенном языке с предикатом для принадлежности к Y.
- Отношение X ≤A Y рефлексивно и транзитивно, что определяет отношение эквивалентности.
-
Арифметическая иерархия подмножеств пространства Кантора и Бэра
- Подмножества пространства Кантора классифицируются как Σn0, Πn0 или Δn0 в зависимости от возможности определения с помощью соответствующих формул.
- Подмножества пространства Бэра классифицируются аналогично через отображение на пространство Кантора.
-
Расширения и вариации
- Можно определить арифметическую иерархию с использованием языка, расширенного функциональным символом для примитивно-рекурсивных функций.
- Более семантическая вариация иерархии может быть определена для конечных отношений в натуральных числах.
-
Определение отношений в арифметической иерархии
- Отношение R(n1, …, nl, m1, …, mk) является Πn0, тогда отношение S(n1, …, nl) = ∃m1 ⋯ ∃mk R(n1, …, nl, m1, …, mk) определяется как Σn+10.
- Σ00 = Π00 = Δ00, что идентично Δ10.
-
Свойства арифметической иерархии
- Πn0 и Σn0 замкнуты при конечных объединениях и пересечениях.
- Набор является Σn0 тогда и только тогда, когда его дополнение является Πn0.
- Набор является Δn0 тогда и только тогда, когда он является Σn0 и Πn0, и его дополнение также является Δn0.
-
Включения и иерархия
- Πn0 ⊊ Πn+10 и Σn0 ⊊ Σn+10 для всех n.
- Δn0 ⊊ Πn0, Δn0 ⊊ Σn0 и Σn0 ∪ Πn0 ⊊ Δn+10 для n ≥ 1.
- Σ00 = Π00 = Δ00 = Σ00 ∪ Π00 ⊆ Δ10.
-
Отношение к машинам Тьюринга
- Вычислимые множества находятся в Δ10.
- Рекурсивно перечислимые множества находятся в Σ10.
- Проблема остановки для Δn0,Y оракула находится в Σn+10,Y.
-
Полиномиальная иерархия
- Полиномиальная иерархия устанавливает полиномиальные ограничения по длине чисел.
- Это дает более точную классификацию множеств на уровне Δ10.
-
Связь с другими иерархиями
- Аналитическая иерархия
- Иерархия Леви
- Иерархия (математика)
- Логика интерпретируемости