Teorie alfa rekurze - Alpha recursion theory

v teorie rekurze, α teorie rekurze je zobecněním teorie rekurze do podskupin přípustná řadová čísla ${displaystyle alpha}$. Přípustná sada je uzavřena pod ${displaystyle Sigma _ {1} (L_ {alpha})}$ funkce. Li ${displaystyle L_ {alpha}}$ je model Teorie množin Kripke – Platek pak ${displaystyle alpha}$ je přípustný pořadový řád. V tom, co následuje ${displaystyle alpha}$ se považuje za pevnou.

Objekty studia v ${displaystyle alpha}$ rekurze jsou podmnožiny ${displaystyle alpha}$. A se říká, že je ${displaystyle alpha}$ rekurzivně spočetné Pokud to je ${displaystyle Sigma _ {1}}$ definovatelný nad ${displaystyle L_ {alpha}}$. A je rekurzivní, pokud A i ${displaystyle alpha setminus A}$ (jeho doplněk v ${displaystyle alpha}$) jsou ${displaystyle alpha}$ rekurzivně spočetné.

Členové ${displaystyle L_ {alpha}}$ jsou nazývány ${displaystyle alpha}$ konečná a hrají podobnou roli jako konečná čísla v klasické teorii rekurze.

Říkáme, že R je redukční procedura, pokud je ${displaystyle alpha}$ rekurzivně vyčíslitelné a každý člen R je ve formě ${displaystyle langle H, J, Kangle}$ kde H, J, K. jsou všechny α-konečné.

A se říká, že je α-rekurzivní v B pokud existují ${displaystyle R_ {0}, R_ {1}}$ redukční postupy, které:

${displaystyle Ksubseteq Aleftrightarrow existuje H: existuje J: [jazyk H, J, Kangle v R_ ​​{0} klín Hsubseteq Bwedge Jsubseteq alfa / B],}$

${displaystyle Ksubseteq alpha / Aleftrightarrow existuje H: existuje J: [jazyk H, J, Kangle v R_ ​​{1} klín Hsubseteq Bwedge Jsubseteq alfa / B].}$

Li A je rekurzivní v B toto je psáno ${displaystyle scriptstyle Aleq _ {alpha} B}$. Podle této definice A je rekurzivní v ${displaystyle scriptstyle varnothing}$ (dále jen prázdná sada ) právě tehdy A je rekurzivní. Rekurzivní bytost A v B však není ekvivalentní bytosti A. ${displaystyle Sigma _ {1} (L_ {alpha} [B])}$.

Říkáme A je pravidelné, pokud ${displaystyle forall eta in alpha: Acap eta in L_ {alpha}}$ nebo jinými slovy, pokud každá počáteční část A je α-konečný.

Výsledky v ${displaystyle alpha}$ rekurze

Shoreova věta o rozdělení: Nechť je A ${displaystyle alpha}$ rekurzivně spočetné a pravidelné. Existují ${displaystyle alpha}$ rekurzivně spočetné ${displaystyle B_ {0}, B_ {1}}$ takhle ${displaystyle A = B_ {0} pohár B_ {1} klín B_ {0} čepice B_ {1} = varnothing klín Aot leq _ {alpha} B_ {i} (i <2).}$

Shoreova věta o hustotě: Let A, C být α-regulární rekurzivně spočetné množiny takové ${displaystyle scriptstyle A <_ {alpha} C}$ pak existuje běžná α-rekurzivně spočetná množina B takhle ${displaystyle scriptstyle A <_ {alpha} B <_ {alpha} C}$.

Reference

• Gerald Sacks, Vyšší teorie rekurzeSpringer Verlag, 1990 https://projecteuclid.org/euclid.pl/1235422631
• Robert Soare, Rekurzivně vyčíslitelné sady a stupněSpringer Verlag, 1987 https://projecteuclid.org/euclid.bams/1183541465