Immun sæt

Et immunsæt er et uendeligt sæt af konstruktive objekter (f.eks. naturlige tal ), hvoraf enhver talløs delmængde er endelig. I konstruktiv matematik bruges immunsæt nogle gange til at konstruere eksempler på objekter med "patologiske" (set fra traditionel mængdeteoretisk matematik) egenskaber.

Eksempel

Det enkleste immunsæt af naturlige tal kan konstrueres som følger. Vi fikserer en vis nummerering af alle delvist rekursive funktioner af en variabel, og betragter det to-placerede prædikat svarende til denne nummerering , der udtrykker betingelsen "en delvist rekursiv funktion med et tal er anvendelig til et naturligt tal ". I dette tilfælde, komplementet af sættet $T(x,\;y)$ $x$ $y$ $I\rightleftharpoons \mathbb {N} \setminus C$

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

er et immunsæt. For ethvert naturligt tal indeholder mængden højst tal mindre end tallet , og derfor er mængden uendelig. På den anden side er enhver numerabel delmængde af et sæt domænet for en eller anden delvis rekursiv funktion af en variabel. Denne funktion svarer til et bestemt tal med den af os fastsatte nummerering - hvilket på grund af arten af sættets konstruktion betyder, at sættet ikke kan indeholde større tal end . Altså en masse selvfølgelig. $n$ $C$ $n$ $2n$ $jeg$ $M$ $jeg$ $n$ $C$ $M$ $2n$ $M$

Se også

Aritmetisk sæt

Litteratur

Rogers H. Rekursiv funktionsteori og effektiv beregnelighed . — M.: Mir, 1972.