ГлавнаяИммунное множество — бесконечное множество конструктивных объектов (например, натуральных чисел), любое перечислимое подмножество которого конечно. В конструктивной математике иммунные множества иногда используются для построения примеров объектов с «патологическими» (с точки зрения традиционной теоретико-множественной математики) свойствами.
Пример
Простейшее иммунное множество натуральных чисел может быть построено следующим образом. Зафиксируем некоторую нумерацию всех частично рекурсивных функций одной переменной, и рассмотрим отвечающий этой нумерации двухместный предикат T ( x , y ) {displaystyle T(x,;y)} , выражающий условие «частично рекурсивная функция с номером x {displaystyle x} применима к натуральному числу y {displaystyle y} ». В таком случае дополнение I ⇌ N ∖ C {displaystyle I ightleftharpoons mathbb {N} setminus C} множества
C ⇌ { x ∈ N ∣ ( ∃ y ) ( 2 y < x ) ∧ ( T ( y , x ) ∧ ( ( ∀ z ) T ( y , z ) ⊃ ( ( z ⩽ 2 y ) ∨ ( z ⩾ x ) ) ) ) } {displaystyle C ightleftharpoons {xin mathbb {N} mid (exists y);(2y<x)land (T(y,;x)land ((forall z);T(y,;z)supset ((zleqslant 2y)lor (zgeqslant x))))}}является иммунным множеством. Действительно, для любого натурального числа n {displaystyle n} множество C {displaystyle C} содержит не более n {displaystyle n} чисел, меньших числа 2 n {displaystyle 2n} , а потому множество I {displaystyle I} бесконечно. С другой стороны, любое перечислимое подмножество M {displaystyle M} множества I {displaystyle I} является областью определения некоторой частично рекурсивной функции одной переменной. Этой функции соответствует некоторый номер n {displaystyle n} при фиксированной нами нумерации — что, ввиду характера построения множества C {displaystyle C} , означает невозможность для множества M {displaystyle M} содержать числа, превосходящие 2 n {displaystyle 2n} . Тем самым, множество M {displaystyle M} конечно.