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




Главная
Новости
Статьи
Ремонт
Каркасный дом
Несущие конструкции
Металлические конструкции
Прочность дорог
Дорожные материалы
Стальные конструкции
Воздухоопорные сооружения
Грунтовые основания




26.01.2021


26.01.2021


25.01.2021


24.01.2021


23.01.2021


21.01.2021


21.01.2021


20.01.2021


19.01.2021


19.01.2021





Яндекс.Метрика
         » » Иммунное множество

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

18.12.2020

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

Пример

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

C ⇌ { x ∈ N ∣ ( ∃ y ) ( 2 y < x ) ∧ ( T ( y , x ) ∧ ( ( ∀ z ) T ( y , z ) ⊃ ( ( z ⩽ 2 y ) ∨ ( z ⩾ x ) ) ) ) } {displaystyle C ightleftharpoons {xin mathbb {N} mid (exists y);(2y<x)land (T(y,;x)land ((forall z);T(y,;z)supset ((zleqslant 2y)lor (zgeqslant x))))}}

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