Арифметическая иерархия

редактировать
Иерархия классов сложности для формул, определяющих наборы Иллюстрация взаимодействия уровней иерархии и некоторых основных категорий наборов

В математической логике, арифметическая иерархия, арифметическая иерархия или Клини - Иерархия Мостовского классифицирует определенные наборы на основе сложности формул, которые их определяют. Любой набор, получивший классификацию, называется арифметическим .

Арифметическая иерархия важна в теории рекурсии, эффективной дескриптивной теории множеств и при изучении формальных теорий, таких как Арифметика Пеано.

Алгоритм Тарского – Куратовски предоставляет простой способ получить верхнюю границу классификации, присвоенной формуле и определяемому ею набору.

гиперарифметическая иерархия и аналитическая иерархия расширяют арифметическую иерархию для классификации дополнительных формул и наборов.

Содержание

  • 1 Арифметическая иерархия формул
  • 2 Арифметическая иерархия наборов натуральных чисел
  • 3 Релятивизированные арифметические иерархии
  • 4 Арифметическая сводимость и степени
  • 5 Арифметическая иерархия подмножеств Пространство Кантора и Бэра
  • 6 Расширения и варианты
  • 7 Значение обозначения
  • 8 Примеры
  • 9 Свойства
  • 10 Отношение к машинам Тьюринга
    • 10.1 Вычислимые множества
    • 10.2 Краткое изложение основных результаты
  • 11 Связь с другими иерархиями
  • 12 См. также
  • 13 Ссылки

Арифметическая иерархия формул

Арифметическая иерархия сначала назначает классификации формулам на языке -порядковая арифметика. Классификации обозначаются Σ n 0 {\ displaystyle \ Sigma _ {n} ^ {0}}\Sigma _{n}^{0}и Π n 0 {\ displaystyle \ Pi _ {n} ^ {0}. }\ Pi ^ 0_n для натуральных чисел n (включая 0). Греческие буквы здесь - это символы lightface, которые указывают на то, что формулы не содержат заданных параметров.

Если формула ϕ {\ displaystyle \ phi}\phi логически эквивалентна формуле только с ограниченными кванторами, то ϕ {\ displaystyle \ phi}\phi присвоены классификации Σ 0 0 {\ displaystyle \ Sigma _ {0} ^ {0}}\Sigma^0_0и Π 0 0 {\ displaystyle \ Pi _ {0} ^ {0}}\Pi^0_0.

Классификации Σ n 0 {\ displaystyle \ Sigma _ {n} ^ {0}}\Sigma _{n}^{0}и Π n 0 {\ displaystyle \ Pi _ {n} ^ {0}}\ Pi ^ 0_n определяются индуктивно для любого натурального числа n по следующим правилам:

  • Если ϕ {\ displaystyle \ phi}\phi логически эквивалентен формуле вида ∃ m 1 ∃ m 2 ⋯ ∃ mk ψ {\ displaystyle \ exists m_ {1} \ exists m_ {2} \ cdots \ exists m_ {k} \ psi}{\displaystyle \exists m_{1}\e xists m_{2}\cdots \exists m_{k}\psi }, где ψ {\ displaystyle \ psi}\psi равно Π n 0 {\ displaystyle \ Pi _ {n} ^ {0}}\ Pi ^ 0_n , тогда ϕ {\ displaystyle \ phi}\phi назначается классификация Σ n + 1 0 {\ displaystyle \ Sigma _ {n + 1} ^ {0}}\Sigma^0_{n+1}.
  • Если ϕ {\ displaystyle \ phi}\phi логически равно эквивалентно формуле вида ∀ m 1 ∀ m 2 ⋯ ∀ mk ψ {\ displaystyle \ forall m_ {1} \ forall m_ {2} \ cdots \ forall m_ {k} \ psi}{\displaystyle \forall m_{1}\forall m_{2}\cdots \ forall m_{k}\psi }, где ψ {\ displaystyle \ psi}\psi равно Σ n 0 {\ displaystyle \ Sigma _ {n} ^ {0}}\Sigma _{n}^{0}, затем ϕ {\ displaystyle \ phi}\phi присвоена классификация Π n + 1 0 {\ displaystyle \ Pi _ {n + 1} ^ {0}}\Pi^0_{n+1}.

Кроме того, a Σ n 0 {\ displaystyle \ Sigma _ {n} ^ {0}}\Sigma _{n}^{0}формула эквивалентна формуле, которая начинается с некоторых кванторов существования и чередуется с n - 1 {\ displaystyle n-1}n-1раз между сериями экзистенциальных и универсальных кванторов ; а формула Π n 0 {\ displaystyle \ Pi _ {n} ^ {0}}\ Pi ^ 0_n эквивалентна формуле, которая начинается с некоторых универсальных кванторов и чередуется аналогичным образом.

Поскольку каждая формула эквивалентна формуле в предварительной нормальной форме, каждой формуле без установленных квантификаторов назначается по крайней мере одна классификация. Поскольку избыточные кванторы могут быть добавлены к любой формуле, как только формуле будет присвоена классификация Σ n 0 {\ displaystyle \ Sigma _ {n} ^ {0}}\Sigma _{n}^{0}или Π n 0 {\ displaystyle \ Pi _ {n} ^ {0}}\ Pi ^ 0_n ему будут присвоены классификации Σ r 0 {\ displaystyle \ Sigma _ {r} ^ {0}}{\displaystyle \Sigma _{r}^{0}}и Π r 0 {\ displaystyle \ Pi _ {r} ^ {0}}{\displaystyle \Pi _{r}^{0}}для каждого r больше n. Таким образом, наиболее важной классификацией, назначаемой формуле, является класс с наименьшим n, поскольку этого достаточно для определения всех остальных классификаций.

