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

редактировать

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

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

Элементы $L α {\ displaystyle L _ {\ alpha}}$ $L _ {\ alpha }$ называются $α {\ displaystyle \ alpha}$ $\ alpha$ конечными и воспроизводят аналогичная роль конечных чисел в классической теории рекурсии.

Мы говорим, что R является процедурой редукции, если она $α {\ displaystyle \ alpha}$ $\ alpha$ рекурсивно перечислима и каждый член R имеет форму $⟨H, J, K⟩ {\ displaystyle \ langle H, J, K \ rangle}$ ${\ displaystyle \ langle H, J, K \ rangle}$ где H, J, K все α-конечны.

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

К ⊆ A ↔ ∃ H: ∃ J: [⟨H, J, K⟩ ∈ R 0 ∧ H ⊆ B ∧ J ⊆ α / B], {\ displaystyle K \ substeq A \ leftrightarrow \ exists H: \ существует J: [\ langle H, J, K \ rangle \ in R_ {0} \ wedge H \ substeq B \ wedge J \ substeq \ alpha / B],}

{\ displaystyle K \ su bseteq A \ leftrightarrow \ exists H: \ exists J: [\ langle H, J, K \ rangle \ in R_ {0} \ wedge H \ substeq B \ wedge J \ substeq \ alpha / B],}

K ⊆ α / A ↔ ∃ H: J: [⟨H, J, K⟩ ∈ R 1 ∧ H ⊆ B ∧ J ⊆ α / B]. {\ displaystyle K \ substeq \ alpha / A \ leftrightarrow \ exists H: \ exists J: [\ langle H, J, K \ rangle \ in R_ {1} \ wedge H \ substeq B \ wedge J \ substeq \ alpha / B].}

{\ displaystyle K \ substeq \ alpha / A \ leftrightarrow \ exists H: \ exists J: [\ langle H, J, K \ rangle \ in R_ {1} \ клин H \ substeq B \ wedge J \ substeq \ alpha /B visible.}

Если A рекурсивен в B, это записывается как $A ≤ α B {\ displaystyle \ scriptstyle A \ leq _ {\ alpha} B}$ ${\ displaystyle \ scriptstyle A \ leq _ {\ alpha} B}$ . По этому определению A рекурсивен в $∅ {\ displaystyle \ scriptstyle \ varnothing}$ ${\ displaystyle \ scriptstyle \ varnothing}$ (пустой набор ) тогда и только тогда, когда A рекурсивен. Однако рекурсивность A в B не эквивалентна тому, что A $Σ 1 (L α [B]) {\ displaystyle \ Sigma _ {1} (L _ {\ alpha} [B])}$ ${\ displaystyle \ Sigma _ {1} (L _ {\ alpha} [ B])}$ .

Мы говорим A является правильным, если $∀ β ∈ α: A ∩ β ∈ L α {\ displaystyle \ forall \ beta \ in \ alpha: A \ cap \ beta \ in L _ {\ alpha}}$ ${\ displaystyle \ forall \ beta \ in \ alpha: A \ cap \ beta \ in L _ {\ alpha}}$ или в другими словами, если каждая начальная часть A α-конечна.

Результат

α {\ displaystyle \ alpha}

\ alpha

рекурсия

Теорема Шора о расщеплении: пусть A будет $α {\ displaystyle \ alpha}$ $\ alpha$ рекурсивно перечислимый и регулярный. Существует $α {\ displaystyle \ alpha}$ $\ alpha$ рекурсивно перечисляемый $B 0, B 1 {\ displaystyle B_ {0}, B_ {1}}$ ${\ displaystyle B_ {0}, B_ {1}}$ такой, что $A = B 0 ∪ B 1 ∧ B 0 ∩ B 1 = ∅ ∧ A ≰ α B i (i < 2). {\displaystyle A=B_{0}\cup B_{1}\wedge B_{0}\cap B_{1}=\varnothing \wedge A\not \leq _{\alpha }B_{i}(i<2).}$ ${\ displaystyle A = B_ {0} \ cup B_ {1} \ wedge B_ {0} \ cap B_ {1} = \ varnothing \ wedge A \ not \ Leq _ {\ альфа} B_ {я} (я <2).}$

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

Ссылки

Джеральд Сакс, Высшая теория рекурсии, Springer Verlag, 1990 https://projecteuclid.org/euclid.pl/1235422631
Роберт Соар, Рекурсивно перечислимые множества и степени, Springer Verlag, 1987 https://projecteuclid.org/euclid.bams/1183541465