КЛИНИ - МОСТОВСКОГО КЛАССИФИКАЦИЯ

КЛИНИ - МОСТОВСКОГО КЛАССИФИКАЦИЯ

- классификация теоретико-числовых предикатов, введенная независимо С. Клини [1] и А. Мостовским [2]. Через П 0 и одновременно через е 0 обозначается класс всех рекурсивных предикатов. Для всякого k>0 класс е k определяется как класс всех предикатов, выразимых в виде где - квантор существования, R(y, x1, ..., х п)- предикат из класса П k-1, а класс П k определяется как класс предикатов, выразимых в виде где - квантор всеобщности, R( у, x1, ..., х п)- предикат из класса е k-1. Таким образом получается последовательность классов:

Если предикат принадлежит классу е k или П k, то он принадлежит классам П j и е j. для любого j>k, т. е. и для любого j>k. Если k>0, то существуют предикаты из класса е k, не принадлежащие П k, а также предикаты из класса П k, не принадлежащие е k,т. е.и

Предикат принадлежит одному из классов е k или П k тогда и только тогда, когда он выразим в языке арифметики формальной. Если предикат Q(x1, ..., х n )принадлежит классу е k (пли П k), то предикат где - знак отрицания, принадлежит классу П k (соответственно е k). Предикат Q(x1, ..., х n )рекурсивен тогда и только тогда, когда предикаты Q(x1, . .., х п принадлежат классу 2t, т. е. е 1 ЗП 1= е 00. Если k>0,то

На классификации предикатов основана классификация множеств, определимых в языке формальной арифметики: множество Мпринадлежит классу П k или е k, если этому классу принадлежит предикат

Лит.:[1] Кlееne S. С, "Trans. Amer. Math. Soc", 1943, v. 53 p. 41-73; [2] Mostowski A., "Fund, math.", 1947, v. 34, p. 81 -112.

В. Е. Плиско.


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

Поможем написать курсовую

Полезное


Смотреть что такое "КЛИНИ - МОСТОВСКОГО КЛАССИФИКАЦИЯ" в других словарях:

  • ИЕРАРХИЯ — классификация тех или иных математич. объектов в соответствии с их сложностью. Первые И. были построены в дескриптивной теории множеств (см. [3]). В этих И. переход к более сложному классу множеств осуществляется путем применения теоретико… …   Математическая энциклопедия

  • МОСТОВСКИЙ — (Mostowski), Анджей (р. 1 нояб. 1913) – польский логик и математик, чл. корр. Польской АН (с 1956), проф. ун та в Варшаве. М. принадлежат труды по математич. логике, логич. основаниям теории множеств, по топологии и алгебре. М. написал также ряд… …   Философская энциклопедия


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

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