WikiDer > Π01 класс

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

Определение

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

А дерево на 2^ω является подмножеством 2^ω закрывается при взятии начальных отрезков. Элемент ж из 2^ω это дорожка через дерево Т на 2^ω если каждый конечный начальный отрезок ж в Т.

А (Lightface) Π⁰₁ учебный класс это подмножество C из 2^ω для которого есть вычислимый дерево Т такой, что C состоит именно из путей через Т. А жирный Π⁰₁ учебный класс это подмножество D из 2^ω для которого есть оракул ж через 2^ω и поддерево Т из 2^<ω из вычислимого из ж такой, что D это набор путей через Т.

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

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

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

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

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

Смотрите также

• Арифметическая иерархия
• Базисная теорема (вычислимость)

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

• Кензер, Дуглас (1999), "${ displaystyle Pi _ {1} ^ {0}}$ занятия по теории вычислимости », Справочник по теории вычислимости, Stud. Логика найдена. Математика, 140, Амстердам: Северная Голландия, стр. 37 85, МИСТЕР 1720779
• Jockush, Carl G .; Соаре, Роберт I. (1972a), "Степени членов ${ displaystyle Pi _ {1} ^ {0}}$ классы ". (PDF), Тихоокеанский математический журнал, 40 (3): 605–616, Дои:10.2140 / pjm.1972.40.605
• Jockush, Carl G .; Соаре, Роберт I. (1972b) "${ displaystyle Pi _ {1} ^ {0}}$ Курсы и степени по теории », Труды Американского математического общества, 173: 33–56, Дои:10.1090 / с0002-9947-1972-0316227-0