Математическая энциклопедия - иммунное множество

бесконечное множество натуральных чисел, не содержащее бесконечных рекурсивно перечислимых подмножеств. В частности, само И. м. не является рекурсивно перечислимым. И. м. по своей насыщенности рекурсивно перечислимыми подмножествами в известном смысле противоположны продуктивным множествам.

Рекурсивно перечислимые множества с иммунными дополнениями наз. простыми и образуют один из важных классов нерекурсивных рекурсивно перечислимых множеств. Типы рекурсивной эквивалентности иммунных и конечных множеств, называемые изолями, представляют интерес с точки зрения рекурсивного аналога теории кардинальных чисел.

Лит.: [1] Роджерс X., Теория рекурсивных функций и эффективная вычислимость, пер. с англ., М., 1972.

В. .