АРИФМЕТИЧЕСКАЯ И АНАЛИТИЧЕСКАЯ ИЕРАРХИИ

— два способа классификации числовых множеств, в основу которых положены языки арифметики соответственно 1-й и 2-й ступени.

Арифметическая иерархия охватывает мн-ва, выразимые в языке элементарной арифметики (см. Арифметика формальная). Эти мн-ва, как мн-ва истинности, можно получить, навешивая кванторы на рекурсивные предикаты числовых переменных. Их классифицируют по числу перемен кванторов и по виду первого квантора. Так, рекурсивно перечислимые мн-ва можно выразить в виде с общерекурсивным они, по определению, составляют класс в арифм. иерархий. Дополнения к рекурсивно перечислимым мн-вам, представимые в виде объединяются в класс . Вообще состоит из мн-в, полученных навешиванием на рекурсивные предикаты чередующихся кванторов, первый из которых — квантор существования. Аналогично определяется класс . Построенные таким образом классы причем равны классу всех рекурсивных характеризуются посредством некоторой канонической формы кванторных приставок. С помощью простых тождественных преобразований можно любое арифм. мн-во привести к каноническому виду.

Аналитическая иерархия охватывает более широкий класс мн-в, представимых в языке т. Н; арифметики 2-й ступени. Этот язык отличается от языка элементарной арифметики наличием функциональных переменных, пробегающих мн-во всех бесконечных числовых последовательностей, и наличием кванторов, связывающих эти переменные. Посредством тождественных преобразований ф-лы этого языка можно привести к такому виду, что все функциональные кванторы окажутся вынесенными в начало формулы. Классификация идет по числу чередований функциональных кванторов. Напр., есть совокупность мн-в, которые представимы ф-лами (в приведенной форме) с одним функциональным квантором общности. Аналитическая иерархия содержит очень неэффективные средства порождения множеств (функциональные кванторы). Поэтому внутри нее выделяют рекурсивные иерархии, использующие более конструктивные принципы. Эти принципы приблизительно состоят в допущении некоторых простых видов счетного перебора, проитерированного по достаточно обозримым трансфинитным отрезкам. Важным примером такого рода служит гиперарифметическая иерархия, являющаяся довольно естественным продолжением арифметической. Эта иерархия исчерпывает класс мн-в, которые попадают в П вместе со своими дополнениями; Ведутся исследования по построению и изучению естественных классов еще более длинных иерархий.

Лит. Роджерс X. Теория рекурсивных функций и эффективная рекурсивность. Пер. с англ. М., 1972 [библиогр. с. 587—599]. Н. В Белякин.