Арифметическая иерархия

Арифметическая иерархия (также известная как иерархия Клини — Мостовского) — это классификация подмножеств натуральных чисел (и, в более общем смысле, подмножеств счётных множеств) по сложности их определимости в языке формальной арифметики первого порядка. Она является фундаментальным понятием теории вычислимости и дескриптивной теории множеств, позволяя оценивать, насколько «сложным» является то или иное множество с точки зрения логических формул, необходимых для его описания.

Основные понятия

В основе арифметической иерархии лежит язык арифметики первого порядка, который включает логические связки (¬, ∧, ∨, →), кванторы (∀ — «для всех», ∃ — «существует»), символы для сложения (+), умножения (×), равенства (=), а также константу 0 и функцию следования (S, обозначающую +1). Формулы этого языка строятся из атомарных высказываний (например, «x + y = z») с помощью логических операций и кванторов.

Ключевым для классификации является понятие кванторной приставки. Формула считается находящейся на определённом уровне иерархии в зависимости от того, сколько блоков одноимённых кванторов (сначала все ∃, затем все ∀, или наоборот) стоит в её начале, и от того, начинается ли эта приставка с квантора существования или всеобщности. Бескванторные формулы (или формулы, все кванторы в которых ограничены, что эквивалентно) считаются базовым уровнем.

Классификация: уровни Σₙ и Πₙ

Арифметическая иерархия состоит из двух семейств классов: Σₙ (сигма-n) и Πₙ (пи-n), где n — натуральное число (включая 0). Класс Δₙ (дельта-n) определяется как пересечение Σₙ и Πₙ, то есть множества, которые могут быть определены как формулой класса Σₙ, так и формулой класса Πₙ.

Определение уровней

• Уровень 0 (Σ₀ и Π₀): К этому уровню относятся множества, определяемые формулами, в которых все кванторы ограничены (то есть имеют вид ∀x < t или ∃x < t, где t — терм, не содержащий x). Такие множества называются арифметическими или рекурсивными (в контексте теории вычислимости — разрешимыми). Пример: множество чётных чисел {x | ∃y (x = y + y)} — хотя здесь есть квантор, он не ограничен, но формула эквивалентна ограниченной, поэтому относится к Σ₀.
• Уровень 1:
• Σ₁: Множества, определимые формулой вида ∃y₁ … ∃yₖ P(x, y₁, …, yₖ), где P — бескванторная (или Σ₀) формула. Это в точности рекурсивно перечислимые (р.п.) множества (или полуразрешимые). Пример: множество чисел, являющихся номерами останавливающихся программ (проблема остановки).
• Π₁: Множества, определимые формулой вида ∀y₁ … ∀yₖ P(x, y₁, …, yₖ). Это дополнения к рекурсивно перечислимым множествам (ко-р.п. множества). Пример: множество чисел, являющихся номерами программ, которые не останавливаются.
• Δ₁: Пересечение Σ₁ и Π₁. Это в точности рекурсивные (разрешимые) множества, то есть те, для которых существует алгоритм, всегда дающий правильный ответ «да» или «нет».
• Уровень 2:
• Σ₂: Множества, определимые формулой вида ∃y₁ … ∃yₖ ∀z₁ … ∀zₘ P(x, y, z). Пример: множество чисел, которые являются номерами программ, останавливающихся на всех входах (тотальные функции).
• Π₂: Множества, определимые формулой вида ∀y₁ … ∀yₖ ∃z₁ … ∃zₘ P(x, y, z). Пример: множество чисел, которые являются номерами программ, вычисляющих конечные множества.
• Δ₂: Множества, определимые как Σ₂, так и Π₂. Сюда входят, например, все множества, разрешимые с помощью оракула для проблемы остановки (Turing jump).

Общий вид

Формула класса Σₙ имеет вид: ∃y₁ ∀y₂ ∃y₃ … Q yₙ P(x, y₁, …, yₙ) где Q — квантор существования, если n нечётно, и всеобщности, если n чётно. Формула класса Πₙ начинается с квантора всеобщности и чередует их n раз.

