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

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

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

Пример

Простейшее иммунное множество натуральных чисел может быть построено следующим образом. Зафиксируем некоторую нумерацию всех частично рекурсивных функций одной переменной, и рассмотрим отвечающий этой нумерации двухместный предикат 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.



Wikimedia Foundation. 2010.

Смотреть что такое "Иммунное множество" в других словарях:

  • ИММУННОЕ МНОЖЕСТВО — бесконечное множество натуральных чисел, не содержащее бесконечных рекурсивно перечислимых подмножеств. В частности, само И. м. не является рекурсивно перечислимым. И. м. по своей насыщенности рекурсивно перечислимыми подмножествами в известном… …   Математическая энциклопедия

  • Перечислимое множество — Не следует путать с счётным множеством. В теории множеств, теории алгоритмов и математической логике, перечислимое множество (эффективно перечислимое, рекурсивно перечислимое, полуразрешимое множество[1])  множество конструктивных объектов… …   Википедия

  • Разрешимое множество — В теории множеств, теории алгоритмов и математической логике, множество натуральных чисел называется разрешимым или рекурсивным, если существует алгоритм, который, получив на вход любое натуральное число, через конечное число шагов завершается и… …   Википедия

  • ПРОСТОЕ МНОЖЕСТВО — рекурсивно перечислимое множество натуральных чисел, дополнение к рого есть иммунное множество. П. м. являются промежуточными в смысле так наз. m сводимости (см. Рекурсивная теория множеств).между разрешимыми множествами и творческими… …   Математическая энциклопедия

  • Конструктивная математика — У этого термина существуют и другие значения, см. конструктивизм. Конструктивная математика абстрактная наука о конструктивных процессах[прояснить], человеческой способности осуществлять их, и об их результатах конструктивных объектах. Содержание …   Википедия

  • Конструктивизм (математика) — Конструктивная математика абстрактная наука о конструктивных процессах, человеческой способности осуществлять их, и об их результатах конструктивных объектах. Содержание 1 Абстракции конструктивной математики 2 Основные объекты рассмотрения …   Википедия

  • Патологическая анатомия внутриутробных инфекций — Внутриутробные инфекции инфекционные заболевания, возникающие вследствие анте или интранатального инфицирования. Содержание 1 Общие вопросы учения о внутриутробных инфекциях 1.1 …   Википедия

  • ИММУНИТЕТ — ИММУНИТЕТ. Содержание: История и современ. состояние учения об И. . 267 И. как явление приспособления........ 283 И. местный.................... 285 И. к животным ядам.............. 289 И. при протозойн. и спирохета, инфекциях . 291 И. к… …   Большая медицинская энциклопедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.