ПРЕДИКАТОВ КЛАССИФИКАЦИИ

иерархии предикатов) – методы приписывания предикатам (в формализованных исчислениях логики и математики) различных "степеней конструктивности", базирующиеся на идеях и аппарате теории алгоритмов и теории рекурсивных функций и предикатов и играющие существ. роль в метаматематических (см. Метатеория) исследованиях. Идеи эти обнаруживают близкое родство с известными принципами классификации множеств и функций, предложенными Р. Бэром, Э. Борелем, Ш. Ж. де ла Валле Пуссеном, ?. ?. Лузиным и др. математиками. Примером классификаций такого рода могут служить иерархии, предложенные С. К. Клини и. А. Мостовским. П. к. Клини – Мостовского позволяет также приписывать различные степени конструктивности арифметическим множествам и функциям и строить иерархии логич. систем. Принцип П. к., разработанный амер. математиком Э. Постом (1944), исходит из разбиения систем множеств, предикатов, св-в, отношений и т.п. посредством рефлексивного, симметричного и транзитивного отношения: "А рекурсивно относительно В и В рекурсивно относительно А" на классы эквивалентности, наз. "степенями (рекурсивной) неразрешимости", причем транзитивное отношение "А рекурсивно относительно В" для представителей классов естеств. образом упорядочивает (см. Порядка отношение) эти степени неразрешимости. Как показали сов. математик А. А. Мучник и амер. математик Р. Фридберг (1956), предикаты (множества), входящие в классификацию Поста, не образуют линейно упорядоченной иерархии. Идея упорядочения классов эквивалентности лежит и в основе предложенной сов. математиком Ю. Т. Медведевым классификации массовых проблем по "степеням трудности" (см. Сводимость). Лит.: Медведев Ю. Т., Степени трудности массовых проблем, "Докл. АН СССР", 1955, т. 104, No 4, с. 501–04; Кlееnе S. С., Recursive predicates and quantifiers, "Trans. Amer. Math. Soc.", 1943, v. 53, p. 41–73; ?оst ?. L., Recursively enumerable sets of positive Integers and their decision problems, "Bull. Amer. Math. Soc.", 1944, v. 50, p. 284–316; Mostowski ?., On definable sets of positive integers, "Fundamenta Mathematicae", 1947, v. 34, p. 81–112.