РЕКУРСИВНОЙ ЭКВИВАЛЕНТНОСТИ ТИП

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

Над Р. э. т. определяются алгебраич. операции, важнейшими из к-рых являются сложение и умножение: если A и B суть Р. э. т., , причем a состоит из четных чисел, a b - из нечетных, то А+В есть Р. э. т. множества есть Р. э. т. множества , где j - общерекурсивная функция, взаимно однозначно отображающая декартов квадрат натурального ряда на натуральный ряд. Алгебра Р. э. т. тесно связана с алгеброй кардинальных чисел, развиваемой без аксиомы выбора. Совокупность изолей замкнута относительно указанных операций.

Предпринимались попытки перенесения понятия Р. э. т. на классы множеств.

Лит.:[1] P о д ж е р с X., Теория рекурсивных функций и эффективная вычислимость, пер. с англ., М., 1972; [2] D е k k е r J. С. Е., М у h i l 1 J., Recursive equivalence types, Berk.- Los Ang., 1960. В. А. Душский.