Арифметическая иерархия множеств натуральных чисел

Множество натуральных чисел X определяется формулой φ на языке арифметики Пеано (язык первого порядка с символы «0» для нуля, «S» для функции-последователя, «+» для сложения, «×» для умножения и «=» для равенства), если элементы X являются в точности числами, которые удовлетворяют φ. То есть для всех натуральных чисел n,

n ∈ X ⇔ N ⊨ φ (n _), {\ displaystyle n \ in X \ Leftrightarrow \ mathbb {N} \ models \ varphi ({\ underline {n}}),}{\displaystyle n\in X\Leftrightarrow \mathbb {N} \models \varphi ({\underline {n}}),}

где n _ {\ displaystyle {\ underline {n}}}\underline n- число на языке арифметики, соответствующее n {\ displaystyle n}n. Множество определимо в арифметике первого порядка, если оно определено некоторой формулой в языке арифметики Пеано.

Каждому набору X натуральных чисел, который может быть определен в арифметике первого порядка, присваиваются классификации вида Σ n 0 {\ displaystyle \ Sigma _ {n} ^ {0}}\Sigma _{n}^{0}, Π n 0 {\ displaystyle \ Pi _ {n} ^ {0}}\ Pi ^ 0_n и Δ n 0 {\ displaystyle \ Delta _ {n} ^ {0}}\ Delta _ {n} ^ {0} , где n {\ displaystyle n}n- натуральное число, как показано ниже. Если X определяется формулой Σ n 0 {\ displaystyle \ Sigma _ {n} ^ {0}}\Sigma _{n}^{0}, то X присваивается классификация Σ n 0 {\ displaystyle \ Sigma _ {n} ^ {0}}\Sigma _{n}^{0}. Если X определяется формулой Π n 0 {\ displaystyle \ Pi _ {n} ^ {0}}\ Pi ^ 0_n , то X присваивается классификация Π n 0 {\ displaystyle \ Pi _ {n} ^ {0}}\ Pi ^ 0_n . Если X равно Σ n 0 {\ displaystyle \ Sigma _ {n} ^ {0}}\Sigma _{n}^{0}и Π n 0 {\ displaystyle \ Pi _ {n} ^ {0} }\ Pi ^ 0_n , тогда X {\ displaystyle X}Xназначается дополнительная классификация Δ n 0 {\ displaystyle \ Delta _ {n} ^ {0}}\ Delta _ {n} ^ {0} .

Обратите внимание, что редко имеет смысл говорить о формулах Δ n 0 {\ displaystyle \ Delta _ {n} ^ {0}}\ Delta _ {n} ^ {0} ; первый квантор формулы либо экзистенциальный, либо универсальный. Таким образом, набор Δ n 0 {\ displaystyle \ Delta _ {n} ^ {0}}\ Delta _ {n} ^ {0} не определяется Δ n 0 {\ displaystyle \ Delta _ {n} ^ {0}}\ Delta _ {n} ^ {0} формула; скорее, есть и Σ n 0 {\ displaystyle \ Sigma _ {n} ^ {0}}\Sigma _{n}^{0}, и Π n 0 {\ displaystyle \ Pi _ {n} ^ {0 }}\ Pi ^ 0_n формулы, определяющие набор.

Параллельное определение используется для определения арифметической иерархии конечных декартовых степеней набора натуральных чисел. Вместо формул с одной свободной переменной, формулы с k свободными числовыми переменными используются для определения арифметической иерархии на наборах k- кортежей натуральных чисел. Фактически, они связаны с использованием функции спаривания .

Релятивизированные арифметические иерархии

Так же, как мы можем определить, что означает, что набор X рекурсивен относительно другой набор Y, позволяя вычислению, определяющему X, обращаться к Y как к оракулу, мы можем расширить это понятие на всю арифметическую иерархию и определить, что означает для X быть Σ n 0 {\ displaystyle \ Sigma _ {n} ^ {0}}\Sigma _{n}^{0}, Δ n 0 {\ displaystyle \ Delta _ {n} ^ {0}}\ Delta _ {n} ^ {0} или Π n 0 {\ displaystyle \ Pi _ {n} ^ {0} }\ Pi ^ 0_n в Y, соответственно обозначается Σ n 0, Y {\ displaystyle \ Sigma _ {n} ^ {0, Y}}\ Sigma ^ {0, Y} _n Δ n 0, Y {\ displaystyle \ Delta _ {n} ^ {0, Y}}\Delta^{0,Y}_nи Π n 0, Y {\ displaystyle \ Pi _ {n} ^ {0, Y}}\ Pi ^ {0, Y} _n . Для этого зафиксируйте набор целых чисел Y и добавьте предикат членства в Y в язык арифметики Пеано. Затем мы говорим, что X находится в Σ n 0, Y {\ displaystyle \ Sigma _ {n} ^ {0, Y}}\ Sigma ^ {0, Y} _n , если он определяется Σ n 0 { \ displaystyle \ Sigma _ {n} ^ {0}}\Sigma _{n}^{0}формула на этом расширенном языке. Другими словами, X равен Σ n 0, Y {\ displaystyle \ Sigma _ {n} ^ {0, Y}}\ Sigma ^ {0, Y} _n , если он определен Σ n 0 {\ displaystyle \ Sigma _ {n} ^ {0}}\Sigma^{0}_nформула позволяет задавать вопросы о членстве в Y. В качестве альтернативы можно просмотреть Σ n 0, Y {\ displaystyle \ Sigma _ {n} ^ {0, Y}}\ Sigma ^ {0, Y} _n наборы как те наборы, которые могут быть построены, начиная с наборов, рекурсивных по Y и поочередно принимая объединений и пересечений этих наборов до п раз.

