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

Иллюстрация того, как взаимодействуют уровни иерархии и где в ней находятся некоторые основные категории.

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

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

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

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

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

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

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

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

• Если ${\displaystyle \phi }$ логически эквивалентно формуле вида ${\displaystyle \exists m_{1}\exists m_{2}\cdots \exists m_{k}\psi }$, где ${\displaystyle \psi }$ является ${\displaystyle \Pi _{n}^{0}}$, тогда ${\displaystyle \phi }$ присвоена классификация ${\displaystyle \Sigma _{n+1}^{0}}$.
• Если ${\displaystyle \phi }$ логически эквивалентно формуле вида ${\displaystyle \forall m_{1}\forall m_{2}\cdots \forall m_{k}\psi }$, где ${\displaystyle \psi }$ является ${\displaystyle \Sigma _{n}^{0}}$, тогда ${\displaystyle \phi }$ присвоена классификация ${\displaystyle \Pi _{n+1}^{0}}$.

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

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

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

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

${\displaystyle n\in X\Leftrightarrow \mathbb {N} \models \varphi ({\underline {n}}),}$

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

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

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

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

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

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

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

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

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

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

Соотношение ${\displaystyle X\leq _{A}Y}$ рефлексивно и транзитивно, поэтому отношение ${\displaystyle \equiv _{A}}$ определяется правилом

${\displaystyle X\equiv _{A}Y\Leftrightarrow X\leq _{A}Y\land Y\leq _{A}X}$

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

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

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

Обычная аксиоматизация арифметика второго порядка использует язык, основанный на множествах, в котором квантификаторы множеств, естественно, могут рассматриваться как количественные в пространстве Кантора. Подмножеству пространства Кантора присваивается классификация ${\displaystyle \Sigma _{n}^{0}}$ если это определяется ${\displaystyle \Sigma _{n}^{0}}$ формула. Набору присвоена классификация ${\displaystyle \Pi _{n}^{0}}$ если это определяется ${\displaystyle \Pi _{n}^{0}}$ формула. Если набор оба ${\displaystyle \Sigma _{n}^{0}}$ и ${\displaystyle \Pi _{n}^{0}}$ затем дается дополнительная классификация ${\displaystyle \Delta _{n}^{0}}$. Например, пусть ${\displaystyle O\subset 2^{\omega }}$ быть набором всех бесконечных двоичных строк, которые не все 0 (или, что эквивалентно, набор всех непустых наборов целых чисел). В качестве ${\displaystyle O=\{X\in 2^{\omega }|\exists n(X(n)=1)\}}$ Мы видим, что ${\displaystyle O}$ определяется ${\displaystyle \Sigma _{1}^{0}}$ формула и, следовательно, является ${\displaystyle \Sigma _{1}^{0}}$ набор.

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

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

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

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

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

Расширения и вариации

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

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

• Если отношение ${\displaystyle R(n_{1},\ldots ,n_{l},m_{1},\ldots ,m_{k})\,}$ является ${\displaystyle \Sigma _{n}^{0}}$ тогда отношение ${\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})}$ определяется как ${\displaystyle \Pi _{n+1}^{0}}$
• Если отношение ${\displaystyle R(n_{1},\ldots ,n_{l},m_{1},\ldots ,m_{k})\,}$ является ${\displaystyle \Pi _{n}^{0}}$ тогда отношение ${\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})}$ определяется как ${\displaystyle \Sigma _{n+1}^{0}}$

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

Значение обозначений

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

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

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

Примеры

