Иерархия

208

- классификация тех или иных математич. Объектов в соответствии с их сложностью. Первые И. Были построены в дескриптивной теории множеств (см. [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, состоят из отношений Р( х 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. А. Л. Семенов..

Значения в других словарях
Иенсена Неравенство

в простейшей дискретной форме. где f(x)- выпуклая (см. Выпуклая функция )на нек-ром множестве Сфункция, i=1, 2, . ., n, Равенство достигается тогда и только тогда, когда либо х 1=x2=. = xn, либо f(x).- линейная функция. И н те тральное И. Н. Для выпуклой функции f(x). где при " Равенство достигается тогда и только тогда, когда либо x(t)=const на D, либо f(x)линейна на x(D). Если f(x)- вогнутая функция, знаки неравенств (1) и (2) меняются на противоположные. Неравенство (1) установлено..

Иенсена Формула

- соотношение, связывающее значения мероморфной функции внутри круга с ее граничными значениями на окружности и с ее нулями и полюсами. Пусть f(z)- мероморфная функция в круге am, и bv , -соответственно все нули и полюсы f(z), причем каждый нуль или полюс считается столько раз, какова его кратность или порядок. Если то справедлива И. Ф. в к-рой суммы распространены на все нули и полюсы f(z)внутри круга |z|<R. Формула (1) получена И. Иенсеном [1]. Небольшое видоизменение позволяет приспос..

Избыток Треугольника

сферический избыток, эксцесс,- разность между суммой углов сферич. Треугольника и двумя прямыми углами. И. Т. Пропорционален площади сферич. Треугольника. А. Б. Иванов.. ..

Избыточность

- мера возможного увеличения скорости передачи информации за счет использования статистич. Зависимостей между компонентами сообщения, вырабатываемого источником сообщений. И. Стационарного источника сообщений с дискретным временем, вырабатывающего сообщение x=(..., x-1, x0, x1, ...), образованное стационарным случайным процессом где xk принимает значения из нек-рого конечного множества Xс числом элементов N, определяется разностью здесь - скорость создания сообщений данным источником U(см. С..

Дополнительный поиск Иерархия Иерархия

Добавить комментарий
Комментарии
Комментариев пока нет

На нашем сайте Вы найдете значение "Иерархия" в словаре Математическая энциклопедия, подробное описание, примеры использования, словосочетания с выражением Иерархия, различные варианты толкований, скрытый смысл.

Первая буква "И". Общая длина 8 символа