Immun készlet

Az immunhalmaz konstruktív objektumok (például természetes számok ) végtelen halmaza , amelyek bármely megszámlálható részhalmaza véges. A konstruktív matematikában az immunhalmazokat néha „patológiás” (a hagyományos halmazelméleti matematika szempontjából) tulajdonságokkal rendelkező objektumok példáinak megalkotására használják.

Példa

A természetes számok legegyszerűbb immunhalmaza a következőképpen szerkeszthető. Rögzítjük egy változó összes részlegesen rekurzív függvényének számozását, és figyelembe vesszük az ennek a számozásnak megfelelő kéthelyes predikátumot , kifejezve a "számmal rendelkező részlegesen rekurzív függvény természetes számra alkalmazható " feltételt. Ebben az esetben a halmaz kiegészítése $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))))\}

egy immunkészlet. Valójában bármely természetes szám esetén a halmaz legfeljebb a számnál kisebb számokat tartalmaz , ezért a halmaz végtelen. Másrészt egy halmaz bármely felsorolható részhalmaza egy változó valamely részlegesen rekurzív függvényének tartománya. Ez a függvény egy bizonyos számnak felel meg az általunk rögzített számozással - ami a halmaz felépítésének jellegéből adódóan azt jelenti, hogy a halmaz nem tartalmazhat nál nagyobb számokat . Így persze sokat. $n$ $C$ $n$ $2n$ $én$ $M$ $én$ $n$ $C$ $M$ $2n$ $M$

Lásd még

Aritmetikai halmaz

Irodalom

Rogers H. Rekurzív függvényelmélet és hatékony kiszámíthatóság . — M.: Mir, 1972.