Свойства и теоремы

Иерархия не коллапсирует

Одним из важнейших результатов является то, что арифметическая иерархия строга: для каждого n класс Σₙ строго содержит Σₙ₋₁, а Πₙ строго содержит Πₙ₋₁. Иными словами, существуют множества, которые являются Σₙ, но не Πₙ, и наоборот. Это означает, что с ростом n сложность определимых множеств действительно возрастает. Доказательство этого факта использует диагонализацию, аналогичную доказательству неразрешимости проблемы остановки.

Связь с вычислимостью

• Тезис Чёрча — Тьюринга связывает интуитивное понятие алгоритма с формальным понятием рекурсивной функции. В рамках арифметической иерархии это отражается в том, что Σ₁-множества — это в точности множества, перечислимые с помощью машины Тьюринга.
• Степени неразрешимости (Turing degrees) тесно связаны с иерархией. Например, проблема остановки (H) является Σ₁-полной (любое Σ₁-множество сводится к ней). Её дополнение — Π₁-полно. Множества, разрешимые с помощью оракула H, образуют класс Δ₂.
• Иерархия Клини (или арифметическая иерархия) является частным случаем более общей гиперарифметической иерархии, которая использует кванторы по функциям, а не по числам.

Теорема о проекции

Теорема о проекции утверждает, что если множество A принадлежит классу Πₙ, то его проекция (множество {x | ∃y (x, y) ∈ A}) принадлежит классу Σₙ. Это свойство является ключевым для понимания того, как кванторы существования «проецируют» множества на более высокий уровень сложности.

Примеры

1. Множество простых чисел: Определяется формулой ∀y (y < x → (y = 1 ∨ ¬∃z (y · z = x))). Здесь все кванторы ограничены, поэтому это Σ₀-множество (и, следовательно, рекурсивное).
2. Множество чисел, которые являются номерами программ, останавливающихся на пустом входе: Это классическая проблема остановки. Определяется формулой ∃t (программа с номером x останавливается за t шагов). Это Σ₁-множество, но не Π₁ (и не рекурсивное).
3. Множество чисел, которые являются номерами программ, вычисляющих тотальные функции (останавливающихся на всех входах): Определяется формулой ∀y ∃t (программа с номером x, запущенная на входе y, останавливается за t шагов). Это Π₂-множество.
4. Множество истинных арифметических предложений (арифметическая истина): Это множество, как показал Тарский, не является арифметическим (то есть не принадлежит ни одному уровню Σₙ или Πₙ). Оно является примером множества, которое находится за пределами арифметической иерархии, в так называемой аналитической иерархии.

Значение и применение

Арифметическая иерархия является незаменимым инструментом в нескольких областях математики:

• Теория вычислимости: Она позволяет классифицировать неразрешимые проблемы по степени их сложности, выходя за рамки простого разделения на разрешимые и неразрешимые.
• Математическая логика: Она используется для анализа выразительной силы формальных теорий, таких как арифметика Пеано. Например, теорема Гёделя о неполноте может быть переформулирована в терминах арифметической иерархии.
• Дескриптивная теория множеств: В контексте анализа подмножеств вещественной прямой арифметическая иерархия обобщается до проективной иерархии, которая классифицирует множества по сложности их определимости с помощью кванторов по вещественным числам.
• Теория алгоритмов: Понятия Σ₁ и Π₁ используются для анализа сложности задач в контексте машин Тьюринга и рекурсивных функций.

Критика и ограничения

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

Источники

1. Роджерс Х. «Теория рекурсивных функций и эффективная вычислимость». — М.: Мир, 1972.
2. Клини С. К. «Введение в метаматематику». — М.: Издательство иностранной литературы, 1957.
3. Ершов Ю. Л., Палютин Е. А. «Математическая логика». — М.: Наука, 1987.
4. Hinman P. G. «Recursion-Theoretic Hierarchies». — Springer-Verlag, 1978.