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

ИЕРАРХИЯ

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

Первые И. были построены в дескриптивной теории множеств (см. [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 руб
  • Иерархия, . Учение Агни Йоги, или Живой Этики, переданное духовными Учителями Шамбалы семье Рерих, по праву считается самым значительным эзотерическим учением современности.Данное издание представляет… Подробнее  Купить за 675 руб
  • Иерархия радуги, Емельянов-Лукьянчиков Максим Александрович. Религия значимее культуры и государства, но цивилизация наличествует только тогда, когда все три ее части сосуществуют друг с другом в гармонии. Все составляющие цивилизации смертны - умирает… Подробнее  Купить за 461 руб
Другие книги по запросу «ИЕРАРХИЯ» >>


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

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