Иммунное Множество

Бесконечное множество натуральных чисел, не содержащее бесконечных рекурсивно перечислимых подмножеств. В частности, само И. м. не является рекурсивно перечислимым. И. м. по своей насыщенности рекурсивно перечислимыми подмножествами в известном смысле противоположны продуктивным множествам. Рекурсивно перечислимые множества с иммунными дополнениями наз. простыми и образуют один из важных классов нерекурсивных рекурсивно перечислимых множеств. Типы рекурсивной эквивалентности иммунных и конечных множеств, называемые изолями, представляют интерес с точки зрения рекурсивного аналога теории кардинальных чисел. В рекурсивной теории множеств и ее приложениях используются также некоторые специальные подклассы класса И. м., особенно гипериммунные (гипериммунным наз. множество натуральных чисел, последовательность элементов к-рого, расположенных в порядке возрастания, не мажорируется никакой общерекурсивной функцией; рекурсивно перечислнмое множество с гипериммунным дополнением наз. гиперпростым). Лит.: [1] Роджерс X., Теория рекурсивных функций и эффективная вычислимость, пер. с англ., М., 1972. В.