Иерархия

- классификация тех или иных математич. объектов в соответствии с их сложностью. Первые И. были построены в дескриптивной теории множеств (см. [3]). В этих И. переход к более сложному классу множеств осуществляется путем применения теоретико-множественных и топологич. операций к элементам более простых классов. Важнейшие И. дескриптивной теории множеств определяются следующим образом. Если Т- некоторое семейство подмножеств множества Х, то через СТ обозначается семейство всех дополнений в X к элементам из Т, через Т s.- семейство всех счетных объединений элементов из Т, через Т d, - семейство всех счетных пересечений элементов из Т. Для фиксированного топологического пространства X через Fобозначается семейство всех замкнутых подмножеств пространства X, через G - семейство всех открытых подмножеств пространства X. По трансфинитной индукции определяется последовательность F, Fs, Fsd, Fsds,..., классы, стоящие в ней на местах, отвечающих предельным ординалам, получаются в результате применения операции d к объединению всех предшествующих классов. Аналогично, с ваменой всюду операций s иdна операции d и а, соответственно, определяется последовательность классов G,Gd, Gds, Gdsd,.... При этом G=CF, Gd.=СFs и т. д. Построенные последовательности образуют борелевскую И. подмножеств пространства X. Объединение всех классов этой И. наз. классом борелевских подмножеств пространства Xи обозначается В. Если Т- некоторое семейство подмножеств топологич. пространства X, то через Р Т обозначается семейство всех образов элементов семейства Тпри непрерывных отображениях Xв X. Классы В, РВ, СРВ, РСРВ и т. д. образуют проективную И. подмножеств пространства X. При этом аналитические множества (А-множества) составляют класс РВ, дополнения к ним (СА -множества) - класс СРВ и т. д. В математич. логике рассматриваются И. множеств и отношений, задаваемых формулами логич. языков (см. [1], [2], [5]). Важнейшими примерами таких И. являются И., основанные на представлении отношения Р(х 1,..., xk)в виде [img: http://localhost:8080/file/021003-31.jpg] Здесь x1,..., х k, у 1,..., у п- переменные, одни из к-рых пробегают множество натуральных чисел (числовые переменные), другие - множество всех подмножеств натуральных чисел (множественные переменные); Q1y1,..., QnVn- последовательность кванторов, в к-рой кванторы всеобщности и существования чередуются, т. е. из любых двух соседних кванторов один является квантором всеобщности, а другой - квантором существования; R(x1,..., xk, y1,..., у п).- произвольное рекурсивное отношение с числовыми и множественными переменными. Класс [img: http://localhost:8080/file/021003-32.jpg] (соответственно П 0n) состоит из всех отношений Р(х 1,..., xk), представимых в виде (*), где переменные y1,..., у п- числовые и символ Q1- это [img: http://localhost:8080/file/021003-33.jpg] (соответственно [img: http://localhost:8080/file/021003-34.jpg]). Классы [img: http://localhost:8080/file/021003-35.jpg] и П 0n, n=0, 1,... образуют арифметическую иерархию Клини - Мостовского (см. Клини - Мостовского классификация). Объединение всех этих классов наз. классом арифметич. отношений. Классы [img: http://localhost:8080/file/021003-36.jpg] (соответственно [img: http://localhost:8080/file/021003-37.jpg]), п>1, состоят из отношений Р(х 1ч..., х k), представимых в виде (*), где все переменные у 1,..., yn-1 - множественные, переменная у п- числовая и символ Q1- это [img: http://localhost:8080/file/021003-38.jpg] (соответственно [img: http://localhost:8080/file/021003-39.jpg]). Через [img: http://localhost:8080/file/021003-40.jpg] и [img: http://localhost:8080/file/021003-41.jpg] обозначается класс арифметич, отношений. Классы [img: http://localhost:8080/file/021003-42.jpg] n=0, 1,..., образуют аналитическую иерархию Клини. Продолжением иерархии Клини - Мостовскего можно считать гиперарифметич. И. множеств из класса [img: http://localhost:8080/file/021003-43.jpg] (см. [2], [5]). Различные И. могут рассматриваться единым образом с точки зрения определимости в логич. языках. В частности, начальные классы борелевской И. можно задать аналогично классам иерархии Клини - Мостовского, аналитич. И. аналогична проективной. При этом ряд утверждений, касающихся строения классов И., получает общую формулировку, а часто, и сходное доказательство (см. [1]). Примером такого утверждения является принцип редукции, состоящий в следующем. Пусть U- класс некоторой И., Xи У - его элементы, тогда существуют такие X' и У из U, что Х' М Х, Y' М Y, [img: http://localhost:8080/file/021003-44.jpg] и [img: http://localhost:8080/file/021003-45.jpg] Этот принцип выполняется, в частности, когда Uсовпадает с [img: http://localhost:8080/file/021003-46.jpg] или СРВ, РСРВ. В моделей теории также строятся И. классов моделей по виду формул, задающих эти классы; имеются аналогии между этими И. и упомянутыми выше (см. [1]). Построение И. рекурсивных функций осуществляется в теории алгоритмов. Один из общих методов построения таких И. основан на задании рекурсивных функций с помощью нек-рых исходных функций и операций (подстановки, примитивной рекурсии и др.). Переход к более сложному классу некоторой И. может осуществляться, напр., в результате добавления к предыдущему классу элемента нек-рой фиксированной последовательности рекурсивных функций и замыкания полученного множества относительно операций подстановки и ограниченной рекурсии. Для получения более сложного класса, наряду с замыканием относительно каких-либо операций (как в предыдущем примере), используется однократное применение, напр., операции примитивной рекурсии к элементам более простого класса (см. [4]). Другой метод построения И.-рекурсивных функций основан на их классификации по сложности вычислений (см. [4]). Рассмотрение характеристич. функций множеств позволяет строить И. разрешимых множеств, исходя из И. рекурсивных функций.