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

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

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

$C\rightleftharpoons \{x\in \mathbb{N}\mid (\mathrm{\exists }y)(2y<x)\wedge (T(y,x)\wedge ((\mathrm{\forall }z)T(y,z)\supset ((z⩽2y)\vee (z⩾x))))\}$

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

См. также

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

Литература

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