Immunuppsättning

En immunmängd är en oändlig uppsättning av konstruktiva objekt (till exempel naturliga tal ), vars alla uppräknade delmängder är ändliga. I konstruktiv matematik används ibland immunmängder för att konstruera exempel på objekt med "patologiska" (ur traditionell mängdteoretisk matematiks synvinkel ) egenskaper.

Exempel

Den enklaste immunuppsättningen av naturliga tal kan konstrueras enligt följande. Vi fixar en viss numrering av alla delvis rekursiva funktioner för en variabel och betraktar det tvåställiga predikatet som motsvarar denna numrering , vilket uttrycker villkoret "en delvis rekursiv funktion med ett tal är tillämplig på ett naturligt tal ". I det här fallet, komplementet till uppsättningen $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))))\}

är en immunuppsättning. Faktum är att för alla naturliga tal innehåller mängden högst tal mindre än talet och därför är mängden oändlig. Å andra sidan är varje uppräknad delmängd av en mängd domänen för någon delvis rekursiv funktion av en variabel. Denna funktion motsvarar ett visst antal med den numrering som vi har fastställt - vilket på grund av mängdens konstruktion gör att mängden inte kan innehålla siffror större än . Alltså en hel del såklart. $n$ $C$ $n$ $2n$ $jag$ $M$ $jag$ $n$ $C$ $M$ $2n$ $M$

Se även

Aritmetisk uppsättning

Litteratur

Rogers H. Rekursiv funktionsteori och effektiv beräkningsbarhet . — M.: Mir, 1972.