Например, пусть Y будет набором целых чисел. Пусть X будет набором чисел, делящихся на элемент Y. Тогда X определяется формулой ϕ (n) = ∃ m ∃ t (Y (m) ∧ m × t = n) {\ displaystyle \ phi (N) = \ существует m \ существует t (Y (m) \ land m \ times t = n)}{\displaystyle \phi (n)=\exists m\exists t(Y(m)\land m\times t=n)}, поэтому X находится в Σ 1 0, Y {\ displaystyle \ Sigma _ { 1} ^ {0, Y}}\Sigma^{0,Y}_1(на самом деле он находится в Δ 0 0, Y {\ displaystyle \ Delta _ {0} ^ {0, Y}}\Delta^{0,Y}_0также, поскольку мы могли связать оба квантора числом n).

Арифметическая сводимость и степени

Арифметическая сводимость - это промежуточное понятие между сводимостью Тьюринга и гиперарифметической сводимостью.

Множество арифметической (также арифметический и арифметически определяемый ), если он определен некоторой формулой на языке арифметики Пеано. Эквивалентно X является арифметическим, если X равно Σ n 0 {\ displaystyle \ Sigma _ {n} ^ {0}}\Sigma _{n}^{0}или Π n 0 {\ displaystyle \ Pi _ {n} ^ {0}}\ Pi ^ 0_n для некоторого целого числа n. Множество X является арифметическим в множестве Y, обозначается X ≤ AY ​​{\ displaystyle X \ leq _ {A} Y}X \leq_A Y, если X определяется как некоторая формула в язык арифметики Пеано, расширенный предикатом для принадлежности к Y. Эквивалентно, X является арифметическим в Y, если X находится в Σ n 0, Y {\ displaystyle \ Sigma _ {n} ^ {0, Y}}\ Sigma ^ {0, Y} _n или Π n 0, Y {\ displaystyle \ Pi _ {n} ^ {0, Y}}\ Pi ^ {0, Y} _n для некоторого целого числа n. Синонимом X ≤ AY ​​{\ displaystyle X \ leq _ {A} Y}X \leq_A Yявляется: X арифметически сводится к Y.

Соотношение Икс ≤ AY ​​{\ displaystyle X \ leq _ {A} Y}X \leq_A Yрефлексивно и транзитивно, и, следовательно, отношение ≡ A {\ displaystyle \ Equiv _ {A}}\ Equiv_A определяется правилом

Икс ≡ AY ⇔ X ≤ AY ​​∧ Y ≤ AX {\ displaystyle X \ Equiv _ {A} Y \ Leftrightarrow X \ leq _ {A} Y \ land Y \ leq _ { A} X}{\ Displaystyle X \ Equiv _ {A} Y \ Leftrightarrow X \ leq _{A}Y\land Y\leq _{A}X}

- отношение эквивалентности. Классы эквивалентности этого отношения называются арифметическими степенями ; они частично упорядочены в соответствии с ≤ A {\ displaystyle \ leq _ {A}}\leq_A.

Арифметическая иерархия подмножеств пространства Кантора и Бэра

пространство Кантора, обозначенное 2 ω {\ displaystyle 2 ^ {\ omega}}2^{ \omega}- множество всех бесконечных последовательностей нулей и единиц; пространство Бэра, обозначаемое ω ω {\ displaystyle \ omega ^ {\ omega}}\omega^{\omega}или N {\ displaystyle {\ mathcal {N}}}{\ mathcal {N}} - это множество всех бесконечных последовательностей натуральных чисел. Обратите внимание, что элементы пространства Кантора можно отождествить с наборами целых чисел, а элементы пространства Бэра - с функциями от целых до целых чисел.

Обычная аксиоматизация арифметики второго порядка использует язык, основанный на множествах, в котором кванторы множеств естественным образом могут рассматриваться как квантификаторы в пространстве Кантора. Подмножеству пространства Кантора присваивается классификация Σ n 0 {\ displaystyle \ Sigma _ {n} ^ {0}}\Sigma _{n}^{0}, если он определяется с помощью Σ n 0 {\ displaystyle \ Sigma _ {n} ^ {0}}\Sigma _{n}^{0}формула. Набору присваивается классификация Π n 0 {\ displaystyle \ Pi _ {n} ^ {0}}\ Pi ^ 0_n , если он определяется с помощью Π n 0 {\ displaystyle \ Pi _ {n} ^ {0}}\ Pi ^ 0_n формула. Если оба набора: Σ n 0 {\ displaystyle \ Sigma _ {n} ^ {0}}\Sigma _{n}^{0}и Π n 0 {\ displaystyle \ Pi _ {n} ^ {0 }}\ Pi ^ 0_n , тогда ему дается дополнительная классификация Δ n 0 {\ displaystyle \ Delta _ {n} ^ {0}}\ Delta _ {n} ^ {0} . Например, пусть O ⊂ 2 ω {\ displaystyle O \ subset 2 ^ {\ omega}}O\subset 2^{\omega}будет набором всех бесконечных двоичных строк, которые не все 0 (или, что эквивалентно, набор все непустые наборы целых чисел). Поскольку O = {X ∈ 2 ω | ∃ N (Икс (N) = 1)} {\ Displaystyle O = \ {X \ in 2 ^ {\ omega} | \ существует n (X (n) = 1) \}}O = \ {X \ in 2 ^ \ omega | \ существует п (Икс (п) = 1) \} мы видим что O {\ displaystyle O}Oопределяется формулой Σ 1 0 {\ displaystyle \ Sigma _ {1} ^ {0}}\Sigma _{1}^{0}и, следовательно, является набор Σ 1 0 {\ displaystyle \ Sigma _ {1} ^ {0}}\Sigma _{1}^{0}.