• В ${\displaystyle \Sigma _{1}^{0}}$ наборы чисел - те, которые могут быть определены формулой вида ${\displaystyle \exists n_{1}\cdots \exists n_{k}\psi (n_{1},\ldots ,n_{k},m)}$ где ${\displaystyle \psi }$ имеет только ограниченные кванторы. Это именно те рекурсивно перечислимые множества.
• Набор натуральных чисел, являющихся индексами машин Тьюринга, вычисляющих общие функции, равен ${\displaystyle \Pi _{2}^{0}}$. Интуитивно понятно, что индекс ${\displaystyle e}$ попадает в это множество тогда и только тогда, когда для каждого ${\displaystyle m}$ "существует ${\displaystyle s}$ так что машина Тьюринга с индексом ${\displaystyle e}$ останавливается при вводе ${\displaystyle m}$ после ${\displaystyle s}$ шаги ». Полное доказательство показало бы, что свойство, указанное в кавычках в предыдущем предложении, может быть определено на языке арифметики Пеано с помощью ${\displaystyle \Sigma _{1}^{0}}$ формула.
• Каждые ${\displaystyle \Sigma _{1}^{0}}$ подмножество пространства Бэра или пространства Кантора является открытым множеством в обычной топологии на пространстве. Более того, для любого такого множества существует вычислимая нумерация гёделевских чисел основных открытых множеств, объединение которых является исходным множеством. Именно по этой причине, ${\displaystyle \Sigma _{1}^{0}}$ наборы иногда называют эффективно открыть. Точно так же каждый ${\displaystyle \Pi _{1}^{0}}$ набор закрыт и ${\displaystyle \Pi _{1}^{0}}$ наборы иногда называют эффективно закрыто.
• Каждое арифметическое подмножество пространства Кантора или пространства Бэра является Набор Бореля. Иерархия Lightface Borel расширяет арифметическую иерархию, включая дополнительные наборы Borel. Например, каждый ${\displaystyle \Pi _{2}^{0}}$ подмножеством пространства Кантора или Бэра является ${\displaystyle G_{\delta }}$ набор (то есть набор, который равен пересечению счетного числа открытых множеств). Более того, каждое из этих открытых множеств ${\displaystyle \Sigma _{1}^{0}}$ и список гёделевских чисел этих открытых множеств имеет вычислимое перечисление. Если ${\displaystyle \phi (X,n,m)}$ это ${\displaystyle \Sigma _{0}^{0}}$ формула со свободным набором переменной Икс и свободные числовые переменные ${\displaystyle n,m}$ затем ${\displaystyle \Pi _{2}^{0}}$ набор ${\displaystyle \{X\mid \forall n\exists m\phi (X,n,m)\}}$ это пересечение ${\displaystyle \Sigma _{1}^{0}}$ наборы формы ${\displaystyle \{X\mid \exists m\phi (X,n,m)\}}$ так как п колеблется в наборе натуральных чисел.
• В ${\displaystyle \Sigma _{0}^{0}=\Pi _{0}^{0}=\Delta _{0}^{0}}$ формулы можно проверить, просматривая все случаи один за другим, что возможно, потому что все их кванторы ограничены. Время для этого полиномиально по их аргументам (например, полиномиально от п за ${\displaystyle \varphi (n)}$); таким образом их соответствующие проблемы решения включены в E (так как п экспоненциально по количеству битов). Это больше не выполняется при альтернативных определениях ${\displaystyle \Sigma _{0}^{0}=\Pi _{0}^{0}=\Delta _{0}^{0}}$, которые позволяют использовать примитивные рекурсивные функции, поскольку теперь кванторы могут быть связаны любой примитивно рекурсивной функцией аргументов.
• В ${\displaystyle \Sigma _{0}^{0}=\Pi _{0}^{0}=\Delta _{0}^{0}}$ формулы с альтернативным определением, которое позволяет использовать примитивно рекурсивные функции с ограниченными кванторами, соответствуют наборам целых чисел вида ${\displaystyle \{n:f(n)=0\}}$ для примитивной рекурсивной функции ж. Это потому, что разрешение ограниченного квантора ничего не добавляет к определению: для примитивно рекурсивного ж, ${\displaystyle \forall k<n:f(k)=0}$ такой же как ${\displaystyle f(0)+f(1)+...f(n)=0}$, и ${\displaystyle \exists k<n:f(k)=0}$ такой же как ${\displaystyle f(0)*f(1)*...f(n)=0}$; с рекурсия курса ценностей каждый из них может быть определен одной простой функцией рекурсии.

Характеристики

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

• Коллекции ${\displaystyle \Pi _{n}^{0}}$ и ${\displaystyle \Sigma _{n}^{0}}$ замкнуты относительно конечных союзы и конечный перекрестки соответствующих элементов.
• Набор есть ${\displaystyle \Sigma _{n}^{0}}$ тогда и только тогда, когда его дополнение ${\displaystyle \Pi _{n}^{0}}$. Набор есть ${\displaystyle \Delta _{n}^{0}}$ тогда и только тогда, когда набор одновременно ${\displaystyle \Sigma _{n}^{0}}$ и ${\displaystyle \Pi _{n}^{0}}$, в этом случае его дополнение также будет ${\displaystyle \Delta _{n}^{0}}$.
• Включения ${\displaystyle \Pi _{n}^{0}\subsetneq \Pi _{n+1}^{0}}$ и ${\displaystyle \Sigma _{n}^{0}\subsetneq \Sigma _{n+1}^{0}}$ держать для всех ${\displaystyle n}$. Таким образом иерархия не разрушается. Это прямое следствие Теорема Поста.
• Включения ${\displaystyle \Delta _{n}^{0}\subsetneq \Pi _{n}^{0}}$, ${\displaystyle \Delta _{n}^{0}\subsetneq \Sigma _{n}^{0}}$ и ${\displaystyle \Sigma _{n}^{0}\cup \Pi _{n}^{0}\subsetneq \Delta _{n+1}^{0}}$ держаться за ${\displaystyle n\geq 1}$.

