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

Иммунное множество — бесконечное множество конструктивных объектов (например, натуральных чисел), любое перечислимое подмножество которого конечно. В конструктивной математике иммунные множества иногда используются для построения примеров объектов с «патологическими» (с точки зрения традиционной теоретико-множественной математики) свойствами.

Пример[править | править код]

Простейшее иммунное множество натуральных чисел может быть построено следующим образом. Зафиксируем некоторую нумерацию всех частично рекурсивных функций одной переменной, и рассмотрим отвечающий этой нумерации двухместный предикат $T(x,\;y)$ , выражающий условие «частично рекурсивная функция с номером $x$ применима к натуральному числу $y$ ». В таком случае дополнение $I\rightleftharpoons \mathbb {N} \setminus C$ множества

C\rightleftharpoons \{x\in \mathbb {N} \mid (\exists y)\;(2y<x)\land (T(y,\;x)\land ((\forall z)\;T(y,\;z)\supset ((z\leqslant 2y)\lor (z\geqslant x))))\}

является иммунным множеством. Действительно, для любого натурального числа $n$ множество $C$ содержит не более $n$ чисел, меньших числа $2n$ , а потому множество $I$ бесконечно. С другой стороны, любое перечислимое подмножество $M$ множества $I$ является областью определения некоторой частично рекурсивной функции одной переменной. Этой функции соответствует некоторый номер $n$ при фиксированной нами нумерации — что, ввиду характера построения множества $C$ , означает невозможность для множества $M$ содержать числа, превосходящие $2n$ . Тем самым, множество $M$ конечно.