Обратите внимание на то, что хотя элементы пространства Кантора (рассматриваемые как наборы целых чисел) и подмножества пространства Кантора классифицируются в арифметических иерархиях, это не одна и та же иерархия. На самом деле отношения между двумя иерархиями интересны и нетривиальны. Например, элементы Π n 0 {\ displaystyle \ Pi _ {n} ^ {0}}\ Pi ^ 0_n пространства Кантора не совпадают (в общем) с элементами X { \ displaystyle X}Xпространства Кантора, так что {X} {\ displaystyle \ {X \}}\{X\}является Π n 0 {\ displaystyle \ Pi _ {n} ^ {0}}\ Pi ^ 0_n подмножество пространства Кантора. Однако есть много интересных результатов, связанных с этими двумя иерархиями.

Есть два способа, которыми подмножество пространства Бэра может быть классифицировано в арифметической иерархии.

  • Подмножество пространства Бэра имеет соответствующее подмножество пространства Кантора под картой, которая принимает каждую функцию от ω {\ displaystyle \ omega}\omega до ω {\ displaystyle \ omega}\omega к характеристической функции его графика. Подмножеству пространства Бэра присваивается классификация Σ n 1 {\ displaystyle \ Sigma _ {n} ^ {1}}\Sigma^1_n, Π n 1 {\ displaystyle \ Pi _ {n} ^ {1}}\ Pi ^ 1_n или Δ n 1 {\ displaystyle \ Delta _ {n} ^ {1}}\Delta _{n}^{1}тогда и только тогда, когда соответствующее подмножество пространства Кантора имеет ту же классификацию.
  • Эквивалентное определение аналитической иерархии в пространстве Бэра дается путем определения аналитической иерархии формул с использованием функциональной версии арифметики второго порядка; тогда аналитическая иерархия на подмножествах пространства Кантора может быть определена из иерархии на пространстве Бэра. Это альтернативное определение дает точно такие же классификации, как и первое определение.

Параллельное определение используется для определения арифметической иерархии конечных декартовых степеней пространства Бэра или пространства Кантора с использованием формул с несколькими свободными переменными. Арифметическая иерархия может быть определена на любом действующем польском пространстве ; определение особенно просто для пространств Кантора и Бэра, потому что они соответствуют языку обычной арифметики второго порядка.

Обратите внимание, что мы также можем определить арифметическую иерархию подмножеств пространств Кантора и Бэра относительно некоторого набора целых чисел. На самом деле жирный шрифт Σ n 0 {\ displaystyle \ mathbf {\ Sigma} _ {n} ^ {0}}{\ displ aystyle \ mathbf {\ Sigma} _ {n} ^ {0}} - это просто объединение Σ n 0, Y {\ displaystyle \ Sigma _ {n} ^ {0, Y}}\ Sigma ^ {0, Y} _n для всех наборов целых чисел Y. Обратите внимание, что иерархия жирным шрифтом - это просто стандартная иерархия наборов Бореля.

Расширения и варианты

Можно определить арифметическую иерархию формул, используя язык, расширенный функциональным символом для каждой примитивной рекурсивной функции. Этот вариант немного меняет классификацию Σ 0 0 = Π 0 0 = Δ 0 0 {\ displaystyle \ Sigma _ {0} ^ {0} = \ Pi _ {0} ^ {0} = \ Delta _ { 0} ^ {0}}{\displaystyle \Sigma _{0}^{0}=\Pi _{0}^{0}= \Delta _{0}^{0}}, поскольку использование примитивных рекурсивных функций в арифметике Пеано первого порядка требует, как правило, неограниченного квантификатора существования и, следовательно, некоторых наборов, которые находятся в Σ 0 0 {\ displaystyle \ Sigma _ {0} ^ {0}}\Sigma^0_0по этому определению находятся в Σ 1 0 {\ displaystyle \ Sigma _ {1} ^ {0}}\Sigma _{1}^{0}по определению, данному в начале статьи. Σ 1 0 {\ displaystyle \ Sigma _ {1} ^ {0}}\Sigma _{1}^{0}и, таким образом, все более высокие классы в иерархии остаются неизменными.

