Иммунное множество
Иммунное множество — бесконечное множество конструктивных объектов (например, натуральных чисел), любое перечислимое подмножество которого конечно. В конструктивной математике иммунные множества иногда используются для построения примеров объектов с «патологическими» (с точки зрения традиционной теоретико-множественной математики) свойствами.
Пример
Простейшее иммунное множество натуральных чисел может быть построено следующим образом. Зафиксируем некоторую нумерацию всех частично рекурсивных функций одной переменной, и рассмотрим отвечающий этой нумерации двухместный предикат [math]\displaystyle{ T(x,\;y) }[/math], выражающий условие «частично рекурсивная функция с номером [math]\displaystyle{ x }[/math] применима к натуральному числу [math]\displaystyle{ y }[/math]». В таком случае дополнение [math]\displaystyle{ I\rightleftharpoons\mathbb N\setminus C }[/math] множества
- [math]\displaystyle{ C\rightleftharpoons\{x\in\mathbb N\mid(\exists y)\;(2y\lt x)\land(T(y,\;x)\land((\forall z)\;T(y,\;z)\supset((z\leqslant 2y)\lor(z\geqslant x))))\} }[/math]
является иммунным множеством. Действительно, для любого натурального числа [math]\displaystyle{ n }[/math] множество [math]\displaystyle{ C }[/math] содержит не более [math]\displaystyle{ n }[/math] чисел, меньших числа [math]\displaystyle{ 2n }[/math], а потому множество [math]\displaystyle{ I }[/math] бесконечно. С другой стороны, любое перечислимое подмножество [math]\displaystyle{ M }[/math] множества [math]\displaystyle{ I }[/math] является областью определения некоторой частично рекурсивной функции одной переменной. Этой функции соответствует некоторый номер [math]\displaystyle{ n }[/math] при фиксированной нами нумерации — что, ввиду характера построения множества [math]\displaystyle{ C }[/math], означает невозможность для множества [math]\displaystyle{ M }[/math] содержать числа, превосходящие [math]\displaystyle{ 2n }[/math]. Тем самым, множество [math]\displaystyle{ M }[/math] конечно.
См. также
Литература
- Роджерс Х. Теория рекурсивных функций и эффективная вычислимость. — М.:Мир, 1972.