П ⁰₁ класс

В теории Π вычислимости ⁰₁ класс является подмножеством 2 ^ой определенной формы. Эти классы представляют интерес как технические инструменты в рамках теории рекурсии и эффективной описательной теории множеств . Они также используются при применении теории рекурсии к другим разделам математики (Cenzer 1999, стр. 39).

Определение

Набор 2 ^<ω состоит из всех конечных последовательностей нулей и единиц, а множество 2 ^ой состоит из всех бесконечных последовательностей нулей и единиц (т. е. функций из ω = {0, 1, 2, ... } до множества {0,1 }).

Дерево 2 на ^<ω является подмножеством 2 ^<ω замкнутый при взятии начальных отрезков. Элемент f из 2 ^ой это путь через дерево T на 2 ^<ω если каждый конечный начальный сегмент f находится в T .

А ( светлое лицо ) П ⁰₁ класс — это подмножество C из 2 ^ой для которого существует вычислимое дерево T такое, что C состоит ровно из путей через T . Жирный шрифт Π ⁰₁ класс — это подмножество D из 2 ^ой для которого существует оракул f в 2 ^ой и дерево поддерева T из 2 ^{< ω} из вычислимого по f такого, что D — множество путей через T .

Как эффективно закрытые множества

Жирный шрифт Π ⁰₁ классы точно такие же, как закрытые множества из 2 ^ой и, следовательно, то же самое, что и жирный шрифт Π ⁰₁ подмножество из 2 ^ой в иерархии Бореля .

Лайтфейс П ⁰₁ занятие в 2 ^ой (т. е. Π ⁰₁ классы, дерево которых вычислимо без оракула), соответствуют эффективно замкнутым множествам . Подмножество B из 2 ^ой эффективно замкнуто, если существует рекурсивно перечислимая последовательность ⟨σ _i : i ∈ ω⟩ элементов из 2 ^{< ω} такой, что каждый g ∈ 2 ^ой находится в B тогда и только тогда, когда существует такой i , что σi _— начальный сегмент B .

Связь с эффективными теориями

Для каждой эффективно аксиоматизированной теории T логики первого порядка множество всех пополнений T есть $\Pi _{1}^{0}$ сорт. Более того, для каждого $\Pi _{1}^{0}$ подмножество S из $2^{\omega }$ существует эффективно аксиоматизированная теория T такая, что каждый элемент S вычисляет пополнение T , а каждое пополнение T вычисляет элемент S (Jockusch and Soare 1972b).

См. также

Ссылки

Цензер, Дуглас (1999), " $\Pi _{1}^{0}$ классы теории вычислимости», Справочник по теории вычислимости , Stud. Logic Found. Math., т. 140, Амстердам: Северная Голландия, стр. 37 85, MR 1720779
Джокуш, Карл Г.; Соаре, Роберт И. (1972а), «Степени членов $\Pi _{1}^{0}$ классы.» (PDF) , Тихоокеанский журнал математики , 40 (3): 605–616, doi : 10.2140/pjm.1972.40.605
Джокуш, Карл Г.; Соаре, Роберт И. (1972b), " $\Pi _{1}^{0}$ Классы и степени теорий», Труды Американского математического общества , 173 : 33–56, doi : 10.1090/s0002-9947-1972-0316227-0