Более семантическая вариация иерархии может быть определена для всех конечных отношений натуральных чисел; используется следующее определение. Каждое вычислимое отношение определяется как Σ 0 0 = Π 0 0 = Δ 0 0 {\ displaystyle \ Sigma _ {0} ^ {0} = \ Pi _ {0} ^ {0} = \ Delta _ { 0} ^ {0}}{\displaystyle \Sigma _{0}^{0}=\Pi _{0}^{0}= \Delta _{0}^{0}}. Классификации Σ n 0 {\ displaystyle \ Sigma _ {n} ^ {0}}\Sigma _{n}^{0}и Π n 0 {\ displaystyle \ Pi _ {n} ^ {0}}\ Pi ^ 0_n определяются индуктивно по следующим правилам.

  • Если отношение R (n 1,…, nl, m 1,…, mk) {\ displaystyle R (n_ {1}, \ ldots, n_ {l}, m_ {1}, \ ldots, m_ {k}) \,}R(n_1,\ldots,n_l,m_1,\ldots, m_k)\,равно Σ n 0 {\ displaystyle \ Sigma _ {n} ^ {0}}\Sigma _{n}^{0}, тогда отношение S ( n 1,…, nl) знак равно ∀ m 1 ⋯ ∀ mk R (n 1,…, nl, m 1,…, mk) {\ displaystyle S (n_ {1}, \ ldots, n_ {l}) = \ forall m_ {1} \ cdots \ forall m_ {k} R (n_ {1}, \ ldots, n_ {l}, m_ {1}, \ ldots, m_ {k})}S(n_1,\ldots, n_l) = \forall m_1\cdots \forall m_k R(n_1,\ldots,n_l,m_1,\ldots,m_k)определено быть Π n + 1 0 {\ displaystyle \ Pi _ {n + 1} ^ {0}}\Pi^0_{n+1}
  • Если отношение R (n 1,…, nl, m 1,…, mk) {\ displaystyle R (n_ {1}, \ ldots, n_ {l}, m_ {1}, \ ldots, m_ {k}) \,}R(n_1,\ldots,n_l,m_1,\ldots, m_k)\,равно Π n 0 {\ displaystyle \ Pi _ {n} ^ {0}}\ Pi ^ 0_n , тогда отношение S (n 1,…, nl) = ∃ m 1 ⋯ ∃ mk R (n 1,…, nl, m 1,…, mk) {\ displaystyle S (n_ {1}, \ ldots, n_ {l}) = \ exists m_ {1} \ cdots \ exists m_ {k} R (n_ {1}, \ ldots, n_ {l}, m_ {1}, \ ldots, m_ {k})}S(n_1,\ldots,n_l) = \exists m_1\cdots \exists m_k R(n_1,\ldots,n_l,m_1,\ldots,m_k)определяется как Σ n + 1 0 {\ displaystyle \ Sigma _ {n + 1} ^ {0 }}\Sigma^0_{n+1}

Этот вариант немного меняет классификацию сомов. е наборы. В частности, Σ 0 0 = Π 0 0 = Δ 0 0 {\ displaystyle \ Sigma _ {0} ^ {0} = \ Pi _ {0} ^ {0} = \ Delta _ {0} ^ { 0}}{\displaystyle \Sigma _{0}^{0}=\Pi _{0}^{0}= \Delta _{0}^{0}}как класс наборов (определяемых отношениями в классе) идентичен Δ 1 0 {\ displaystyle \ Delta _ {1} ^ {0}}\Delta^0_1, как было определено ранее. Его можно расширить, чтобы охватить финитарные отношения в натуральных числах, пространстве Бэра и пространстве Кантора.

Значение нотации

Нотации арифметической иерархии в формулах могут быть приданы следующие значения.

Нижний индекс n {\ displaystyle n}nв символах Σ n 0 {\ displaystyle \ Sigma _ {n} ^ {0}}\Sigma _{n}^{0}и Π n 0 {\ displaystyle \ Pi _ {n} ^ {0}}\ Pi ^ 0_n указывает количество чередований блоков квантификаторов универсальных и экзистенциальных чисел, которые используются в формуле. Более того, самый внешний блок существует в формулах Σ n 0 {\ displaystyle \ Sigma _ {n} ^ {0}}\Sigma _{n}^{0}и универсален в Π n 0 {\ displaystyle \ Pi _ {n} ^ {0}}\ Pi ^ 0_n формулы.

Верхний индекс 0 {\ displaystyle 0}{\displaystyle 0}в символах Σ n 0 {\ displaystyle \ Sigma _ {n} ^ {0}}\Sigma _{n}^{0}, Π n 0 {\ displaystyle \ Pi _ {n} ^ {0}}\ Pi ^ 0_n и Δ n 0 {\ displaystyle \ Delta _ {n} ^ {0}}\ Delta _ {n} ^ {0} указывает тип объектов, по которым проводится количественная оценка. Объекты типа 0 - это натуральные числа, а объекты типа i + 1 {\ displaystyle i + 1}i + 1 - это функции, которые сопоставляют набор объектов типа i {\ displaystyle i}i в натуральные числа. Количественная оценка объектов более высокого типа, таких как функции от натуральных чисел к натуральным числам, описывается надстрочным индексом больше 0, как в аналитической иерархии. Верхний индекс 0 указывает кванторы над числами, верхний индекс 1 будет указывать количественную оценку функций от чисел к числам (объекты типа 1), верхний индекс 2 будет соответствовать количественной оценке функций, которые принимают объект типа 1 и возвращают число, и так далее.