• Например, для универсальной машины Тьюринга T набор пар (n, m) таких, что T останавливается на n, но не на m, находится в ${\displaystyle \Delta _{2}^{0}}$ (вычисляемый с помощью оракула для решения проблемы остановки), но не в ${\displaystyle \Sigma _{1}^{0}\cup \Pi _{1}^{0}}$, .
• ${\displaystyle \Sigma _{0}^{0}=\Pi _{0}^{0}=\Delta _{0}^{0}=\Sigma _{0}^{0}\cup \Pi _{0}^{0}\subset \Delta _{1}^{0}}$. Включение строго по определению, данному в этой статье, но тождество с ${\displaystyle \Delta _{1}^{0}}$ выполняется при одном из вариантов определения приведено выше.

Отношение к машинам Тьюринга

Смотрите также: Теорема Поста

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

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

К Теорема Поста, и S, и его дополнение лежат в ${\displaystyle \Sigma _{1}^{0}}$. Это означает, что S находится как в ${\displaystyle \Sigma _{1}^{0}}$ И в ${\displaystyle \Pi _{1}^{0}}$, а значит, и в ${\displaystyle \Delta _{1}^{0}}$.

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

Резюме основных результатов

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

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

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

• Набор ${\displaystyle \emptyset ^{(n)}}$ (в пth Прыжок Тьюринга пустого множества) много-один полный в ${\displaystyle \Sigma _{n}^{0}}$.
• Набор ${\displaystyle \mathbb {N} \setminus \emptyset ^{(n)}}$ много-одно полное в ${\displaystyle \Pi _{n}^{0}}$.
• Набор ${\displaystyle \emptyset ^{(n-1)}}$ является Тьюринг завершен в ${\displaystyle \Delta _{n}^{0}}$.

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

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

Lightface		Жирный шрифт
Σ^0 0 = Π^0 0 = Δ^0 0 (иногда то же самое, что Δ^0 1)		Σ^0 0 = Π^0 0 = Δ^0 0 (если определено)
Δ^0 1 = рекурсивный		Δ^0 1 = прищемить
Σ^0 1 = рекурсивно перечислимый	Π^0 1 = ко-рекурсивно перечислимый	Σ^0 1 = г = открыто	Π^0 1 = F = закрыто
Δ^0 2		Δ^0 2
Σ^0 2	Π^0 2	Σ^0 2 = Fσ	Π^0 2 = гδ
Δ^0 3		Δ^0 3
Σ^0 3	Π^0 3	Σ^0 3 = гδσ	Π^0 3 = Fσδ
⋮		⋮
Σ^0 <ω = Π^0 <ω = Δ^0 <ω = Σ^1 0 = Π^1 0 = Δ^1 0 = арифметический		Σ^0 <ω = Π^0 <ω = Δ^0 <ω = Σ^1 0 = Π^1 0 = Δ^1 0 = жирный арифметический
⋮		⋮
Δ^0 α (α рекурсивный )		Δ^0 α (α счетный )
Σ^0 α	Π^0 α	Σ^0 α	Π^0 α
⋮		⋮
Σ^0 ω^СК 1 = Π^0 ω^СК 1 = Δ^0 ω^СК 1 = Δ^1 1 = гиперарифметический		Σ^0 ω1 = Π^0 ω1 = Δ^0 ω1 = Δ^1 1 = B = Борель
Σ^1 1 = лайтфейс аналитический	Π^1 1 = световой коаналитический	Σ^1 1 = А = аналитический	Π^1 1 = CA = коаналитический
Δ^1 2		Δ^1 2
Σ^1 2	Π^1 2	Σ^1 2 = PCA	Π^1 2 = CPCA
Δ^1 3		Δ^1 3
Σ^1 3	Π^1 3	Σ^1 3 = PCPCA	Π^1 3 = CPCPCA
⋮		⋮
Σ^1 <ω = Π^1 <ω = Δ^1 <ω = Σ^2 0 = Π^2 0 = Δ^2 0 = аналитический		Σ^1 <ω = Π^1 <ω = Δ^1 <ω = Σ^2 0 = Π^2 0 = Δ^2 0 = п = проективный
⋮		⋮

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

• Иерархия Леви
• Иерархия (математика)
• Логика интерпретируемости
• Полиномиальная иерархия

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

• Джапаридзе, Георгий (1994), «Логика арифметической иерархии», Анналы чистой и прикладной логики, 66 (2): 89–112, Дои:10.1016/0168-0072(94)90063-9, Zbl  0804.03045.
• Мощовакис, Яннис Н. (1980), Описательная теория множеств, Исследования по логике и основам математики, 100, Северная Голландия, ISBN  0-444-70199-0, Zbl  0433.03025.
• Нис, Андре (2009), Вычислимость и случайность, Oxford Logic Guides, 51, Оксфорд: Издательство Оксфордского университета, ISBN  978-0-19-923076-1, Zbl  1169.03034.
• Роджерс, Х., младший (1967), Теория рекурсивных функций и эффективная вычислимость, Мейденхед: Макгроу-Хилл, Zbl  0183.01401.