Imunitní sada

Imunitní množina je nekonečná množina konstruktivních objektů (například přirozených čísel ), jejichž jakákoliv spočetná podmnožina je konečná. V konstruktivní matematice se někdy používají imunní množiny ke konstrukci příkladů objektů s „patologickými“ (z hlediska tradiční množinově teoretické matematiky) vlastnostmi.

Příklad

Nejjednodušší imunitní množinu přirozených čísel lze sestavit následovně. Opravíme nějaké číslování všech částečně rekurzivních funkcí jedné proměnné a uvažujeme dvoumístný predikát odpovídající tomuto číslování , vyjadřující podmínku "částečně rekurzivní funkce s číslem je použitelná pro přirozené číslo ". V tomto případě doplněk sestavy $T(x,\;y)$ $X$ $y$ $I\rightleftharpoons \mathbb {N} \setminus C$

C\rightleftharpoons \{x\in \mathbb {N} \mid (\existuje y)\;(2y<x)\land (T(y,\;x)\land ((\forall z)\ ;T(y,\;z)\supset ((z\leqslant 2y)\lor (z\geqslant x))))\}

je imunitní sada. Pro jakékoli přirozené číslo totiž množina obsahuje nanejvýš čísla menší než číslo , a proto je množina nekonečná. Na druhou stranu jakákoliv vyčíslitelná podmnožina množiny je doménou nějaké částečně rekurzivní funkce jedné proměnné. Tato funkce odpovídá určitému číslu s námi pevně stanoveným číslováním - což vzhledem k povaze konstrukce množiny znamená, že množina nemůže obsahovat čísla větší než . Tak samozřejmě hodně . $n$ $C$ $n$ $2n$ $já$ $M$ $já$ $n$ $C$ $M$ $2n$ $M$

Viz také

Aritmetická sada

Literatura

Rogers H. Teorie rekurzivní funkce a efektivní vyčíslitelnost . — M.: Mir, 1972.