Примеры

  • Наборы чисел Σ 1 0 {\ displaystyle \ Sigma _ {1} ^ {0}}\Sigma _{1}^{0}могут быть определены формулой вида ∃ N 1 ⋯ ∃ nk ψ (n 1,…, nk, m) {\ displaystyle \ exists n_ {1} \ cdots \ exists n_ {k} \ psi (n_ {1}, \ ldots, n_ {k }, m)}\ exists n_1 \ cdots \ exists n_k \ psi (n_1, \ ldots, n_k, m) где ψ {\ displaystyle \ psi}\psi имеет только ограниченные кванторы. Это в точности рекурсивно перечислимые множества..
  • Набор натуральных чисел, которые являются индексами машин Тьюринга, вычисляющих общие функции, равен Π 2 0 {\ displaystyle \ Pi _ {2} ^ {0}}\Pi _{2}^{0}. Интуитивно, индекс e {\ displaystyle e}eпопадает в этот набор тогда и только тогда, когда для каждого m {\ displaystyle m}m"существует s {\ displaystyle s}sтаким образом, что машина Тьюринга с индексом e {\ displaystyle e}eостанавливается при вводе m {\ displaystyle m}mпосле s {\ displaystyle s}sшагов ». Полное доказательство покажет, что свойство, отображаемое в кавычках в предыдущем предложении, может быть определено на языке арифметики Пеано с помощью Σ 1 0 {\ displaystyle \ Sigma _ {1} ^ {0}}\Sigma _{1}^{0}formula.
  • Каждые Σ 1 0 {\ displaystyle \ Sigma _ {1} ^ {0 }}\Sigma _{1}^{0}подмножество пространства Бэра или пространства Кантора является открытым множеством в обычной топологии на пространстве. Более того, для любого такого множества существует вычислимая нумерация гёделевских чисел основных открытых множеств, объединение которых является исходным набор. По этой причине Σ 1 0 {\ displaystyle \ Sigma _ {1} ^ {0}}\Sigma _{1}^{0}наборы иногда называются эффективно открытыми. Аналогично, каждое Π 1 0 {\ стиль отображения \ Pi _ {1} ^ {0}}\ Pi _ {1 } ^ {0} набор закрыт, а наборы Π 1 0 {\ displaystyle \ Pi _ {1} ^ {0}}\ Pi _ {1 } ^ {0} иногда называют эффективно замкнутым.
  • Каждое арифметическое подмножество пространства Кантора или пространства Бэра является борелевским множеством. Иерархия Lightface Borel расширяет арифметическую иерархию, включая дополнительные наборы Borel. Например, каждое Π 2 0 {\ displaystyle \ Pi _ {2} ^ {0}}\Pi _{2}^{0}подмножество пространства Кантора или Бэра является G δ {\ displaystyle G _ {\ delta }}G_\deltaнабор (то есть набор, который равен пересечению счетного числа открытых множеств). Более того, каждое из этих открытых множеств - это Σ 1 0 {\ displaystyle \ Sigma _ {1} ^ {0}}\Sigma _{1}^{0}, и список гёделевских чисел этих открытых множеств имеет вычислимое перечисление. Если ϕ (X, n, m) {\ displaystyle \ phi (X, n, m)}\phi(X,n,m)- это Σ 0 0 {\ displaystyle \ Sigma _ {0} ^ { 0}}\Sigma^0_0формула со свободным набором переменной X и свободными числовыми переменными n, m {\ displaystyle n, m}n,m, затем Π 2 0 {\ displaystyle \ Pi _ {2} ^ {0}}\Pi _{2}^{0}установить {X ∣ ∀ n ∃ m ϕ (X, n, m)} {\ displaystyle \ {X \ mid \ forall n \ exists m \ phi (X, n, m) \}}\{X \mid \forall n \exists m \phi(X,n,m)\}является пересечением Σ 1 0 {\ displaystyle \ Sigma _ {1} ^ {0}}\Sigma _{1}^{0}наборы формы {X ∣ ∃ m ϕ (X, n, m)} {\ displaystyle \ {X \ mid \ exists m \ phi (X, n, m) \}}\ {X \ mid \ exists m \ phi (X, n, m) \} поскольку n колеблется в наборе натуральных чисел.
  • Σ 0 0 = Π 0 0 = Δ 0 0 {\ displaystyle \ Sigma _ {0} ^ {0} = \ Pi _ {0 } ^ {0} = \ Delta _ {0} ^ {0}}{\displaystyle \Sigma _{0}^{0}=\Pi _{0}^{0}= \Delta _{0}^{0}}формулы можно проверить, просматривая все варианты один за другим, что возможно, потому что все их кванторы ограничены. Время для этого полиномиально по аргументам (например, полиномиально от n для φ (n) {\ displaystyle \ varphi (n)}\varphi (n)); таким образом, соответствующие им проблемы решения включены в E (поскольку n экспоненциально по количеству битов). Это больше не выполняется согласно альтернативным определениям Σ 0 0 = Π 0 0 = Δ 0 0 {\ displaystyle \ Sigma _ {0} ^ {0} = \ Pi _ {0} ^ {0} = \ Delta _ {0} ^ {0}}{\displaystyle \Sigma _{0}^{0}=\Pi _{0}^{0}= \Delta _{0}^{0}}, которые позволяют использовать примитивные рекурсивные функции, поскольку теперь кванторы могут быть связаны любой примитивно рекурсивной функцией аргументов.
  • Σ 0 0 знак равно Π 0 0 знак равно Δ 0 0 {\ Displaystyle \ Sigma _ {0} ^ {0} = \ Pi _ {0} ^ {0} = \ Delta _ {0} ^ {0}}{\displaystyle \Sigma _{0}^{0}=\Pi _{0}^{0}= \Delta _{0}^{0}}формулы согласно альтернативному определению, которое позволяет использовать примитивно рекурсивные функции с ограниченными кванторами, соответствуют наборам целых чисел вида {n: f (n) = 0} {\ displaystyle \ {n: f (n) = 0 \}}{\displaystyle \{n:f( n)=0\}}для примитивной рекурсивной функции f. Это связано с тем, что разрешение ограниченного квантора ничего не добавляет к определению: для примитивной рекурсивной f ∀ k < n : f ( k) = 0 {\displaystyle \forall k{\displaystyle \forall k<n:f(k)=0}совпадает с f (0) + f (1) +... f (n) = 0 {\ displaystyle f (0) + f (1) +... f (n) = 0}{\displaystyle f(0)+f(1)+...f(n)=0}, а ∃ k < n : f ( k) = 0 {\displaystyle \exists k{\ displaystyle \ exists k <n: f (k) = 0} совпадает с f (0) ∗ f (1) ∗... е (п) знак равно 0 {\ Displaystyle е (0) * е (1) *... е (п) = 0}{\displaystyle f(0)*f(1)*...f(n)=0}; с рекурсией курса значений каждый из них может быть определен с помощью одной примитивной функции рекурсии.

Свойства

Следующие свойства сохраняются для арифметической иерархии наборов натуральных чисел и арифметическая иерархия подмножеств пространства Кантора или Бэра.

  • Коллекции Π n 0 {\ displaystyle \ Pi _ {n} ^ {0}}\ Pi ^ 0_n и Σ n 0 {\ displaystyle \ Sigma _ {n} ^ {0 }}\Sigma _{n}^{0}замкнуты относительно конечных объединений и конечных пересечений их соответствующих элементов.
  • Набор равен Σ n 0 {\ displaystyle \ Sigma _ {n} ^ {0}}\Sigma _{n}^{0}тогда и только тогда, когда его дополнение равно Π n 0 {\ displaystyle \ Pi _ {n} ^ {0}}\ Pi ^ 0_n . Набор равен Δ n 0 {\ displaystyle \ Delta _ {n} ^ {0}}\ Delta _ {n} ^ {0} тогда и только тогда, когда оба набора являются Σ n 0 {\ displaystyle \ Sigma _ { n} ^ {0}}\Sigma _{n}^{0}и Π n 0 {\ displaystyle \ Pi _ {n} ^ {0}}\ Pi ^ 0_n , и в этом случае его дополнение также будет Δ N 0 {\ displaystyle \ Delta _ {n} ^ {0}}\ Delta _ {n} ^ {0} .
  • Включения Π n 0 ⊊ Π n + 1 0 {\ displaystyle \ Pi _ {n} ^ {0} \ subsetneq \ Pi _ {n + 1} ^ {0}}\Pi^0_n \subsetneq \Pi^0_{n+1 }и Σ n 0 ⊊ Σ n + 1 0 {\ displaystyle \ Sigma _ {n} ^ {0} \ subsetneq \ Sigma _ {n + 1} ^ {0}}\ Sigma ^ 0_n \ subsetneq \ Sigma ^ 0_ {n +1} удерживать для всех n {\ displaystyle n}n. Таким образом иерархия не разрушается. Это прямое следствие теоремы Поста.
  • Включения Δ n 0 ⊊ Π n 0 {\ displaystyle \ Delta _ {n} ^ {0} \ subsetneq \ Pi _ {n} ^ {0 }}\ Delta ^ 0_n \ subsetneq \ Pi ^ 0_n , Δ N 0 ⊊ Σ n 0 {\ displaystyle \ Delta _ {n} ^ {0} \ subsetneq \ Sigma _ {n} ^ {0}}\ Delta ^ 0_n \ subsetneq \ Sigma ^ 0_n и Σ n 0 ∪ Π N 0 ⊊ Δ N + 1 0 {\ Displaystyle \ Sigma _ {n} ^ {0} \ cup \ Pi _ {n} ^ {0} \ subsetneq \ Delta _ {n + 1} ^ {0} }\Sigma^0_n \cup \Pi^0_n \subsetneq \Delta^0_{n+1}удерживается для n ≥ 1 {\ displaystyle n \ geq 1}n\geq 1.
  • Например, для универсальной машины Тьюринга T набор пар (n, m) таких, что T останавливается на n, но не на m, находится в Δ 2 0 {\ displaystyle \ Delta _ {2} ^ {0}}\Delta _{2}^{0}(вычисляется с помощью оракула для решения проблемы остановки), но не в Σ 1 0 ∪ Π 1 0 {\ displaystyle \ Sigma _ {1} ^ {0} \ cup \ Pi _ {1} ^ {0}}{\displaystyle \Sigma _{1}^{0}\cup \Pi _{1}^{0}},.
  • Σ 0 0 = Π 0 0 знак равно Δ 0 0 знак равно Σ 0 0 ∪ Π 0 0 ⊂ Δ 1 0 {\ displaystyle \ Sigma _ {0} ^ {0} = \ Pi _ {0} ^ {0} = \ Delta _ {0} ^ {0} = \ Sigma _ {0} ^ {0} \ cup \ Pi _ {0} ^ {0} \ subset \ Delta _ {1} ^ {0}}{\displaystyle \Sigma _{0} ^{0}=\Pi _{0}^{0}=\Delta _{0}^{0}=\Sigma _{0}^{0}\cup \Pi _{0}^{0}\ subset \Delta _{1}^{0}}. Включение строгое по определению, данному в этой статье, но тождество с Δ 1 0 {\ displaystyle \ Delta _ {1} ^ {0}}\Delta^0_1сохраняется в одном из вариантов определение приведено выше.

Связь с машинами Тьюринга

Вычислимые множества

Если S является вычислимым множеством Тьюринга, то и S, и его дополняют рекурсивно перечислимы (если T - машина Тьюринга, дающая 1 для входных данных в S и 0, в противном случае мы можем построить машину Тьюринга, останавливающуюся только на первом, а другую - только на втором).

Согласно теореме Поста, как S, так и его дополнение находятся в Σ 1 0 {\ displaystyle \ Sigma _ {1} ^ {0}}\Sigma _{1}^{0}. Это означает, что S находится как в Σ 1 0 {\ displaystyle \ Sigma _ {1} ^ {0}}\Sigma _{1}^{0}, так и в Π 1 0 {\ displaystyle \ Pi _ {1} ^ {0}}\ Pi _ {1 } ^ {0} , следовательно, он находится в Δ 1 0 {\ displaystyle \ Delta _ {1} ^ {0}}\Delta^0_1.

Аналогично для каждого набора S в Δ 1 0 {\ displaystyle \ Delta _ {1} ^ {0}}\Delta^0_1, S и его дополнение находятся в Σ 1 0 {\ displaystyle \ Sigma _ {1} ^ {0} }\Sigma _{1}^{0}и поэтому (согласно теореме Поста ) рекурсивно перечисляются некоторыми машинами Тьюринга T 1 и T 2 соответственно. Для каждого числа n ровно одна из этих остановок. Следовательно, мы можем построить машину Тьюринга T, которая чередуется между T 1 и T 2, останавливаясь и возвращая 1, когда первая останавливается, или останавливается и возвращает 0, когда вторая останавливается. Таким образом, T останавливается на каждом n и возвращает, находится ли он в S, поэтому S вычислим.

Сводка основных результатов

Вычислимые по Тьюрингу наборы натуральных чисел - это в точности наборы на уровне Δ 1 0 {\ displaystyle \ Delta _ {1} ^ {0}}\Delta^0_1арифметической иерархии. Рекурсивно перечислимые множества - это в точности наборы на уровне Σ 1 0 {\ displaystyle \ Sigma _ {1} ^ {0}}\Sigma _{1}^{0}.

Никакая машина-оракул не способна решить свою собственную проблема остановки (применяется вариант доказательства Тьюринга). Проблема остановки для оракула Δ n 0, Y {\ displaystyle \ Delta _ {n} ^ {0, Y}}\Delta^{0,Y}_nфактически находится в Σ n + 1 0, Y {\ displaystyle \ Sigma _ {n + 1} ^ {0, Y}}\Sigma^{0,Y}_{n+1}.

Теорема Поста устанавливает тесную связь между арифметической иерархией множеств натуральных чисел и степенями Тьюринга. В частности, он устанавливает следующие факты для всех n ≥ 1:

  • Множество ∅ (n) {\ displaystyle \ emptyset ^ {(n)}}\emptyset^{(n)}(n-й Скачок Тьюринга пустого набора) составляет полный набор в Σ n 0 {\ displaystyle \ Sigma _ {n} ^ {0}}\Sigma _{n}^{0}.
  • Набор N ∖ ∅ (n) {\ displaystyle \ mathbb {N} \ setminus \ emptyset ^ {(n)}}\mathbb{N} \setminus \emptyset^{(n)}завершено в Π n 0 {\ displaystyle \ Pi _ { n} ^ {0}}\ Pi ^ 0_n .
  • Набор ∅ (n - 1) {\ displaystyle \ emptyset ^ {(n-1)}}\emptyset^{(n-1)}является полным по Тьюрингу в Δ n 0 {\ displaystyle \ Delta _ {n} ^ {0}}\ Delta _ {n} ^ {0} .

полиномиальная иерархия - это версия арифметической иерархии с «допустимыми ограниченными ресурсами», в которой полиномиальная длина на задействованные числа ставятся границы (или, что то же самое, на задействованные машины Тьюринга устанавливаются полиномиальные временные границы). Он дает более точную классификацию некоторых наборов натуральных чисел, находящихся на уровне Δ 1 0 {\ displaystyle \ Delta _ {1} ^ {0}}\Delta^0_1арифметической иерархии.

Отношение к другим иерархиям

Lightface Boldface
Σ. 0= Π. 0= Δ. 0(иногда то же самое, что Δ. 1)Σ. 0= Π. 0= Δ. 0(если определено)
Δ. 1= рекурсивный Δ. 1= clopen
Σ. 1= рекурсивно перечисляемый Π. 1= ко-рекурсивно перечисляемыйΣ. 1= G = открытый Π. 1= F = закрытый
Δ. 2Δ. 2
Σ. 2Π. 2Σ. 2= Π. 2=
Δ. 3Δ. 3
Σ. 3Π. 3Σ. 3= G δσΠ. 3= F σδ
Σ. <ω= Π. <ω= Δ. <ω= Σ. 0= Π. 0= Δ. 0= арифметический Σ. <ω= Π. <ω= Δ. <ω= Σ. 0= Π. 0= Δ. 0= жирный арифметический
Δ. α(α рекурсивный )Δ. α(α счетный )
Σ. αΠ. αΣ. αΠ. α
Σ. ω. 1 = Π. ω. 1 = Δ. ω. 1 = Δ. 1= гиперарифметический Σ. ω1= Π. ω1= Δ. ω1= Δ. 1= B= Борель
Σ. 1= светолицый аналитическийΠ. 1= светолицый коаналитическийΣ. 1= A = аналитический Π. 1= CA = коаналитический
Δ. 2Δ. 2
Σ. 2Π. 2Σ. 2= PCAΠ. 2= CPCA
Δ. 3Δ. 3
Σ. 3Π. 3Σ. 3= PCPCAΠ. 3= CPCPCA
Σ. <ω= Π. <ω= Δ. <ω= Σ. 0= Π. 0= Δ. 0= аналитический Σ. <ω= Π. <ω= Δ. <ω= Σ. 0= Π. 0= Δ. 0= P= проективный

.

См. также

Ссылки

Последняя правка сделана 2021-06-11 16:16:22
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте