- Иммунное множество
-
Иммунное множество — бесконечное множество конструктивных объектов (например, натуральных чисел), любое перечислимое подмножество которого конечно. В конструктивной математике иммунные множества иногда используются для построения примеров объектов с «патологическими» (с точки зрения традиционной теоретико-множественной математики) свойствами — например, функций, непрерывных по Гейне и разрывных по Коши .
Пример
Простейшее иммунное множество натуральных чисел может быть построено следующим образом. Зафиксируем некоторую нумерацию всех частично рекурсивных функций одной переменной, и рассмотрим отвечающий этой нумерации двухместный предикат
, выражающий условие «частично рекурсивная функция с номером
применима к натуральному числу
». В таком случае дополнение
множества
является иммунным множеством. Действительно, для любого натурального числа
множество
содержит не более
чисел, меньших числа
, а потому множество
бесконечно. С другой стороны, любое перечислимое подмножество
множества
является областью определения некоторой частично рекурсивной функции одной переменной. Этой функции соответствует некоторый номер
при фиксированной нами нумерации — что, ввиду характера построения множества
, означает невозможность для множества
содержать числа, превосходящие
. Тем самым, множество
конечно.
См. также
Литература
- Роджерс Х. Теория рекурсивных функций и эффективная вычислимость. — М.:Мир, 1972.
Для улучшения этой статьи желательно?: - Проверить достоверность указанной в статье информации.
Категории:- Философия математики
- Теория множеств
Wikimedia Foundation. 2010.