ИЕРАРХИЯ это:

ИЕРАРХИЯ

- классификация тех или иных математич. объектов в соответствии с их сложностью.

Первые И. были построены в дескриптивной теории множеств (см. [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 )в виде

Здесь x1, . .., х k, у 1, . . ., у п- переменные, одни из к-рых пробегают множество натуральных чисел (числовые переменные), другие - множество всех подмножеств натуральных чисел (множественные переменные); Q1y1, ..., QnVn- последовательность кванторов, в к-рой кванторы всеобщности и существования чередуются, т. е. из любых двух соседних кванторов один является квантором всеобщности, а другой - квантором существования; R(x1, . .., xk, y1, . . ., у п).- произвольное рекурсивное отношение с числовыми и множественными переменными. Класс (соответственно П 0n) состоит из всех отношений Р( х 1, . . ., xk), представимых в виде (*), где переменные y1 , ... , у п- числовые и символ Q1- это (соответственно ). Классы и П 0n, n=0, 1, ... образуют арифметическую иерархию Клини - Мостовского (см. Клини - Мостовского классификация). Объединение всех этих классов наз. классом арифметич. отношений. Классы (соответственно ), п>1, состоят из отношений Р( х . . ., х k), представимых в виде (*), где все переменные у 1, ..., yn-1 - множественные, переменная у п- числовая и символ Q1- это (соответственно ). Через и обозначается класс арифметич, отношений. Классы n=0, 1, . . ., образуют аналитическую иерархию Клини. Продолжением иерархии Клини - Мостовскего можно считать гиперарифметич. И. множеств из класса (см. [2], [5]).

Различные И. могут рассматриваться единым образом с точки зрения определимости в логич. языках. В частности, начальные классы борелевской И. можно задать аналогично классам иерархии Клини - Мостовского, аналитич. И. аналогична проективной. При этом ряд утверждений, касающихся строения классов И., получает общую формулировку, а часто, и сходное доказательство (см. [1]). Примером такого утверждения является принцип редукции, состоящий в следующем. Пусть U- класс некоторой И., Xи У - его элементы, тогда существуют такие X' и У из U, что Х' М Х, Y' М Y, и Этот принцип выполняется, в частности, когда Uсовпадает с или СРВ, РСРВ. В моделей теории также строятся И. классов моделей по виду формул, задающих эти классы; имеются аналогии между этими И. и упомянутыми выше (см. [1]).

Построение И. рекурсивных функций осуществляется в теории алгоритмов. Один из общих методов построения таких И. основан на задании рекурсивных функций с помощью нек-рых исходных функций и операций (подстановки, примитивной рекурсии и др.). Переход к более сложному классу некоторой И. может осуществляться, напр., в результате добавления к предыдущему классу элемента нек-рой фиксированной последовательности рекурсивных функций и замыкания полученного множества относительно операций подстановки и ограниченной рекурсии. Для получения более сложного класса, наряду с замыканием относительно каких-либо операций (как в предыдущем примере), используется однократное применение, напр., операции примитивной рекурсии к элементам более простого класса (см. [4]). Другой метод построения И.-рекурсивных функций основан на их классификации по сложности вычислений (см. [4]). Рассмотрение характеристич. функций множеств позволяет строить И. разрешимых множеств, исходя из И. рекурсивных функций.

Лит.:[1] Аддисон Д ж.. Математическая логика и ее применения, пер. с англ., М., 1 965, с. 23-36; [2] Нinman Р., Recursion-theoretic hierarhies, В., 1976; [3] Куратовский К., Мостовский А., Теория множеств, пер. с англ., М., 1970; [4] Проблемы математической логики, сб. переводов, М., 1970; [5]Роджерс X., Теория рекурсивных функций и эффективная вычислимость, пер. с англ., М., 1972.

А. Л. Семенов.


Математическая энциклопедия. — М.: Советская энциклопедия. . 1977—1985.

Синонимы:

Смотреть что такое "ИЕРАРХИЯ" в других словарях:

  • ИЕРАРХИЯ — (от греч. hieros священный, arche власть) расположение частей или элементов целого в порядке от низшего к высшему, с возрастающим значением и уменьшающимся числом членов (напр., И. ценностей, И. наук и т.п.). И. были особенно характерны для… …   Философская энциклопедия

  • ИЕРАРХИЯ — (греч. hierarchia, от hieros священный, и archo управляю). Чиноначалие, преемственность старшинства. Словарь иностранных слов, вошедших в состав русского языка. Чудинов А.Н., 1910. ИЕРАРХИЯ [гр. hierarchia < hieros священный + arche власть]… …   Словарь иностранных слов русского языка

  • ИЕРАРХИЯ — ИЕРАРХИЯ, иерархии, жен. (греч.hierarchia) (книжн.). 1. Порядок подчинения низших высшим по точно определенным степеням, градации. Церковная иерархия. Общественная иерархия. В царской армии существовала строгая иерархия чинов. Служебная иерархия …   Толковый словарь Ушакова

  • Иерархия —  Иерархия  ♦ Hierarchie    Нормативная классификация, устанавливающая связи господства, зависимости или подчинения. Норму чаще всего задают власть или деньги. Подобную иерархию называют социальной, и она заставляет усомниться в самой идее… …   Философский словарь Спонвиля

  • иерархия — См …   Словарь синонимов

  • ИЕРАРХИЯ — (от греч. hieros священный и arche власть), 1) принцип структурной организации сложных многоуровневых животных сообществ и растительных систем, состоящий в упорядочении взаимодействия между уровнями в порядке от высшего к низшему. Каждый из двух… …   Экологический словарь

  • Иерархия — деление на высшие и низшие должности и чины, порядок подчинения низших по должности и чин лиц высшим. Первоначально иерархия сложилась в период рабовладельческого общества (Египет, Вавилон, Византия). В. Д. Гладкий Древний Мир Том 1 (Источник:… …   Энциклопедия мифологии

  • иерархия — и, ж. hiérarchie f.<гр. hierarchia. 1. Последовательное расположение должностей, званий и т. п. в порядке следования от низших к высшим. БАС 1. Гиерархия, подчиненность судов. 1808. АБТ 1 195. Гиерархия, или подчиненность. 1820. АБТ 5 388. ||… …   Исторический словарь галлицизмов русского языка

  • иерархия —     ИЕРАРХИЯ, духовенство, клир, священство …   Словарь-тезаурус синонимов русской речи

  • иерархия — (неправильно иерархия) …   Словарь трудностей произношения и ударения в современном русском языке

  • Иерархия — от греч. hieros священный и arche власть А. Расположение совокупности элементов в порядке от высшего к низшему. Б. Способ устройства сложных систем управления, при котором звенья системы распределены по различным уровням в соответствии с заданным …   Словарь бизнес-терминов

Книги

  • Иерархия, Николай Константинович Рерих. Эта книга будет изготовлена в соответствии с Вашим заказом по технологии Print-on-Demand. Погружаясь в волны Беспредельности, мы можем уподобиться цветам, сорванным бурею. Как найдем себя… Подробнее  Купить за 1475 руб
  • Иерархия, Н. Рерих. Погружаясь в волны Беспредельности, мы можем уподобиться цветам, сорванным бурею. Как найдем себя преображенными в океане Беспредельности? Не мудро было бы послатьладью без руля. Но урочен… Подробнее  Купить за 1369 грн (только Украина)
  • Иерархия, . Учение Агни Йоги, или Живой Этики, переданное духовными Учителями Шамбалы семье Рерих, по праву считается самым значительным эзотерическим учением современности. Данное издание представляет… Подробнее  Купить за 675 руб
Другие книги по запросу «ИЕРАРХИЯ» >>


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»