Set imunitar

O mulțime imună este un set infinit de obiecte constructive (de exemplu, numere naturale ), orice submulțime enumerabilă a cărora este finită. În matematica constructivă, seturile imune sunt uneori folosite pentru a construi exemple de obiecte cu proprietăți „patologice” (din punctul de vedere al matematicii tradiționale teoretice a mulțimilor).

Exemplu

Cel mai simplu set imun de numere naturale poate fi construit după cum urmează. Fixăm o numerotare a tuturor funcțiilor parțial recursive ale unei variabile și luăm în considerare predicatul cu două locuri corespunzător acestei numerotări , exprimând condiția „o funcție parțial recursivă cu un număr este aplicabilă unui număr natural ”. În acest caz, complementul setului $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))))\}

este un set imunitar. Într-adevăr, pentru orice număr natural, mulțimea conține cel mult numere mai mici decât numărul și, prin urmare, mulțimea este infinită. Pe de altă parte, orice subset enumerabil al unei mulțimi este domeniul unei funcții parțial recursive a unei variabile. Această funcție corespunde unui anumit număr cu numerotarea fixată de noi - ceea ce, datorită naturii construcției mulțimii , înseamnă că mulțimea nu poate conține numere mai mari de . Astfel, multe desigur. $n$ $C$ $n$ $2n$ $eu$ $M$ $eu$ $n$ $C$ $M$ $2n$ $M$

Vezi și

Mulțimea aritmetică

Literatură

Rogers H. Teoria funcției recursive și calculabilitatea efectivă . — M.: Mir, 1972.