Иммунное множество — бесконечное множество конструктивных объектов (например, натуральных чисел), любое перечислимое подмножество которого конечно. В конструктивной математике иммунные множества иногда используются для построения примеров объектов с «патологическими» (с точки зрения традиционной теоретико-множественной математики) свойствами.
Пример
Простейшее иммунное множество натуральных чисел может быть построено следующим образом. Зафиксируем некоторую нумерацию всех частично рекурсивных функций одной переменной, и рассмотрим отвечающий этой нумерации двухместный предикат
, выражающий условие «частично рекурсивная функция с номером
применима к натуральному числу
». В таком случае дополнение
множества
![{\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))))\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/417430910ae801c0add81022a48685e99a57482d)
является иммунным множеством. Действительно, для любого натурального числа
множество
содержит не более
чисел, меньших числа
, а потому множество
бесконечно. С другой стороны, любое перечислимое подмножество
множества
является областью определения некоторой частично рекурсивной функции одной переменной. Этой функции соответствует некоторый номер
при фиксированной нами нумерации — что, ввиду характера построения множества
, означает невозможность для множества
содержать числа, превосходящие
. Тем самым, множество
конечно.
См. также
Литература
- Роджерс Х. Теория рекурсивных функций и эффективная вычислимость. — М.:Мир, 1972.