Викия

Математика

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

1457статей на
этой вики
Добавить новую страницу
Обсуждение0 Share

Обнаружено использование расширения AdBlock.


Викия — это свободный ресурс, который существует и развивается за счёт рекламы. Для блокирующих рекламу пользователей мы предоставляем модифицированную версию сайта.

Викия не будет доступна для последующих модификаций. Если вы желаете продолжать работать со страницей, то, пожалуйста, отключите расширение для блокировки рекламы.

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

ПримерПравить

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

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))))\}

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

ЛитератураПравить

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

Викия-сеть

Случайная вики