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

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

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

${\displaystyle 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))))\}}$

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

• Арифметическое множество

• Роджерс Х. Теория рекурсивных функций и эффективная вычислимость. — М.:Мир, 1972.