Теория альфа-рекурсии - Alpha recursion theory

В теория рекурсии, α теория рекурсии является обобщением теория рекурсии к подмножествам допустимые порядковые номера ${displaystyle alpha}$ . Допустимое множество замкнуто относительно ${displaystyle Sigma _ {1} (L_ {alpha})}$ функции. Если ${displaystyle L_ {alpha}}$ это модель Теория множеств Крипке – Платека. тогда ${displaystyle alpha}$ допустимый ординал. В дальнейшем ${displaystyle alpha}$ считается исправленным.

Объекты исследования в ${displaystyle alpha}$ рекурсия - это подмножества ${displaystyle alpha}$ . А называется ${displaystyle alpha}$ рекурсивно перечислимый если это ${displaystyle Sigma _ {1}}$ определяемый по ${displaystyle L_ {alpha}}$ . A рекурсивно, если и A, и ${displaystyle alpha setminus A}$ (его дополнение в ${displaystyle alpha}$ ) находятся ${displaystyle alpha}$ рекурсивно перечислимый.

Члены ${displaystyle L_ {alpha}}$ называются ${displaystyle alpha}$ конечны и играют роль, аналогичную конечным числам в классической теории рекурсии.

Мы говорим, что R - процедура редукции, если она ${displaystyle alpha}$ рекурсивно перечислим, и каждый член R имеет вид ${displaystyle langle H, J, Kangle}$ куда ЧАС, J, K все α-конечны.

А называется α-рекурсивным в B если есть ${displaystyle R_ {0}, R_ {1}}$ процедуры сокращения, такие как:

{displaystyle Ksubseteq Aleftrightarrow exists H: exists J: [langle H, J, Kangle in R_ {0} wedge Hsubseteq Bwedge Jsubseteq alpha / B],}

{displaystyle Ksubseteq alpha / Aleftrightarrow exists H: exists J: [langle H, J, Kangle in R_ {1} wedge Hsubseteq Bwedge Jsubseteq alpha / B].}

Если А рекурсивно в B это написано ${displaystyle scriptstyle Aleq _ {alpha} B}$ . По этому определению А рекурсивно в ${displaystyle scriptstyle varnothing}$ (в пустой набор ) если и только если А рекурсивно. Однако рекурсивность A в B не эквивалентна тому, что A является ${displaystyle Sigma _ {1} (L_ {alpha} [B])}$ .

Мы говорим А регулярно, если ${displaystyle forall eta в альфа: Acap eta в L_ {alpha}}$ или другими словами, если каждая начальная часть А α-конечно.

Результаты в ${displaystyle alpha}$ рекурсия

Теорема Шора о расщеплении: пусть A будет ${displaystyle alpha}$ рекурсивно перечислимые и регулярные. Существуют ${displaystyle alpha}$ рекурсивно перечислимый ${displaystyle B_ {0}, B_ {1}}$ такой, что ${displaystyle A = B_ {0} чашка B_ {1} клин B_ {0} крышка B_ {1} = varnothing клин Aot leq _ {alpha} B_ {i} (i <2).}$

Теорема Шора о плотности: Пусть А, C - α-регулярные рекурсивно перечислимые множества такие, что ${displaystyle scriptstyle A <_ {alpha} C}$ то существует регулярное α-рекурсивно перечислимое множество B такой, что ${displaystyle scriptstyle A <_ {alpha} B <_ {alpha} C}$ .

Теория альфа-рекурсии - Alpha recursion theory

Результаты в α {displaystyle alpha} рекурсия

Рекомендации

Результаты в ${displaystyle alpha}$ рекурсия